Sokoban: Difference between revisions

Content added Content deleted
(Updated first D entry)
(Updated D entry)
Line 758: Line 758:
private immutable int playerx, playery;
private immutable int playerx, playery;


this(in string[] board) pure nothrow const
this(in string[] board) pure nothrow const @safe
in {
in {
foreach (const row; board) {
foreach (const row; board) {
Line 767: Line 767:
}
}
} body {
} body {
immutable sMap = [' ':' ', '.':'.', '@':' ', '#':'#', '$':' '];
/*static*/ immutable sMap =
immutable dMap = [' ':' ', '.':' ', '@':'@', '#':' ', '$':'*'];
[' ':' ', '.':'.', '@':' ', '#':'#', '$':' '];
/*static*/ immutable dMap =
[' ':' ', '.':' ', '@':'@', '#':' ', '$':'*'];
ncols = board[0].length;
ncols = board[0].length;


Line 792: Line 794:
private bool move(in int x, in int y, in int dx,
private bool move(in int x, in int y, in int dx,
in int dy, ref CTable data)
in int dy, ref CTable data)
const pure nothrow {
const pure nothrow /*@safe*/ {
if (sData[(y+dy) * ncols + x + dx] == El.wall ||
if (sData[(y+dy) * ncols + x + dx] == El.wall ||
data[(y+dy) * ncols + x + dx] != El.floor)
data[(y+dy) * ncols + x + dx] != El.floor)
Line 806: Line 808:
private bool push(in int x, in int y, in int dx,
private bool push(in int x, in int y, in int dx,
in int dy, ref CTable data)
in int dy, ref CTable data)
const pure nothrow {
const pure nothrow /*@safe*/ {
if (sData[(y + 2*dy) * ncols + x+2*dx] == El.wall ||
if (sData[(y + 2*dy) * ncols + x+2*dx] == El.wall ||
data[(y + 2*dy) * ncols + x+2*dx] != El.floor)
data[(y + 2*dy) * ncols + x+2*dx] != El.floor)
Line 819: Line 821:
}
}


private bool isSolved(in CTable data) const pure nothrow {
private bool isSolved(in CTable data)
const pure nothrow @safe @nogc {
foreach (immutable i, immutable d; data)
foreach (immutable i, immutable d; data)
if ((sData[i] == El.goal) != (d == El.boxOnGoal))
if ((sData[i] == El.goal) != (d == El.boxOnGoal))
Line 826: Line 829:
}
}


string solve() pure nothrow {
string solve() pure nothrow /*@safe*/ {
bool[immutable CTable] visitedSet = [dData: true];
bool[immutable CTable] visitedSet = [dData: true];


Line 921: Line 924:
CellIndex[0] c_;
CellIndex[0] c_;


CellIndex get(in size_t i) inout pure nothrow {
CellIndex get(in size_t i) inout pure nothrow @nogc {
return c_.ptr[i];
return c_.ptr[i];
}
}


void set(in size_t i, in CellIndex v) pure nothrow {
void set(in size_t i, in CellIndex v) pure nothrow @nogc {
c_.ptr[i] = v;
c_.ptr[i] = v;
}
}


CellIndex[] slice(in size_t i, in size_t j) pure nothrow {
CellIndex[] slice(in size_t i, in size_t j) pure nothrow @nogc {
return c_.ptr[i .. j];
return c_.ptr[i .. j];
}
}
Line 943: Line 946:




State* newState(State* parent) nothrow {
State* newState(State* parent) nothrow @nogc {
static State* nextOf(State *s) nothrow {
static State* nextOf(State *s) nothrow @nogc {
return cast(State*)(cast(ubyte*)s + stateSize);
return cast(State*)(cast(ubyte*)s + stateSize);
}
}
Line 972: Line 975:




void unNewState(State* p) nothrow {
void unNewState(State* p) nothrow @nogc {
p.next = blockHead;
p.next = blockHead;
blockHead = p;
blockHead = p;
Line 979: Line 982:


/// Mark up positions where a box definitely should not be.
/// Mark up positions where a box definitely should not be.
void markLive(in size_t c) nothrow {
void markLive(in size_t c) nothrow @nogc {
immutable y = c / w;
immutable y = c / w;
immutable x = c % w;
immutable x = c % w;
Line 1,001: Line 1,004:




State* parseBoard(in size_t y, in size_t x, in char* s) nothrow {
State* parseBoard(in size_t y, in size_t x, in char* s) nothrow @nogc {
static T[] myCalloc(T)(in size_t n) nothrow {
static T[] myCalloc(T)(in size_t n) nothrow @nogc {
auto ptr = cast(T*)calloc(n, T.sizeof);
auto ptr = cast(T*)calloc(n, T.sizeof);
if (ptr == null)
if (ptr == null)
Line 1,058: Line 1,061:


/// K&R hash function.
/// K&R hash function.
void hash(State* s, in size_t nBoxes) pure nothrow {
void hash(State* s, in size_t nBoxes) pure nothrow @nogc {
if (!s.h) {
if (!s.h) {
Thash ha = 0;
Thash ha = 0;
Line 1,068: Line 1,071:




void extendTable() nothrow {
void extendTable() nothrow @nogc {
int oldSize = hashSize;
int oldSize = hashSize;


Line 1,102: Line 1,105:




State* lookup(State *s) nothrow {
State* lookup(State *s) nothrow @nogc {
s.hash(nBoxes);
s.hash(nBoxes);
auto f = buckets[s.h & (hashSize - 1)];
auto f = buckets[s.h & (hashSize - 1)];
Line 1,114: Line 1,117:




bool addToTable(State* s) nothrow {
bool addToTable(State* s) nothrow @nogc {
if (s.lookup) {
if (s.lookup) {
s.unNewState;
s.unNewState;
Line 1,131: Line 1,134:




bool success(in State* s) nothrow {
bool success(in State* s) nothrow @nogc {
foreach (immutable i; 1 .. nBoxes + 1)
foreach (immutable i; 1 .. nBoxes + 1)
if (!goals[s.get(i)])
if (!goals[s.get(i)])
Line 1,139: Line 1,142:




State* moveMe(State* s, in int dy, in int dx) nothrow {
State* moveMe(State* s, in int dy, in int dx) nothrow @nogc {
immutable int y = s.get(0) / w;
immutable int y = s.get(0) / w;
immutable int x = s.get(0) % w;
immutable int x = s.get(0) % w;
Line 1,192: Line 1,195:




bool queueMove(State *s) nothrow {
bool queueMove(State *s) nothrow @nogc {
if (!s || !s.addToTable)
if (!s || !s.addToTable)
return false;
return false;
Line 1,208: Line 1,211:




bool doMove(State* s) nothrow {
bool doMove(State* s) nothrow @nogc {
return s.moveMe( 1, 0).queueMove ||
return s.moveMe( 1, 0).queueMove ||
s.moveMe(-1, 0).queueMove ||
s.moveMe(-1, 0).queueMove ||
Line 1,216: Line 1,219:




void showBoard(in State* s) nothrow {
void showBoard(in State* s) nothrow @nogc {
static immutable glyphs1 = " #@$", glyphs2 = ".#@$";
static immutable glyphs1 = " #@$", glyphs2 = ".#@$";


Line 1,237: Line 1,240:




void showMoves(in State* s) nothrow {
void showMoves(in State* s) nothrow @nogc {
if (s.prev)
if (s.prev)
s.prev.showMoves;
s.prev.showMoves;
Line 1,244: Line 1,247:
}
}


⚫
int main() nothrow @nogc {
// Workaround for @nogc.
alias ctEval(alias expr) = expr;


⚫
int main() nothrow {
enum uint problem = 0;
enum uint problem = 0;


static if (problem == 0) {
static if (problem == 0) {
auto s = parseBoard(8, 7,
auto s = parseBoard(8, 7, ctEval!(
"#######"~
"#######"~
"# #"~
"# #"~
Line 1,257: Line 1,262:
"#.$$ #"~
"#.$$ #"~
"#.# @#"~
"#.# @#"~
"#######");
"#######"));


} else static if (problem == 1) {
} else static if (problem == 1) {
auto s = parseBoard(5, 13,
auto s = parseBoard(5, 13, ctEval!(
"#############"~
"#############"~
"# # #"~
"# # #"~
"# $$$$$$$ @#"~
"# $$$$$$$ @#"~
"#....... #"
"#....... #"
"#############");
"#############"));


} else static if (problem == 2) {
} else static if (problem == 2) {
auto s = parseBoard(11, 19,
auto s = parseBoard(11, 19, ctEval!(
" ##### "~
" ##### "~
" # # "~
" # # "~
Line 1,279: Line 1,284:
"##### ### #@## .#"~
"##### ### #@## .#"~
" # #########"~
" # #########"~
" ####### ");
" ####### "));
} else {
} else {
asset(0, "Not present problem.");
asset(0, "Not present problem.");
Retrieved from "https://rosettacode.org/wiki/Sokoban"