Non-transitive dice: Difference between revisions
m →{{header|J}}: fix markup |
New post. |
||
(7 intermediate revisions by 6 users not shown) | |||
Line 85: | Line 85: | ||
<br> |
<br> |
||
=={{header|ALGOL 68}}== |
|||
<syntaxhighlight lang="algol68"># iterates through all possible dice # |
|||
PROC iterate = (PROC(INT, []INT)VOID f)VOID: |
|||
BEGIN |
|||
INT n := 1; |
|||
[4]INT sides; |
|||
FOR i FROM 1 TO 4 DO FOR j FROM i TO 4 DO |
|||
FOR k FROM j TO 4 DO FOR l FROM k TO 4 DO |
|||
sides := (i, j, k, l); |
|||
f(n, sides); |
|||
n +:= 1 |
|||
OD OD OD OD |
|||
END; |
|||
# compares 2 dice, returns (-1, 0, 1) for a (<, =, >) b # |
|||
PROC compare = ([]INT a, []INT b)INT: |
|||
BEGIN |
|||
INT result := 0; |
|||
FOR i TO UPB a DO |
|||
FOR j TO UPB b DO |
|||
result +:= SIGN(a[i] - b[j]) |
|||
OD |
|||
OD; |
|||
SIGN result |
|||
END; |
|||
# compact representation of die # |
|||
PROC str = ([]INT die)STRING: |
|||
BEGIN |
|||
STRING result := " " * UPB die; |
|||
FOR i TO UPB die DO |
|||
result[i] := REPR (die[i] + ABS "0") |
|||
OD; |
|||
result |
|||
END; |
|||
# first count all possible dice # |
|||
INT ndice := 0; |
|||
iterate((INT n, []INT sides)VOID: ndice +:= 1); |
|||
# store them by index # |
|||
[ndice][4]INT dice; |
|||
iterate((INT n, []INT sides)VOID: dice[n] := sides); |
|||
# fill the results of an all-play-all tournament # |
|||
[ndice,ndice]INT results; |
|||
FOR i TO ndice DO |
|||
FOR j FROM i TO ndice DO |
|||
results[i,j] := compare(dice[i], dice[j]); |
|||
results[j,i] := results[i,j] * -1 |
|||
OD |
|||
OD; |
|||
# helper function to print the intransitive sequence # |
|||
PROC print seq = ([]INT idxs)VOID: |
|||
BEGIN |
|||
FOR i TO UPB idxs DO |
|||
IF i > 1 THEN print((" < ")) FI; |
|||
print((str(dice[idxs[i]]))) |
|||
OD; |
|||
print((newline)) |
|||
END; |
|||
# find all (s,t,u) where s < t < u < s # |
|||
print(("3 dice:", newline)); |
|||
FOR s TO ndice DO |
|||
FOR t TO ndice DO |
|||
IF results[s,t] = -1 THEN |
|||
FOR u TO ndice DO |
|||
IF results[t,u] = -1 AND results[u,s] = -1 THEN |
|||
print seq((s, t, u, s)) |
|||
FI |
|||
OD |
|||
FI |
|||
OD |
|||
OD; |
|||
# find all (s,t,u,v) where s < t < u < v < s # |
|||
print(("4 dice:", newline)); |
|||
FOR s TO ndice DO |
|||
FOR t TO ndice DO |
|||
IF results[s,t] = -1 THEN |
|||
FOR u TO ndice DO |
|||
IF results[t,u] = -1 THEN |
|||
FOR v TO ndice DO |
|||
IF results[u,v] = -1 AND results[v,s] = -1 THEN |
|||
print seq((s, t, u, v, s)) |
|||
FI |
|||
OD |
|||
FI |
|||
OD |
|||
FI |
|||
OD |
|||
OD</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3 dice: |
|||
1144 < 2224 < 1333 < 1144 |
|||
1333 < 1144 < 2224 < 1333 |
|||
2224 < 1333 < 1144 < 2224 |
|||
4 dice: |
|||
1144 < 2224 < 2233 < 1333 < 1144 |
|||
1333 < 1144 < 2224 < 2233 < 1333 |
|||
2224 < 2233 < 1333 < 1144 < 2224 |
|||
2233 < 1333 < 1144 < 2224 < 2233</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="c++"> |
|||
#include <algorithm> |
|||
#include <cstdint> |
|||
#include <iostream> |
|||
#include <set> |
|||
#include <vector> |
|||
void print_vector(const std::vector<uint32_t>& list) { |
|||
std::cout << "["; |
|||
for ( uint64_t i = 0; i < list.size() - 1; ++i ) { |
|||
std::cout << list[i] << ", "; |
|||
} |
|||
std::cout << list.back() << "]"; |
|||
} |
|||
void display_table(const std::vector<std::vector<uint32_t>> table) { |
|||
std::cout << "["; |
|||
for ( uint64_t i = 0; i < table.size() - 1; ++i ) { |
|||
print_vector(table[i]); |
|||
std::cout << ", "; |
|||
} |
|||
print_vector(table.back()); |
|||
std::cout << "]" << "\n"; |
|||
} |
|||
std::vector<std::vector<uint32_t>> four_face_combinations() { |
|||
std::vector<std::vector<uint32_t>> result = { }; |
|||
std::set<uint32_t> found = { }; |
|||
for ( uint32_t i = 1; i <= 4; ++i ) { |
|||
for ( uint32_t j = 1; j <= 4; ++j ) { |
|||
for ( uint32_t k = 1; k <= 4; ++k ) { |
|||
for ( uint32_t l = 1; l <= 4; ++l ) { |
|||
std::vector<uint32_t> combo = { i, j, k, l }; |
|||
std::sort(combo.begin(), combo.end()); |
|||
const uint32_t key = 64 * combo[0] + 16 * combo[1] + 4 * combo[2] + combo[3]; |
|||
if ( found.insert(key).second ) { |
|||
result.emplace_back(combo); |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return result; |
|||
} |
|||
bool comparator(const std::vector<uint32_t>& one, const std::vector<uint32_t>& two) { |
|||
uint32_t one_wins = 0; |
|||
uint32_t two_wins = 0; |
|||
for ( uint32_t i = 0; i < 4; ++i ) { |
|||
for ( uint32_t j = 0; j < 4; ++j ) { |
|||
if ( one[i] > two[j] ) { |
|||
one_wins++; |
|||
} else if ( one[i] < two[j] ) { |
|||
two_wins++; |
|||
} |
|||
} |
|||
} |
|||
return ( one_wins < two_wins ); |
|||
} |
|||
std::vector<std::vector<std::vector<uint32_t>>> find_intransitive_3( |
|||
const std::vector<std::vector<uint32_t>>& combos) { |
|||
std::vector<std::vector<std::vector<uint32_t>>> result = { }; |
|||
for ( uint64_t i = 0; i < combos.size(); ++i ) { |
|||
for ( uint64_t j = 0; j < combos.size(); ++j ) { |
|||
if ( comparator(combos[i], combos[j]) ) { |
|||
for ( const std::vector<uint32_t>& combo : combos ) { |
|||
if ( comparator(combos[j], combo) && comparator(combo, combos[i]) ) { |
|||
std::vector<std::vector<uint32_t>> entry = { combos[i], combos[j], combo }; |
|||
result.emplace_back(entry); |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return result; |
|||
} |
|||
std::vector<std::vector<std::vector<uint32_t>>> find_intransitive_4( |
|||
const std::vector<std::vector<uint32_t>>& combos) { |
|||
std::vector<std::vector<std::vector<uint32_t>>> result = { }; |
|||
for ( uint64_t i = 0; i < combos.size(); ++i ) { |
|||
for ( uint64_t j = 0; j < combos.size(); ++j ) { |
|||
if ( comparator(combos[i], combos[j]) ) { |
|||
for ( uint64_t k = 0; k < combos.size(); ++k ) { |
|||
if ( comparator(combos[j], combos[k]) ) { |
|||
for ( const std::vector<uint32_t>& combo : combos ) { |
|||
if ( comparator(combos[k], combo) && comparator(combo, combos[i]) ) { |
|||
std::vector<std::vector<uint32_t>> entry = |
|||
{ combos[i], combos[j], combos[k], combo }; |
|||
result.emplace_back(entry); |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return result; |
|||
} |
|||
int main() { |
|||
std::vector<std::vector<uint32_t>> combinations = four_face_combinations(); |
|||
std::cout << "The number of eligible 4-faced dice: " << combinations.size() << "\n\n"; |
|||
std::vector<std::vector<std::vector<uint32_t>>> intransitive_3 = find_intransitive_3(combinations); |
|||
std::cout << intransitive_3.size() << " ordered lists of 3 non-transitive dice found, namely:" << "\n"; |
|||
for ( const std::vector<std::vector<uint32_t>>& table : intransitive_3 ) { |
|||
display_table(table); |
|||
} |
|||
std::cout << "\n"; |
|||
std::vector<std::vector<std::vector<uint32_t>>> intransitive_4 = find_intransitive_4(combinations); |
|||
std::cout << intransitive_4.size() << " ordered lists of 4 non-transitive dice found, namely:" << "\n"; |
|||
for ( const std::vector<std::vector<uint32_t>>& table : intransitive_4 ) { |
|||
display_table(table); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
The 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|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===The task (4 sided die)=== |
===The task (4 sided die)=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Non-transitive dice. Nigel Galloway: August 9th., 2020 |
// Non-transitive dice. Nigel Galloway: August 9th., 2020 |
||
let die=[for n0 in [1..4] do for n1 in [n0..4] do for n2 in [n1..4] do for n3 in [n2..4]->[n0;n1;n2;n3]] |
let die=[for n0 in [1..4] do for n1 in [n0..4] do for n2 in [n1..4] do for n3 in [n2..4]->[n0;n1;n2;n3]] |
||
Line 95: | Line 343: | ||
let n4=seq{for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do for d4 in N.[d3] do if List.contains d1 N.[d4] then yield (d1,d2,d3,d4)} |
let n4=seq{for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do for d4 in N.[d3] do if List.contains d1 N.[d4] then yield (d1,d2,d3,d4)} |
||
n3|>Seq.iter(fun(d1,d2,d3)->printfn "%A<%A; %A<%A; %A>%A\n" d1 d2 d2 d3 d1 d3) |
n3|>Seq.iter(fun(d1,d2,d3)->printfn "%A<%A; %A<%A; %A>%A\n" d1 d2 d2 d3 d1 d3) |
||
n4|>Seq.iter(fun(d1,d2,d3,d4)->printfn "%A<%A; %A<%A; %A<%A; %A>%A" d1 d2 d2 d3 d3 d4 d1 d4)</ |
n4|>Seq.iter(fun(d1,d2,d3,d4)->printfn "%A<%A; %A<%A; %A<%A; %A>%A" d1 d2 d2 d3 d3 d4 d1 d4)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 111: | Line 359: | ||
===Extra credit (6 sided die)=== |
===Extra credit (6 sided die)=== |
||
;Sides numbered 1..6 |
;Sides numbered 1..6 |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Non-transitive diceNigel Galloway: August 9th., 2020 |
// Non-transitive diceNigel Galloway: August 9th., 2020 |
||
let die=[for n0 in [1..6] do for n1 in [n0..6] do for n2 in [n1..6] do for n3 in [n2..6] do for n4 in [n3..6] do for n5 in [n4..6]->[n0;n1;n2;n3;n4;n5]] |
let die=[for n0 in [1..6] do for n1 in [n0..6] do for n2 in [n1..6] do for n3 in [n2..6] do for n4 in [n3..6] do for n5 in [n4..6]->[n0;n1;n2;n3;n4;n5]] |
||
Line 117: | Line 365: | ||
let n3=[for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)] |
let n3=[for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)] |
||
let d1,d2,d3=List.last n3 in printfn "Solutions found = %d\nLast solution found is %A<%A; %A<%A; %A>%A" (n3.Length) d1 d2 d2 d3 d1 d3 |
let d1,d2,d3=List.last n3 in printfn "Solutions found = %d\nLast solution found is %A<%A; %A<%A; %A>%A" (n3.Length) d1 d2 d2 d3 d1 d3 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 125: | Line 373: | ||
</pre> |
</pre> |
||
;Sides numbered 1..7 |
;Sides numbered 1..7 |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Non-transitive diceNigel Galloway: August 9th., 2020 |
// Non-transitive diceNigel Galloway: August 9th., 2020 |
||
let die=[for n0 in [1..7] do for n1 in [n0..7] do for n2 in [n1..7] do for n3 in [n2..7] do for n4 in [n3..7] do for n5 in [n4..7]->[n0;n1;n2;n3;n4;n5]] |
let die=[for n0 in [1..7] do for n1 in [n0..7] do for n2 in [n1..7] do for n3 in [n2..7] do for n4 in [n3..7] do for n5 in [n4..7]->[n0;n1;n2;n3;n4;n5]] |
||
Line 131: | Line 379: | ||
let n3=[for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)] |
let n3=[for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)] |
||
let d1,d2,d3=List.last n3 in printfn "Solutions found = %d\nLast solution found is %A<%A; %A<%A; %A>%A" (n3.Length) d1 d2 d2 d3 d1 d3 |
let d1,d2,d3=List.last n3 in printfn "Solutions found = %d\nLast solution found is %A<%A; %A<%A; %A>%A" (n3.Length) d1 d2 d2 d3 d1 d3 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 140: | Line 388: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: grouping io kernel math math.combinatorics math.ranges |
||
prettyprint sequences ; |
prettyprint sequences ; |
||
Line 164: | Line 412: | ||
"All ordered lists of 4 non-transitive dice with 4 sides:" print |
"All ordered lists of 4 non-transitive dice with 4 sides:" print |
||
4 4 find-non-transitive .</ |
4 4 find-non-transitive .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 187: | Line 435: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 294: | Line 542: | ||
fmt.Println(a) |
fmt.Println(a) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 314: | Line 562: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">{-# language LambdaCase #-} |
||
import Data.List |
import Data.List |
||
import Control.Monad |
import Control.Monad |
||
Line 340: | Line 588: | ||
(a:as) <- go (n-1) |
(a:as) <- go (n-1) |
||
b <- filter (< a) dice |
b <- filter (< a) dice |
||
return (b:a:as)</ |
return (b:a:as)</syntaxhighlight> |
||
<pre>*Main> mapM_ print $ nonTrans (dices 4) 3 |
<pre>*Main> mapM_ print $ nonTrans (dices 4) 3 |
||
Line 362: | Line 610: | ||
Implementation (rotations of results here are also solutions): |
Implementation (rotations of results here are also solutions): |
||
< |
<syntaxhighlight lang="j">NB. unique list of all y faced dice |
||
udice=: {{ 1+~./:~"1 (#: ,@i.)y#y }} |
udice=: {{ 1+~./:~"1 (#: ,@i.)y#y }} |
||
Line 376: | Line 624: | ||
r=. ; extend^:(x-1)&.> i.#ud |
r=. ; extend^:(x-1)&.> i.#ud |
||
ud{~ ~.((i.<./)|.])"1 r #~ lt{~({:,&.>{.)|:r |
ud{~ ~.((i.<./)|.])"1 r #~ lt{~({:,&.>{.)|:r |
||
}}</ |
}}</syntaxhighlight> |
||
Here, <tt>extend</tt> takes a list of die sequences and appends each possibility of a new die where the new die is not less than the last die in the sequence. So, <tt>r</tt> is all such lists of length x. We discard the cases where the last element of the list is not less than the first, rotate each dice index list into canonical order, discard duplicates, and then use these indices to select the associated dice. |
Here, <tt>extend</tt> takes a list of die sequences and appends each possibility of a new die where the new die is not less than the last die in the sequence. So, <tt>r</tt> is all such lists of length x. We discard the cases where the last element of the list is not less than the first, rotate each dice index list into canonical order, discard duplicates, and then use these indices to select the associated dice. |
||
Line 382: | Line 630: | ||
Task examples: |
Task examples: |
||
< |
<syntaxhighlight lang="j"> 3 cycles 4 |
||
1 1 4 4 |
1 1 4 4 |
||
2 2 2 4 |
2 2 2 4 |
||
Line 390: | Line 638: | ||
2 2 2 4 |
2 2 2 4 |
||
2 2 3 3 |
2 2 3 3 |
||
1 3 3 3</ |
1 3 3 3</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="java">import java.util.ArrayList; |
||
import java.util.HashSet; |
import java.util.HashSet; |
||
import java.util.List; |
import java.util.List; |
||
Line 499: | Line 747: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Number of eligible 4-faced dice: 35 |
<pre>Number of eligible 4-faced dice: 35 |
||
Line 516: | Line 764: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">import Base.>, Base.< |
||
using Memoize, Combinatorics |
using Memoize, Combinatorics |
||
Line 592: | Line 840: | ||
@time testnontransitivedice(5) |
@time testnontransitivedice(5) |
||
@time testnontransitivedice(6) |
@time testnontransitivedice(6) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
All possible 1..3 3-sided dice |
All possible 1..3 3-sided dice |
||
Line 674: | Line 922: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="scala">fun fourFaceCombos(): List<Array<Int>> { |
||
val res = mutableListOf<Array<Int>>() |
val res = mutableListOf<Array<Int>>() |
||
val found = mutableSetOf<Int>() |
val found = mutableSetOf<Int>() |
||
Line 775: | Line 1,023: | ||
println(a.joinToString(", ", "[", "]") { it.joinToString(", ", "[", "]") }) |
println(a.joinToString(", ", "[", "]") { it.joinToString(", ", "[", "]") }) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Number of eligible 4-faced dice: 35 |
<pre>Number of eligible 4-faced dice: 35 |
||
Line 789: | Line 1,037: | ||
[[2, 2, 2, 4], [2, 2, 3, 3], [1, 3, 3, 3], [1, 1, 4, 4]] |
[[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> |
[[2, 2, 3, 3], [1, 3, 3, 3], [1, 1, 4, 4], [2, 2, 2, 4]]</pre> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">ClearAll[DieFight] |
|||
DieFight[d1_List, d2_List] := Module[{sets}, |
|||
sets = Tuples[{d1, d2}]; |
|||
sets = sets[[All, 2]] - sets[[All, 1]]; |
|||
Sign[Total[Sign[sets]]] |
|||
] |
|||
ds = DeleteDuplicates[Sort /@ Tuples[Range[4], 4]]; |
|||
ssis = Subsets[Range[Length[ds]], {3}]; |
|||
ssis //= Map[Permutations]; |
|||
ssis //= Catenate; |
|||
ssis //= Select[DieFight[ds[[#[[1]]]], ds[[#[[2]]]]] == 1 &]; |
|||
ssis //= Select[DieFight[ds[[#[[2]]]], ds[[#[[3]]]]] == 1 &]; |
|||
ssis //= Select[DieFight[ds[[#[[1]]]], ds[[#[[3]]]]] == -1 &]; |
|||
nontransitiveds = Map[ds[[#]] &, ssis, {2}]; |
|||
Column[Row[{#1, "<", #2, " ; ", #2, "<", #3, " ; ", #1, ">", #3}] & @@@ nontransitiveds] |
|||
ssis = Subsets[Range[Length[ds]], {4}]; |
|||
ssis //= Map[Permutations]; |
|||
ssis //= Catenate; |
|||
ssis //= Select[DieFight[ds[[#[[1]]]], ds[[#[[2]]]]] == 1 &]; |
|||
ssis //= Select[DieFight[ds[[#[[2]]]], ds[[#[[3]]]]] == 1 &]; |
|||
ssis //= Select[DieFight[ds[[#[[3]]]], ds[[#[[4]]]]] == 1 &]; |
|||
ssis //= Select[DieFight[ds[[#[[1]]]], ds[[#[[4]]]]] == -1 &]; |
|||
nontransitiveds = Map[ds[[#]] &, ssis, {2}]; |
|||
Column[Row[{#1, "<", #2, " ; ", #2, "<", #3, " ; ", #3, "<", #4, " ; ", #1, ">", #4}] & @@@ nontransitiveds]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{1,1,4,4}<{2,2,2,4} ; {2,2,2,4}<{1,3,3,3} ; {1,1,4,4}>{1,3,3,3} |
|||
{1,3,3,3}<{1,1,4,4} ; {1,1,4,4}<{2,2,2,4} ; {1,3,3,3}>{2,2,2,4} |
|||
{2,2,2,4}<{1,3,3,3} ; {1,3,3,3}<{1,1,4,4} ; {2,2,2,4}>{1,1,4,4} |
|||
{1,1,4,4}<{2,2,2,4} ; {2,2,2,4}<{2,2,3,3} ; {2,2,3,3}<{1,3,3,3} ; {1,1,4,4}>{1,3,3,3} |
|||
{1,3,3,3}<{1,1,4,4} ; {1,1,4,4}<{2,2,2,4} ; {2,2,2,4}<{2,2,3,3} ; {1,3,3,3}>{2,2,3,3} |
|||
{2,2,2,4}<{2,2,3,3} ; {2,2,3,3}<{1,3,3,3} ; {1,3,3,3}<{1,1,4,4} ; {2,2,2,4}>{1,1,4,4} |
|||
{2,2,3,3}<{1,3,3,3} ; {1,3,3,3}<{1,1,4,4} ; {1,1,4,4}<{2,2,2,4} ; {2,2,3,3}>{2,2,2,4}</pre> |
|||
=={{header|MiniZinc}}== |
=={{header|MiniZinc}}== |
||
===The model=== |
===The model=== |
||
<syntaxhighlight lang="minizinc"> |
|||
<lang MiniZinc> |
|||
%Non transitive dice. Nigel Galloway, September 14th., 2020 |
%Non transitive dice. Nigel Galloway, September 14th., 2020 |
||
int: die; int: faces; set of int: values; |
int: die; int: faces; set of int: values; |
||
Line 802: | Line 1,090: | ||
constraint pN(g[die,1..faces],g[1,1..faces]); |
constraint pN(g[die,1..faces],g[1,1..faces]); |
||
output[join(" ",[show(g[n,1..faces])++"<"++show(g[n+1,1..faces]) | n in 1..die-1])," "++show(g[die,1..faces])++">"++show(g[1,1..faces])]; |
output[join(" ",[show(g[n,1..faces])++"<"++show(g[n+1,1..faces]) | n in 1..die-1])," "++show(g[die,1..faces])++">"++show(g[1,1..faces])]; |
||
</syntaxhighlight> |
|||
</lang> |
|||
===The task(4 sided die)=== |
===The task(4 sided die)=== |
||
;3 die values=1..4 |
;3 die values=1..4 |
||
Line 1,060: | Line 1,348: | ||
{{trans|Python}} |
{{trans|Python}} |
||
{{libheader|itertools}} |
{{libheader|itertools}} |
||
<syntaxhighlight lang="nim"> |
|||
<lang Nim> |
|||
import algorithm, sequtils, sets, strformat |
import std/[algorithm, sequtils, sets, strformat] |
||
import itertools |
import itertools |
||
Line 1,079: | Line 1,367: | ||
func cmp(die1, die2: Die): int = |
func cmp(die1, die2: Die): int = |
||
## Compare two |
## Compare two dice returning 1, -1 or 0 for operators >, < ==. |
||
var tot: array[3, int] |
var tot: array[3, int] |
||
for d in product(die1.faces, die2.faces): |
for d in product(die1.faces, die2.faces): |
||
Line 1,087: | Line 1,375: | ||
func verboseCmp(die1, die2: Die): string = |
func verboseCmp(die1, die2: Die): string = |
||
## Compare |
## Compare two dice returning a string. |
||
var win1, win2 = 0 |
var win1, win2 = 0 |
||
for (d1, d2) in product(die1.faces, die2.faces): |
for (d1, d2) in product(die1.faces, die2.faces): |
||
Line 1,192: | Line 1,480: | ||
echo &"\n More verbose comparison of last non-transitive result:" |
echo &"\n More verbose comparison of last non-transitive result:" |
||
echo " ", verboseDiceCmp(nonTrans[^1]) |
echo " ", verboseDiceCmp(nonTrans[^1]) |
||
echo "\n ===="</ |
echo "\n ===="</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,248: | Line 1,536: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
Line 1,397: | Line 1,685: | ||
} |
} |
||
main();</ |
main();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Number of eligible 4-faced dice: 35 |
<pre>Number of eligible 4-faced dice: 35 |
||
Line 1,413: | Line 1,701: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0.8.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (added sq_cmp() builtin that returns nested -1/0/+1 compare() results, just like the existing sq_eq() does for equal().)</span> |
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0.8.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (added sq_cmp() builtin that returns nested -1/0/+1 compare() results, just like the existing sq_eq() does for equal().)</span> |
||
Line 1,633: | Line 1,921: | ||
<span style="color: #000000;">show_dice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dice</span><span style="color: #0000FF;">,</span><span style="color: #000000;">find_non_trans</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dice</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">),</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">show_dice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dice</span><span style="color: #0000FF;">,</span><span style="color: #000000;">find_non_trans</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dice</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">),</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,707: | Line 1,995: | ||
With the recent optimisations I can just about stretch to power(924,3), but I think I was right to skip power(924,4) above, it would probably take over two and a half ''days''.<br> |
With the recent optimisations I can just about stretch to power(924,3), but I think I was right to skip power(924,4) above, it would probably take over two and a half ''days''.<br> |
||
I have also estimated that power(3003,3) (ie 1..9 on the sides) would probably take around 4 hours (assuming such attempts didn't run out of memory). |
I have also estimated that power(3003,3) (ie 1..9 on the sides) would probably take around 4 hours (assuming such attempts didn't run out of memory). |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
||
<span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">6</span> |
<span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">6</span> |
||
Line 1,721: | Line 2,009: | ||
<span style="color: #000000;">show_dice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dice</span><span style="color: #0000FF;">,</span><span style="color: #000000;">find_non_trans</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dice</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">show_dice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dice</span><span style="color: #0000FF;">,</span><span style="color: #000000;">find_non_trans</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dice</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,783: | Line 2,071: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Trivial rotations of the same loop are not shown. |
|||
<lang python>from collections import namedtuple |
|||
<syntaxhighlight lang="python">from itertools import combinations_with_replacement as cmbr |
|||
from time import time |
|||
def dice_gen(n, faces, m): |
|||
dice = list(cmbr(faces, n)) |
|||
succ = [set(j for j, b in enumerate(dice) |
|||
if sum((x>y) - (x<y) for x in a for y in b) > 0) |
|||
for a in dice] |
|||
def loops(seq): |
|||
s = succ[seq[-1]] |
|||
if len(seq) == m: |
|||
if seq[0] in s: yield seq |
|||
return |
|||
for d in (x for x in s if x > seq[0] and not x in seq): |
|||
yield from loops(seq + (d,)) |
|||
yield from (tuple(''.join(dice[s]) for s in x) |
|||
for i, v in enumerate(succ) |
|||
for x in loops((i,))) |
|||
t = time() |
|||
for n, faces, loop_len in [(4, '1234', 3), (4, '1234', 4), (6, '123456', 3), (6, '1234567', 3)]: |
|||
for i, x in enumerate(dice_gen(n, faces, loop_len)): pass |
|||
print(f'{n}-sided, markings {faces}, loop length {loop_len}:') |
|||
print(f'\t{i + 1}*{loop_len} solutions, e.g. {" > ".join(x)} > [loop]') |
|||
t, t0 = time(), t |
|||
print(f'\ttime: {t - t0:.4f} seconds\n')</syntaxhighlight> |
|||
{{out}} |
|||
<pre>4-sided, markings 1234, loop length 3: |
|||
1*3 solutions, e.g. 1144 > 1333 > 2224 > [loop] |
|||
time: 0.0000 seconds |
|||
4-sided, markings 1234, loop length 4: |
|||
1*4 solutions, e.g. 1144 > 1333 > 2233 > 2224 > [loop] |
|||
time: 0.0100 seconds |
|||
6-sided, markings 123456, loop length 3: |
|||
40666*3 solutions, e.g. 335666 > 555556 > 444666 > [loop] |
|||
time: 1.1459 seconds |
|||
6-sided, markings 1234567, loop length 3: |
|||
423063*3 solutions, e.g. 446777 > 666667 > 555777 > [loop] |
|||
time: 6.9465 seconds</pre> |
|||
===Alternative=== |
|||
<syntaxhighlight lang="python">from collections import namedtuple |
|||
from itertools import permutations, product |
from itertools import permutations, product |
||
from functools import lru_cache |
from functools import lru_cache |
||
Line 1,857: | Line 2,196: | ||
print('\n More verbose comparison of last non_transitive result:') |
print('\n More verbose comparison of last non_transitive result:') |
||
print(' ', verbose_dice_cmp(non_trans[-1])) |
print(' ', verbose_dice_cmp(non_trans[-1])) |
||
print('\n ====')</ |
print('\n ====')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,918: | Line 2,257: | ||
=={{header|R}}== |
=={{header|R}}== |
||
It would not be difficult to adapt this code to meet the stretch goal, but readability would suffer. |
It would not be difficult to adapt this code to meet the stretch goal, but readability would suffer. |
||
< |
<syntaxhighlight lang="rsplus">findNonTrans <- function() |
||
{ |
{ |
||
diceSet <- unique(t(apply(expand.grid(1:4, 1:4, 1:4, 1:4), 1, sort))) #By construction, each row is a unique dice. |
diceSet <- unique(t(apply(expand.grid(1:4, 1:4, 1:4, 1:4), 1, sort))) #By construction, each row is a unique dice. |
||
Line 1,953: | Line 2,292: | ||
} |
} |
||
} |
} |
||
findNonTrans()</ |
findNonTrans()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,975: | Line 2,314: | ||
Thanks to Thundergnat for the nice "less-is-more" tweaks now the 4 dice portion takes around 10 (down from 17 ) minutes to run .. |
Thanks to Thundergnat for the nice "less-is-more" tweaks now the 4 dice portion takes around 10 (down from 17 ) minutes to run .. |
||
{{trans|Go}} |
{{trans|Go}} |
||
<lang |
<syntaxhighlight lang="raku" line># 20201225 Raku programming solution |
||
my @dicepool = ^4 xx 4 ; |
my @dicepool = ^4 xx 4 ; |
||
Line 2,010: | Line 2,349: | ||
say +@output, " ordered lists of $_ non-transitive dice found, namely:"; |
say +@output, " ordered lists of $_ non-transitive dice found, namely:"; |
||
.say for @output; |
.say for @output; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Number of eligible 4-faced dice : 35 |
<pre>Number of eligible 4-faced dice : 35 |
||
Line 2,025: | Line 2,364: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-sort}} |
{{libheader|Wren-sort}} |
||
< |
<syntaxhighlight lang="wren">import "./sort" for Sort |
||
var fourFaceCombs = Fn.new { |
var fourFaceCombs = Fn.new { |
||
Line 2,115: | Line 2,454: | ||
it = findIntransitive4.call(combs) |
it = findIntransitive4.call(combs) |
||
System.print("\n%(it.count) ordered lists of 4 non-transitive dice found, namely:") |
System.print("\n%(it.count) ordered lists of 4 non-transitive dice found, namely:") |
||
System.print(it.join("\n"))</ |
System.print(it.join("\n"))</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 21:06, 15 August 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
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
- Rotations: Any rotation of non-transitive dice from an answer is also an answer. You may optionally compute and show only one of each such rotation sets, ideally the first when sorted in a natural way. If this option is used then prominently state in the output that rotations of results are also solutions.
- 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.
ALGOL 68
# iterates through all possible dice #
PROC iterate = (PROC(INT, []INT)VOID f)VOID:
BEGIN
INT n := 1;
[4]INT sides;
FOR i FROM 1 TO 4 DO FOR j FROM i TO 4 DO
FOR k FROM j TO 4 DO FOR l FROM k TO 4 DO
sides := (i, j, k, l);
f(n, sides);
n +:= 1
OD OD OD OD
END;
# compares 2 dice, returns (-1, 0, 1) for a (<, =, >) b #
PROC compare = ([]INT a, []INT b)INT:
BEGIN
INT result := 0;
FOR i TO UPB a DO
FOR j TO UPB b DO
result +:= SIGN(a[i] - b[j])
OD
OD;
SIGN result
END;
# compact representation of die #
PROC str = ([]INT die)STRING:
BEGIN
STRING result := " " * UPB die;
FOR i TO UPB die DO
result[i] := REPR (die[i] + ABS "0")
OD;
result
END;
# first count all possible dice #
INT ndice := 0;
iterate((INT n, []INT sides)VOID: ndice +:= 1);
# store them by index #
[ndice][4]INT dice;
iterate((INT n, []INT sides)VOID: dice[n] := sides);
# fill the results of an all-play-all tournament #
[ndice,ndice]INT results;
FOR i TO ndice DO
FOR j FROM i TO ndice DO
results[i,j] := compare(dice[i], dice[j]);
results[j,i] := results[i,j] * -1
OD
OD;
# helper function to print the intransitive sequence #
PROC print seq = ([]INT idxs)VOID:
BEGIN
FOR i TO UPB idxs DO
IF i > 1 THEN print((" < ")) FI;
print((str(dice[idxs[i]])))
OD;
print((newline))
END;
# find all (s,t,u) where s < t < u < s #
print(("3 dice:", newline));
FOR s TO ndice DO
FOR t TO ndice DO
IF results[s,t] = -1 THEN
FOR u TO ndice DO
IF results[t,u] = -1 AND results[u,s] = -1 THEN
print seq((s, t, u, s))
FI
OD
FI
OD
OD;
# find all (s,t,u,v) where s < t < u < v < s #
print(("4 dice:", newline));
FOR s TO ndice DO
FOR t TO ndice DO
IF results[s,t] = -1 THEN
FOR u TO ndice DO
IF results[t,u] = -1 THEN
FOR v TO ndice DO
IF results[u,v] = -1 AND results[v,s] = -1 THEN
print seq((s, t, u, v, s))
FI
OD
FI
OD
FI
OD
OD
- Output:
3 dice: 1144 < 2224 < 1333 < 1144 1333 < 1144 < 2224 < 1333 2224 < 1333 < 1144 < 2224 4 dice: 1144 < 2224 < 2233 < 1333 < 1144 1333 < 1144 < 2224 < 2233 < 1333 2224 < 2233 < 1333 < 1144 < 2224 2233 < 1333 < 1144 < 2224 < 2233
C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <set>
#include <vector>
void print_vector(const std::vector<uint32_t>& list) {
std::cout << "[";
for ( uint64_t i = 0; i < list.size() - 1; ++i ) {
std::cout << list[i] << ", ";
}
std::cout << list.back() << "]";
}
void display_table(const std::vector<std::vector<uint32_t>> table) {
std::cout << "[";
for ( uint64_t i = 0; i < table.size() - 1; ++i ) {
print_vector(table[i]);
std::cout << ", ";
}
print_vector(table.back());
std::cout << "]" << "\n";
}
std::vector<std::vector<uint32_t>> four_face_combinations() {
std::vector<std::vector<uint32_t>> result = { };
std::set<uint32_t> found = { };
for ( uint32_t i = 1; i <= 4; ++i ) {
for ( uint32_t j = 1; j <= 4; ++j ) {
for ( uint32_t k = 1; k <= 4; ++k ) {
for ( uint32_t l = 1; l <= 4; ++l ) {
std::vector<uint32_t> combo = { i, j, k, l };
std::sort(combo.begin(), combo.end());
const uint32_t key = 64 * combo[0] + 16 * combo[1] + 4 * combo[2] + combo[3];
if ( found.insert(key).second ) {
result.emplace_back(combo);
}
}
}
}
}
return result;
}
bool comparator(const std::vector<uint32_t>& one, const std::vector<uint32_t>& two) {
uint32_t one_wins = 0;
uint32_t two_wins = 0;
for ( uint32_t i = 0; i < 4; ++i ) {
for ( uint32_t j = 0; j < 4; ++j ) {
if ( one[i] > two[j] ) {
one_wins++;
} else if ( one[i] < two[j] ) {
two_wins++;
}
}
}
return ( one_wins < two_wins );
}
std::vector<std::vector<std::vector<uint32_t>>> find_intransitive_3(
const std::vector<std::vector<uint32_t>>& combos) {
std::vector<std::vector<std::vector<uint32_t>>> result = { };
for ( uint64_t i = 0; i < combos.size(); ++i ) {
for ( uint64_t j = 0; j < combos.size(); ++j ) {
if ( comparator(combos[i], combos[j]) ) {
for ( const std::vector<uint32_t>& combo : combos ) {
if ( comparator(combos[j], combo) && comparator(combo, combos[i]) ) {
std::vector<std::vector<uint32_t>> entry = { combos[i], combos[j], combo };
result.emplace_back(entry);
}
}
}
}
}
return result;
}
std::vector<std::vector<std::vector<uint32_t>>> find_intransitive_4(
const std::vector<std::vector<uint32_t>>& combos) {
std::vector<std::vector<std::vector<uint32_t>>> result = { };
for ( uint64_t i = 0; i < combos.size(); ++i ) {
for ( uint64_t j = 0; j < combos.size(); ++j ) {
if ( comparator(combos[i], combos[j]) ) {
for ( uint64_t k = 0; k < combos.size(); ++k ) {
if ( comparator(combos[j], combos[k]) ) {
for ( const std::vector<uint32_t>& combo : combos ) {
if ( comparator(combos[k], combo) && comparator(combo, combos[i]) ) {
std::vector<std::vector<uint32_t>> entry =
{ combos[i], combos[j], combos[k], combo };
result.emplace_back(entry);
}
}
}
}
}
}
}
return result;
}
int main() {
std::vector<std::vector<uint32_t>> combinations = four_face_combinations();
std::cout << "The number of eligible 4-faced dice: " << combinations.size() << "\n\n";
std::vector<std::vector<std::vector<uint32_t>>> intransitive_3 = find_intransitive_3(combinations);
std::cout << intransitive_3.size() << " ordered lists of 3 non-transitive dice found, namely:" << "\n";
for ( const std::vector<std::vector<uint32_t>>& table : intransitive_3 ) {
display_table(table);
}
std::cout << "\n";
std::vector<std::vector<std::vector<uint32_t>>> intransitive_4 = find_intransitive_4(combinations);
std::cout << intransitive_4.size() << " ordered lists of 4 non-transitive dice found, namely:" << "\n";
for ( const std::vector<std::vector<uint32_t>>& table : intransitive_4 ) {
display_table(table);
}
}
- Output:
The 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]]
F#
The task (4 sided die)
// Non-transitive dice. Nigel Galloway: August 9th., 2020
let die=[for n0 in [1..4] do for n1 in [n0..4] do for n2 in [n1..4] do for n3 in [n2..4]->[n0;n1;n2;n3]]
let N=seq{for n in die->(n,[for g in die do if (seq{for n in n do for g in g->compare n g}|>Seq.sum<0) then yield g])}|>Map.ofSeq
let n3=seq{for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)}
let n4=seq{for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do for d4 in N.[d3] do if List.contains d1 N.[d4] then yield (d1,d2,d3,d4)}
n3|>Seq.iter(fun(d1,d2,d3)->printfn "%A<%A; %A<%A; %A>%A\n" d1 d2 d2 d3 d1 d3)
n4|>Seq.iter(fun(d1,d2,d3,d4)->printfn "%A<%A; %A<%A; %A<%A; %A>%A" d1 d2 d2 d3 d3 d4 d1 d4)
- Output:
[1; 1; 4; 4]<[2; 2; 2; 4]; [2; 2; 2; 4]<[1; 3; 3; 3]; [1; 1; 4; 4]>[1; 3; 3; 3] [1; 3; 3; 3]<[1; 1; 4; 4]; [1; 1; 4; 4]<[2; 2; 2; 4]; [1; 3; 3; 3]>[2; 2; 2; 4] [2; 2; 2; 4]<[1; 3; 3; 3]; [1; 3; 3; 3]<[1; 1; 4; 4]; [2; 2; 2; 4]>[1; 1; 4; 4] Real: 00:00:00.039 [1; 1; 4; 4]<[2; 2; 2; 4]; [2; 2; 2; 4]<[2; 2; 3; 3]; [2; 2; 3; 3]<[1; 3; 3; 3]; [1; 1; 4; 4]>[1; 3; 3; 3] [1; 3; 3; 3]<[1; 1; 4; 4]; [1; 1; 4; 4]<[2; 2; 2; 4]; [2; 2; 2; 4]<[2; 2; 3; 3]; [1; 3; 3; 3]>[2; 2; 3; 3] [2; 2; 2; 4]<[2; 2; 3; 3]; [2; 2; 3; 3]<[1; 3; 3; 3]; [1; 3; 3; 3]<[1; 1; 4; 4]; [2; 2; 2; 4]>[1; 1; 4; 4] [2; 2; 3; 3]<[1; 3; 3; 3]; [1; 3; 3; 3]<[1; 1; 4; 4]; [1; 1; 4; 4]<[2; 2; 2; 4]; [2; 2; 3; 3]>[2; 2; 2; 4] Real: 00:00:00.152
Extra credit (6 sided die)
- Sides numbered 1..6
// Non-transitive diceNigel Galloway: August 9th., 2020
let die=[for n0 in [1..6] do for n1 in [n0..6] do for n2 in [n1..6] do for n3 in [n2..6] do for n4 in [n3..6] do for n5 in [n4..6]->[n0;n1;n2;n3;n4;n5]]
let N=seq{for n in die->(n,[for g in die do if (seq{for n in n do for g in g->compare n g}|>Seq.sum<0) then yield g])}|>Map.ofSeq
let n3=[for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)]
let d1,d2,d3=List.last n3 in printfn "Solutions found = %d\nLast solution found is %A<%A; %A<%A; %A>%A" (n3.Length) d1 d2 d2 d3 d1 d3
- Output:
Solutions found = 121998 Last solution found is [5; 5; 5; 5; 5; 6]<[3; 3; 5; 6; 6; 6]; [3; 3; 5; 6; 6; 6]<[4; 4; 4; 6; 6; 6]; [5; 5; 5; 5; 5; 6]>[4; 4; 4; 6; 6; 6] Real: 00:05:32.984
- Sides numbered 1..7
// Non-transitive diceNigel Galloway: August 9th., 2020
let die=[for n0 in [1..7] do for n1 in [n0..7] do for n2 in [n1..7] do for n3 in [n2..7] do for n4 in [n3..7] do for n5 in [n4..7]->[n0;n1;n2;n3;n4;n5]]
let N=seq{for n in die->(n,[for g in die do if (seq{for n in n do for g in g->compare n g}|>Seq.sum<0) then yield g])}|>Map.ofSeq
let n3=[for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)]
let d1,d2,d3=List.last n3 in printfn "Solutions found = %d\nLast solution found is %A<%A; %A<%A; %A>%A" (n3.Length) d1 d2 d2 d3 d1 d3
- Output:
Solutions found = 1269189 Last solution found is [6; 6; 6; 6; 6; 7]<[4; 4; 6; 7; 7; 7]; [4; 4; 6; 7; 7; 7]<[5; 5; 5; 7; 7; 7]; [6; 6; 6; 6; 6; 7]>[5; 5; 5; 7; 7; 7] Real: 01:21:36.912
Factor
USING: grouping io kernel math math.combinatorics math.ranges
prettyprint sequences ;
: possible-dice ( n -- seq )
[ [1,b] ] [ selections ] bi [ [ <= ] monotonic? ] filter ;
: cmp ( seq seq -- n ) [ - sgn ] cartesian-map concat sum ;
: non-transitive? ( seq -- ? )
[ 2 clump [ first2 cmp neg? ] all? ]
[ [ last ] [ first ] bi cmp neg? and ] bi ;
: find-non-transitive ( #sides #dice -- seq )
[ possible-dice ] [ <k-permutations> ] bi*
[ non-transitive? ] filter ;
! Task
"Number of eligible 4-sided dice: " write
4 possible-dice length . nl
"All ordered lists of 3 non-transitive dice with 4 sides:" print
4 3 find-non-transitive . nl
"All ordered lists of 4 non-transitive dice with 4 sides:" print
4 4 find-non-transitive .
- Output:
Number of eligible 4-sided dice: 35 All ordered lists of 3 non-transitive dice with 4 sides: V{ { { 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 } } } All ordered lists of 4 non-transitive dice with 4 sides: V{ { { 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 } } }
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)
}
}
- 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]]
Haskell
{-# language LambdaCase #-}
import Data.List
import Control.Monad
newtype Dice = Dice [Int]
instance Show Dice where
show (Dice s) = "(" ++ unwords (show <$> s) ++ ")"
instance Eq Dice where
d1 == d2 = d1 `compare` d2 == EQ
instance Ord Dice where
Dice d1 `compare` Dice d2 = (add $ compare <$> d1 <*> d2) `compare` 0
where
add = sum . map (\case {LT -> -1; EQ -> 0; GT -> 1})
dices n = Dice <$> (nub $ sort <$> replicateM n [1..n])
nonTrans dice = filter (\x -> last x < head x) . go
where
go 0 = []
go 1 = sequence [dice]
go n = do
(a:as) <- go (n-1)
b <- filter (< a) dice
return (b:a:as)
*Main> mapM_ print $ nonTrans (dices 4) 3 [(2 2 2 4),(1 3 3 3),(1 1 4 4)] [(1 1 4 4),(2 2 2 4),(1 3 3 3)] [(1 3 3 3),(1 1 4 4),(2 2 2 4)] *Main> mapM_ print $ nonTrans (dices 4) 4 [(2 2 2 4),(2 2 3 3),(1 3 3 3),(1 1 4 4)] [(1 1 4 4),(2 2 2 4),(2 2 3 3),(1 3 3 3)] [(2 2 3 3),(1 3 3 3),(1 1 4 4),(2 2 2 4)] [(1 3 3 3),(1 1 4 4),(2 2 2 4),(2 2 3 3)] *Main> length $ nonTrans (dices 4) 5 0 *Main> length $ nonTrans (dices 5) 3 2022
J
Implementation (rotations of results here are also solutions):
NB. unique list of all y faced dice
udice=: {{ 1+~./:~"1 (#: ,@i.)y#y }}
NB. which dice are less than which other dice?
NB. y here is a result of udice
lthan=: {{ 0>*@(+/)@,@:*@(-/)"1/~ y}}
NB. "less than loops" length x, for y sided non-transitive dice
cycles=: {{
ud=. udice y
lt=. lthan ud
extend=. [:; lt{{< y,"1 0 y-.~I.m{~{:y }}"1
r=. ; extend^:(x-1)&.> i.#ud
ud{~ ~.((i.<./)|.])"1 r #~ lt{~({:,&.>{.)|:r
}}
Here, extend takes a list of die sequences and appends each possibility of a new die where the new die is not less than the last die in the sequence. So, r is all such lists of length x. We discard the cases where the last element of the list is not less than the first, rotate each dice index list into canonical order, discard duplicates, and then use these indices to select the associated dice.
Task examples:
3 cycles 4
1 1 4 4
2 2 2 4
1 3 3 3
4 cycles 4
1 1 4 4
2 2 2 4
2 2 3 3
1 3 3 3
Java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Main {
private static List<List<Integer>> fourFaceCombos() {
List<List<Integer>> res = new ArrayList<>();
Set<Integer> found = new HashSet<>();
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
for (int k = 1; k <= 4; k++) {
for (int l = 1; l <= 4; l++) {
List<Integer> c = IntStream.of(i, j, k, l).sorted().boxed().collect(Collectors.toList());
int key = 64 * (c.get(0) - 1) + 16 * (c.get(1) - 1) + 4 * (c.get(2) - 1) + (c.get(3) - 1);
if (found.add(key)) {
res.add(c);
}
}
}
}
}
return res;
}
private static int cmp(List<Integer> x, List<Integer> y) {
int xw = 0;
int yw = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (x.get(i) > y.get(j)) {
xw++;
} else if (x.get(i) < y.get(j)) {
yw++;
}
}
}
return Integer.compare(xw, yw);
}
private static List<List<List<Integer>>> findIntransitive3(List<List<Integer>> cs) {
int c = cs.size();
List<List<List<Integer>>> res = new ArrayList<>();
for (int i = 0; i < c; i++) {
for (int j = 0; j < c; j++) {
if (cmp(cs.get(i), cs.get(j)) == -1) {
for (List<Integer> kl : cs) {
if (cmp(cs.get(j), kl) == -1 && cmp(kl, cs.get(i)) == -1) {
res.add(List.of(cs.get(i), cs.get(j), kl));
}
}
}
}
}
return res;
}
private static List<List<List<Integer>>> findIntransitive4(List<List<Integer>> cs) {
int c = cs.size();
List<List<List<Integer>>> res = new ArrayList<>();
for (int i = 0; i < c; i++) {
for (int j = 0; j < c; j++) {
if (cmp(cs.get(i), cs.get(j)) == -1) {
for (int k = 0; k < cs.size(); k++) {
if (cmp(cs.get(j), cs.get(k)) == -1) {
for (List<Integer> ll : cs) {
if (cmp(cs.get(k), ll) == -1 && cmp(ll, cs.get(i)) == -1) {
res.add(List.of(cs.get(i), cs.get(j), cs.get(k), ll));
}
}
}
}
}
}
}
return res;
}
public static void main(String[] args) {
List<List<Integer>> combos = fourFaceCombos();
System.out.printf("Number of eligible 4-faced dice: %d%n", combos.size());
System.out.println();
List<List<List<Integer>>> it3 = findIntransitive3(combos);
System.out.printf("%d ordered lists of 3 non-transitive dice found, namely:%n", it3.size());
for (List<List<Integer>> a : it3) {
System.out.println(a);
}
System.out.println();
List<List<List<Integer>>> it4 = findIntransitive4(combos);
System.out.printf("%d ordered lists of 4 non-transitive dice found, namely:%n", it4.size());
for (List<List<Integer>> a : it4) {
System.out.println(a);
}
}
}
- 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]]
Julia
import Base.>, Base.<
using Memoize, Combinatorics
struct Die
name::String
faces::Vector{Int}
end
""" Compares two die returning 1, -1 or 0 for operators >, < == """
function cmpd(die1, die2)
# 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 d in Iterators.product(die1.faces, die2.faces)
tot[2 + (d[1] > d[2]) - (d[2] > d[1])] += 1
end
return (tot[3] > tot[1]) - (tot[1] > tot[3])
end
Base.:>(d1::Die, d2::Die) = cmpd(d1, d2) == 1
Base.:<(d1::Die, d2::Die) = cmpd(d1, d2) == -1
""" True iff ordering of die in dice is non-transitive """
isnontrans(dice) = all(x -> x[1] < x[2], zip(dice[1:end-1], dice[2:end])) && dice[1] > dice[end]
findnontrans(alldice, n=3) = [perm for perm in permutations(alldice, n) if isnontrans(perm)]
function possible_dice(sides, mx)
println("\nAll possible 1..$mx $sides-sided dice")
dice = [Die("D $(n+1)", [i for i in f]) for (n, f) in
enumerate(Iterators.product(fill(1:mx, sides)...))]
println(" Created $(length(dice)) dice")
println(" Remove duplicate with same bag of numbers on different faces")
uniquedice = collect(values(Dict(sort(d.faces) => d for d in dice)))
println(" Return $(length(uniquedice)) filtered dice")
return uniquedice
end
""" Compares two die returning their relationship of their names as a string """
function verbosecmp(die1, die2)
# Numbers of times one die wins against the other for all combinations
win1 = sum(p[1] > p[2] for p in Iterators.product(die1.faces, die2.faces))
win2 = sum(p[2] > p[1] for p in Iterators.product(die1.faces, die2.faces))
n1, n2 = die1.name, die2.name
return win1 > win2 ? "$n1 > $n2" : win1 < win2 ? "$n1 < $n2" : "$n1 = $n2"
end
""" Dice cmp function with verbose extra checks """
function verbosedicecmp(dice)
return join([[verbosecmp(x, y) for (x, y) in zip(dice[1:end-1], dice[2:end])];
[verbosecmp(dice[1], dice[end])]], ", ")
end
function testnontransitivedice(faces)
dice = possible_dice(faces, faces)
for N in (faces < 5 ? [3, 4] : [3]) # length of non-transitive group of dice searched for
nontrans = unique(map(x -> sort!(x, lt=(x, y)->x.name<y.name), findnontrans(dice, N)))
println("\n Unique sorted non_transitive length-$N combinations found: $(length(nontrans))")
for list in (faces < 5 ? nontrans : [nontrans[end]])
println(faces < 5 ? "" : " Only printing last example for brevity")
for (i, die) in enumerate(list)
println(" $die$(i < N - 1 ? "," : "]")")
end
end
if !isempty(nontrans)
println("\n More verbose comparison of last non_transitive result:")
println(" ", verbosedicecmp(nontrans[end]))
end
println("\n ====")
end
end
@time testnontransitivedice(3)
@time testnontransitivedice(4)
@time testnontransitivedice(5)
@time testnontransitivedice(6)
- Output:
All possible 1..3 3-sided dice Created 27 dice Remove duplicate with same bag of numbers on different faces Return 10 filtered dice Unique sorted non_transitive length-3 combinations found: 0 ==== Unique sorted non_transitive length-4 combinations found: 0 ==== 0.762201 seconds (1.72 M allocations: 89.509 MiB, 1.65% gc time) All possible 1..4 4-sided dice Created 256 dice Remove duplicate with same bag of numbers on different faces Return 35 filtered dice Unique sorted non_transitive length-3 combinations found: 1 Die("D 170", [1, 3, 3, 3]), Die("D 215", [2, 2, 2, 4])] Die("D 242", [1, 1, 4, 4])] More verbose comparison of last non_transitive result: D 170 > D 215, D 215 > D 242, D 170 < D 242 ==== Unique sorted non_transitive length-4 combinations found: 1 Die("D 167", [2, 2, 3, 3]), Die("D 170", [1, 3, 3, 3]), Die("D 215", [2, 2, 2, 4])] Die("D 242", [1, 1, 4, 4])] More verbose comparison of last non_transitive result: D 167 < D 170, D 170 > D 215, D 215 > D 242, D 167 = D 242 ==== 1.075354 seconds (8.15 M allocations: 1.075 GiB, 11.05% gc time) All possible 1..5 5-sided dice Created 3125 dice Remove duplicate with same bag of numbers on different faces Return 126 filtered dice Unique sorted non_transitive length-3 combinations found: 674 Only printing last example for brevity Die("D 2938", [2, 3, 3, 4, 5]), Die("D 3058", [2, 2, 3, 5, 5])] Die("D 3082", [1, 2, 4, 5, 5])] More verbose comparison of last non_transitive result: D 2938 > D 3058, D 3058 > D 3082, D 2938 < D 3082 ==== 2.422382 seconds (11.51 M allocations: 2.834 GiB, 18.87% gc time) All possible 1..6 6-sided dice Created 46656 dice Remove duplicate with same bag of numbers on different faces Return 462 filtered dice Unique sorted non_transitive length-3 combinations found: 40666 Only printing last example for brevity Die("D 35727", [2, 3, 3, 4, 4, 5]), Die("D 41991", [2, 3, 3, 3, 3, 6])] Die("D 46484", [1, 2, 2, 6, 6, 6])] More verbose comparison of last non_transitive result: D 35727 > D 41991, D 41991 > D 46484, D 35727 < D 46484 ==== 123.182432 seconds (553.51 M allocations: 392.013 GiB, 17.02% gc time
Kotlin
fun fourFaceCombos(): List<Array<Int>> {
val res = mutableListOf<Array<Int>>()
val found = mutableSetOf<Int>()
for (i in 1..4) {
for (j in 1..4) {
for (k in 1..4) {
for (l in 1..4) {
val c = arrayOf(i, j, k, l)
c.sort()
val key = 64 * (c[0] - 1) + 16 * (c[1] - 1) + 4 * (c[2] - 1) + (c[3] - 1)
if (!found.contains(key)) {
found.add(key)
res.add(c)
}
}
}
}
}
return res
}
fun cmp(x: Array<Int>, y: Array<Int>): Int {
var xw = 0
var yw = 0
for (i in 0 until 4) {
for (j in 0 until 4) {
if (x[i] > y[j]) {
xw++
} else if (y[j] > x[i]) {
yw++
}
}
}
if (xw < yw) {
return -1
}
if (xw > yw) {
return 1
}
return 0
}
fun findIntransitive3(cs: List<Array<Int>>): List<Array<Array<Int>>> {
val c = cs.size
val res = mutableListOf<Array<Array<Int>>>()
for (i in 0 until c) {
for (j in 0 until c) {
if (cmp(cs[i], cs[j]) == -1) {
for (k in 0 until c) {
if (cmp(cs[j], cs[k]) == -1 && cmp(cs[k], cs[i]) == -1) {
res.add(arrayOf(cs[i], cs[j], cs[k]))
}
}
}
}
}
return res
}
fun findIntransitive4(cs: List<Array<Int>>): List<Array<Array<Int>>> {
val c = cs.size
val res = mutableListOf<Array<Array<Int>>>()
for (i in 0 until c) {
for (j in 0 until c) {
if (cmp(cs[i], cs[j]) == -1) {
for (k in 0 until c) {
if (cmp(cs[j], cs[k]) == -1) {
for (l in 0 until c) {
if (cmp(cs[k], cs[l]) == -1 && cmp(cs[l], cs[i]) == -1) {
res.add(arrayOf(cs[i], cs[j], cs[k], cs[l]))
}
}
}
}
}
}
}
return res
}
fun main() {
val combos = fourFaceCombos()
println("Number of eligible 4-faced dice: ${combos.size}")
println()
val it3 = findIntransitive3(combos)
println("${it3.size} ordered lists of 3 non-transitive dice found, namely:")
for (a in it3) {
println(a.joinToString(", ", "[", "]") { it.joinToString(", ", "[", "]") })
}
println()
val it4 = findIntransitive4(combos)
println("${it4.size} ordered lists of 4 non-transitive dice found, namely:")
for (a in it4) {
println(a.joinToString(", ", "[", "]") { it.joinToString(", ", "[", "]") })
}
}
- 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]]
Mathematica /Wolfram Language
ClearAll[DieFight]
DieFight[d1_List, d2_List] := Module[{sets},
sets = Tuples[{d1, d2}];
sets = sets[[All, 2]] - sets[[All, 1]];
Sign[Total[Sign[sets]]]
]
ds = DeleteDuplicates[Sort /@ Tuples[Range[4], 4]];
ssis = Subsets[Range[Length[ds]], {3}];
ssis //= Map[Permutations];
ssis //= Catenate;
ssis //= Select[DieFight[ds[[#[[1]]]], ds[[#[[2]]]]] == 1 &];
ssis //= Select[DieFight[ds[[#[[2]]]], ds[[#[[3]]]]] == 1 &];
ssis //= Select[DieFight[ds[[#[[1]]]], ds[[#[[3]]]]] == -1 &];
nontransitiveds = Map[ds[[#]] &, ssis, {2}];
Column[Row[{#1, "<", #2, " ; ", #2, "<", #3, " ; ", #1, ">", #3}] & @@@ nontransitiveds]
ssis = Subsets[Range[Length[ds]], {4}];
ssis //= Map[Permutations];
ssis //= Catenate;
ssis //= Select[DieFight[ds[[#[[1]]]], ds[[#[[2]]]]] == 1 &];
ssis //= Select[DieFight[ds[[#[[2]]]], ds[[#[[3]]]]] == 1 &];
ssis //= Select[DieFight[ds[[#[[3]]]], ds[[#[[4]]]]] == 1 &];
ssis //= Select[DieFight[ds[[#[[1]]]], ds[[#[[4]]]]] == -1 &];
nontransitiveds = Map[ds[[#]] &, ssis, {2}];
Column[Row[{#1, "<", #2, " ; ", #2, "<", #3, " ; ", #3, "<", #4, " ; ", #1, ">", #4}] & @@@ nontransitiveds]
- Output:
{1,1,4,4}<{2,2,2,4} ; {2,2,2,4}<{1,3,3,3} ; {1,1,4,4}>{1,3,3,3} {1,3,3,3}<{1,1,4,4} ; {1,1,4,4}<{2,2,2,4} ; {1,3,3,3}>{2,2,2,4} {2,2,2,4}<{1,3,3,3} ; {1,3,3,3}<{1,1,4,4} ; {2,2,2,4}>{1,1,4,4} {1,1,4,4}<{2,2,2,4} ; {2,2,2,4}<{2,2,3,3} ; {2,2,3,3}<{1,3,3,3} ; {1,1,4,4}>{1,3,3,3} {1,3,3,3}<{1,1,4,4} ; {1,1,4,4}<{2,2,2,4} ; {2,2,2,4}<{2,2,3,3} ; {1,3,3,3}>{2,2,3,3} {2,2,2,4}<{2,2,3,3} ; {2,2,3,3}<{1,3,3,3} ; {1,3,3,3}<{1,1,4,4} ; {2,2,2,4}>{1,1,4,4} {2,2,3,3}<{1,3,3,3} ; {1,3,3,3}<{1,1,4,4} ; {1,1,4,4}<{2,2,2,4} ; {2,2,3,3}>{2,2,2,4}
MiniZinc
The model
%Non transitive dice. Nigel Galloway, September 14th., 2020
int: die; int: faces; set of int: values;
predicate pN(array[1..faces] of var values: n, array[1..faces] of var values: g) = sum(i in 1..faces,j in 1..faces)(if n[i]<g[j] then 1 elseif n[i]>g[j] then -1 else 0 endif)>0;
predicate pG(array[1..faces] of var values: n) = forall(g in 1..faces-1)(n[g]<=n[g+1]);
array[1..die,1..faces] of var values: g;
constraint forall(n in 1..die)(pG(g[n,1..faces]));
constraint forall(n in 1..die-1)(pN(g[n,1..faces],g[n+1,1..faces]));
constraint pN(g[die,1..faces],g[1,1..faces]);
output[join(" ",[show(g[n,1..faces])++"<"++show(g[n+1,1..faces]) | n in 1..die-1])," "++show(g[die,1..faces])++">"++show(g[1,1..faces])];
The task(4 sided die)
- 3 die values=1..4
Compiling non_trans.mzn, additional arguments die=3; faces=4; values=1..4; Running non_trans.mzn [1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]<[1, 3, 3, 3] [1, 3, 3, 3]>[1, 1, 4, 4] ---------- [2, 2, 2, 4]<[1, 3, 3, 3] [1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]>[2, 2, 2, 4] ---------- [1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]>[1, 3, 3, 3] ---------- ========== %%%mzn-stat: nodes=669 %%%mzn-stat: failures=413 %%%mzn-stat: restarts=0 %%%mzn-stat: variables=746 %%%mzn-stat: intVars=60 %%%mzn-stat: boolVariables=684 %%%mzn-stat: propagators=205 %%%mzn-stat: propagations=35274 %%%mzn-stat: peakDepth=49 %%%mzn-stat: nogoods=413 %%%mzn-stat: backjumps=256 %%%mzn-stat: peakMem=0.00 %%%mzn-stat: time=0.011 %%%mzn-stat: initTime=0.004 %%%mzn-stat: solveTime=0.007 %%%mzn-stat: baseMem=0.00 %%%mzn-stat: trailMem=0.00 %%%mzn-stat: randomSeed=1599951884 Finished in 174msec
- 4 die values=1..4
Compiling non_trans.mzn, additional arguments die=4; faces=4; values=1..4; Running non_trans.mzn [1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]<[2, 2, 3, 3] [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, 3, 3]<[1, 3, 3, 3] [1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]>[2, 2, 2, 4] ---------- [1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]<[2, 2, 3, 3] [2, 2, 3, 3]>[1, 3, 3, 3] ---------- [2, 2, 3, 3]<[1, 3, 3, 3] [1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]>[2, 2, 3, 3] ---------- ========== %%%mzn-stat: nodes=1573 %%%mzn-stat: failures=856 %%%mzn-stat: restarts=0 %%%mzn-stat: variables=994 %%%mzn-stat: intVars=80 %%%mzn-stat: boolVariables=912 %%%mzn-stat: propagators=273 %%%mzn-stat: propagations=85224 %%%mzn-stat: peakDepth=65 %%%mzn-stat: nogoods=856 %%%mzn-stat: backjumps=717 %%%mzn-stat: peakMem=0.00 %%%mzn-stat: time=0.022 %%%mzn-stat: initTime=0.007 %%%mzn-stat: solveTime=0.015 %%%mzn-stat: baseMem=0.00 %%%mzn-stat: trailMem=0.01 %%%mzn-stat: randomSeed=1599951808 Finished in 190msec
Extra Credt(6 sided die)
- 3 die values=1..6
Compiling non_trans.mzn, additional arguments die=3; faces=6; values=1..6; Running non_trans.mzn [3, 3, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[2, 3, 5, 6, 6, 6] [2, 3, 5, 6, 6, 6]>[3, 3, 4, 6, 6, 6] ---------- [3, 3, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 3, 5, 6, 6, 6] [1, 3, 5, 6, 6, 6]>[3, 3, 4, 6, 6, 6] ---------- [2, 2, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[2, 2, 4, 6, 6, 6] ---------- [2, 2, 3, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[2, 2, 3, 6, 6, 6] ---------- [3, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 3, 5, 6, 6, 6] [1, 3, 5, 6, 6, 6]>[3, 4, 4, 6, 6, 6] ---------- [3, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[2, 3, 5, 6, 6, 6] [2, 3, 5, 6, 6, 6]>[3, 4, 4, 6, 6, 6] ---------- [3, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[3, 3, 5, 6, 6, 6] [3, 3, 5, 6, 6, 6]>[3, 4, 4, 6, 6, 6] ---------- [2, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[2, 4, 4, 6, 6, 6] ---------- [1, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 1, 5, 6, 6, 6] [1, 1, 5, 6, 6, 6]>[1, 4, 4, 6, 6, 6] ---------- [2, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[2, 2, 5, 6, 6, 6] [2, 2, 5, 6, 6, 6]>[2, 4, 4, 6, 6, 6] ---------- [2, 3, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[2, 3, 4, 6, 6, 6] ---------- [ 9 more solutions ] [4, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[4, 4, 4, 6, 6, 6] ---------- [ 19 more solutions ] [2, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 3, 5, 6, 6, 6] [1, 3, 5, 6, 6, 6]>[2, 4, 4, 6, 6, 6] ---------- [ 39 more solutions ] [1, 5, 5, 5, 5, 6]<[1, 2, 2, 6, 6, 6] [1, 2, 2, 6, 6, 6]<[3, 4, 5, 5, 5, 6] [3, 4, 5, 5, 5, 6]>[1, 5, 5, 5, 5, 6] ---------- [ 79 more solutions ] [1, 2, 5, 6, 6, 6]<[2, 3, 3, 6, 6, 6] [2, 3, 3, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]>[1, 2, 5, 6, 6, 6] ---------- [ 159 more solutions ] [1, 1, 5, 5, 5, 6]<[2, 3, 3, 4, 6, 6] [2, 3, 3, 4, 6, 6]<[1, 4, 5, 5, 5, 5] [1, 4, 5, 5, 5, 5]>[1, 1, 5, 5, 5, 6] ---------- [ 319 more solutions ] [2, 2, 4, 4, 6, 6]<[4, 4, 4, 4, 4, 6] [4, 4, 4, 4, 4, 6]<[1, 2, 5, 5, 5, 5] [1, 2, 5, 5, 5, 5]>[2, 2, 4, 4, 6, 6] ---------- [ 639 more solutions ] [1, 2, 2, 2, 6, 6]<[2, 3, 3, 3, 3, 5] [2, 3, 3, 3, 3, 5]<[1, 1, 5, 5, 5, 5] [1, 1, 5, 5, 5, 5]>[1, 2, 2, 2, 6, 6] ---------- [ 1279 more solutions ] [1, 1, 2, 6, 6, 6]<[2, 3, 4, 5, 5, 6] [2, 3, 4, 5, 5, 6]<[1, 4, 5, 5, 5, 5] [1, 4, 5, 5, 5, 5]>[1, 1, 2, 6, 6, 6] ---------- [ 2559 more solutions ] [1, 1, 2, 6, 6, 6]<[3, 4, 4, 5, 5, 6] [3, 4, 4, 5, 5, 6]<[2, 5, 5, 5, 5, 5] [2, 5, 5, 5, 5, 5]>[1, 1, 2, 6, 6, 6] ---------- [ 5119 more solutions ] [3, 4, 4, 4, 4, 6]<[1, 3, 5, 5, 5, 5] [1, 3, 5, 5, 5, 5]<[2, 2, 2, 6, 6, 6] [2, 2, 2, 6, 6, 6]>[3, 4, 4, 4, 4, 6] ---------- [ 10239 more solutions ] [3, 3, 3, 3, 4, 5]<[1, 3, 3, 4, 4, 5] [1, 3, 3, 4, 4, 5]<[2, 2, 2, 5, 5, 6] [2, 2, 2, 5, 5, 6]>[3, 3, 3, 3, 4, 5] ---------- [ 20479 more solutions ] [2, 2, 3, 3, 3, 6]<[1, 1, 4, 4, 4, 5] [1, 1, 4, 4, 4, 5]<[1, 1, 1, 5, 5, 5] [1, 1, 1, 5, 5, 5]>[2, 2, 3, 3, 3, 6] ---------- [ 40959 more solutions ] [1, 1, 3, 3, 4, 4]<[1, 1, 1, 4, 6, 6] [1, 1, 1, 4, 6, 6]<[1, 2, 2, 3, 3, 6] [1, 2, 2, 3, 3, 6]>[1, 1, 3, 3, 4, 4] ---------- [ 40076 more solutions ] [2, 2, 2, 4, 5, 5]<[3, 3, 3, 3, 3, 4] [3, 3, 3, 3, 3, 4]<[2, 3, 3, 3, 4, 4] [2, 3, 3, 3, 4, 4]>[2, 2, 2, 4, 5, 5] ---------- ========== %%%mzn-stat: nodes=203916 %%%mzn-stat: failures=185337 %%%mzn-stat: restarts=0 %%%mzn-stat: variables=1658 %%%mzn-stat: intVars=126 %%%mzn-stat: boolVariables=1530 %%%mzn-stat: propagators=451 %%%mzn-stat: propagations=8595895 %%%mzn-stat: peakDepth=109 %%%mzn-stat: nogoods=185337 %%%mzn-stat: backjumps=18579 %%%mzn-stat: peakMem=0.00 %%%mzn-stat: time=11.444 %%%mzn-stat: initTime=0.010 %%%mzn-stat: solveTime=11.434 %%%mzn-stat: baseMem=0.00 %%%mzn-stat: trailMem=0.01 %%%mzn-stat: randomSeed=1599951938 Finished in 12s 600msec
- 3 die values=1..7
Compiling non_trans.mzn, additional arguments die=3; faces=6; values=1..7; Running non_trans.mzn [4, 4, 6, 7, 7, 7]<[4, 5, 5, 7, 7, 7] [4, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[4, 4, 6, 7, 7, 7] ---------- [3, 4, 6, 7, 7, 7]<[4, 5, 5, 7, 7, 7] [4, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[3, 4, 6, 7, 7, 7] ---------- [3, 3, 6, 7, 7, 7]<[3, 5, 5, 7, 7, 7] [3, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[3, 3, 6, 7, 7, 7] ---------- [3, 3, 6, 7, 7, 7]<[3, 4, 5, 7, 7, 7] [3, 4, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[3, 3, 6, 7, 7, 7] ---------- [3, 3, 6, 7, 7, 7]<[3, 4, 4, 7, 7, 7] [3, 4, 4, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[3, 3, 6, 7, 7, 7] ---------- [2, 3, 6, 7, 7, 7]<[3, 5, 5, 7, 7, 7] [3, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 3, 6, 7, 7, 7] ---------- [2, 4, 6, 7, 7, 7]<[4, 5, 5, 7, 7, 7] [4, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 4, 6, 7, 7, 7] ---------- [2, 2, 6, 7, 7, 7]<[2, 5, 5, 7, 7, 7] [2, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 2, 6, 7, 7, 7] ---------- [2, 3, 6, 7, 7, 7]<[3, 4, 5, 7, 7, 7] [3, 4, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 3, 6, 7, 7, 7] ---------- [2, 2, 6, 7, 7, 7]<[2, 4, 5, 7, 7, 7] [2, 4, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 2, 6, 7, 7, 7] ---------- [2, 3, 6, 7, 7, 7]<[3, 4, 4, 7, 7, 7] [3, 4, 4, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 3, 6, 7, 7, 7] ---------- [ 9 more solutions ] [1, 2, 6, 7, 7, 7]<[2, 3, 5, 7, 7, 7] [2, 3, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[1, 2, 6, 7, 7, 7] ---------- [ 19 more solutions ] [1, 1, 6, 7, 7, 7]<[2, 5, 5, 7, 7, 7] [2, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[1, 1, 6, 7, 7, 7] ---------- [ 39 more solutions ] [2, 2, 6, 7, 7, 7]<[4, 5, 5, 7, 7, 7] [4, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 2, 6, 7, 7, 7] ---------- [ 79 more solutions ] [5, 5, 5, 6, 7, 7]<[1, 6, 6, 6, 6, 7] [1, 6, 6, 6, 6, 7]<[1, 2, 6, 6, 7, 7] [1, 2, 6, 6, 7, 7]>[5, 5, 5, 6, 7, 7] ---------- [ 159 more solutions ] [1, 1, 6, 6, 6, 7]<[3, 3, 3, 4, 7, 7] [3, 3, 3, 4, 7, 7]<[1, 4, 6, 6, 6, 6] [1, 4, 6, 6, 6, 6]>[1, 1, 6, 6, 6, 7] ---------- [ 319 more solutions ] [3, 3, 4, 6, 6, 7]<[4, 4, 5, 5, 5, 7] [4, 4, 5, 5, 5, 7]<[1, 2, 6, 6, 6, 7] [1, 2, 6, 6, 6, 7]>[3, 3, 4, 6, 6, 7] ---------- [ 639 more solutions ] [2, 2, 2, 6, 6, 7]<[5, 5, 5, 5, 5, 7] [5, 5, 5, 5, 5, 7]<[1, 2, 6, 6, 6, 6] [1, 2, 6, 6, 6, 6]>[2, 2, 2, 6, 6, 7] ---------- [ 1279 more solutions ] [1, 2, 2, 6, 7, 7]<[4, 5, 5, 5, 5, 7] [4, 5, 5, 5, 5, 7]<[1, 1, 6, 6, 6, 6] [1, 1, 6, 6, 6, 6]>[1, 2, 2, 6, 7, 7] ---------- [ 2559 more solutions ] [3, 3, 3, 6, 7, 7]<[3, 4, 5, 5, 7, 7] [3, 4, 5, 5, 7, 7]<[2, 6, 6, 6, 6, 6] [2, 6, 6, 6, 6, 6]>[3, 3, 3, 6, 7, 7] ---------- [ 5119 more solutions ] [4, 4, 4, 5, 7, 7]<[5, 5, 5, 5, 5, 7] [5, 5, 5, 5, 5, 7]<[3, 4, 6, 6, 6, 6] [3, 4, 6, 6, 6, 6]>[4, 4, 4, 5, 7, 7] ---------- [ 10239 more solutions ] [3, 4, 5, 5, 7, 7]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[2, 2, 6, 6, 6, 6] [2, 2, 6, 6, 6, 6]>[3, 4, 5, 5, 7, 7] ---------- [ 20479 more solutions ] [1, 3, 3, 3, 7, 7]<[2, 4, 4, 5, 5, 6] [2, 4, 4, 5, 5, 6]<[1, 2, 4, 6, 6, 6] [1, 2, 4, 6, 6, 6]>[1, 3, 3, 3, 7, 7] ---------- [ 40959 more solutions ] [2, 3, 4, 4, 7, 7]<[3, 4, 4, 5, 5, 5] [3, 4, 4, 5, 5, 5]<[1, 1, 4, 5, 6, 7] [1, 1, 4, 5, 6, 7]>[2, 3, 4, 4, 7, 7] ---------- [ 81919 more solutions ] [2, 2, 2, 2, 7, 7]<[1, 3, 3, 3, 3, 5] [1, 3, 3, 3, 3, 5]<[1, 2, 2, 4, 6, 6] [1, 2, 2, 4, 6, 6]>[2, 2, 2, 2, 7, 7] ---------- [ 163839 more solutions ] [1, 1, 2, 7, 7, 7]<[2, 3, 4, 5, 5, 7] [2, 3, 4, 5, 5, 7]<[2, 3, 5, 5, 6, 6] [2, 3, 5, 5, 6, 6]>[1, 1, 2, 7, 7, 7] ---------- [ 327679 more solutions ] [1, 1, 4, 6, 7, 7]<[2, 2, 3, 5, 7, 7] [2, 2, 3, 5, 7, 7]<[3, 4, 4, 4, 5, 7] [3, 4, 4, 4, 5, 7]>[1, 1, 4, 6, 7, 7] ---------- [ 613827 more solutions ] [3, 3, 3, 4, 4, 5]<[2, 2, 3, 5, 6, 6] [2, 2, 3, 5, 6, 6]<[2, 2, 2, 5, 7, 7] [2, 2, 2, 5, 7, 7]>[3, 3, 3, 4, 4, 5] ---------- ========== %%%mzn-stat: nodes=1659193 %%%mzn-stat: failures=1573389 %%%mzn-stat: restarts=0 %%%mzn-stat: variables=1694 %%%mzn-stat: intVars=126 %%%mzn-stat: boolVariables=1566 %%%mzn-stat: propagators=451 %%%mzn-stat: propagations=54691502 %%%mzn-stat: peakDepth=109 %%%mzn-stat: nogoods=1573389 %%%mzn-stat: backjumps=85804 %%%mzn-stat: peakMem=0.00 %%%mzn-stat: time=128.215 %%%mzn-stat: initTime=0.010 %%%mzn-stat: solveTime=128.205 %%%mzn-stat: baseMem=0.00 %%%mzn-stat: trailMem=0.01 %%%mzn-stat: randomSeed=1599952012 Finished in 2m 9s
Nim
import std/[algorithm, sequtils, sets, strformat]
import itertools
type Die = object
name: string
faces: seq[int]
####################################################################################################
# Die functions.
func `$`(die: Die): string =
## Return the string representation of a Die.
&"({die.name}: {($die.faces)[1..^1]})"
func cmp(die1, die2: Die): int =
## Compare two dice returning 1, -1 or 0 for operators >, < ==.
var tot: array[3, int]
for d in product(die1.faces, die2.faces):
inc tot[1 + ord(d[1] < d[0]) - ord(d[0] < d[1])]
result = ord(tot[0] < tot[2]) - ord(tot[2] < tot[0])
func verboseCmp(die1, die2: Die): string =
## Compare two dice returning a string.
var win1, win2 = 0
for (d1, d2) in product(die1.faces, die2.faces):
inc win1, ord(d1 > d2)
inc win2, ord(d2 > d1)
result = if win1 > win2: &"{die1.name} > {die2.name}"
elif win1 < win2: &"{die1.name} < {die2.name}"
else: &"{die1.name} = {die2.name}"
func `>`(die1, die2: Die): bool = cmp(die1, die2) > 0
func `<=`(die1, die2: Die): bool = cmp(die1, die2) <= 0
####################################################################################################
# Added a permutation iterator as that of "itertools" doesn't allow to specify the length.
iterator permutations[T](values: openArray[T]; r: int): seq[T] {.closure} =
## Yield permutations of length "r" with elements taken from "values".
let n = values.len
if r > n: return
var indices = toSeq(0..<n)
var cycles = toSeq(countdown(n, n - r + 1))
var perm = values[0..<r]
yield perm
if n == 0: return
while true:
var exit = true
for i in countdown(r - 1, 0):
dec cycles[i]
if cycles[i] == 0:
discard indices.rotateLeft(i..indices.high, 1)
cycles[i] = n - i
else:
let j = cycles[i]
swap indices[i], indices[^j]
for iperm, ivalues in indices[0..<r]:
perm[iperm] = values[ivalues]
yield perm
exit = false
break
if exit: return
####################################################################################################
# Dice functions.
func isNonTrans(dice: openArray[Die]): bool =
## Return true if ordering of die in dice is non-transitive.
for i in 1..dice.high:
if dice[i] <= dice[i-1]: return false
result = dice[0] > dice[^1]
func findNonTrans(allDice: openArray[Die]; n = 3): seq[seq[Die]] =
## Return the list of non-transitive dice.
for perm in permutations(allDice, n):
if perm.isNontrans:
result.add perm
proc possibleDice(sides, maxval: Positive): seq[Die] =
## Return the list of possible dice with given number of sides and maximum value.
echo &"All possible 1..{maxval} {sides}-sided dice."
var dice: seq[Die]
var n = 1
for faces in product(toSeq(1..maxval), repeat = sides):
dice.add Die(name: &"D{n}", faces: faces)
inc n
echo &" Created {dice.len} dice."
echo " Remove duplicate with same bag of numbers on different faces."
var found: HashSet[seq[int]]
for d in dice:
let count = sorted(d.faces)
if count notin found:
found.incl count
result.add d
echo &" Return {result.len} filtered dice."
func verboseDiceCmp(dice: openArray[Die]): string =
## Return the verbose comparison of dice.
for i in 1..dice.high:
result.add verboseCmp(dice[i-1], dice[i]) & ", "
result.add verboseCmp(dice[0], dice[^1])
#———————————————————————————————————————————————————————————————————————————————————————————————————
when isMainModule:
let dice = possibleDice(sides = 4, maxval = 4)
for n in [3, 4]:
let nonTrans = dice.findNonTrans(n)
echo &"\n Non-transitive length-{n} combinations found: {nonTrans.len}."
for list in nonTrans:
echo ""
for i, die in list:
echo " ", if i == 0: '[' else: ' ', die, if i == list.high: "]" else: ","
if nonTrans.len != 0:
echo &"\n More verbose comparison of last non-transitive result:"
echo " ", verboseDiceCmp(nonTrans[^1])
echo "\n ===="
- 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. [(D16: [1, 1, 4, 4]), (D88: [2, 2, 2, 4]), (D43: [1, 3, 3, 3])] [(D43: [1, 3, 3, 3]), (D16: [1, 1, 4, 4]), (D88: [2, 2, 2, 4])] [(D88: [2, 2, 2, 4]), (D43: [1, 3, 3, 3]), (D16: [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. [(D16: [1, 1, 4, 4]), (D88: [2, 2, 2, 4]), (D91: [2, 2, 3, 3]), (D43: [1, 3, 3, 3])] [(D43: [1, 3, 3, 3]), (D16: [1, 1, 4, 4]), (D88: [2, 2, 2, 4]), (D91: [2, 2, 3, 3])] [(D88: [2, 2, 2, 4]), (D91: [2, 2, 3, 3]), (D43: [1, 3, 3, 3]), (D16: [1, 1, 4, 4])] [(D91: [2, 2, 3, 3]), (D43: [1, 3, 3, 3]), (D16: [1, 1, 4, 4]), (D88: [2, 2, 2, 4])] More verbose comparison of last non-transitive result: D91 < D43, D43 < D16, D16 < D88, D91 > D88 ====
Perl
use strict;
use warnings;
sub fourFaceCombs {
my %found = ();
my @res = ();
for (my $i = 1; $i <= 4; $i++) {
for (my $j = 1; $j <= 4; $j++) {
for (my $k = 1; $k <= 4; $k++) {
for (my $l = 1; $l <= 4; $l++) {
my @c = sort ($i, $j, $k, $l);
my $key = 0;
for my $p (@c) {
$key = 10 * $key + $p;
}
if (not exists $found{$key}) {
$found{$key} = 1;
push @res, \@c;
}
}
}
}
}
return @res;
}
sub compare {
my $xref = shift;
my $yref = shift;
my @x = @$xref;
my $xw = 0;
my @y = @$yref;
my $yw = 0;
for my $i (@x) {
for my $j (@y) {
if ($i < $j) {
$yw++;
}
if ($j < $i) {
$xw++;
}
}
}
if ($xw < $yw) {
return -1;
}
if ($yw < $xw) {
return 1;
}
return 0;
}
sub findIntransitive3 {
my $dice_ref = shift;
my @dice = @$dice_ref;
my $len = scalar @dice;
my @res = ();
for (my $i = 0; $i < $len; $i++) {
for (my $j = 0; $j < $len; $j++) {
my $first = compare($dice[$i], $dice[$j]);
if ($first == 1) {
for (my $k = 0; $k < $len; $k++) {
my $second = compare($dice[$j], $dice[$k]);
if ($second == 1) {
my $third = compare($dice[$k], $dice[$i]);
if ($third == 1) {
my $d1r = $dice[$i];
my $d2r = $dice[$j];
my $d3r = $dice[$k];
my @itd = ($d1r, $d2r, $d3r);
push @res, \@itd;
}
}
}
}
}
}
return @res;
}
sub findIntransitive4 {
my $dice_ref = shift;
my @dice = @$dice_ref;
my $len = scalar @dice;
my @res = ();
for (my $i = 0; $i < $len; $i++) {
for (my $j = 0; $j < $len; $j++) {
for (my $k = 0; $k < $len; $k++) {
for (my $l = 0; $l < $len; $l++) {
my $first = compare($dice[$i], $dice[$j]);
if ($first == 1) {
my $second = compare($dice[$j], $dice[$k]);
if ($second == 1) {
my $third = compare($dice[$k], $dice[$l]);
if ($third == 1) {
my $fourth = compare($dice[$l], $dice[$i]);
if ($fourth == 1) {
my $d1r = $dice[$i];
my $d2r = $dice[$j];
my $d3r = $dice[$k];
my $d4r = $dice[$l];
my @itd = ($d1r, $d2r, $d3r, $d4r);
push @res, \@itd;
}
}
}
}
}
}
}
}
return @res;
}
sub main {
my @dice = fourFaceCombs();
my $len = scalar @dice;
print "Number of eligible 4-faced dice: $len\n\n";
my @it3 = findIntransitive3(\@dice);
my $count3 = scalar @it3;
print "$count3 ordered lists of 3 non-transitive dice found, namely:\n";
for my $itref (@it3) {
print "[ ";
for my $r (@$itref) {
print "[@$r] ";
}
print "]\n";
}
print "\n";
my @it4 = findIntransitive4(\@dice);
my $count = scalar @it4;
print "$count ordered lists of 4 non-transitive dice found, namely:\n";
for my $itref (@it4) {
print "[ ";
for my $r (@$itref) {
print "[@$r] ";
}
print "]\n";
}
}
main();
- Output:
Number of eligible 4-faced dice: 35 3 ordered lists of 3 non-transitive dice found, namely: [ [1 1 4 4] [1 3 3 3] [2 2 2 4] ] [ [1 3 3 3] [2 2 2 4] [1 1 4 4] ] [ [2 2 2 4] [1 1 4 4] [1 3 3 3] ] 4 ordered lists of 4 non-transitive dice found, namely: [ [1 1 4 4] [1 3 3 3] [2 2 3 3] [2 2 2 4] ] [ [1 3 3 3] [2 2 3 3] [2 2 2 4] [1 1 4 4] ] [ [2 2 2 4] [1 1 4 4] [1 3 3 3] [2 2 3 3] ] [ [2 2 3 3] [2 2 2 4] [1 1 4 4] [1 3 3 3] ]
Phix
with javascript_semantics requires("0.8.2") -- (added sq_cmp() builtin that returns nested -1/0/+1 compare() results, just like the existing sq_eq() does for equal().) integer mx = 4, -- max number of a die side (later set to 6) mn = 1 -- min number of a die side (later set to 0) function possible_dice(integer sides) -- -- construct all non-descending permutes of mn..mx, -- ie/eg {1,1,1,1}..{4,4,4,4} with (say), amongst -- others, {1,1,2,4} but not {1,1,4,2}. -- sequence die = repeat(mn,sides), -- (main work area) res = {deep_copy(die)} while true do -- find rightmost incrementable side -- ie/eg {1,2,4,4} -> set rdx to 2 (if 1-based indexing) integer rdx = rfind(true,sq_lt(die,mx)) if rdx=0 then exit end if -- set that and all later to that incremented -- ie/eg {1,2,4,4} -> {1,3,3,3} die[rdx..$] = die[rdx]+1 res = append(res,deep_copy(die)) end while printf(1,"There are %d possible %d..%d %d-sided dice\n",{length(res),mn,mx,sides}) return res end function function Dnn(sequence die) -- reconstruct the python die numbering (string) -- essentially just treat it as a base-N number. integer l = length(die), -- (sides) N = mx-mn+1, -- (base) n = 0 -- (result) for k=1 to l do n += (die[k]-mn)*power(N,l-k) end for return sprintf("D%d",n+1) end function function cmpd(sequence die1, die2) -- compares two die returning -1, 0, or +1 for <, =, > integer res = 0 for i=1 to length(die1) do res += sum(sq_cmp(die1[i],die2)) end for return sign(res) end function function low_rotation(sequence set) integer k = find(min(set),set) return set[k..$]&set[1..k-1] end function integer rotations function find_non_trans(sequence dice, integer n=3) atom t1 = time()+1 integer l = length(dice), sk, sk1, c sequence set = repeat(1,n), -- (indexes to dice) cache = repeat(repeat(-2,l),l), res = {} while true do bool valid = true for k=1 to n-1 do sk = set[k] sk1 = set[k+1] c = cache[sk][sk1] if c=-2 then c = cmpd(dice[sk],dice[sk1]) cache[sk][sk1] = c end if if c!=-1 then valid = false -- force k+1 to be incremented next: set[k+2..$] = l exit end if end for if valid then sk = set[1] sk1 = set[$] c = cache[sk][sk1] if c=-2 then c = cmpd(dice[sk],dice[sk1]) cache[sk][sk1] = c end if if c=+1 then res = append(res,low_rotation(set)) end if end if -- find rightmost incrementable die index -- ie/eg if l is 35 and set is {1,2,35,35} -- -> set rdx to 2 (if 1-based indexing) integer rdx = rfind(true,sq_lt(set,l)) if rdx=0 then exit end if -- increment that and reset all later -- ie/eg {1,2,35,35} -> {1,3,1,1} set[rdx] += 1 set[rdx+1..$] = 1 if time()>t1 and platform()!=JS then progress("working... (%d/%d)\r",{set[1],l}) t1 = time()+1 end if end while if platform()!=JS then progress("") end if rotations = length(res) res = unique(res) rotations -= length(res) return res end function function verbose_cmp(sequence die1, die2) -- compares two die returning their relationship of their names as a string integer c = cmpd(die1,die2) string op = {"<","=",">"}[c+2], n1 = Dnn(die1), n2 = Dnn(die2) return sprintf("%s %s %s",{n1,op,n2}) end function function verbose_dice_cmp(sequence dice, set) sequence c = {}, d1, d2 for j=1 to length(set)-1 do d1 = dice[set[j]] d2 = dice[set[j+1]] c = append(c,verbose_cmp(d1,d2)) end for d1 = dice[set[1]] d2 = dice[set[$]] c = append(c,verbose_cmp(d1,d2)) return join(c,", ") end function procedure show_dice(sequence dice, non_trans, integer N) integer l = length(non_trans), omissions = 0, last = 0 if N then printf(1,"\n Non_transitive length-%d combinations found: %d\n",{N,l+rotations}) end if for i=1 to l do object ni = non_trans[i] if sequence(ni) then if i<5 then printf(1,"\n") for j=1 to length(ni) do sequence d = dice[ni[j]] printf(1," %s:%v\n",{Dnn(d),d}) end for last = i else omissions += 1 end if end if end for if omissions then printf(1," (%d omitted)\n",omissions) end if if rotations then printf(1," (%d rotations omitted)\n",rotations) end if if last then printf(1,"\n") if mx<=6 and mn=1 then printf(1," More verbose comparison of last result:\n") end if printf(1," %s\n",{verbose_dice_cmp(dice,non_trans[last])}) printf(1,"\n ====\n") end if printf(1,"\n") end procedure atom t0 = time() sequence dice = possible_dice(4) for N=3 to 4 do show_dice(dice,find_non_trans(dice,N),N) end for -- From the numberphile video (Efron's dice): mx = 6 mn = 0 dice = possible_dice(6) --show_dice(dice,find_non_trans(dice,4),4) -- ok, dunno about you but I'm not waiting for power(924,4) permutes... -- limit to the ones discussed, plus another 4 random ones -- (hopefully it'll just pick out the right ones...) printf(1,"\nEfron's dice\n") dice = {{0,0,4,4,4,4}, {1,1,1,1,1,1}, -- (rand) {1,1,1,5,5,5}, {1,2,3,4,5,6}, -- (rand) {2,2,2,2,6,6}, {5,5,5,6,6,6}, -- (rand) {3,3,3,3,3,3}, {6,6,6,6,6,6}} -- (rand) show_dice(dice,find_non_trans(dice,4),0) -- and from wp: mx = 9 mn = 1 dice = possible_dice(6) printf(1,"\nFrom wp\n") dice = {{1,1,6,6,8,8}, {2,2,4,4,9,9}, {3,3,5,5,7,7}} show_dice(dice,find_non_trans(dice,3),0) -- Miwin's dice printf(1,"Miwin's dice\n") dice = {{1,2,5,6,7,9}, {1,3,4,5,8,9}, {2,3,4,6,7,8}} show_dice(dice,find_non_trans(dice,3),0) printf(1,"%s\n\n",elapsed(time()-t0))
- Output:
There are 35 possible 1..4 4-sided dice Non_transitive length-3 combinations found: 3 D16:{1,1,4,4} D88:{2,2,2,4} D43:{1,3,3,3} (2 rotations omitted) More verbose comparison of last result: D16 < D88, D88 < D43, D16 > D43 ==== Non_transitive length-4 combinations found: 4 D16:{1,1,4,4} D88:{2,2,2,4} D91:{2,2,3,3} D43:{1,3,3,3} (3 rotations omitted) More verbose comparison of last result: D16 < D88, D88 < D91, D91 < D43, D16 > D43 ==== There are 924 possible 0..6 6-sided dice Efron's dice D1601:{0,0,4,4,4,4} D19837:{1,1,1,5,5,5} D39249:{2,2,2,2,6,6} D58825:{3,3,3,3,3,3} (3 rotations omitted) D1601 < D19837, D19837 < D39249, D39249 < D58825, D1601 > D58825 ==== There are 3003 possible 1..9 6-sided dice From wp D4121:{1,1,6,6,8,8} D68121:{2,2,4,4,9,9} D134521:{3,3,5,5,7,7} (2 rotations omitted) D4121 < D68121, D68121 < D134521, D4121 > D134521 ==== Miwin's dice D9945:{1,2,5,6,7,9} D74825:{2,3,4,6,7,8} D15705:{1,3,4,5,8,9} (2 rotations omitted) D9945 < D74825, D74825 < D15705, D9945 > D15705 ==== "0.3s"
Stretch: length-3 combinations of 6-sided dice
With the recent optimisations I can just about stretch to power(924,3), but I think I was right to skip power(924,4) above, it would probably take over two and a half days.
I have also estimated that power(3003,3) (ie 1..9 on the sides) would probably take around 4 hours (assuming such attempts didn't run out of memory).
t0 = time() mx = 6 mn = 1 dice = possible_dice(6) show_dice(dice,find_non_trans(dice,3),3) printf(1,"%s\n\n",elapsed(time()-t0)) t0 = time() mx = 6 mn = 0 dice = possible_dice(6) show_dice(dice,find_non_trans(dice,3),3) printf(1,"%s\n\n",elapsed(time()-t0))
- Output:
There are 462 possible 1..6 6-sided dice Non_transitive length-3 combinations found: 121998 D58:{1,1,1,2,4,4} D262:{1,1,2,2,2,4} D88:{1,1,1,3,3,4} D58:{1,1,1,2,4,4} D1556:{1,2,2,2,2,2} D87:{1,1,1,3,3,3} D58:{1,1,1,2,4,4} D1556:{1,2,2,2,2,2} D88:{1,1,1,3,3,4} D58:{1,1,1,2,4,4} D1557:{1,2,2,2,2,3} D88:{1,1,1,3,3,4} (40662 omitted) (81332 rotations omitted) More verbose comparison of last result: D58 < D1557, D1557 < D88, D58 > D88 ==== "30.9s" There are 924 possible 0..6 6-sided dice Non_transitive length-3 combinations found: 1269189 D74:{0,0,0,1,3,3} D403:{0,0,1,1,1,3} D116:{0,0,0,2,2,3} D74:{0,0,0,1,3,3} D2802:{0,1,1,1,1,1} D115:{0,0,0,2,2,2} D74:{0,0,0,1,3,3} D2802:{0,1,1,1,1,1} D116:{0,0,0,2,2,3} D74:{0,0,0,1,3,3} D2803:{0,1,1,1,1,2} D116:{0,0,0,2,2,3} (423059 omitted) (846126 rotations omitted) D74 < D2803, D2803 < D116, D74 > D116 ==== "3 minutes and 60s"
Python
Trivial rotations of the same loop are not shown.
from itertools import combinations_with_replacement as cmbr
from time import time
def dice_gen(n, faces, m):
dice = list(cmbr(faces, n))
succ = [set(j for j, b in enumerate(dice)
if sum((x>y) - (x<y) for x in a for y in b) > 0)
for a in dice]
def loops(seq):
s = succ[seq[-1]]
if len(seq) == m:
if seq[0] in s: yield seq
return
for d in (x for x in s if x > seq[0] and not x in seq):
yield from loops(seq + (d,))
yield from (tuple(''.join(dice[s]) for s in x)
for i, v in enumerate(succ)
for x in loops((i,)))
t = time()
for n, faces, loop_len in [(4, '1234', 3), (4, '1234', 4), (6, '123456', 3), (6, '1234567', 3)]:
for i, x in enumerate(dice_gen(n, faces, loop_len)): pass
print(f'{n}-sided, markings {faces}, loop length {loop_len}:')
print(f'\t{i + 1}*{loop_len} solutions, e.g. {" > ".join(x)} > [loop]')
t, t0 = time(), t
print(f'\ttime: {t - t0:.4f} seconds\n')
- Output:
4-sided, markings 1234, loop length 3: 1*3 solutions, e.g. 1144 > 1333 > 2224 > [loop] time: 0.0000 seconds 4-sided, markings 1234, loop length 4: 1*4 solutions, e.g. 1144 > 1333 > 2233 > 2224 > [loop] time: 0.0100 seconds 6-sided, markings 123456, loop length 3: 40666*3 solutions, e.g. 335666 > 555556 > 444666 > [loop] time: 1.1459 seconds 6-sided, markings 1234567, loop length 3: 423063*3 solutions, e.g. 446777 > 666667 > 555777 > [loop] time: 6.9465 seconds
Alternative
from collections import namedtuple
from itertools import permutations, product
from functools import lru_cache
Die = namedtuple('Die', 'name, faces')
@lru_cache(maxsize=None)
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(d.faces))
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 ====')
- 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 ====
- Caching information
In [45]: cmpd.cache_info() Out[45]: CacheInfo(hits=2148761, misses=1190, maxsize=None, currsize=1190)
R
It would not be difficult to adapt this code to meet the stretch goal, but readability would suffer.
findNonTrans <- function()
{
diceSet <- unique(t(apply(expand.grid(1:4, 1:4, 1:4, 1:4), 1, sort))) #By construction, each row is a unique dice.
winningDice <- function(X, Y) #Recall 'Example 1' in the task.
{
comparisonTable <- data.frame(X = rep(X, each = length(X)), Y = rep(Y, times = length(Y)))
rowWinner <- ifelse(comparisonTable["X"] > comparisonTable["Y"], "X",
ifelse(comparisonTable["X"] == comparisonTable["Y"], "-", "Y"))
netXWins <- sum(rowWinner == "X") - sum(rowWinner == "Y")
if(netXWins > 0) "X" else if(netXWins == 0) "Draw" else "Y"
}
rows <- seq_len(nrow(diceSet)) #Recall that each row of diceSet is a dice.
XvsAllY <- function(X) sapply(rows, function(i) winningDice(X, diceSet[i, ]))
winners <- as.data.frame(lapply(rows, function(i) XvsAllY(diceSet[i, ])),
row.names = paste("Y=Dice", rows), col.names = paste("X=Dice", rows), check.names = FALSE)
solutionCount <- 0
for(S in rows)
{
beatsS <- which(winners[paste("X=Dice", S)] == "Y") #Finds the indices of all T such that S<T.
beatsT <- lapply(beatsS, function(X) which(winners[paste("X=Dice", X)] == "Y")) #To begin finding U such that T<U.
beatenByS <- which(winners[paste("X=Dice", S)] == "X") #Finds the indices of all U such that S>U.
potentialU <- lapply(beatsT, function(X) intersect(X, beatenByS)) #Combining previous two lines.
nonEmptyIndices <- lengths(potentialU) != 0 #Most of potentialU is usually empty lists.
if(any(nonEmptyIndices)) #If any lists in potentialU are non-empty, then their entry is the index of a U with S>U & T<U.
{
solutionCount <- solutionCount + 1
diceUIndex <- potentialU[nonEmptyIndices][[1]] #Assumes that there is only one valid U for this S.
diceTIndex <- beatsS[nonEmptyIndices][[1]] #Finds the T corresponding to the chosen U.
cat("Solution", solutionCount, "is:\n")
output <- rbind(S = diceSet[S,], T = diceSet[diceTIndex,], U = diceSet[diceUIndex,])
colnames(output) <- paste("Dice", 1:4)
print(output)
}
}
}
findNonTrans()
- Output:
Solution 1 is: Dice 1 Dice 2 Dice 3 Dice 4 S 1 1 4 4 T 2 2 2 4 U 1 3 3 3 Solution 2 is: Dice 1 Dice 2 Dice 3 Dice 4 S 1 3 3 3 T 1 1 4 4 U 2 2 2 4 Solution 3 is: Dice 1 Dice 2 Dice 3 Dice 4 S 2 2 2 4 T 1 3 3 3 U 1 1 4 4
Raku
Thanks to Thundergnat for the nice "less-is-more" tweaks now the 4 dice portion takes around 10 (down from 17 ) minutes to run ..
# 20201225 Raku programming solution
my @dicepool = ^4 xx 4 ;
sub FaceCombs(\N, @dp) { # for brevity, changed to use 0-based dice on input
my @res = my @found = [];
for [X] @dp {
unless @found[ my \key = [+] ( N «**« (N-1…0) ) Z* .sort ] {
@found[key] = True;
@res.push: $_ »+» 1
}
}
@res
}
sub infix:<⚖️>(@x, @y) { +($_{Less} <=> $_{More}) given (@x X<=> @y).Bag }
sub findIntransitive(\N, \cs) {
my @res = [];
race for [X] ^+cs xx N -> @lot {
my $skip = False;
for @lot.rotor(2 => -1) {
{ $skip = True and last } unless cs[ @_[0] ] ⚖️ cs[ @_[1] ] == -1
}
next if $skip;
if cs[ @lot[0] ] ⚖️ cs[ @lot[*-1] ] == 1 { @res.push: [ cs[ @lot ] ] }
}
@res
}
say "Number of eligible 4-faced dice : ", +(my \combs = FaceCombs(4,@dicepool));
for 3, 4 {
my @output = findIntransitive($_, combs);
say +@output, " ordered lists of $_ non-transitive dice found, namely:";
.say for @output;
}
- 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)]
Wren
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"))
- 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]]