Anonymous user
Nonogram solver: Difference between revisions
Changed the way to initialize using an algorithm derived from that of Java/Kotlin/Go.
m (Corrected a typo.) |
(Changed the way to initialize using an algorithm derived from that of Java/Kotlin/Go.) |
||
Line 2,130:
=={{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,
type
Line 2,137 ⟶ 2,138:
# Lengths of distinct runs of occupied cells.
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.
Line 2,144 ⟶ 2,148:
list: seq[int] # List of possibilities.
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
var n = n▼
proc initPossibilities(lengthsList: openArray[Lengths]; length: Positive): seq[Possibilities] =
let initMask0 = 1 shl length - 1
let sumLengths = sum(lengths)
let prep = lengths.mapIt(1 shl it - 1)
let possList = genSequence(prep, length - sumLengths + 1).mapIt(it shr 1)
func updateUnset(
## Update the lists of possibilities keeping only those
## compatible with the mask (for bits not set only).
var mask = mask
for
if (mask and 1) == 0:
for
if poss
# Bit is set, so the value is not compatible: remove it.
poss
mask = mask shr 1
func updateSet(
## Update the lists of possibilities keeping only those
## compatible with the mask (for bits set only).
var mask = mask
for
if (mask and 1) != 0:
for
if not poss
# Bit is not set, so the value is not compatible: remove it.
poss
mask = mask shr 1
Line 2,228 ⟶ 2,227:
## Solve nonogram defined by "rowLengths" and "colLengths".
# Solve nonogram.▼
▲ # Initialize the list of possibilities for rows and columns.
▲ for lengths in rowLengths:
▲ rowPoss.add Possibilities(mask0: rowmax, mask1: 0, list: rowConfs[lengths])
▲ # Solve nonogram.
var hasChanged = true
while hasChanged:
Line 2,258 ⟶ 2,247:
var val = poss.list[0]
for i in 0..colPoss.high:
line.add if val.testBit(
echo line
Line 2,267 ⟶ 2,255:
for elem in s.splitWhitespace():
result.add elem.mapIt(ord(it) - ord('A') + 1)
proc solve(rows, cols: string) =
| |||