diff options
Diffstat (limited to 'src/libsok')
| -rw-r--r-- | src/libsok/sok-cache.c | 168 | ||||
| -rw-r--r-- | src/libsok/sok-ctx-hash.c | 41 | ||||
| -rw-r--r-- | src/libsok/sok-ctx.c | 636 | ||||
| -rw-r--r-- | src/libsok/sok-level-parser.c | 193 | ||||
| -rw-r--r-- | src/libsok/sok-solve.c | 89 | ||||
| -rw-r--r-- | src/libsok/sok.h | 257 |
6 files changed, 0 insertions, 1384 deletions
diff --git a/src/libsok/sok-cache.c b/src/libsok/sok-cache.c deleted file mode 100644 index df3c729..0000000 --- a/src/libsok/sok-cache.c +++ /dev/null @@ -1,168 +0,0 @@ -#include <stdbool.h> // bool -#include <stdint.h> // uint64_t -#include <stdlib.h> // bsearch(), qsort() -#include <string.h> // memcpy -#include <stdio.h> // debug -#include "sok.h" - -#define UNUSED(a) ((void) (a)) -#define GROW_SIZE (4096 / sizeof(uint64_t)) -#define USE_QSORT 1 - -static int -u64_cmp( - const void * const ap, - const void * const bp -) { - const uint64_t a = *((uint64_t*) ap), - b = *((uint64_t*) bp); - - return (a > b) ? -1 : ((a == b) ? 0 : 1); -} - -static bool -sok_cache_grow( - sok_cache_t * const cache -) { - // calculate new capacity - const size_t new_capacity = cache->capacity + GROW_SIZE; - if (new_capacity < cache->capacity) { - return false; - } - - // reallocate memory - uint64_t * const vals = realloc(cache->vals, new_capacity * sizeof(uint64_t)); - if (!vals) { - return false; - } - - // update data - cache->vals = vals; - cache->capacity = new_capacity; - - // return success - return true; -} - -static bool -sok_cache_has_hash( - const sok_cache_t * const cache, - const uint64_t hash -) { -#if 0 - for (size_t i = 0; i < cache->num_vals; i++) { - if (cache->vals[i] == hash) { - return true; - } - } - - // return failure - return false; -#else - return !!bsearch( - &hash, - cache->vals, - cache->num_vals, - sizeof(uint64_t), - u64_cmp - ); -#endif /* 0 */ -} - -bool -sok_cache_has( - const sok_cache_t * const cache, - const sok_ctx_t * const ctx -) { - return sok_cache_has_hash(cache, sok_ctx_hash(ctx)); -} - -bool -sok_cache_add( - sok_cache_t * const cache, - const sok_ctx_t * const ctx -) { -/* - * // hash context - * const uint64_t hash = sok_ctx_hash(ctx); - * - * // check for duplicates - * if (sok_cache_has_hash(cache, hash)) { - * return false; - * } - */ - - // check capacity - if (cache->num_vals >= cache->capacity) { - // grow cache - if (!sok_cache_grow(cache)) { - // return failure - return false; - } - } - - // append hash - const uint64_t hash = sok_ctx_hash(ctx); -#if USE_QSORT - cache->vals[cache->num_vals] = hash; - cache->num_vals++; - - // sort values - qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp); -#else - size_t i; - for (i = 0; cache->vals[i] < hash && i < cache->num_vals; i++); - if (i < cache->num_vals) { - if (cache->vals[i] == hash) { - return true; - } - - // move remaining data - const size_t num_bytes = (cache->num_vals - i) * sizeof(uint64_t); - memmove(cache->vals + (i + 1), cache->vals + i, num_bytes); - - // insert value - cache->vals[i] = hash; - cache->num_vals++; - } else { - // append value - cache->vals[cache->num_vals] = hash; - cache->num_vals++; - } -#endif /* USE_QSORT */ - - // return success - return true; -} - -bool -sok_cache_init( - sok_cache_t * const cache, - const size_t capacity -) { - // alloc memory, check for error - uint64_t * const vals = malloc(capacity * sizeof(uint64_t)); - if (!vals) { - // return failure - return false; - } - - // populate cache - cache->vals = vals; - cache->num_vals = 0; - cache->capacity = capacity; - - // return success - return true; -} - -void -sok_cache_fini( - sok_cache_t * const cache -) { - if (cache->vals) { - // free memory - free(cache->vals); - cache->vals = NULL; - } -} diff --git a/src/libsok/sok-ctx-hash.c b/src/libsok/sok-ctx-hash.c deleted file mode 100644 index 61689ea..0000000 --- a/src/libsok/sok-ctx-hash.c +++ /dev/null @@ -1,41 +0,0 @@ -#include <stdint.h> // uint16_t -#include "sok.h" - -// fnv64 -// src: https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function -#define FNV_OFFSET 1099511628211 -#define FNV_PRIME 0xcbf29ce484222325 - -static uint64_t -fnv1a( - const uint8_t * const buf, - const size_t len -) { - uint64_t hash = FNV_OFFSET; - - for (size_t i = 0; i < len; i++) { - hash ^= buf[i]; - hash *= FNV_PRIME; - } - - return hash; -} - -uint64_t -sok_ctx_hash( - const sok_ctx_t * const ctx -) { - uint16_t buf[512] = {ctx->home.x, ctx->home.y, 0}; - const size_t BUF_MASK = (sizeof(buf) / sizeof(uint16_t) - 1); - - for (size_t i = 0; i < ctx->level.num_boxes; i++) { - buf[(2 * (i + 1) + 0) & BUF_MASK] = ctx->boxes[i].x; - buf[(2 * (i + 1) + 1) & BUF_MASK] = ctx->boxes[i].y; - } - - // calculate buffer length - const size_t used = 2 * (ctx->level.num_boxes + 1) * sizeof(uint16_t); - const size_t len = (used < sizeof(buf)) ? used : sizeof(buf); - - return fnv1a((uint8_t*) buf, len); -} diff --git a/src/libsok/sok-ctx.c b/src/libsok/sok-ctx.c deleted file mode 100644 index e278af1..0000000 --- a/src/libsok/sok-ctx.c +++ /dev/null @@ -1,636 +0,0 @@ -#include <stdbool.h> -#include <string.h> // memset() -#include "sok.h" - -#define UNUSED(a) ((void) (a)) - -#define VALID_POS(pos) ( \ - (pos).x < SOK_LEVEL_MAX_WIDTH && \ - (pos).y < SOK_LEVEL_MAX_HEIGHT \ -) - -#define POINTS_EQUAL(a, b) ( \ - ((a).x == (b).x) && \ - ((a).y == (b).y) \ -) - -static bool -ctx_is_wall( - const sok_ctx_t * const ctx, - const sok_pos_t pos -) { - return ctx->level.walls[pos.y * ctx->level.size.x + pos.x]; -} - -static void -ctx_set_wall( - sok_ctx_t * const ctx, - const sok_pos_t pos -) { - ctx->level.walls[pos.y * ctx->level.size.x + pos.x] = true; -} - -static void -ctx_clear_walls( - sok_ctx_t * const ctx -) { - memset(ctx->level.walls, 0, SOK_LEVEL_MAX_WIDTH * SOK_LEVEL_MAX_HEIGHT); -} - -static bool -on_size( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // size out of bounds - return false; - } - - // save width and height - ctx->level.size = pos; - - // return success - return true; -} - -static bool -on_home( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // position out of bounds - return false; - } - - // save start position - ctx->level.home = pos; - - // return success - return true; -} - -static bool -on_wall( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // position out of bounds - return false; - } - - // save wall - ctx_set_wall(ctx, pos); - - // return sucess - return true; -} - -static bool -on_goal( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // position out of bounds - return false; - } - - if (ctx->level.num_goals >= SOK_LEVEL_MAX_GOALS - 1) { - // too many goals - return false; - } - - // save goal - ctx->level.goals[ctx->level.num_goals++] = pos; - - // return sucess - return true; -} - -static bool -on_box( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // position out of bounds - return false; - } - - if (ctx->level.num_boxes >= SOK_LEVEL_MAX_BOXES - 1) { - // too many boxes - return false; - } - - // save box - ctx->level.boxes[ctx->level.num_boxes++] = pos; - - // return sucess - return true; -} - -static bool -on_junk( - const sok_level_parser_t * const parser, - const size_t ofs, - const char tile -) { - UNUSED(parser); - UNUSED(ofs); - UNUSED(tile); - - // TODO - - // return sucess - return true; -} - -static const sok_level_parser_cbs_t -LEVEL_PARSER_CBS = { - .on_size = on_size, - .on_home = on_home, - .on_wall = on_wall, - .on_goal = on_goal, - .on_box = on_box, - .on_junk = on_junk, -}; - -static size_t -pos_find( - const sok_pos_t pos, - const sok_pos_t * const set, - const size_t len -) { - for (size_t i = 0; i < len; i++) { - if (POINTS_EQUAL(pos, set[i])) { - return i; - } - } - - return len; -} - -static size_t -sok_ctx_count_goals_left( - sok_ctx_t * const ctx -) { - const size_t num_boxes = ctx->level.num_boxes; - size_t r = 0; - - for (size_t i = 0; i < ctx->level.num_goals; i++) { - r += pos_find( - ctx->level.goals[i], - ctx->boxes, - num_boxes - ) < num_boxes ? 0 : 1; - } - - return r; -} - -/* - * static bool - * sok_ctx_has_corner_boxes( - * const sok_ctx_t * const ctx - * ) { - * for (size_t i = 0; i < ctx->level.num_boxes; i++) { - * // right - * const bool r = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x + 1, - * .y = ctx->boxes[i].y, - * }); - * - * // top-right - * const bool tr = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x + 1, - * .y = ctx->boxes[i].y - 1, - * }); - * - * // top - * const bool t = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x, - * .y = ctx->boxes[i].y - 1, - * }); - * - * // top-left - * const bool tl = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x - 1, - * .y = ctx->boxes[i].y - 1, - * }); - * - * // left - * const bool l = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x - 1, - * .y = ctx->boxes[i].y, - * }); - * - * // bottom-left - * const bool bl = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x - 1, - * .y = ctx->boxes[i].y + 1, - * }); - * - * // bottom - * const bool b = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x, - * .y = ctx->boxes[i].y + 1, - * }); - * - * const bool br = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x + 1, - * .y = ctx->boxes[i].y + 1, - * }); - * - * if ( - * (r && tr && t) || // top-right - * (t && tl && l) || // top-left - * (l && bl && b) || // bottom-left - * (b && br && r) // bottom-right - * ) { - * // return - * return true; - * } - * } - * - * return false; - * } - */ - -void -sok_ctx_init(sok_ctx_t * const ctx, void *user_data) { - memset(ctx, 0, sizeof(sok_ctx_t)); - ctx->user_data = user_data; -} - -bool -sok_ctx_set_level( - sok_ctx_t * const ctx, - const char * const str -) { - - // clear level - ctx->level.num_goals = 0; - ctx->level.num_boxes = 0; - ctx_clear_walls(ctx); - - // parse level - sok_level_parser_t parser; - sok_level_parser_init(&parser, &LEVEL_PARSER_CBS, ctx); - if (!sok_level_parser_parse(&parser, str, strlen(str))) { - // return failure - return false; - } - - // init moves, player, and boxes - ctx->num_moves = 0; - ctx->home = ctx->level.home; - memcpy(ctx->boxes, ctx->level.boxes, ctx->level.num_boxes * sizeof(sok_pos_t)); - - // count number of goals left and check whether there are - ctx->num_goals_left = sok_ctx_count_goals_left(ctx); - // ctx->is_lost = sok_ctx_is_lost(ctx); - - // return success - return true; -} - -static bool -tile_is_floor( - const sok_ctx_t * const ctx, - const sok_pos_t pos -) { - return ( - (pos.x < SOK_LEVEL_MAX_WIDTH - 1) && - (pos.y < SOK_LEVEL_MAX_HEIGHT - 1) && - !ctx_is_wall(ctx, pos) - ); -} - -static bool -tile_is_box( - const sok_ctx_t * const ctx, - const sok_pos_t pos -) { - const size_t num_boxes = ctx->level.num_boxes; - return pos_find(pos, ctx->boxes, num_boxes) < num_boxes; -} - -static bool -tile_is_goal( - const sok_ctx_t * const ctx, - const sok_pos_t pos -) { - const size_t num_goals = ctx->level.num_goals; - return pos_find(pos, ctx->level.goals, num_goals) < num_goals; -} - -static bool -sok_ctx_push_move( - sok_ctx_t * const ctx, - const sok_dir_t dir, - const bool is_push -) { - if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) { - return false; - } - - ctx->moves[ctx->num_moves].pos = ctx->home; - ctx->moves[ctx->num_moves].dir = dir; - ctx->moves[ctx->num_moves].is_push = is_push; - ctx->num_moves++; - - return true; -} - -static bool -sok_ctx_pop_move( - sok_ctx_t * const ctx, - sok_move_t * const ret -) { - if (!ctx->num_moves) { - // return failure - return false; - } - - // decriment moves - ctx->num_moves--; - - if (ret) { - // save popped move - *ret = ctx->moves[ctx->num_moves]; - } - - // return success - return true; -} - -static bool -sok_ctx_move_box( - sok_ctx_t * const ctx, - const sok_pos_t old_pos, - const sok_pos_t new_pos -) { - const size_t num_boxes = ctx->level.num_boxes, - box_ofs = pos_find(old_pos, ctx->boxes, num_boxes); - - if (box_ofs < num_boxes) { - // update box and goal count - ctx->boxes[box_ofs] = new_pos; - ctx->num_goals_left = sok_ctx_count_goals_left(ctx); - // ctx->is_lost = sok_ctx_has_corner_boxes(ctx); - - // return success - return true; - } - - // return failure - return false; -} - -bool -sok_ctx_is_done( - const sok_ctx_t * const ctx -) { - return ctx->num_goals_left == 0; -} - -/* - * bool - * sok_ctx_is_lost( - * const sok_ctx_t * const ctx - * ) { - * return ctx->is_lost; - * } - */ - -bool -sok_ctx_move( - sok_ctx_t * const ctx, - const sok_dir_t dir -) { - if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) { - // no more move slots available - return false; - } - - const sok_pos_t ps[2] = {{ - .x = ctx->home.x + ((dir == SOK_DIR_LEFT) ? -1 : ((dir == SOK_DIR_RIGHT) ? 1 : 0)), - .y = ctx->home.y + ((dir == SOK_DIR_UP) ? -1 : ((dir == SOK_DIR_DOWN) ? 1 : 0)) - }, { - .x = ctx->home.x + ((dir == SOK_DIR_LEFT) ? -2 : ((dir == SOK_DIR_RIGHT) ? 2 : 0)), - .y = ctx->home.y + ((dir == SOK_DIR_UP) ? -2 : ((dir == SOK_DIR_DOWN) ? 2 : 0)) - }}; - - const bool can_move = ( - (dir == SOK_DIR_UP) ? (ctx->home.y > 0) : - ((dir == SOK_DIR_DOWN) ? (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 1) : - ((dir == SOK_DIR_LEFT) ? (ctx->home.x > 0) : - ((dir == SOK_DIR_RIGHT) ? (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 1) : - false - )))); - - const bool can_push = ( - (dir == SOK_DIR_UP) ? (ctx->home.y > 1) : - ((dir == SOK_DIR_DOWN) ? (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 2) : - ((dir == SOK_DIR_LEFT) ? (ctx->home.x > 1) : - ((dir == SOK_DIR_RIGHT) ? (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 2) : - false - )))); - - if ( - can_move && - tile_is_floor(ctx, ps[0]) && - !tile_is_box(ctx, ps[0]) - ) { - // push move - if (!sok_ctx_push_move(ctx, dir, false)) { - return false; - } - - // update position - ctx->home.x += (dir == SOK_DIR_LEFT) ? -1 : ((dir == SOK_DIR_RIGHT) ? 1 : 0); - ctx->home.y += (dir == SOK_DIR_UP) ? -1 : ((dir == SOK_DIR_DOWN) ? 1 : 0); - - // return success - return true; - } else if ( - can_push && - tile_is_floor(ctx, ps[0]) && - tile_is_box(ctx, ps[0]) && - tile_is_floor(ctx, ps[1]) && - !tile_is_box(ctx, ps[1]) - ) { - // push move - if (!sok_ctx_push_move(ctx, dir, true)) { - return false; - } - - // move box - if (!sok_ctx_move_box(ctx, ps[0], ps[1])) { - return false; - } - - // update position - ctx->home.x += (dir == SOK_DIR_LEFT) ? -1 : ((dir == SOK_DIR_RIGHT) ? 1 : 0); - ctx->home.y += (dir == SOK_DIR_UP) ? -1 : ((dir == SOK_DIR_DOWN) ? 1 : 0); - - - // return success - return true; - } - - // return failure - return false; -} - -bool -sok_ctx_undo( - sok_ctx_t * const ctx -) { - sok_move_t move; - if (!sok_ctx_pop_move(ctx, &move)) { - // return failure - return false; - } - - if (move.is_push) { - const sok_pos_t box_pos = { - .x = move.pos.x + ((move.dir == SOK_DIR_LEFT) ? -2 : ((move.dir == SOK_DIR_RIGHT) ? 2 : 0)), - .y = move.pos.y + ((move.dir == SOK_DIR_UP) ? -2 : ((move.dir == SOK_DIR_DOWN) ? 2 : 0)), - }; - - sok_ctx_move_box(ctx, box_pos, ctx->home); - } - - // update position - ctx->home = move.pos; - - // return success - return true; -} - -bool sok_ctx_walk( - const sok_ctx_t * const ctx, - const sok_ctx_walk_cbs_t * const cbs, - void * const data -) { - if (!cbs) { - return false; - } - - if (cbs->on_size) { - // emit size - if (!cbs->on_size(ctx, ctx->level.size, data)) { - return false; - } - } - - if (cbs->on_walls_start && !cbs->on_walls_start(ctx, data)) { - return false; - } - - if (cbs->on_wall) { - // walk walls - for (size_t i = 0; i < (ctx->level.size.x * ctx->level.size.y); i++) { - const sok_pos_t pos = { - .y = i / ctx->level.size.x, - .x = i % ctx->level.size.x, - }; - - if (ctx_is_wall(ctx, pos)) { - // emit wall - if (!cbs->on_wall(ctx, pos, data)) { - return false; - } - } - } - } - - if (cbs->on_walls_end && !cbs->on_walls_end(ctx, data)) { - return false; - } - - if (cbs->on_goals_start && !cbs->on_goals_start(ctx, data)) { - return false; - } - - if (cbs->on_goal) { - // walk goals - for (size_t i = 0; i < ctx->level.num_goals; i++) { - const bool has_player = POINTS_EQUAL(ctx->level.goals[i], ctx->home); - const bool has_box = tile_is_box(ctx, ctx->level.goals[i]); - - // emit goal - if (!cbs->on_goal(ctx, ctx->level.goals[i], has_player, has_box, data)) { - return false; - } - } - } - - if (cbs->on_goals_end && !cbs->on_goals_end(ctx, data)) { - return false; - } - - if (cbs->on_boxes_start && !cbs->on_boxes_start(ctx, data)) { - return false; - } - - if (cbs->on_home) { - const bool has_goal = tile_is_goal(ctx, ctx->home); - - // emit home - if (!cbs->on_home(ctx, ctx->home, has_goal, data)) { - return false; - } - } - - if (cbs->on_box) { - // walk boxes - for (size_t i = 0; i < ctx->level.num_boxes; i++) { - const bool has_goal = tile_is_goal(ctx, ctx->boxes[i]); - - // emit box - if (!cbs->on_box(ctx, ctx->boxes[i], has_goal, data)) { - return false; - } - } - } - - if (cbs->on_boxes_end && !cbs->on_boxes_end(ctx, data)) { - return false; - } - - if (cbs->on_moves_start && !cbs->on_moves_start(ctx, data)) { - return false; - } - - if (cbs->on_move) { - // walk moves - for (size_t i = 0; i < ctx->num_moves; i++) { - // emit move - if (!cbs->on_move(ctx, ctx->moves[i], data)) { - return false; - } - } - } - - if (cbs->on_moves_end && !cbs->on_moves_end(ctx, data)) { - return false; - } - - // return success - return true; -} diff --git a/src/libsok/sok-level-parser.c b/src/libsok/sok-level-parser.c deleted file mode 100644 index 276ebcb..0000000 --- a/src/libsok/sok-level-parser.c +++ /dev/null @@ -1,193 +0,0 @@ -#include <stdbool.h> -#include <stddef.h> // size_t -#include "sok.h" - -#define UNUSED(a) ((void) (a)) - -#define IS_DIGIT(c) ((c) >= '0' && (c) <= '9') -#define CASE_DIGIT \ - case '0': \ - case '1': \ - case '2': \ - case '3': \ - case '4': \ - case '5': \ - case '6': \ - case '7': \ - case '8': \ - case '9': - -void -sok_level_parser_init( - sok_level_parser_t * const parser, - const sok_level_parser_cbs_t * const cbs, - void * const user_data -) { - parser->cbs = cbs; - parser->user_data = user_data; -} - -bool -sok_level_parser_parse( - sok_level_parser_t * const parser, - const char * const buf, - const size_t buf_len -) { - sok_pos_t size = { .x = 0, .y = 0 }; - - for (size_t i = 0, ofs = 0, w = 0; i < buf_len; i++) { - if (buf[i] == '|') { - if (w > size.x) { - size.x = w; - } - - // reset column position, increment row count - w = 0; - size.y++; - } else if (IS_DIGIT(buf[i])) { - ofs = 10 * ofs + (buf[i] - '0'); - } else if (ofs > 0) { - w += ofs; - ofs = 0; - } else { - w++; - } - } - - // increment row count - size.y++; - - // emit level size - if ( - parser->cbs->on_size && - !parser->cbs->on_size(parser, size) - ) { - // return failure - return false; - } - - sok_pos_t pos = { 0, 0 }; - for (size_t i = 0, ofs = 0; i < buf_len; i++) { - switch (buf[i]) { - case '|': - // new line - pos.x = 0; - pos.y++; - - break; - CASE_DIGIT - ofs = 10 * ofs + (buf[i] - '0'); - break; - case '-': - case '_': - case ' ': - // advance - pos.x += (ofs > 0) ? ofs : 1; - ofs = 0; - - break; - case '+': - // emit goal - if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { - // return failure - return false; - } - - // emit home - if (parser->cbs->on_home && !parser->cbs->on_home(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - - break; - case '@': - // emit home - if (parser->cbs->on_home && !parser->cbs->on_home(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - - break; - case '#': - for (size_t j = (ofs > 0) ? ofs : 1; j; j--) { - // emit wall - if (parser->cbs->on_wall && !parser->cbs->on_wall(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - } - ofs = 0; - - break; - case '*': - for (size_t j = (ofs > 0) ? ofs : 1; j--;) { - // emit goal - if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { - // return failure - return false; - } - - // emit box - if (parser->cbs->on_box && !parser->cbs->on_box(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - } - ofs = 0; - - break; - case '.': - for (size_t j = (ofs > 0) ? ofs : 1; j--;) { - // emit goal - if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - } - ofs = 0; - - break; - case '$': - for (size_t j = (ofs > 0) ? ofs : 1; j--;) { - // emit box - if (parser->cbs->on_box && !parser->cbs->on_box(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - } - ofs = 0; - - break; - default: - // emit junk - if (parser->cbs->on_junk && !parser->cbs->on_junk(parser, i, buf[i])) { - // return failure - return false; - } - - // return failure - return false; - } - } - - // return success - return true; -} diff --git a/src/libsok/sok-solve.c b/src/libsok/sok-solve.c deleted file mode 100644 index 34a8320..0000000 --- a/src/libsok/sok-solve.c +++ /dev/null @@ -1,89 +0,0 @@ -#include <stdbool.h> -#include "sok.h" - -#define UNUSED(a) ((void) (a)) - -static bool -sok_solve_step( - sok_ctx_t * const ctx, - sok_cache_t * const cache, - void (*on_error)(const char * const) -) { - // check for success - if (sok_ctx_is_done(ctx)) { - // return success - return true; - } - - if (sok_cache_has(cache, ctx)) { - // return failure - return false; - } - - // add to cache - if (!sok_cache_add(cache, ctx)) { - if (on_error) { - // log error - on_error("sok_cache_add() failed"); - } - - // return failure - return false; - } - -/* - * // make sure level is solvable - * if (sok_ctx_is_lost(ctx)) { - * // return failure - * return false; - * } - */ - - for (size_t dir = 0; dir < SOK_DIR_LAST; dir++) { - if (!sok_ctx_move(ctx, dir)) { - continue; - } - - // recurse, check for success - if (sok_solve_step(ctx, cache, on_error)) { - // return success - return true; - } - - // undo move - if (!sok_ctx_undo(ctx)) { - if (on_error) { - // log error - on_error("sok_ctx_undo() failed"); - } - - // return failure - return false; - } - } - - // return failure - return false; -} - -bool -sok_solve( - sok_ctx_t * const ctx, - void (*on_error)(const char * const) -) { - // init cache - sok_cache_t cache; - if (!sok_cache_init(&cache, SOK_CACHE_DEFAULT_CAPACITY)) { - on_error("sok_cache_init() failed"); - return false; - } - - // solve - const bool r = sok_solve_step(ctx, &cache, on_error); - - // finalize cache - sok_cache_fini(&cache); - - // return result - return r; -} diff --git a/src/libsok/sok.h b/src/libsok/sok.h deleted file mode 100644 index 1503b5f..0000000 --- a/src/libsok/sok.h +++ /dev/null @@ -1,257 +0,0 @@ -#ifndef SOK_H -#define SOK_H - -#ifdef __cplusplus -extern "C" { -#endif /* __cplusplus */ - -#include <stdint.h> // uint16_t -#include <stddef.h> // size_t - -/*********/ -/* types */ -/*********/ - -typedef struct { - uint16_t x, y; -} sok_pos_t; - -typedef enum { - SOK_DIR_RIGHT, - SOK_DIR_UP, - SOK_DIR_LEFT, - SOK_DIR_DOWN, - SOK_DIR_LAST, -} sok_dir_t; - -#define SOK_DIR_TO_CHAR(dir) ( \ - ((dir) == SOK_DIR_RIGHT) ? 'r' : \ - (((dir) == SOK_DIR_UP) ? 'u' : \ - ((((dir) == SOK_DIR_LEFT) ? 'l' : \ - (((((dir) == SOK_DIR_DOWN) ? 'd' : \ - 'X' \ -))))))) - - -#define SOK_DIR_TO_STR(dir) ( \ - ((dir) == SOK_DIR_RIGHT) ? "r" : \ - (((dir) == SOK_DIR_UP) ? "u" : \ - ((((dir) == SOK_DIR_LEFT) ? "l" : \ - (((((dir) == SOK_DIR_DOWN) ? "d" : \ - "X" \ -))))))) - -typedef struct { - sok_pos_t pos; - sok_dir_t dir; - _Bool is_push; -} sok_move_t; - -/****************/ -/* level parser */ -/****************/ - -typedef struct sok_level_parser_t_ sok_level_parser_t; - -typedef _Bool (*sok_level_parser_pos_cb_t)( - const sok_level_parser_t * const, - const sok_pos_t -); - -typedef _Bool (*sok_level_parser_junk_cb_t)( - const sok_level_parser_t * const, - const size_t, - const char -); - -typedef struct { - sok_level_parser_pos_cb_t on_size, - on_home, - on_wall, - on_goal, - on_box; - sok_level_parser_junk_cb_t on_junk; -} sok_level_parser_cbs_t; - -struct sok_level_parser_t_ { - const sok_level_parser_cbs_t *cbs; - void *user_data; -}; - -void sok_level_parser_init( - sok_level_parser_t * const parser, - const sok_level_parser_cbs_t * const cbs, - void * const user_data -); - -_Bool sok_level_parser_parse( - sok_level_parser_t * const parser, - const char * const buf, - const size_t buf_len -); - -/*********/ -/* level */ -/*********/ - -#define SOK_LEVEL_MAX_WIDTH (1 << 8) -#define SOK_LEVEL_MAX_HEIGHT (1 << 8) -#define SOK_LEVEL_MAX_BOXES 64 -#define SOK_LEVEL_MAX_GOALS 64 - -typedef struct { - sok_pos_t size; - _Bool walls[SOK_LEVEL_MAX_WIDTH * SOK_LEVEL_MAX_HEIGHT]; - - // player home position - sok_pos_t home; - - // boxes - sok_pos_t boxes[SOK_LEVEL_MAX_BOXES]; - size_t num_boxes; - - // goals - sok_pos_t goals[SOK_LEVEL_MAX_GOALS]; - size_t num_goals; -} sok_level_t; - -/***********/ -/* context */ -/***********/ - -#define SOK_CTX_MAX_MOVES 1024 - -typedef struct { - sok_level_t level; - - // moves - sok_move_t moves[SOK_CTX_MAX_MOVES]; - size_t num_moves; - - // number of open goals - size_t num_goals_left; - - // are there boxes in corners? - // _Bool is_lost; - - // player position - sok_pos_t home; - - // box positions - sok_pos_t boxes[SOK_LEVEL_MAX_BOXES]; - - // user data - void *user_data; -} sok_ctx_t; - -void sok_ctx_init(sok_ctx_t * const ctx, void *user_data); - -_Bool sok_ctx_set_level(sok_ctx_t * const ctx, const char * const level); - -_Bool sok_ctx_is_done(const sok_ctx_t * const); -// _Bool sok_ctx_is_lost(const sok_ctx_t * const); - -_Bool sok_ctx_move(sok_ctx_t * const, const sok_dir_t); -_Bool sok_ctx_undo(sok_ctx_t * const); - -/******************/ -/* context walker */ -/******************/ - -typedef _Bool (*sok_ctx_walk_step_cb_t)( - const sok_ctx_t * const, - void * const -); - -typedef _Bool (*sok_ctx_walk_pos_cb_t)( - const sok_ctx_t * const, - const sok_pos_t, - void * const -); - -typedef _Bool (*sok_ctx_walk_tile_cb_t)( - const sok_ctx_t * const, - const sok_pos_t, - const _Bool, - void * const -); - -typedef _Bool (*sok_ctx_walk_goal_cb_t)( - const sok_ctx_t * const, - const sok_pos_t, - const _Bool has_player, - const _Bool has_box, - void * const -); - -typedef _Bool (*sok_ctx_walk_move_cb_t)( - const sok_ctx_t * const, - const sok_move_t, - void * const -); - -typedef struct { - sok_ctx_walk_pos_cb_t on_size; - - sok_ctx_walk_step_cb_t on_walls_start, - on_walls_end; - sok_ctx_walk_pos_cb_t on_wall; - - sok_ctx_walk_tile_cb_t on_home; - - sok_ctx_walk_step_cb_t on_boxes_start, - on_boxes_end; - sok_ctx_walk_tile_cb_t on_box; - - sok_ctx_walk_step_cb_t on_goals_start, - on_goals_end; - sok_ctx_walk_goal_cb_t on_goal; - - sok_ctx_walk_step_cb_t on_moves_start, - on_moves_end; - sok_ctx_walk_move_cb_t on_move; -} sok_ctx_walk_cbs_t; - -_Bool sok_ctx_walk( - const sok_ctx_t * const, - const sok_ctx_walk_cbs_t * const, - void * const -); - -/****************/ -/* context hash */ -/****************/ - -uint64_t sok_ctx_hash(const sok_ctx_t * const); - -/*********/ -/* cache */ -/*********/ - -#define SOK_CACHE_DEFAULT_CAPACITY 1024 - -typedef struct { - uint64_t *vals; - size_t num_vals, capacity; -} sok_cache_t; - -_Bool sok_cache_init(sok_cache_t * const, const size_t); -void sok_cache_fini(sok_cache_t * const); - -_Bool sok_cache_has(const sok_cache_t * const, const sok_ctx_t * const); -_Bool sok_cache_add(sok_cache_t * const, const sok_ctx_t * const); - -/*********/ -/* solve */ -/*********/ - -_Bool sok_solve( - sok_ctx_t * const, - void (*on_error)(const char * const) -); - -#ifdef __cplusplus -}; -#endif /* __cplusplus */ - -#endif /* SOK_H */ |