110 lines
2.8 KiB
Plaintext
110 lines
2.8 KiB
Plaintext
F gen_row(w, s)
|
||
‘Create all patterns of a row or col that match given runs.’
|
||
F gen_seg([[Int]] o, Int sp) -> [[Int]]
|
||
I o.empty
|
||
R [[2] * sp]
|
||
[[Int]] r
|
||
L(x) 1 .< sp - o.len + 2
|
||
L(tail) @gen_seg(o[1..], sp - x)
|
||
r [+]= [2] * x [+] o[0] [+] tail
|
||
R r
|
||
|
||
R gen_seg(s.map(i -> [1] * i), w + 1 - sum(s)).map(x -> x[1..])
|
||
|
||
F deduce(hr, vr)
|
||
‘Fix inevitable value of cells, and propagate.’
|
||
F allowable(row)
|
||
R row.reduce((a, b) -> zip(a, b).map((x, y) -> x [|] y))
|
||
|
||
F fits(a, b)
|
||
R all(zip(a, b).map((x, y) -> x [&] y))
|
||
|
||
V (w, h) = (vr.len, hr.len)
|
||
V rows = hr.map(x -> gen_row(@w, x))
|
||
V cols = vr.map(x -> gen_row(@h, x))
|
||
V can_do = rows.map(allowable)
|
||
|
||
V mod_rows = Set[Int]()
|
||
V mod_cols = Set(0 .< w)
|
||
|
||
F fix_col(n)
|
||
‘See if any value in a given column is fixed;
|
||
if so, mark its corresponding row for future fixup.’
|
||
V c = @can_do.map(x -> x[@n])
|
||
@cols[n] = @cols[n].filter(x -> @@fits(x, @c))
|
||
L(x) @allowable(@cols[n])
|
||
V i = L.index
|
||
I x != @can_do[i][n]
|
||
@mod_rows.add(i)
|
||
@can_do[i][n] [&]= x
|
||
|
||
F fix_row(n)
|
||
‘Ditto, for rows.’
|
||
V c = @can_do[n]
|
||
@rows[n] = @rows[n].filter(x -> @@fits(x, @c))
|
||
L(x) @allowable(@rows[n])
|
||
V i = L.index
|
||
I x != @can_do[n][i]
|
||
@mod_cols.add(i)
|
||
@can_do[n][i] [&]= x
|
||
|
||
F show_gram(m)
|
||
L(x) m
|
||
print(x.map(i -> ‘x#.?’[i]).join(‘ ’))
|
||
print()
|
||
|
||
L !mod_cols.empty
|
||
L(i) mod_cols
|
||
fix_col(i)
|
||
mod_cols.clear()
|
||
L(i) mod_rows
|
||
fix_row(i)
|
||
mod_rows.clear()
|
||
|
||
I all(multiloop((0 .< w), (0 .< h), (j, i) -> @can_do[i][j] C (1, 2)))
|
||
print(‘Solution would be unique’)
|
||
E
|
||
print(‘Solution may not be unique, doing exhaustive search:’)
|
||
|
||
V out = [[Int]()] * h
|
||
|
||
F try_all(Int n) -> Int
|
||
I n >= @h
|
||
L(j) 0 .< @w
|
||
I @out.map(x -> x[@j]) !C @cols[j]
|
||
R 0
|
||
@show_gram(@out)
|
||
R 1
|
||
V sol = 0
|
||
L(x) @rows[n]
|
||
@out[n] = x
|
||
sol += @try_all(n + 1)
|
||
R sol
|
||
|
||
V n = try_all(0)
|
||
I n == 0
|
||
print(‘No solution.’)
|
||
E I n == 1
|
||
print(‘Unique solution.’)
|
||
E
|
||
print(n‘ solutions.’)
|
||
print()
|
||
|
||
F solve(p, show_runs = 1B)
|
||
[[[Int]]] s
|
||
L(l) p.split("\n")
|
||
s [+]= l.split(‘ ’).map(w -> w.map(c -> c.code - ‘A’.code + 1))
|
||
I show_runs
|
||
print(‘Horizontal runs: ’s[0])
|
||
print(‘Vertical runs: ’s[1])
|
||
deduce(s[0], s[1])
|
||
|
||
L(p) File(‘nonogram_problems.txt’).read().split("\n\n")
|
||
solve(p)
|
||
|
||
print(‘Extra example not solvable by deduction alone:’)
|
||
solve("B B A A\nB B A A")
|
||
|
||
print(‘Extra example where there is no solution:’)
|
||
solve("B A A\nA A A")
|