Rosetta Code

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.
 
PureFox (talk | contribs)
9,506 edits
m Fixed syntax highlighting.
 
(3 intermediate revisions by one other user not shown)
Line 1:
C99.
<langsyntaxhighlight lang="c>"#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include <assert.h>
#include <stdbool.h>
 
#define ensure(x) { if (!(x)) printf("\nabort: line %d\n", __LINE__); }
#define inline
 
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 = malloc(block_size * state_size);
ensure(p = malloc(block_size * state_size));
alloced += block_size - 1;
assert(p);
p->next = block_root;
block_root = p;
Line 87:
if (board[c + d] != wall && board[c + d * 2] != wall)
mark_live(c + d);
}
}
 
void show_live()
{
puts("live");
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
putchar(live[i * w + j] ? '+' : '.');
putchar('\n');
}
}
Line 103 ⟶ 93:
{
w = x, h = y;
assertensure( board = calloc(w * h, sizeof(uint8_t)) );
assertensure( goals tmpmap= calloc(w * h, sizeof(uint8_t)) );
assertensure( live goals = calloc(w * h, sizeof(uint8_t)) );
assertensure( distlive = calloc(w * h, sizeof(intuint8_t)) );
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 *= 24;
fill_limit *= 24;
}
 
buckets = realloc(buckets, state_size * hash_size);
assert(buckets);
 
// 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:
}
 
boolinline success(constvoid sort_state(state_t *sn)
{
// 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;
 
return 1;
sort_state(s);
return 0;
 
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;
 
cidx_t *p = n->c;
 
// leet bubble sort: boxes are indistinguishable
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;
}
 
return n;
}
Line 485 ⟶ 524:
state_t *s = parse_board(
 
#define BIG 40
 
#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, alloced * state_size / (1 << 20));filled,
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;
}</langsyntaxhighlight>
Retrieved from "https://rosettacode.org/wiki/Sokoban/C"