Dominoes: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: rearrange) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
{{task|Games}}
Warning: If you are looking for pizza delivery you have come to the wrong page. Bloody Google (other search engines are available).
Line 319:
Possible flip configurations: 268435456
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}}==
Line 775 ⟶ 967:
{{trans|Julia}}
===Basic task===
<syntaxhighlight lang="
[0, 5, 1, 3, 2, 2, 3, 1],
[0, 5, 5, 0, 5, 2, 4, 6],
Line 952 ⟶ 1,144:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
Line 992 ⟶ 1,184:
{{libheader|Wren-gmp}}
This is just to give what will probably be a rare outing to the Mpf class though (despite their usage in the Julia example) we don't need 'big floats' here, just 'big ints'. Slightly slower than the Wren-cli example as a result.
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||