Dominoes: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: rearrange) |
(Created Nim solution.) |
||
Line 319: | Line 319: | ||
Possible flip configurations: 268435456 |
Possible flip configurations: 268435456 |
||
Possible permuted arrangements with flips: 105797996085635281181632579889767907328000000</pre> |
Possible permuted arrangements with flips: 105797996085635281181632579889767907328000000</pre> |
||
=={{header|Nim}}== |
|||
{{trans|Wren}} |
|||
<syntaxhighlight lang="Nim">import std/[monotimes, sequtils, strformat, strutils, times] |
|||
const |
|||
None = -1 |
|||
NoPosition = (None, None) |
|||
type |
|||
Value = None..6 |
|||
Domino = (Value, Value) |
|||
Position = (int, int) |
|||
Tableau = array[7, array[8, Value]] |
|||
Pattern = (seq[seq[Value]], seq[Domino], seq[Position]) |
|||
const |
|||
Tableau1 = [[Value 0, 5, 1, 3, 2, 2, 3, 1], |
|||
[Value 0, 5, 5, 0, 5, 2, 4, 6], |
|||
[Value 4, 3, 0, 3, 6, 6, 2, 0], |
|||
[Value 0, 6, 2, 3, 5, 1, 2, 6], |
|||
[Value 1, 1, 3, 0, 0, 2, 4, 5], |
|||
[Value 2, 1, 4, 3, 3, 4, 6, 6], |
|||
[Value 6, 4, 5, 1, 5, 4, 1, 4]] |
|||
Tableau2 = [[Value 6, 4, 2, 2, 0, 6, 5, 0], |
|||
[Value 1, 6, 2, 3, 4, 1, 4, 3], |
|||
[Value 2, 1, 0, 2, 3, 5, 5, 1], |
|||
[Value 1, 3, 5, 0, 5, 6, 1, 0], |
|||
[Value 4, 2, 6, 0, 4, 0, 1, 1], |
|||
[Value 4, 4, 2, 0, 5, 3, 6, 3], |
|||
[Value 6, 6, 5, 2, 5, 3, 3, 4]] |
|||
func domino(v1, v2: Value): Domino = |
|||
if v1 > v2: (v2, v1) else: (v1, v2) |
|||
func findLayouts(tab: Tableau; domCount: Positive): seq[Pattern] = |
|||
let nrows = tab.len |
|||
let ncols = tab[0].len |
|||
var m = newSeqWith(nrows, repeat(Value None, ncols)) |
|||
result = @[(m, newSeq[Domino](), newSeq[Position]())] |
|||
while true: |
|||
var newpats: seq[Pattern] |
|||
for pat in result: |
|||
let (ut, ud, up) = pat |
|||
var pos = NoPosition |
|||
block Outer: |
|||
for j in 0..<ncols: |
|||
for i in 0..<nrows: |
|||
if ut[i][j] == None: |
|||
pos = (i, j) |
|||
break Outer |
|||
if pos == NoPosition: |
|||
continue |
|||
let (row , col) = pos |
|||
if row < nrows - 1 and ut[row+1][col] == None: |
|||
let dom = domino(tab[row][col], tab[row+1][col]) |
|||
if dom notin ud: |
|||
var newUt = ut |
|||
newut[row][col] = tab[row][col] |
|||
newut[row+1][col] = tab[row+1][col] |
|||
newpats.add (newut, |
|||
ud & domino(tab[row][col], tab[row+1][col]), |
|||
up & @[(row, col), (row+1, col)]) |
|||
if col < ncols - 1 and ut[row][col+1] == None: |
|||
let dom = domino(tab[row][col], tab[row][col+1]) |
|||
if dom notin ud: |
|||
var newUt = ut |
|||
newut[row][col] = tab[row][col] |
|||
newut[row][col+1] = tab[row][col+1] |
|||
newpats.add (newut, |
|||
ud & domino(tab[row][col], tab[row][col+1]), |
|||
up & @[(row, col), (row, col+1)]) |
|||
if newPats.len == 0: break |
|||
result = move(newPats) |
|||
if result[0][2].len == domCount: |
|||
break |
|||
proc printLayout(pattern: Pattern) = |
|||
let (tab, _, pos) = pattern |
|||
var output = newSeqWith(2 * tab.len, repeat(' ', tab[0].len * 2 - 1)) |
|||
var idx = 0 |
|||
while idx < pos.len - 1: |
|||
let |
|||
(x1, y1) = pos[idx] |
|||
(x2, y2) = pos[idx+1] |
|||
let |
|||
n1 = tab[x1][y1] |
|||
n2 = tab[x2][y2] |
|||
output[x1*2][y1*2] = chr(48 + n1) |
|||
output[x2*2][y2*2] = chr(48 + n2) |
|||
if x1 == x2: |
|||
output[x1*2][y1*2+1] = '+' |
|||
elif y1 == y2: |
|||
output[x1*2+1][y1*2] = '+' |
|||
inc idx, 2 |
|||
for i in 0..output.high: |
|||
echo output[i] |
|||
var domCount: Positive |
|||
for j in 0..Tableau1[0].high: |
|||
for i in 0..Tableau1.high: |
|||
if i <= j: |
|||
inc domCount |
|||
for t in [Tableau1, Tableau2]: |
|||
let start = getMonoTime() |
|||
let lays = t.findLayouts(domCount) |
|||
lays[0].printLayout() |
|||
let lc = lays.len |
|||
let pl = if lc > 1: "s" else: "" |
|||
let fo = if lc > 1: " (first one shown)" else: "" |
|||
echo &"{lc} layout{pl} found{fo}." |
|||
echo &"Took {(getMonoTime() - start).inMilliseconds} ms.\n" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0+5 1+3 2 2+3 1 |
|||
+ + |
|||
0 5+5 0 5 2+4 6 |
|||
+ + |
|||
4 3 0 3 6+6 2 0 |
|||
+ + + + |
|||
0 6 2 3+5 1 2 6 |
|||
+ + |
|||
1 1 3 0+0 2 4 5 |
|||
+ + + + |
|||
2 1 4 3+3 4 6 6 |
|||
+ + |
|||
6 4+5 1+5 4 1+4 |
|||
1 layout found. |
|||
Took 1 ms. |
|||
6 4 2 2 0 6+5 0 |
|||
+ + + + + + |
|||
1 6 2 3 4 1+4 3 |
|||
2 1 0 2 3+5 5 1 |
|||
+ + + + + + |
|||
1 3 5 0 5 6 1 0 |
|||
+ + |
|||
4 2 6 0 4 0 1+1 |
|||
+ + + + |
|||
4 4 2 0 5 3 6 3 |
|||
+ + + + |
|||
6+6 5+2 5 3 3 4 |
|||
2025 layouts found (first one shown). |
|||
Took 42 ms. |
|||
</pre> |
|||
===Extra credit task === |
|||
{{trans|Wren}} |
|||
{{libheader|Nim-Integers}} |
|||
<syntaxhighlight lang="Nim">import std/[math, monotimes, strutils, times] |
|||
import integers |
|||
func dominoTilingCount(m, n: Positive): int = |
|||
var prod = 1.0 |
|||
for j in 1..((m + 1) div 2): |
|||
for k in 1..((n + 1) div 2): |
|||
let cm = cos(PI * (j / (m + 1))) |
|||
let cn = cos(PI * (k / (n + 1))) |
|||
prod *= (cm * cm + cn * cn) * 4 |
|||
result = int(prod) |
|||
let |
|||
start = getMonoTime() |
|||
arrang = dominoTilingCount(7, 8) |
|||
perms = factorial(28) |
|||
flips = 1 shl 28 |
|||
echo "Arrangements ignoring values: ", insertSep($arrang) |
|||
echo "Permutations of 28 dominos: ", insertSep($perms) |
|||
echo "Permuted arrangements ignoring flipping dominos: ", insertSep($(perms * arrang)) |
|||
echo "Possible flip configurations: ", insertSep($flips) |
|||
echo "Possible permuted arrangements with flips: ", insertSep($(perms * flips * arrang)) |
|||
echo "\nTook $# µs.".format((getMonoTime() - start).inMicroseconds) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Arrangements ignoring values: 1_292_697 |
|||
Permutations of 28 dominos: 304_888_344_611_713_860_501_504_000_000 |
|||
Permuted arrangements ignoring flipping dominos: 394_128_248_414_528_672_328_712_716_288_000_000 |
|||
Possible flip configurations: 268_435_456 |
|||
Possible permuted arrangements with flips: 105_797_996_085_635_281_181_632_579_889_767_907_328_000_000 |
|||
Took 107 µs. |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |