Nonogram solver: Difference between revisions

Content added Content deleted
m (Corrected a typo.)
(Changed the way to initialize using an algorithm derived from that of Java/Kotlin/Go.)
Line 2,130: Line 2,130:


=={{header|Nim}}==
=={{header|Nim}}==
To generate the sequence, we use the Java algorithm modified to directly generate bit strings (as integers) rather than character strings.


<lang Nim>import bitops, sequtils, strutils, tables
<lang Nim>import bitops, math, sequtils, strutils


type
type
Line 2,137: Line 2,138:
# Lengths of distinct runs of occupied cells.
# Lengths of distinct runs of occupied cells.
Lengths = seq[int]
Lengths = seq[int]

# Possibility, i.e. sequence of bits managed as an integer.
Possibility = int


# Possibilities described by tow masks and a list of integer values.
# Possibilities described by tow masks and a list of integer values.
Line 2,144: Line 2,148:
list: seq[int] # List of possibilities.
list: seq[int] # List of possibilities.


# Mapping of lists of lengths to lists of possible values.
Configs = Table[seq[int], seq[int]]


proc genSequence(ones: seq[int]; numZeroes: Natural): seq[Possibility] =
## Generate a sequence of possibilities.
if ones.len == 0: return @[0]
for x in 1..(numZeroes - ones.len + 1):
for tail in genSequence(ones[1..^1], numZeroes - x):
result.add (tail shl countSetBits(ones[0]) or ones[0]) shl x


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


proc initPossibilities(lengthsList: openArray[Lengths]; length: Positive): seq[Possibilities] =
⚫
## Initialize the list of possibilities from a list of lengths.


let initMask0 = 1 shl length - 1
func initConfigs(n: int): Configs =
⚫
for lengths in lengthsList:
## Initialize a configs table.
let sumLengths = sum(lengths)
for val in 0..n:
let prep = lengths.mapIt(1 shl it - 1)
result.mgetOrPut(lengths(val), @[]).add val
let possList = genSequence(prep, length - sumLengths + 1).mapIt(it shr 1)
⚫
result.add Possibilities(mask0: initMask0, mask1: 0, list: possList)




func updateUnset(poss: var seq[Possibilities]; mask, rank: int) =
func updateUnset(possList: var seq[Possibilities]; mask, rank: int) =
## Update the lists of possibilities keeping only those
## Update the lists of possibilities keeping only those
## compatible with the mask (for bits not set only).
## compatible with the mask (for bits not set only).
var mask = mask
var mask = mask
for i in 0..poss.high:
for poss in possList.mitems:
if (mask and 1) == 0:
if (mask and 1) == 0:
for j in countdown(poss[i].list.high, 0):
for i in countdown(poss.list.high, 0):
if poss[i].list[j].testBit(rank):
if poss.list[i].testBit(rank):
# Bit is set, so the value is not compatible: remove it.
# Bit is set, so the value is not compatible: remove it.
poss[i].list.delete(j)
poss.list.delete(i)
mask = mask shr 1
mask = mask shr 1




func updateSet(poss: var seq[Possibilities]; mask, rank: int) =
func updateSet(possList: var seq[Possibilities]; mask, rank: int) =
## Update the lists of possibilities keeping only those
## Update the lists of possibilities keeping only those
## compatible with the mask (for bits set only).
## compatible with the mask (for bits set only).
var mask = mask
var mask = mask
for i in 0..poss.high:
for poss in possList.mitems:
if (mask and 1) != 0:
if (mask and 1) != 0:
for j in countdown(poss[i].list.high, 0):
for i in countdown(poss.list.high, 0):
if not poss[i].list[j].testBit(rank):
if not poss.list[i].testBit(rank):
# Bit is not set, so the value is not compatible: remove it.
# Bit is not set, so the value is not compatible: remove it.
poss[i].list.delete(j)
poss.list.delete(i)
mask = mask shr 1
mask = mask shr 1


Line 2,228: Line 2,227:
## Solve nonogram defined by "rowLengths" and "colLengths".
## Solve nonogram defined by "rowLengths" and "colLengths".


⚫
var
# Build auxiliary tables.
let rowmax = 1 shl colLengths.len - 1
rowPoss = initPossibilities(rowLengths, colLengths.len)
let colmax = 1 shl rowLengths.len - 1
colPoss = initPossibilities(colLengths, rowLengths.len)
let rowConfs = initConfigs(rowmax)
let colConfs = initConfigs(colmax)


⚫
# Solve nonogram.
⚫
# 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
var hasChanged = true
while hasChanged:
while hasChanged:
Line 2,258: Line 2,247:
var val = poss.list[0]
var val = poss.list[0]
for i in 0..colPoss.high:
for i in 0..colPoss.high:
line.add if (val and 1) == 0: " " else: "# "
line.add if val.testBit(i): "# " else: " "
val = val shr 1
echo line
echo line


Line 2,267: Line 2,255:
for elem in s.splitWhitespace():
for elem in s.splitWhitespace():
result.add elem.mapIt(ord(it) - ord('A') + 1)
result.add elem.mapIt(ord(it) - ord('A') + 1)



proc solve(rows, cols: string) =
proc solve(rows, cols: string) =
Retrieved from "https://rosettacode.org/wiki/Nonogram_solver"