Non-transitive dice: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Haskell}}: fixed typos) |
m (→{{header|Wren}}: Minor tidy) |
||
| (16 intermediate revisions by 7 users not shown) | |||
Line 85:
<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|F_Sharp|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]]
Line 95 ⟶ 200:
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)</
{{out}}
<pre>
Line 111 ⟶ 216:
===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]]
Line 117 ⟶ 222:
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
</syntaxhighlight>
{{out}}
<pre>
Line 125 ⟶ 230:
</pre>
;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]]
Line 131 ⟶ 236:
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
</syntaxhighlight>
{{out}}
<pre>
Line 140 ⟶ 245:
=={{header|Factor}}==
<
prettyprint sequences ;
Line 164 ⟶ 269:
"All ordered lists of 4 non-transitive dice with 4 sides:" print
4 4 find-non-transitive .</
{{out}}
<pre>
Line 187 ⟶ 292:
=={{header|Go}}==
{{trans|Wren}}
<
import (
Line 294 ⟶ 399:
fmt.Println(a)
}
}</
{{out}}
Line 314 ⟶ 419:
=={{header|Haskell}}==
<
import Data.List
import Control.Monad
Line 340 ⟶ 445:
(a:as) <- go (n-1)
b <- filter (< a) dice
return (b:a:as)</
<pre>*Main> mapM_ print $ nonTrans (dices 4) 3
Line 358 ⟶ 463:
*Main> length $ nonTrans (dices 5) 3
2022</pre>
=={{header|J}}==
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 }}
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
}}</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.
Task examples:
<syntaxhighlight lang="j"> 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</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.util.HashSet;
import java.util.List;
Line 466 ⟶ 604:
}
}
}</
{{out}}
<pre>Number of eligible 4-faced dice: 35
Line 483 ⟶ 621:
=={{header|Julia}}==
{{trans|Python}}
<
using Memoize, Combinatorics
Line 559 ⟶ 697:
@time testnontransitivedice(5)
@time testnontransitivedice(6)
</
<pre>
All possible 1..3 3-sided dice
Line 641 ⟶ 779:
=={{header|Kotlin}}==
{{trans|Go}}
<
val res = mutableListOf<Array<Int>>()
val found = mutableSetOf<Int>()
Line 742 ⟶ 880:
println(a.joinToString(", ", "[", "]") { it.joinToString(", ", "[", "]") })
}
}</
{{out}}
<pre>Number of eligible 4-faced dice: 35
Line 756 ⟶ 894:
[[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|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}}==
===The model===
<syntaxhighlight lang="minizinc">
%Non transitive dice. Nigel Galloway, September 14th., 2020
int: die; int: faces; set of int: values;
Line 769 ⟶ 947:
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])];
</syntaxhighlight>
===The task(4 sided die)===
;3 die values=1..4
Line 1,027 ⟶ 1,205:
{{trans|Python}}
{{libheader|itertools}}
<syntaxhighlight lang="nim">
import std/[algorithm, sequtils, sets, strformat]
import itertools
Line 1,046 ⟶ 1,224:
func cmp(die1, die2: Die): int =
## Compare two
var tot: array[3, int]
for d in product(die1.faces, die2.faces):
Line 1,054 ⟶ 1,232:
func verboseCmp(die1, die2: Die): string =
## Compare
var win1, win2 = 0
for (d1, d2) in product(die1.faces, die2.faces):
Line 1,159 ⟶ 1,337:
echo &"\n More verbose comparison of last non-transitive result:"
echo " ", verboseDiceCmp(nonTrans[^1])
echo "\n ===="</
{{out}}
Line 1,215 ⟶ 1,393:
=={{header|Perl}}==
{{trans|Go}}
<
use warnings;
Line 1,364 ⟶ 1,542:
}
main();</
{{out}}
<pre>Number of eligible 4-faced dice: 35
Line 1,380 ⟶ 1,558:
=={{header|Phix}}==
<!--<
<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>
Line 1,600 ⟶ 1,778:
<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>
<!--</
{{out}}
<pre>
Line 1,674 ⟶ 1,852:
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).
<!--<
<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>
Line 1,688 ⟶ 1,866:
<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>
<!--</
{{out}}
<pre>
Line 1,750 ⟶ 1,928:
=={{header|Python}}==
Trivial rotations of the same loop are not shown.
<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 functools import lru_cache
Line 1,824 ⟶ 2,053:
print('\n More verbose comparison of last non_transitive result:')
print(' ', verbose_dice_cmp(non_trans[-1]))
print('\n ====')</
{{out}}
Line 1,885 ⟶ 2,114:
=={{header|R}}==
It would not be difficult to adapt this code to meet the stretch goal, but readability would suffer.
<
{
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,920 ⟶ 2,149:
}
}
findNonTrans()</
{{out}}
Line 1,942 ⟶ 2,171:
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}}
<syntaxhighlight lang="raku"
my @dicepool = ^4 xx 4 ;
Line 1,977 ⟶ 2,206:
say +@output, " ordered lists of $_ non-transitive dice found, namely:";
.say for @output;
}</
{{out}}
<pre>Number of eligible 4-faced dice : 35
Line 1,992 ⟶ 2,221:
=={{header|Wren}}==
{{libheader|Wren-sort}}
<
var fourFaceCombs = Fn.new {
Line 2,082 ⟶ 2,311:
it = findIntransitive4.call(combs)
System.print("\n%(it.count) ordered lists of 4 non-transitive dice found, namely:")
System.print(it.join("\n"))</
{{out}}
| |||