import std.string, std.typecons, std.exception,
std.algorithm,std.stdio;
import std.traits: hasIndirections;
struct GrowableCircularQueue(T) {
public size_t length;
private size_t first, last;
private T[] A = [T.init];
this(T[] items...) pure nothrow @safe {
foreach (x; items)
push(x);
}
@property bool empty() const pure nothrow @safe @nogc {
return length == 0;
}
@property T front() pure nothrow @safe @nogc {
assert(length != 0);
return A[first];
}
T opIndex(in size_t i) pure nothrow @safe @nogc {
assert(i < length);
return A[(first + i) & (A.length - 1)];
}
void push(T item) pure nothrow @safe {
if (length >= A.length) { // Double the queue.
immutable oldALen = A.length;
A.length *= 2;
if (last < first) {
A[oldALen .. oldALen + last + 1] = A[0 .. last +
1];
static if (hasIndirections!T)
A[0 .. last + 1] = T.init; // Help for the GC.
last += oldALen;
}
}
last = (last + 1) & (A.length - 1);
A[last] = item;
length++;
}
@property T pop() pure nothrow @safe @nogc {
assert(length != 0);
auto saved = A[first];
static if (hasIndirections!T)
A[first] = T.init; // Help for the GC.
first = (first + 1) & (A.length - 1);
length--;
return saved;
}
}
const struct Board {
private enum El { floor = ' ', wall = '#', goal = '.',
box = '$', player = '@', boxOnGoal='*' }
private alias CTable = string;
private immutable size_t ncols;
private immutable CTable sData, dData;
private immutable int playerx, playery;
this(in string[] board) immutable
in {
foreach (const row; board) {
assert(row.length == board[0].length,
"Unequal board rows.");
foreach (immutable c; row)
assert(c.inPattern(" #.$@*"), "Not valid input");
}
} body {
/*static*/ immutable sMap =
[' ':' ', '.':'.', '@':' ', '#':'#', '$':' '];
/*static*/ immutable dMap =
[' ':' ', '.':' ', '@':'@', '#':' ', '$':'*'];
ncols = board[0].length;
writeln("ncols =",ncols);
int plx = 0, ply = 0;
CTable sDataBuild, dDataBuild;
foreach (immutable r, const row; board)
foreach (immutable c, const ch; row) {
sDataBuild ~= sMap[ch];
dDataBuild ~= dMap[ch];
if (ch == El.player) {
plx = c;
ply = r;
}
// writeln("c ch row ",c," ",ch," ",row);
// writeln("board =>",board);
}
this.sData = sDataBuild;
this.dData = dDataBuild;
this.playerx = plx;
this.playery = ply;
}
private bool move(in int x, in int y, in int dx,
in int dy, ref CTable data)
const pure nothrow /*@safe*/ {
if (sData[(y + dy) * ncols + x + dx] == El.wall ||
data[(y + dy) * ncols + x + dx] != El.floor)
return false;
auto data2 = data.dup;
data2[y * ncols + x] = El.floor;
data2[(y + dy) * ncols + x + dx] = El.player;
data = data2.assumeUnique; // Not enforced.
return true;
}
private bool push(in int x, in int y, in int dx,
in int dy, ref CTable data)
const pure nothrow /*@safe*/ {
if (sData[(y + 2 * dy) * ncols + x + 2 * dx] == El.wall ||
data[(y + 2 * dy) * ncols + x + 2 * dx] != El.floor)
return false;
auto data2 = data.dup;
data2[y * ncols + x] = El.floor;
data2[(y + dy) * ncols + x + dx] = El.player;
data2[(y + 2 * dy) * ncols + x + 2*dx] = El.boxOnGoal;
data = data2.assumeUnique; // Not enforced.
return true;
}
private bool isSolved(in CTable data)
const pure nothrow @safe @nogc {
foreach (immutable i, immutable d; data)
if ((sData[i] == El.goal) != (d == El.boxOnGoal))
return false;
return true;
}
string solve() pure nothrow /*@safe*/ {
bool[immutable CTable] visitedSet = [dData: true];
alias Four = Tuple!(CTable, string, int, int);
GrowableCircularQueue!Four open;
open.push(Four(dData, "", playerx, playery));
static immutable dirs = [tuple( 0, -1, 'u', 'U'),
tuple( 1, 0, 'r', 'R'),
tuple( 0, 1, 'd', 'D'),
tuple(-1, 0, 'l', 'L')];
while (!open.empty) {
//immutable (cur, cSol, x, y) = open.pop;
immutable item = open.pop;
immutable cur = item[0];
immutable cSol = item[1];
immutable x = item[2];
immutable y = item[3];
foreach (immutable di; dirs) {
CTable temp = cur;
//immutable (dx, dy) = di[0 .. 2];
immutable dx = di[0];
immutable dy = di[1];
if (temp[(y + dy) * ncols + x + dx] ==
El.boxOnGoal) {
if (push(x, y, dx, dy, temp) && temp !in
visitedSet) {
if (isSolved(temp))
return cSol ~ di[3];
open.push(Four(temp, cSol ~ di[3], x +
dx, y + dy));
visitedSet[temp] = true;
}
} else if (move(x, y, dx, dy, temp) && temp !in
visitedSet) {
if (isSolved(temp))
return cSol ~ di[2];
open.push(Four(temp, cSol ~ di[2], x + dx, y
+ dy));
visitedSet[temp] = true;
}
}
}
return "No solution";
}
}
void main() {
import std.stdio;
GC.disable; // Uses about twice the memory.
immutable level =
"###########
#### #####
# ##
#.$***** ##
# @# * ##
###### * ##
###### * ##
###### * ##
###### ##
###### ##
###########";
immutable b = immutable(Board)(level.splitLines);
writeln(level, "\n\n", b.solve);
}
// it thows a range exception and I am trying to figure it out.
