137 lines
4.3 KiB
D
137 lines
4.3 KiB
D
import std.stdio, std.range, std.file, std.algorithm, std.string;
|
|
|
|
/// Create all patterns of a row or col that match given runs.
|
|
auto genRow(in int w, in int[] s) pure nothrow @safe {
|
|
static int[][] genSeg(in int[][] o, in int sp) pure nothrow @safe {
|
|
if (o.empty)
|
|
return [[2].replicate(sp)];
|
|
|
|
typeof(return) result;
|
|
foreach (immutable x; 1 .. sp - o.length + 2)
|
|
foreach (const tail; genSeg(o[1 .. $], sp - x))
|
|
result ~= [2].replicate(x) ~ o[0] ~ tail;
|
|
return result;
|
|
}
|
|
|
|
const ones = s.map!(i => [1].replicate(i)).array;
|
|
return genSeg(ones, w + 1 - s.sum).map!dropOne;
|
|
}
|
|
|
|
/// Fix inevitable value of cells, and propagate.
|
|
void deduce(in int[][] hr, in int[][] vr) {
|
|
static int[] allowable(in int[][] row) pure nothrow @safe {
|
|
//return row.dropOne.fold!q{ a[] |= b[] }(row[0].dup);
|
|
return reduce!q{ a[] |= b[] }(row[0].dup, row.dropOne);
|
|
}
|
|
|
|
static bool fits(in int[] a, in int[] b)
|
|
pure /*nothrow*/ @safe /*@nogc*/ {
|
|
return zip(a, b).all!(xy => xy[0] & xy[1]);
|
|
}
|
|
|
|
immutable int w = vr.length,
|
|
h = hr.length;
|
|
auto rows = hr.map!(x => genRow(w, x).array).array;
|
|
auto cols = vr.map!(x => genRow(h, x).array).array;
|
|
auto canDo = rows.map!allowable.array;
|
|
|
|
// Initially mark all columns for update.
|
|
bool[uint] modRows, modCols;
|
|
modCols = true.repeat.enumerate!uint.take(w).assocArray;
|
|
|
|
/// See if any value a given column is fixed; if so,
|
|
/// mark its corresponding row for future fixup.
|
|
void fixCol(in int n) /*nothrow*/ @safe {
|
|
const c = canDo.map!(x => x[n]).array;
|
|
cols[n] = cols[n].remove!(x => !fits(x, c)); // Throws.
|
|
foreach (immutable i, immutable x; allowable(cols[n]))
|
|
if (x != canDo[i][n]) {
|
|
modRows[i] = true;
|
|
canDo[i][n] &= x;
|
|
}
|
|
}
|
|
|
|
/// Ditto, for rows.
|
|
void fixRow(in int n) /*nothrow*/ @safe {
|
|
const c = canDo[n];
|
|
rows[n] = rows[n].remove!(x => !fits(x, c)); // Throws.
|
|
foreach (immutable i, immutable x; allowable(rows[n]))
|
|
if (x != canDo[n][i]) {
|
|
modCols[i] = true;
|
|
canDo[n][i] &= x;
|
|
}
|
|
}
|
|
|
|
void showGram(in int[][] m) {
|
|
// If there's 'x', something is wrong.
|
|
// If there's '?', needs more work.
|
|
m.each!(x => writefln("%-(%c %)", x.map!(i => "x#.?"[i])));
|
|
writeln;
|
|
}
|
|
|
|
while (modCols.length > 0) {
|
|
modCols.byKey.each!fixCol;
|
|
modCols = null;
|
|
modRows.byKey.each!fixRow;
|
|
modRows = null;
|
|
}
|
|
|
|
if (cartesianProduct(h.iota, w.iota)
|
|
.all!(ij => canDo[ij[0]][ij[1]] == 1 || canDo[ij[0]][ij[1]] == 2))
|
|
"Solution would be unique".writeln;
|
|
else
|
|
"Solution may not be unique, doing exhaustive search:".writeln;
|
|
|
|
// We actually do exhaustive search anyway. Unique
|
|
// solution takes no time in this phase anyway.
|
|
auto out_ = new const(int)[][](h);
|
|
|
|
uint tryAll(in int n = 0) {
|
|
if (n >= h) {
|
|
foreach (immutable j; 0 .. w)
|
|
if (!cols[j].canFind(out_.map!(x => x[j]).array))
|
|
return 0;
|
|
showGram(out_);
|
|
return 1;
|
|
}
|
|
typeof(return) sol = 0;
|
|
foreach (const x; rows[n]) {
|
|
out_[n] = x;
|
|
sol += tryAll(n + 1);
|
|
}
|
|
return sol;
|
|
}
|
|
|
|
immutable n = tryAll;
|
|
switch (n) {
|
|
case 0: "No solution.".writeln; break;
|
|
case 1: "Unique solution.".writeln; break;
|
|
default: writeln(n, " solutions."); break;
|
|
}
|
|
writeln;
|
|
}
|
|
|
|
void solve(in string p, in bool showRuns=true) {
|
|
immutable s = p.splitLines.map!(l => l.split.map!(w =>
|
|
w.map!(c => int(c - 'A' + 1)).array).array).array;
|
|
//w.map!(c => c - 'A' + 1))).to!(int[][][]);
|
|
|
|
if (showRuns) {
|
|
writeln("Horizontal runs: ", s[0]);
|
|
writeln("Vertical runs: ", s[1]);
|
|
}
|
|
deduce(s[0], s[1]);
|
|
}
|
|
|
|
void main() {
|
|
// Read problems from file.
|
|
immutable fn = "nonogram_problems.txt";
|
|
fn.readText.split("\n\n").filter!(p => !p.strip.empty).each!(p => p.strip.solve);
|
|
|
|
"Extra example not solvable by deduction alone:".writeln;
|
|
"B B A A\nB B A A".solve;
|
|
|
|
"Extra example where there is no solution:".writeln;
|
|
"B A A\nA A A".solve;
|
|
}
|