110 lines
2.8 KiB
Text
110 lines
2.8 KiB
Text
|
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")
|