Non-transitive dice: Difference between revisions
(→{{header|Wren}}: More efficient.) |
(Added Go) |
||
Line 84: | Line 84: | ||
<br> |
<br> |
||
=={{header|Go}}== |
|||
{{trans|Wren}} |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"sort" |
|||
) |
|||
func fourFaceCombs() (res [][4]int) { |
|||
found := make([]bool, 256) |
|||
for i := 1; i <= 4; i++ { |
|||
for j := 1; j <= 4; j++ { |
|||
for k := 1; k <= 4; k++ { |
|||
for l := 1; l <= 4; l++ { |
|||
c := [4]int{i, j, k, l} |
|||
sort.Ints(c[:]) |
|||
key := 64*(c[0]-1) + 16*(c[1]-1) + 4*(c[2]-1) + (c[3] - 1) |
|||
if !found[key] { |
|||
found[key] = true |
|||
res = append(res, c) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return |
|||
} |
|||
func cmp(x, y [4]int) int { |
|||
xw := 0 |
|||
yw := 0 |
|||
for i := 0; i < 4; i++ { |
|||
for j := 0; j < 4; j++ { |
|||
if x[i] > y[j] { |
|||
xw++ |
|||
} else if y[j] > x[i] { |
|||
yw++ |
|||
} |
|||
} |
|||
} |
|||
if xw < yw { |
|||
return -1 |
|||
} else if xw > yw { |
|||
return 1 |
|||
} |
|||
return 0 |
|||
} |
|||
func findIntransitive3(cs [][4]int) (res [][3][4]int) { |
|||
var c = len(cs) |
|||
for i := 0; i < c; i++ { |
|||
for j := 0; j < c; j++ { |
|||
for k := 0; k < c; k++ { |
|||
first := cmp(cs[i], cs[j]) |
|||
if first == -1 { |
|||
second := cmp(cs[j], cs[k]) |
|||
if second == -1 { |
|||
third := cmp(cs[i], cs[k]) |
|||
if third == 1 { |
|||
res = append(res, [3][4]int{cs[i], cs[j], cs[k]}) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return |
|||
} |
|||
func findIntransitive4(cs [][4]int) (res [][4][4]int) { |
|||
c := len(cs) |
|||
for i := 0; i < c; i++ { |
|||
for j := 0; j < c; j++ { |
|||
for k := 0; k < c; k++ { |
|||
for l := 0; l < c; l++ { |
|||
first := cmp(cs[i], cs[j]) |
|||
if first == -1 { |
|||
second := cmp(cs[j], cs[k]) |
|||
if second == -1 { |
|||
third := cmp(cs[k], cs[l]) |
|||
if third == -1 { |
|||
fourth := cmp(cs[i], cs[l]) |
|||
if fourth == 1 { |
|||
res = append(res, [4][4]int{cs[i], cs[j], cs[k], cs[l]}) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return |
|||
} |
|||
func main() { |
|||
combs := fourFaceCombs() |
|||
fmt.Println("Number of eligible 4-faced dice", len(combs)) |
|||
it3 := findIntransitive3(combs) |
|||
fmt.Printf("\n%d ordered lists of 3 non-transitive dice found, namely:\n", len(it3)) |
|||
for _, a := range it3 { |
|||
fmt.Println(a) |
|||
} |
|||
it4 := findIntransitive4(combs) |
|||
fmt.Printf("\n%d ordered lists of 4 non-transitive dice found, namely:\n", len(it4)) |
|||
for _, a := range it4 { |
|||
fmt.Println(a) |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Number of eligible 4-faced dice 35 |
|||
3 ordered lists of 3 non-transitive dice found, namely: |
|||
[[1 1 4 4] [2 2 2 4] [1 3 3 3]] |
|||
[[1 3 3 3] [1 1 4 4] [2 2 2 4]] |
|||
[[2 2 2 4] [1 3 3 3] [1 1 4 4]] |
|||
4 ordered lists of 4 non-transitive dice found, namely: |
|||
[[1 1 4 4] [2 2 2 4] [2 2 3 3] [1 3 3 3]] |
|||
[[1 3 3 3] [1 1 4 4] [2 2 2 4] [2 2 3 3]] |
|||
[[2 2 2 4] [2 2 3 3] [1 3 3 3] [1 1 4 4]] |
|||
[[2 2 3 3] [1 3 3 3] [1 1 4 4] [2 2 2 4]] |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 18:09, 7 September 2020
Let our dice select numbers on their faces with equal probability, i.e. fair dice. Dice may have more or less than six faces. (The possibility of there being a 3D physical shape that has that many "faces" that allow them to be fair dice, is ignored for this task - a die with 3 or 33 defined sides is defined by the number of faces and the numbers on each face).
Throwing dice will randomly select a face on each die with equal probability. To show which die of dice thrown multiple times is more likely to win over the others:
- calculate all possible combinations of different faces from each die
- Count how many times each die wins a combination
- Each combination is equally likely so the die with more winning face combinations is statistically more likely to win against the other dice.
If two dice X and Y are thrown against each other then X likely to: win, lose, or break-even against Y can be shown as: X > Y, X < Y, or X = Y
respectively.
- Example 1
If X is the three sided die with 1, 3, 6 on its faces and Y has 2, 3, 4 on its faces then the equal possibility outcomes from throwing both, and the winners is:
X Y Winner = = ====== 1 2 Y 1 3 Y 1 4 Y 3 2 X 3 3 - 3 4 Y 6 2 X 6 3 X 6 4 X TOTAL WINS: X=4, Y=4
Both die will have the same statistical probability of winning, i.e.their comparison can be written as X = Y
- Transitivity
In mathematics transitivity are rules like:
if a op b and b op c then a op c
If, for example, the op, (for operator), is the familiar less than, <, and it's applied to integers
we get the familiar if a < b and b < c then a < c
- Non-transitive dice
These are an ordered list of dice where the '>' operation between successive
dice pairs applies but a comparison between the first and last of the list
yields the opposite result, '<'.
(Similarly '<' successive list comparisons with a final '>' between first and last is also non-transitive).
Three dice S, T, U with appropriate face values could satisfy
S < T, T < U and yet S > U
To be non-transitive.
- Notes
- The order of numbers on the faces of a die is not relevant. For example, three faced die described with face numbers of 1, 2, 3 or 2, 1, 3 or any other permutation are equivalent. For the purposes of the task show only the permutation in lowest-first sorted order i.e. 1, 2, 3 (and remove any of its perms).
- A die can have more than one instance of the same number on its faces, e.g.
2, 3, 3, 4
- Task
- ====
Find all the ordered lists of three non-transitive dice S, T, U of the form S < T, T < U and yet S > U; where the dice are selected from all four-faced die , (unique w.r.t the notes), possible by having selections from the integers one to four on any dies face.
Solution can be found by generating all possble individual die then testing all possible permutations, (permutations are ordered), of three dice for non-transitivity.
- Optional stretch goal
Find lists of four non-transitive dice selected from the same possible dice from the non-stretch goal.
Show the results here, on this page.
- References
- The Most Powerful Dice - Numberphile Video.
- Nontransitive dice - Wikipedia.
Go
<lang go>package main
import (
"fmt" "sort"
)
func fourFaceCombs() (res [][4]int) {
found := make([]bool, 256) for i := 1; i <= 4; i++ { for j := 1; j <= 4; j++ { for k := 1; k <= 4; k++ { for l := 1; l <= 4; l++ { c := [4]int{i, j, k, l} sort.Ints(c[:]) key := 64*(c[0]-1) + 16*(c[1]-1) + 4*(c[2]-1) + (c[3] - 1) if !found[key] { found[key] = true res = append(res, c) } } } } } return
}
func cmp(x, y [4]int) int {
xw := 0 yw := 0 for i := 0; i < 4; i++ { for j := 0; j < 4; j++ { if x[i] > y[j] { xw++ } else if y[j] > x[i] { yw++ } } } if xw < yw { return -1 } else if xw > yw { return 1 } return 0
}
func findIntransitive3(cs [][4]int) (res [][3][4]int) {
var c = len(cs) for i := 0; i < c; i++ { for j := 0; j < c; j++ { for k := 0; k < c; k++ { first := cmp(cs[i], cs[j]) if first == -1 { second := cmp(cs[j], cs[k]) if second == -1 { third := cmp(cs[i], cs[k]) if third == 1 { res = append(res, [3][4]int{cs[i], cs[j], cs[k]}) } } } } } } return
}
func findIntransitive4(cs [][4]int) (res [][4][4]int) {
c := len(cs) for i := 0; i < c; i++ { for j := 0; j < c; j++ { for k := 0; k < c; k++ { for l := 0; l < c; l++ { first := cmp(cs[i], cs[j]) if first == -1 { second := cmp(cs[j], cs[k]) if second == -1 { third := cmp(cs[k], cs[l]) if third == -1 { fourth := cmp(cs[i], cs[l]) if fourth == 1 { res = append(res, [4][4]int{cs[i], cs[j], cs[k], cs[l]}) } } } } } } } } return
}
func main() {
combs := fourFaceCombs() fmt.Println("Number of eligible 4-faced dice", len(combs)) it3 := findIntransitive3(combs) fmt.Printf("\n%d ordered lists of 3 non-transitive dice found, namely:\n", len(it3)) for _, a := range it3 { fmt.Println(a) } it4 := findIntransitive4(combs) fmt.Printf("\n%d ordered lists of 4 non-transitive dice found, namely:\n", len(it4)) for _, a := range it4 { fmt.Println(a) }
}</lang>
- Output:
Number of eligible 4-faced dice 35 3 ordered lists of 3 non-transitive dice found, namely: [[1 1 4 4] [2 2 2 4] [1 3 3 3]] [[1 3 3 3] [1 1 4 4] [2 2 2 4]] [[2 2 2 4] [1 3 3 3] [1 1 4 4]] 4 ordered lists of 4 non-transitive dice found, namely: [[1 1 4 4] [2 2 2 4] [2 2 3 3] [1 3 3 3]] [[1 3 3 3] [1 1 4 4] [2 2 2 4] [2 2 3 3]] [[2 2 2 4] [2 2 3 3] [1 3 3 3] [1 1 4 4]] [[2 2 3 3] [1 3 3 3] [1 1 4 4] [2 2 2 4]]
Python
<lang python>from collections import namedtuple, Counter from itertools import permutations, product
Die = namedtuple('Die', 'name, faces')
def cmpd(die1, die2):
'compares two die returning 1, -1 or 0 for >, < ==' # Numbers of times one die wins against the other for all combinations # cmp(x, y) is `(x > y) - (y > x)` to return 1, 0, or -1 for numbers tot = [0, 0, 0] for d1, d2 in product(die1.faces, die2.faces): tot[1 + (d1 > d2) - (d2 > d1)] += 1 win2, _, win1 = tot return (win1 > win2) - (win2 > win1)
def is_non_trans(dice):
"Check if ordering of die in dice is non-transitive returning dice or None"
check = (all(cmpd(c1, c2) == -1 for c1, c2 in zip(dice, dice[1:])) # Dn < Dn+1 and cmpd(dice[0], dice[-1]) == 1) # But D[0] > D[-1] return dice if check else False
def find_non_trans(alldice, n=3):
return [perm for perm in permutations(alldice, n) if is_non_trans(perm)]
def possible_dice(sides, mx):
print(f"\nAll possible 1..{mx} {sides}-sided dice") dice = [Die(f"D{n+1}", faces) for n, faces in enumerate(product(range(1, mx+1), repeat=sides))] print(f' Created {len(dice)} dice') print(' Remove duplicate with same bag of numbers on different faces') found = set() filtered = [] for d in dice: count = tuple(sorted(Counter(d.faces).items())) if count not in found: found.add(count) filtered.append(d) l = len(filtered) print(f' Return {l} filtered dice') return filtered
- %% more verbose extra checks
def verbose_cmp(die1, die2):
'compares two die returning their relationship of their names as a string' # Numbers of times one die wins against the other for all combinations win1 = sum(d1 > d2 for d1, d2 in product(die1.faces, die2.faces)) win2 = sum(d2 > d1 for d1, d2 in product(die1.faces, die2.faces)) n1, n2 = die1.name, die2.name return f'{n1} > {n2}' if win1 > win2 else (f'{n1} < {n2}' if win1 < win2 else f'{n1} = {n2}')
def verbose_dice_cmp(dice):
c = [verbose_cmp(x, y) for x, y in zip(dice, dice[1:])] c += [verbose_cmp(dice[0], dice[-1])] return ', '.join(c)
- %% Use
if __name__ == '__main__':
dice = possible_dice(sides=4, mx=4) for N in (3, 4): # length of non-transitive group of dice searched for non_trans = find_non_trans(dice, N) print(f'\n Non_transitive length-{N} combinations found: {len(non_trans)}') for lst in non_trans: print() for i, die in enumerate(lst): print(f" {' ' if i else '['}{die}{',' if i < N-1 else ']'}") if non_trans: print('\n More verbose comparison of last non_transitive result:') print(' ', verbose_dice_cmp(non_trans[-1])) print('\n ====')</lang>
- Output:
All possible 1..4 4-sided dice Created 256 dice Remove duplicate with same bag of numbers on different faces Return 35 filtered dice Non_transitive length-3 combinations found: 3 [Die(name='D16', faces=(1, 1, 4, 4)), Die(name='D88', faces=(2, 2, 2, 4)), Die(name='D43', faces=(1, 3, 3, 3))] [Die(name='D43', faces=(1, 3, 3, 3)), Die(name='D16', faces=(1, 1, 4, 4)), Die(name='D88', faces=(2, 2, 2, 4))] [Die(name='D88', faces=(2, 2, 2, 4)), Die(name='D43', faces=(1, 3, 3, 3)), Die(name='D16', faces=(1, 1, 4, 4))] More verbose comparison of last non_transitive result: D88 < D43, D43 < D16, D88 > D16 ==== Non_transitive length-4 combinations found: 4 [Die(name='D16', faces=(1, 1, 4, 4)), Die(name='D88', faces=(2, 2, 2, 4)), Die(name='D91', faces=(2, 2, 3, 3)), Die(name='D43', faces=(1, 3, 3, 3))] [Die(name='D43', faces=(1, 3, 3, 3)), Die(name='D16', faces=(1, 1, 4, 4)), Die(name='D88', faces=(2, 2, 2, 4)), Die(name='D91', faces=(2, 2, 3, 3))] [Die(name='D88', faces=(2, 2, 2, 4)), Die(name='D91', faces=(2, 2, 3, 3)), Die(name='D43', faces=(1, 3, 3, 3)), Die(name='D16', faces=(1, 1, 4, 4))] [Die(name='D91', faces=(2, 2, 3, 3)), Die(name='D43', faces=(1, 3, 3, 3)), Die(name='D16', faces=(1, 1, 4, 4)), Die(name='D88', faces=(2, 2, 2, 4))] More verbose comparison of last non_transitive result: D91 < D43, D43 < D16, D16 < D88, D91 > D88 ====
Wren
<lang ecmascript>import "/sort" for Sort
var fourFaceCombs = Fn.new {
var res = [] var found = List.filled(256, false) for (i in 1..4) { for (j in 1..4) { for (k in 1..4) { for (l in 1..4) { var c = [i, j, k, l] Sort.insertion(c) var key = 64*(c[0]-1) + 16*(c[1]-1) + 4*(c[2]-1) + (c[3]-1) if (!found[key]) { found[key] = true res.add(c) } } } } } return res
}
var cmp = Fn.new { |x, y|
var xw = 0 var yw = 0 for (i in 0..3) { for (j in 0..3) { if (x[i] > y[j]) { xw = xw + 1 } else if (y[j] > x[i]) { yw = yw + 1 } } } return (xw - yw).sign
}
var findIntransitive3 = Fn.new { |cs|
var c = cs.count var res = [] for (i in 0...c) { for (j in 0...c) { for (k in 0...c) { var first = cmp.call(cs[i], cs[j]) if (first == -1) { var second = cmp.call(cs[j], cs[k]) if (second == -1) { var third = cmp.call(cs[i], cs[k]) if (third == 1) res.add([cs[i], cs[j], cs[k]]) } } } } } return res
}
var findIntransitive4 = Fn.new { |cs|
var c = cs.count var res = [] for (i in 0...c) { for (j in 0...c) { for (k in 0...c) { for (l in 0...c) { var first = cmp.call(cs[i], cs[j]) if (first == -1) { var second = cmp.call(cs[j], cs[k]) if (second == -1) { var third = cmp.call(cs[k], cs[l]) if (third == -1) { var fourth = cmp.call(cs[i], cs[l]) if (fourth == 1) res.add([cs[i], cs[j], cs[k], cs[l]]) } } } } } } } return res
}
var combs = fourFaceCombs.call() System.print("Number of eligible 4-faced dice: %(combs.count)") var it = findIntransitive3.call(combs) System.print("\n%(it.count) ordered lists of 3 non-transitive dice found, namely:") System.print(it.join("\n")) it = findIntransitive4.call(combs) System.print("\n%(it.count) ordered lists of 4 non-transitive dice found, namely:") System.print(it.join("\n"))</lang>
- Output:
Number of eligible 4-faced dice: 35 3 ordered lists of 3 non-transitive dice found, namely: [[1, 1, 4, 4], [2, 2, 2, 4], [1, 3, 3, 3]] [[1, 3, 3, 3], [1, 1, 4, 4], [2, 2, 2, 4]] [[2, 2, 2, 4], [1, 3, 3, 3], [1, 1, 4, 4]] 4 ordered lists of 4 non-transitive dice found, namely: [[1, 1, 4, 4], [2, 2, 2, 4], [2, 2, 3, 3], [1, 3, 3, 3]] [[1, 3, 3, 3], [1, 1, 4, 4], [2, 2, 2, 4], [2, 2, 3, 3]] [[2, 2, 2, 4], [2, 2, 3, 3], [1, 3, 3, 3], [1, 1, 4, 4]] [[2, 2, 3, 3], [1, 3, 3, 3], [1, 1, 4, 4], [2, 2, 2, 4]]