// Compiled with DMD 2.058 (also try 2.057)
import std.stdio, std.conv, std.datetime, std.string, std.array, std.exception;
enum : int { NONE = -2,
IMPOSSIBLE = -1,
OPEN = 0,
SOLVED = 1 }
// //////////////////////////////////////////////
int makePoint(in int x, in int y) pure nothrow {
return ((x & 0xf) << 4) | (y & 0xf);
}
int pointX(in int point) pure nothrow {
return (point >> 4) & 0xf;
}
int pointY(in int point) pure nothrow {
return point & 0xf;
}
// //////////////////////////////////////////////
struct Done {
private int done;
private int[] cells;
public int used;
this(in int count) pure nothrow {
this.cells = new int[count];
this.cells[] = NONE;
}
public bool alreadyDone(in int i) const pure nothrow {
return this.cells[i] != NONE;
}
public int nextCell() const pure nothrow {
return this.done;
}
public int get(in int i) const pure nothrow {
return this.cells[i];
}
private void adjustDone() pure nothrow {
foreach (i; this.done .. this.cells.length) {
if (this.cells[i] == NONE) {
this.done = i;
return;
}
}
this.done = -1;
}
public void addDone(in int i, in int v) pure nothrow {
this.cells[i] = v;
this.used++;
this.adjustDone();
}
public void removeDone(in int i) pure nothrow {
this.cells[i] = NONE;
this.used--;
if (this.done < 0 || i < this.done)
this.done = i;
}
}
// //////////////////////////////////////////////
final class Node {
public const int pos;
public const int id;
public int[] links;
this(in int pos, in int id, int[] links) pure nothrow {
this.pos = pos;
this.id = id;
this.links = links;
}
public void appendLink(in int id) pure nothrow {
int[] nlinks = new int[this.links.length + 1];
nlinks[0 .. this.links.length] = this.links[];
nlinks[this.links.length] = id;
this.links = nlinks;
}
public override string toString() const {
string lstr = "[";
foreach (i; 0 .. this.links.length) {
if (i > 0)
lstr ~= ",";
lstr ~= text(i);
}
lstr ~= "]";
return text("<id=", this.id, " ", this.pos, " ", lstr, ">");
}
}
// //////////////////////////////////////////////
final class Hex {
public const int size;
public const int count;
public Node[] nodesById;
public Node[] nodesByPos;
this(in int size) pure nothrow {
this.size = size;
this.count = 3 * size * (size - 1) + 1;
this.nodesById = new Node[this.count];
const int maxCode = 256;
this.nodesByPos = new Node[maxCode];
int id = 0;
foreach (y; 0 .. size) {
foreach (x; 0 .. size + y) {
const int pos = makePoint(x, y);
Node node = new Node(pos, id, null);
this.nodesByPos[pos] = node;
this.nodesById[id] = node;
id++;
}
}
foreach (y; 1 .. size) {
foreach (x; y .. size * 2 - 1) {
const int ry = size + y - 1;
const int pos = makePoint(x, ry);
Node node = new Node(pos, id, null);
this.nodesByPos[pos] = node;
this.nodesById[id] = node;
id++;
}
}
}
public void linkNodes() pure nothrow {
__gshared immutable int[][] dirs = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [-1, -1]];
foreach (node; this.nodesById) {
const int p = node.pos;
foreach (d, dd; dirs) {
const int nx = pointX(p) + dd[0];
const int ny = pointY(p) + dd[1];
const int ncode = makePoint(nx, ny);
if (this.containsPos(ncode))
node.appendLink(this.nodesByPos[ncode].id);
}
}
}
public bool containsPos(in int code) const pure nothrow {
return (code >= 0) && (code < this.nodesByPos.length) &&
(this.nodesByPos[code] !is null);
}
public Node getByPos(in int pos) /*const*/ pure nothrow {
return this.nodesByPos[pos];
}
public Node getById(in int id) /*const*/ pure nothrow {
return this.nodesById[id];
}
}
// //////////////////////////////////////////////
private int[] makeTiles() pure nothrow {
return new int[8];
}
public int sumTiles(in int[] tiles) pure nothrow {
int sum = 0;
foreach (i; 0 .. 7)
sum += tiles[i];
return sum;
}
// //////////////////////////////////////////////
final class Pos {
public Hex hex;
public int[] tiles;
public int sumTiles;
public Done done;
this(Hex hex, int[] tiles, Done done) pure nothrow {
this.hex = hex;
this.tiles = tiles;
this.sumTiles = .sumTiles(tiles);
this.done = done;
}
}
// //////////////////////////////////////////////
private int findMoves(Pos pos, int[] moves) pure nothrow {
int count, index;
Hex hex = pos.hex;
int[] tiles = pos.tiles;
Done done = pos.done;
const int cellId = done.nextCell();
if (cellId < 0)
return count;
int[] cellsAround;
int minPossible, maxPossible;
foreach (i; 0 .. 8) {
if (tiles[i] > 0) {
bool valid = true;
if (i < 7) {
if (cellsAround == null) {
cellsAround = hex.getById(cellId).links;
maxPossible = cellsAround.length;
foreach (ca; 0 .. cellsAround.length) {
int j = cellsAround[ca];
if (done.alreadyDone(j)) {
int dj = done.get(j);
if (dj > 0 && dj < 7) {
minPossible++;
} else if (dj == 0) {
maxPossible = 0;
minPossible++;
}
}
}
}
valid = (minPossible <= i) && (i <= maxPossible);
}
if (valid) {
moves[index] = cellId;
moves[index + 1] = i;
count++;
index += 2;
}
}
}
return count;
}
private void playMove(Pos pos, in int cellId, in int value) pure nothrow {
pos.tiles[value]--;
if (value < 7)
pos.sumTiles--;
pos.done.addDone(cellId, value);
}
private void undoMove(Pos pos, in int cellId, in int value) pure nothrow {
pos.tiles[value]++;
if (value < 7)
pos.sumTiles++;
pos.done.removeDone(cellId);
}
private enum string SPACES = " ";
private void printPos(Pos pos) {
Hex hex = pos.hex;
const Done done = pos.done;
const int size = hex.size;
foreach (y; 0 .. size) {
write(SPACES[0 .. size - y - 1]);
foreach (x; 0 .. size + y) {
const int pos2 = makePoint(x, y);
const int id = hex.getByPos(pos2).id;
if (done.alreadyDone(id) && (done.get(id) < 7))
write(done.get(id));
else
write(".");
write(" ");
}
writeln();
}
foreach (y; 1 .. size) {
write(SPACES[0 .. y]);
foreach (x; y .. size * 2 - 1) {
const int ry = size + y - 1;
const int pos2 = makePoint(x, ry);
const int id = hex.getByPos(pos2).id;
if (done.alreadyDone(id) && (done.get(id) < 7))
write(done.get(id));
else
write(".");
write(" ");
}
writeln();
}
}
private int solved(Pos pos) {
Hex hex = pos.hex;
const Done done = pos.done;
bool exact = true;
foreach (i; 0 .. hex.count) {
if (done.alreadyDone(i)) {
int num = done.get(i);
int min, max;
if (num < 7) {
int[] cellsAround = hex.getById(i).links; // slower if const
foreach (nid; cellsAround) {
if (done.alreadyDone(nid)) {
if (done.get(nid) < 7) {
min++;
max++;
}
} else {
max++;
}
}
if (num < min || num > max) {
return IMPOSSIBLE;
}
if (num != min) {
exact = false;
}
}
}
}
if (pos.sumTiles > 0 || !exact)
return OPEN;
printPos(pos);
return SOLVED;
}
private int solveStep(Pos pos) {
int[16] moves = void;
immutable int count = findMoves(pos, moves);
foreach (i; 0 .. count) {
immutable int cellId = moves[2 * i];
immutable int value = moves[2 * i + 1];
playMove(pos, cellId, value);
immutable int curStatus = solved(pos);
int ret = OPEN;
if (curStatus != OPEN) {
ret = curStatus;
} else if (solveStep(pos) == SOLVED) {
ret = SOLVED;
}
undoMove(pos, cellId, value);
if (ret == SOLVED)
return ret;
}
return IMPOSSIBLE;
}
private void checkValid(Pos pos) {
Hex hex = pos.hex;
int[] tiles = pos.tiles;
const Done done = pos.done;
int tot = done.used;
// Fill missing entries in tiles
foreach (i; 0 .. 8) {
if (tiles[i] > 0)
tot += tiles[i];
else
tiles[i] = 0;
}
// Check total
if (tot != hex.count) {
throw new Exception(text("Invalid input. Expected ",
hex.count, " tiles, got ", tot, "."));
}
}
private int solve(Pos pos) {
checkValid(pos);
return solveStep(pos);
}
private Pos readFile(in string file) {
string[] lines;
auto input = File(file);
try {
string line;
while (!(line = input.readln().stripRight()).empty) {
lines ~= line;
}
} finally {
input.close();
}
const int size = to!int(lines[0]);
Hex hex = new Hex(size);
int linei = 1;
int[] tiles = makeTiles();
Done done = Done(hex.count);
foreach (y; 0 .. size) {
const string line = lines[linei][size - y - 1 .. $];
int p = 0;
foreach (x; 0 .. size + y) {
string tile = line[p .. p + 2];
p += 2;
int inctile = 0;
if (tile[1] == '.') {
inctile = 7;
} else {
inctile = to!int(tile[1 .. $]);
}
if (tile[0] == '+') {
writefln("Adding locked tile: %d at pos %d, %d, id=%d\n", inctile, x, y,
hex.getByPos(makePoint(x, y)).id);
done.addDone(hex.getByPos(makePoint(x, y)).id, inctile);
} else {
tiles[inctile]++;
}
}
linei += 1;
}
foreach (y; 1 .. size) {
const int ry = size - 1 + y;
string line = lines[linei][y .. $];
int p;
foreach (x; y .. size * 2 - 1) {
string tile = line[p .. p + 2];
p += 2;
int inctile;
if (tile[1] == '.') {
inctile = 7;
} else {
inctile = to!int(tile[1 .. $]);
}
if (tile[0] == '+') {
writefln("Adding locked tile: %d at pos %d, %d, id=%d\n", inctile,
x, ry, hex.getByPos(makePoint(x, ry)).id);
done.addDone(hex.getByPos(makePoint(x, ry)).id, inctile);
} else {
tiles[inctile]++;
}
}
linei += 1;
}
hex.linkNodes();
return new Pos(hex, tiles, done);
}
private void solveFile(in string file) {
try {
scope Pos pos = readFile(file);
solve(pos);
} catch (ErrnoException e) {
writeln("Cannot solve ", file, ", error reading");
//e.printStackTrace(System.out); // not available?
}
}
void main(in string[] args) {
StopWatch sw;
sw.start();
foreach (f; args[1.. $]) {
writeln(" File : ", f);
solveFile(f);
writeln("-------------------");
}
sw.stop();
writeln("Elapsed time: ", sw.peek().msecs / 1000.0, " s");
}