Non-transitive dice: Difference between revisions
→{{header|Phix}}: omit rotations, stretch, progress
(→{{header|F_Sharp|F#}}: added extra credit) |
(→{{header|Phix}}: omit rotations, stretch, progress) |
||
Line 315:
integer l = length(die), -- (sides)
N = mx-mn+1, -- (base)
n =
for k=1 to l do
n += (die[k]-mn)*power(N,l-k)
end for
return sprintf("D%d",n+1)
end function
Line 331:
end function
integer lp = 0 -- (last progress length, to be wiped out)
procedure progress(string msg, sequence args = {})
if length(args) then msg = sprintf(msg,args) end if
integer lm = length(msg)
if lm=0 then
puts(1,repeat(' ',lp))
lp = 0
else
if lm<lp then msg[$..$] = repeat(' ',lp-lm)&msg[$] end if
puts(1,msg)
lp = iff(msg[$]='\r'?lm:0)
end if
end procedure
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)
Line 348 ⟶ 364:
if c!=-1 then
valid = false
-- force k+1 to be incremented next:
set[k+2..$] = l
exit
Line 361 ⟶ 378:
end if
if c=+1 then
res = append(res,sort(set))
end if
end if
-- find rightmost incrementable die index
-- ie/eg
-- -> 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,
set[rdx] += 1
set[rdx+1..$] = 1
if time()>t1 then
progress("working... (%d/%d)\r",{set[1],l})
t1 = time()+1
end if
end while
progress("")
rotations = length(res)
res = unique(res)
rotations -= length(res)
return res
end function
Line 399 ⟶ 425:
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
printf(1,"
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
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<=
printf(1," More verbose comparison of last
end if
printf(1," %s\n",{verbose_dice_cmp(dice,non_trans[
printf(1,"\n ====\n")
end if
Line 430 ⟶ 472:
mn = 0
dice = possible_dice(6)
--show_dice(dice,find_non_trans(dice,6),6)
-- ok, dunno about you but I'm not waiting for power(924,6) 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 = {{
{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)
Line 450 ⟶ 493:
dice = possible_dice(6)
printf(1,"\nFrom wp\n")
dice = {{
{
{3,3,5,5,7,7}}
Line 470 ⟶ 513:
D16:{1,1,4,4}
D43:{1,3,3,3}
D88:{2,2,2,4}
(2 rotations omitted)
More verbose comparison of last result:
D16 > D43
====
Line 490 ⟶ 526:
D16:{1,1,4,4}
D43:{1,3,3,3}
D88:{2,2,2,4}
D91:{2,2,3,3}
(3 rotations omitted)
More verbose comparison of last result:
D16 > D43, D43 > D88, D88 < D91, D16 = D91
====
Line 517 ⟶ 539:
Efron's dice
D1601:{0,0,4,4,4,4}
Line 527 ⟶ 544:
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
====
Line 545 ⟶ 553:
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
====
Line 565 ⟶ 566:
D9945:{1,2,5,6,7,9}
D15705:{1,3,4,5,8,9}
D74825:{2,3,4,6,7,8}
(2 rotations omitted)
D9945 > D15705, D15705 > D74825
====
</pre>
=== Stretch: length-3 combinations of six 6-sided dice ===
Actually, given recent optimisations and that this power(462,6) takes about 30s, the previously dismissed power(924,6) is probably doable, and maybe even power(3003,6)...
<lang Phix>mx = 6
mn = 1
dice = possible_dice(6)
show_dice(dice,find_non_trans(dice,3),3)</lang>
{{out}}
<pre>
There are 462 possible 1..6 6-sided dice
Non_transitive length-3 combinations found: 121998
D58:{1,1,1,2,4,4}
D87:{1,1,1,3,3,3}
D1556:{1,2,2,2,2,2}
D58:{1,1,1,2,4,4}
D88:{1,1,1,3,3,4}
D262:{1,1,2,2,2,4}
D58:{1,1,1,2,4,4}
D88:{1,1,1,3,3,4}
D1556:{1,2,2,2,2,2}
D58:{1,1,1,2,4,4}
D88:{1,1,1,3,3,4}
D1557:{1,2,2,2,2,3}
(40662 omitted)
(81332 rotations omitted)
More verbose comparison of last result:
D58 > D88, D88 > D1557, D58 < D1557
====
|