Sokoban/C: Difference between revisions
Content deleted Content added
adding modified solution: quite more complicated, but tends to be faster and use much less memory. |
m Fixed syntax highlighting. |
||
(3 intermediate revisions by one other user not shown) | |||
Line 1:
C99.
<
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include <stdbool.h>
#define ensure(x) { if (!(x)) printf("\nabort: line %d\n", __LINE__); }
int w, h, n_boxes;
int offset[4] = {0, 0, 1, -1};
uint8_t *board, *goals, *live, *tmpmap;
int *dist;
Line 42:
if (!block_head) {
block_size *= 2;
state_t *p
ensure(p = malloc(block_size * state_size));
alloced += block_size - 1;
p->next = block_root;
block_root = p;
Line 87:
if (board[c + d] != wall && board[c + d * 2] != wall)
mark_live(c + d);
}
}
Line 103 ⟶ 93:
{
w = x, h = y;
ensure( dist = calloc(w * h, sizeof(int)) );
n_boxes = 0;
Line 144 ⟶ 135:
}
memcpy(tmpmap, board, sizeof(uint8_t) * w * h);
return state;
}
Line 189 ⟶ 181:
fill_limit = hash_size * 3 / 4; // 0.75 load factor
} else {
hash_size *=
fill_limit *=
}
// rehash
ensure(buckets = realloc(buckets, sizeof(state_t*) * hash_size));
memset(buckets + old_size, 0, sizeof(state_t*) * (hash_size - old_size));
Line 247 ⟶ 237:
}
{
// leet bubble sort: boxes are indistinguishable
cidx_t *p = n->c;
for (int i = n_boxes; --i; ) {
cidx_t t = 0;
for (int j = 1; j < i; j++) {
if (p[j] > p[j + 1])
t = p[j], p[j] = p[j+1], p[j+1] = t;
}
if (!t) break;
}
}
inline bool success(const state_t *s)
{
for (int i = 1; i <= n_boxes; i++)
Line 257 ⟶ 261:
{
for (int i = 1; i <= n_boxes; i++)
if (!live[s->c[i]]) return 1;
sort_state(s);
int ret = 0;
for (int i = 1; i <= n_boxes; i++)
tmpmap[s->c[i]] = box;
/* check if two boxes are next to each other and sitting along a wall
or some such */
for (int i = 1; i < n_boxes; i++) {
int x = s->c[i];
int y = s->c[i + 1];
if (y == x + 1 && !(goals[x] && goals[y])) {
if ((tmpmap[x - w] >= wall && tmpmap[y - w] >= wall) ||
(tmpmap[x + w] >= wall && tmpmap[y + w] >= wall))
{
ret = 1;
goto bail;
}
if ((tmpmap[x - w] == wall || tmpmap[x + w] == wall) &&
(tmpmap[y - w] == wall || tmpmap[y + w] == wall))
{
ret = 1;
goto bail;
}
}
for (int j = i + 1; j <= n_boxes; j++) {
y = s->c[j];
if (y == x + w) {
if (goals[x] && goals[y]) continue;
if ((tmpmap[x - 1] >= wall && tmpmap[y - 1] >= wall) ||
(tmpmap[x + 1] >= wall && tmpmap[y + 1] >= wall))
{
ret = 1;
goto bail;
}
if ((tmpmap[x - 1] == wall || tmpmap[x + 1] == wall) &&
(tmpmap[y - 1] == wall || tmpmap[y + 1] == wall))
{
ret = 1;
goto bail;
}
}
}
}
bail: for(int i = 1; i <= n_boxes; i++)
tmpmap[s->c[i]] = space;
return ret;
}
Line 327 ⟶ 379:
n->c[i] = (s->c[i] == c1) ? c2 : s->c[i];
n->c[0] = c1;
return n;
}
Line 485 ⟶ 524:
state_t *s = parse_board(
#define BIG
#if BIG == 0
Line 517 ⟶ 556:
" ##### "
" # # "
" #
" ### $## "
" # $ $ # "
"### # ## # ######"
"# # ## ##### ..#"
"# $ $
"##### ### #@## ..#"
" # #########"
Line 549 ⟶ 588:
for (int d = 1; d < known_moves; d++) {
state_t *s = queue[d];
printf("depth %d (%d records, mem: %d/%dM)\r", d,
filled * state_size / (1 << 20),
alloced * state_size / (1 << 20));
fflush(stdout);
Line 565 ⟶ 606:
free(buckets);
free(board);
free(tmpmap);
free(goals);
free(live);
Line 577 ⟶ 619:
return 0;
}</
|