Anonymous user
Nonogram solver: Difference between revisions
→{{header|Nim}}
Thundergnat (talk | contribs) (alphabetize, minor clean-up) |
|||
Line 2,128:
. . . . . . . . . . . . . . . . . . # # # # # # #
</pre>
=={{header|Nim}}==
<lang Nim>import bitops, sequtils, strutils, tables
type
# Lengths of distinct runs of occupied cells.
Lengths = seq[int]
# Possibilities described by tow masks and a list of integer values.
Possibilities = object
mask0: int # Mask indicating the positions of free cells.
mask1: int # Mask indicating the positions of occupied cells.
list: seq[int] # List of possibilities.
# Mapping of lists of lengths to lists of possible values.
Configs = Table[seq[int], seq[int]]
func lengths(n: int): Lengths =
## Return the lengths corresponding to a possibility.
var n = n
var count = 0
while n != 0:
if (n and 1) != 0:
inc count
elif count != 0:
result.add count
count = 0
n = n shr 1
if count != 0:
result.add count
func initConfigs(n: int): Configs =
## Initialize a configs table.
for val in 0..n:
result.mgetOrPut(lengths(val), @[]).add val
func updateUnset(poss: var seq[Possibilities]; mask, rank: int) =
## Update the lists of possibilities keeping only those
## compatible with the mask (for bits not set only).
var mask = mask
for i in 0..poss.high:
if (mask and 1) == 0:
for j in countdown(poss[i].list.high, 0):
if poss[i].list[j].testBit(rank):
# Bit is set, so the value is not compatible: remove it.
poss[i].list.delete(j)
mask = mask shr 1
func updateSet(poss: var seq[Possibilities]; mask, rank: int) =
## Update the lists of possibilities keeping only those
## compatible with the mask (for bits set only).
var mask = mask
for i in 0..poss.high:
if (mask and 1) != 0:
for j in countdown(poss[i].list.high, 0):
if not poss[i].list[j].testBit(rank):
# Bit is not set, so the value is not compatible: remove it.
poss[i].list.delete(j)
mask = mask shr 1
proc process(poss1, poss2: var seq[Possibilities]): bool =
## Look at possobilities in list "poss1", compute the masks for
## bits unset and bits set and update "poss2" accordingly.
var num = 0
for poss in poss1.mitems:
# Check bits unset.
var mask = 0
for value in poss.list:
mask = mask or value
if mask != poss.mask0:
# Mask has changed: update.
result = true
poss2.updateUnset(mask, num)
poss.mask0 = mask
# Check bits set.
mask = 1 shl poss2.len - 1
for value in poss.list:
mask = mask and value
if mask != poss.mask1:
# Mask has changed: update.
result = true
poss2.updateSet(mask, num)
poss.mask1 = mask
inc num
proc solve(rowLengths, colLengths: openArray[Lengths]) =
## Solve nonogram defined by "rowLengths" and "colLengths".
# Build auxiliary tables.
let rowmax = 1 shl colLengths.len - 1
let colmax = 1 shl rowLengths.len - 1
let rowConfs = initConfigs(rowmax)
let colConfs = initConfigs(colmax)
# Initialize the list of possibilities for rows and columns.
var rowPoss: seq[Possibilities]
for lengths in rowLengths:
rowPoss.add Possibilities(mask0: rowmax, mask1: 0, list: rowConfs[lengths])
var colPoss: seq[Possibilities]
for lengths in colLengths:
colPoss.add Possibilities(mask0: colmax, mask1: 0, list: colConfs[lengths])
# Solve nonogram.
var hasChanged = true
while hasChanged:
hasChanged = process(rowPoss, colPoss) or process(colPoss, rowPoss)
# Check if solved.
for poss in rowPoss:
if poss.list.len != 1:
echo "Unable to solve the nonogram."
return
# Display the solution.
for poss in rowPoss:
var line = ""
var val = poss.list[0]
for i in 0..colPoss.high:
line.add if (val and 1) == 0: " " else: "# "
val = val shr 1
echo line
func expand(s: string): seq[Lengths] =
## Expand a compact description into a sequence of lengths.
for elem in s.splitWhitespace():
result.add elem.mapIt(ord(it) - ord('A') + 1)
proc solve(rows, cols: string) =
## Solve using compact description parameters.
solve(rows.expand(), cols.expand())
when isMainModule:
const
Data1 = ("C BA CB BB F AE F A B", "AB CA AE GA E C D C")
Data2 = ("F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC",
"D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA")
Data3 = ("CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
"BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC")
Data4 = ("E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G",
"E CB BAB AAA AAA AC BB ACC ACCA AGB AIA AJ AJ ACE AH BAF CAG DAG FAH FJ GJ ADK ABK BL CM")
for (rows, cols) in [Data1, Data2, Data3, Data4]:
echo rows
echo cols
echo ""
solve(rows, cols)
echo ""</lang>
{{out}}
<pre>C BA CB BB F AE F A B
AB CA AE GA E C D C
# # #
# # #
# # # # #
# # # #
# # # # # #
# # # # # #
# # # # # #
#
# #
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
# # # # # #
# # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # #
# # #
# # # # # #
# # # # # # # # #
# # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
# # # #
# # # # # # #
# # # # # # #
# # # # # #
# # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # #
# # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # #
# # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # #
# # # # # #
# # # # # #
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
E CB BAB AAA AAA AC BB ACC ACCA AGB AIA AJ AJ ACE AH BAF CAG DAG FAH FJ GJ ADK ABK BL CM
# # # # #
# # # # # # #
# # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # #
# # # # # # #
# # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # </pre>
=={{header|Perl}}==
| |||