Sokoban: Difference between revisions

Content added Content deleted
(→‎{{header|Perl}}: Totally rewrote the perl solution.)
(Safer second D entry)
Line 923: Line 923:


enum Cell : ubyte { space, wall, player, box }
enum Cell : ubyte { space, wall, player, box }
alias CellIndex = ushort;

alias CellIndex = ushort,
alias Thash = uint;
hash_t = uint;




Line 931: Line 930:
/// indices of player and boxes.
/// indices of player and boxes.
struct State { // Variable length struct.
struct State { // Variable length struct.
hash_t h;
Thash h;
State* prev, next, qNext;
State* prev, next, qNext;
CellIndex[0] c_;
CellIndex[0] c_;


ref CellIndex idx(in size_t i) pure nothrow inout {
CellIndex get(in size_t i) inout pure nothrow {
return (cast(CellIndex*)&c_)[i];
return c_.ptr[i];
}

void set(in size_t i, in CellIndex v) pure nothrow {
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 {
return (cast(CellIndex*)&c_)[i .. j];
return c_.ptr[i .. j];
}
}
}
}
Line 950: Line 953:
__gshared State* blockRoot, blockHead, nextLevel, done;
__gshared State* blockRoot, blockHead, nextLevel, done;
__gshared State*[] buckets;
__gshared State*[] buckets;
__gshared hash_t hashSize, fillLimit, filled;
__gshared Thash hashSize, fillLimit, filled;




Line 1,058: Line 1,061:
i.markLive;
i.markLive;
if (s[i] == '$' || s[i] == '*')
if (s[i] == '$' || s[i] == '*')
state.idx(++j) = i;
state.set(++j, i);
else if (s[i] == '@' || s[i] == '+')
else if (s[i] == '@' || s[i] == '+')
state.idx(0) = i;
state.set(0, i);
}
}


Line 1,070: Line 1,073:
void hash(State* s, in size_t nBoxes) pure nothrow {
void hash(State* s, in size_t nBoxes) pure nothrow {
if (!s.h) {
if (!s.h) {
hash_t ha = 0;
Thash ha = 0;
foreach (immutable i; 0 .. nBoxes + 1)
foreach (immutable i; 0 .. nBoxes + 1)
ha = s.idx(i) + 31 * ha;
ha = s.get(i) + 31 * ha;
s.h = ha;
s.h = ha;
}
}
Line 1,097: Line 1,100:
buckets[oldSize .. hashSize] = null;
buckets[oldSize .. hashSize] = null;


immutable hash_t bits = hashSize - 1;
immutable Thash bits = hashSize - 1;
foreach (immutable i; 0 .. oldSize) {
foreach (immutable i; 0 .. oldSize) {
auto head = buckets[i];
auto head = buckets[i];
Line 1,133: Line 1,136:
extendTable;
extendTable;


immutable hash_t i = s.h & (hashSize - 1);
immutable Thash i = s.h & (hashSize - 1);


s.next = buckets[i];
s.next = buckets[i];
Line 1,143: Line 1,146:
bool success(in State* s) nothrow {
bool success(in State* s) nothrow {
foreach (immutable i; 1 .. nBoxes + 1)
foreach (immutable i; 1 .. nBoxes + 1)
if (!goals[s.idx(i)])
if (!goals[s.get(i)])
return false;
return false;
return true;
return true;
Line 1,150: Line 1,153:


State* moveMe(State* s, in int dy, in int dx) nothrow {
State* moveMe(State* s, in int dy, in int dx) nothrow {
immutable int y = s.idx(0) / w;
immutable int y = s.get(0) / w;
immutable int x = s.idx(0) % w;
immutable int x = s.get(0) % w;
immutable int y1 = y + dy;
immutable int y1 = y + dy;
immutable int x1 = x + dx;
immutable int x1 = x + dx;
Line 1,161: Line 1,164:
int atBox = 0;
int atBox = 0;
foreach (immutable i; 1 .. nBoxes + 1)
foreach (immutable i; 1 .. nBoxes + 1)
if (s.idx(i) == c1) {
if (s.get(i) == c1) {
atBox = i;
atBox = i;
break;
break;
Line 1,172: Line 1,175:
return null;
return null;
foreach (immutable i; 1 .. nBoxes + 1)
foreach (immutable i; 1 .. nBoxes + 1)
if (s.idx(i) == c2)
if (s.get(i) == c2)
return null;
return null;
}
}
Line 1,179: Line 1,182:
n.slice(1, nBoxes + 1)[] = s.slice(1, nBoxes + 1);
n.slice(1, nBoxes + 1)[] = s.slice(1, nBoxes + 1);


n.idx(0) = cast(CellIndex)c1;
n.set(0, cast(CellIndex)c1);


if (atBox)
if (atBox)
n.idx(atBox) = cast(CellIndex)c2;
n.set(atBox, cast(CellIndex)c2);


// Bubble sort.
// Bubble sort.
Line 1,188: Line 1,191:
CellIndex t = 0;
CellIndex t = 0;
foreach (immutable j; 1 .. i) {
foreach (immutable j; 1 .. i) {
if (n.idx(j) > n.idx(j + 1)) {
if (n.get(j) > n.get(j + 1)) {
t = n.idx(j);
t = n.get(j);
n.idx(j) = n.idx(j + 1);
n.set(j, n.get(j + 1));
n.idx(j + 1) = t;
n.set(j + 1, t);
}
}
}
}
Line 1,235: Line 1,238:
b[] = cast(typeof(b))board[];
b[] = cast(typeof(b))board[];


b[s.idx(0)] = Cell.player;
b[s.get(0)] = Cell.player;
foreach (immutable i; 1 .. nBoxes + 1)
foreach (immutable i; 1 .. nBoxes + 1)
b[s.idx(i)] = Cell.box;
b[s.get(i)] = Cell.box;


foreach (immutable i, immutable bi; b) {
foreach (immutable i, immutable bi; b) {
Retrieved from "https://rosettacode.org/wiki/Sokoban"