Anonymous user
Non-transitive dice: Difference between revisions
→{{header|Nim}}
m (→{{header|Raku}}: update timing and make insignificant changes) |
|||
Line 736:
Finished in 2m 9s
</pre>
=={{header|Nim}}==
{{trans|Python}}
{{libheader|itertools}}
<lang Nim>
import 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 die 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 tow die 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 ===="</lang>
{{out}}
<pre>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
====</pre>
=={{header|Phix}}==
| |||