⚠️ Warning: This is a draft ⚠️
This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.
If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.
C99.
#include <stdio.h> #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; typedef uint16_t cidx_t; typedef unsigned int hash_t; /* board configuration is represented by an array of cell indices of player and boxes */ typedef struct state_t state_t; struct state_t { // variable length hash_t h; int depth; state_t *prev, *next, *qprev, *qnext; cidx_t c[]; }; size_t boxsize; size_t state_size, block_size = 32; state_t *block_root, *block_head; int alloced = 0; inline state_t* newstate(state_t *parent) { inline state_t* next_of(state_t *s) { return (void*)((uint8_t*)s + state_size); } state_t *ptr; 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; ptr = (void*)((uint8_t*)p + state_size * block_size); p = block_head = next_of(p); state_t *q; for (q = next_of(p); q < ptr; p = q, q = next_of(q)) p->next = q; p->next = NULL; } ptr = block_head; block_head = block_head->next; ptr->prev = parent; ptr->qprev = ptr->qnext = 0; ptr->h = 0; return ptr; } inline void unnewstate(state_t *p) { p->next = block_head; block_head = p; } enum { space, wall, player, box }; #define E "\033[" const char * const glyph1[] = { " ", "#", E"31m@"E"m", E"33m$"E"m"}; const char * const glyph2[] = { E"32m."E"m", "#", E"32m@"E"m", E"32m$"E"m"}; #undef E // mark up positions where a box definitely should not be void mark_live(const int c) { if (live[c]) return; live[c] = 1; for (int i = 0; i < 4; i++) { int d = offset[i]; if (board[c + d] != wall && board[c + d * 2] != wall) mark_live(c + d); } } state_t *parse_board(const int y, const int x, const char *s) { w = x, h = y; ensure( board = calloc(w * h, sizeof(uint8_t)) ); ensure( tmpmap= calloc(w * h, sizeof(uint8_t)) ); ensure( goals = calloc(w * h, sizeof(uint8_t)) ); ensure( live = calloc(w * h, sizeof(uint8_t)) ); ensure( dist = calloc(w * h, sizeof(int)) ); n_boxes = 0; for (int i = 0; s[i]; i++) { switch(s[i]) { case '#': board[i] = wall; continue; case '.': // fallthrough case '+': goals[i] = 1; // fallthrough case '@': continue; case '*': goals[i] = 1; // fallthrough case '$': n_boxes++; continue; default: continue; } } const int is = sizeof(int); state_size = (sizeof(state_t) + (1 + n_boxes) * sizeof(cidx_t) + is - 1) / is * is; boxsize = sizeof(cidx_t) * (1 + n_boxes); state_t *state = newstate(NULL); state->depth = 0; offset[0] = w; offset[1] = -w; for (int i = 0, j = 0; i < w * h; i++) { if (goals[i]) mark_live(i); if (s[i] == '$' || s[i] == '*') state->c[++j] = i; else if (s[i] == '@' || s[i] == '+') state->c[0] = i; } memcpy(tmpmap, board, sizeof(uint8_t) * w * h); return state; } void show_board(const state_t *s) { printf("move %d\n", s->depth); unsigned char b[w * h]; memcpy(b, board, w * h); b[ s->c[0] ] = player; for (int i = 1; i <= n_boxes; i++) b[ s->c[i] ] = box; for (int i = 0; i < w * h; i++) { printf((goals[i] ? glyph2 : glyph1)[ b[i] ]); if (! ((1 + i) % w)) putchar('\n'); } } // K&R hash function inline void hash(state_t *s) { if (!s->h) { register hash_t ha = 0; cidx_t *p = s->c; for (int i = 0; i <= n_boxes; i++) ha = p[i] + 31 * ha; s->h = ha; } } state_t **buckets; hash_t hash_size, fill_limit, filled; void extend_table() { int old_size = hash_size; if (!old_size) { hash_size = 1024; filled = 0; fill_limit = hash_size * 3 / 4; // 0.75 load factor } else { hash_size *= 4; fill_limit *= 4; } // rehash ensure(buckets = realloc(buckets, sizeof(state_t*) * hash_size)); memset(buckets + old_size, 0, sizeof(state_t*) * (hash_size - old_size)); const hash_t bits = hash_size - 1; for (int i = 0; i < old_size; i++) { state_t *head = buckets[i]; buckets[i] = NULL; while (head) { state_t *next = head->next; const int j = head->h & bits; head->next = buckets[j]; buckets[j] = head; head = next; } } } state_t *lookup(state_t *s) { hash(s); state_t *f = buckets[s->h & (hash_size - 1)]; while(f && !((f->h == s->h) && !memcmp(s->c, f->c, boxsize))) f = f->next; return f; } state_t* add_to_table(state_t *s) { state_t *f; if ((f = lookup(s))) { if (f->depth > s->depth) { f->depth = s->depth; f->prev = s->prev; unnewstate(s); return f; } unnewstate(s); return 0; } if (filled++ >= fill_limit) extend_table(); hash_t i = s->h & (hash_size - 1); s->next = buckets[i]; buckets[i] = s; return s; } inline void sort_state(state_t *n) { // 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++) if (!goals[s->c[i]]) return false; return true; } inline int deadlocked(state_t *s) { 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; } // Dijkstra's, calculate move distance from the state's player to all cells void calc_dist(state_t *s) { int qlen = 0, t = w * h, qidx[t]; cidx_t pq[t], pop; memset(qidx, 0, sizeof(int) * t); for (int i = w * h; i--; ) dist[i] = t; inline void pq_push(cidx_t c, short d) { if (board[c] >= wall || dist[c] <= d) return; int i = qidx[c], j; if (!i) i = ++qlen; while (i > 1 && dist[pq[j = i / 2]] > d) { pq[i] = pq[j]; qidx[pq[i]] = i; i = j; } qidx[c] = i; pq[i] = c; dist[pq[i]] = d; } inline void pq_pop() { pop = pq[1]; short tmp = pq[qlen--]; pq[0] = pq[1]; int i = 1, j; for (i = 1; (j = i * 2) <= qlen; i = j) { if (j < qlen && dist[pq[j]] > dist[pq[j + 1]]) j++; if (dist[pq[j]] >= dist[tmp]) break; pq[i] = pq[j]; qidx[pq[i]] = i; } pq[i] = tmp; qidx[tmp] = i; } pq_push(s->c[0], 0); while (qlen) { pq_pop(); short d = dist[pop] + 1; pq_push(pop - w, d); pq_push(pop + w, d); pq_push(pop - 1, d); pq_push(pop + 1, d); } } // make a new state by push a box in current state state_t* push_me(state_t *s, int dc) { int c1 = s->c[0] + dc; if (board[c1] != box) return 0; int c2 = c1 + dc; if (board[c2] >= wall) return 0; state_t *n = newstate(s); n->depth = s->depth + 1; for (int i = 1; i <= n_boxes; i++) n->c[i] = (s->c[i] == c1) ? c2 : s->c[i]; n->c[0] = c1; return n; } #define MAX_MOVE 1024 state_t *solution, *queue[MAX_MOVE]; int known_moves = MAX_MOVE; // if a better move is found for a configuration already queued void unqueue_move(state_t *s) { state_t *p = s->qnext; if (p) p->qprev = s->qprev; p = s->qprev; if (!p) { if (queue[s->depth] == s) queue[s->depth] = s->qnext; } else p->qnext = s->qnext; } int queue_move(state_t *s) { if (!s) return 0; int d = s->depth; if (d >= known_moves || deadlocked(s)) { unnewstate(s); return 0; } state_t *f = lookup(s); if (f) { if (f->depth <= d) { unnewstate(s); return 0; } unqueue_move(f); f->depth = d; f->prev = s->prev; unnewstate(s); s = f; } else add_to_table(s); s->qprev = 0; if ((s->qnext = queue[d])) s->qnext->qprev = s; queue[d] = s; if (success(s)) { if (s->depth < known_moves) { known_moves = s->depth; solution = s; printf("\nfound solution at move %d\n", known_moves); } } return 1; } // this is called for queued moves; only push moves ever show up in queue int do_move(state_t *s) { for (int i = 1; i <= n_boxes; i++) board[s->c[i]] = box; calc_dist(s); int t = w * h; uint8_t near_box[t]; memset(near_box, 0, t); for (int i = 1; i <= n_boxes; i++) { int c = s->c[i]; near_box[c - w] = near_box[c + w] = near_box[c - 1] = near_box[c + 1] = 1; } for (int i = w + 1; i < w * (h - 1); i++) { if (!near_box[i] || dist[i] >= t) continue; state_t *n = s; if (dist[i]) { n = newstate(s); memcpy(n->c, s->c, boxsize); n->c[0] = i; n->depth = s->depth + dist[i]; n = add_to_table(n); } if (!dist[i] || n) { queue_move(push_me(n, -1)); queue_move(push_me(n, 1)); queue_move(push_me(n, -w)); queue_move(push_me(n, w)); } } for (int i = 1; i <= n_boxes; i++) board[s->c[i]] = space; return 0; } void show_moves(state_t *s) { if (s->prev) { show_moves(s->prev); int d = s->depth - s->prev->depth; if (d > 1) { for (int i = 1; i <= n_boxes; i++) board[s->c[i]] = box; calc_dist(s); s->c[0] = s->prev->c[0]; s->depth = s->prev->depth; while (d--) { s->depth++; for (int i = 0; i < 4; i++) { int c = s->c[0] + offset[i]; if (dist[c] == d) { s->c[0] = c; break; } } if (d) { printf("\033[H"); show_board(s); usleep(100000); } } for (int i = 1; i <= n_boxes; i++) board[s->c[i]] = space; } } printf("\033[H"); show_board(s); usleep(300000); } int main() { state_t *s = parse_board( #define BIG 0 #if BIG == 0 8, 7, "#######" "# #" "# #" "#. # #" "#. $$ #" "#.$$ #" "#.# @#" "#######" #elif BIG == 1 5, 13, "#############" "# # #" "# $$$$$$$ @#" "#....... #" "#############" #elif BIG == 2 5, 13, "#############" "#... # #" "#.$$$$$$$ @#" "#... #" "#############" #elif BIG == 3 11, 19, " ##### " " # # " " #$ # " " ### $## " " # $ $ # " "### # ## # ######" "# # ## ##### ..#" "# $ $ ..#" "##### ### #@## ..#" " # #########" " ####### " #else 11, 13, "#############" "#### ####" "# .### ####" "# # # ####" "# # $ $#. ###" "# # * # ###" "# .#$ $ # ###" "## # # ###" "## ###. @#" "## ## #" "#############" #endif ); show_board(s); extend_table(); do_move(s); for (int d = 1; d < known_moves; d++) { state_t *s = queue[d]; printf("depth %d (%d records, mem: %d/%dM)\r", d, filled, filled * state_size / (1 << 20), alloced * state_size / (1 << 20)); fflush(stdout); for (; s; s = s->qnext) do_move(s); } if (solution) { printf("\npress any key to see solution\n"); getchar(); puts("\033[H\033[J"); show_moves(solution); } #if 0 free(buckets); free(board); free(tmpmap); free(goals); free(live); free(dist); while (block_root) { void *tmp = block_root->next; free(block_root); block_root = tmp; } #endif return 0; }