diff options
| -rw-r--r-- | meson.build | 1 | ||||
| -rw-r--r-- | src/libsok/sok-cache.c | 53 | ||||
| -rw-r--r-- | src/libsok/sok-ctx-hash.c | 72 | ||||
| -rw-r--r-- | src/libsok/sok-solve.c | 50 | ||||
| -rw-r--r-- | src/libsok/sok.h | 12 | ||||
| -rw-r--r-- | src/text/main.c | 52 |
6 files changed, 192 insertions, 48 deletions
diff --git a/meson.build b/meson.build index 1a52bbe..110e0c0 100644 --- a/meson.build +++ b/meson.build @@ -3,6 +3,7 @@ project('sok', 'c', default_options: ['c_std=c11']) sources = [ 'src/libsok/sok-level-parser.c', 'src/libsok/sok-ctx.c', + 'src/libsok/sok-ctx-hash.c', 'src/libsok/sok-cache.c', 'src/libsok/sok-solve.c', ] diff --git a/src/libsok/sok-cache.c b/src/libsok/sok-cache.c index 748614e..261d6b9 100644 --- a/src/libsok/sok-cache.c +++ b/src/libsok/sok-cache.c @@ -1,23 +1,16 @@ #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)) -static uint64_t -hash_ctx( - const sok_ctx_t * const ctx -) { - UNUSED(ctx); - // TODO - return 0; -} - static int u64_cmp( - const void * const ap, + const void * const ap, const void * const bp ) { const uint64_t a = *((uint64_t*) ap), @@ -37,7 +30,7 @@ sok_cache_grow( } // reallocate memory - uint64_t * const vals = realloc(cache->vals, new_capacity); + uint64_t * const vals = realloc(cache->vals, new_capacity * sizeof(uint64_t)); if (!vals) { return false; } @@ -55,6 +48,16 @@ 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, @@ -62,6 +65,7 @@ sok_cache_has_hash( sizeof(uint64_t), u64_cmp ); +#endif /* 0 */ } bool @@ -69,7 +73,7 @@ sok_cache_has( const sok_cache_t * const cache, const sok_ctx_t * const ctx ) { - return sok_cache_has_hash(cache, hash_ctx(ctx)); + return sok_cache_has_hash(cache, sok_ctx_hash(ctx)); } bool @@ -77,13 +81,15 @@ sok_cache_add( sok_cache_t * const cache, const sok_ctx_t * const ctx ) { - // hash context - const uint64_t hash = hash_ctx(ctx); - - // check for duplicates - if (sok_cache_has_hash(cache, hash)) { - return true; - } +/* + * // 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) { @@ -94,8 +100,11 @@ sok_cache_add( } } - // append hash, sort values - cache->vals[cache->num_vals++] = hash_ctx(ctx); + // append hash + cache->vals[cache->num_vals] = sok_ctx_hash(ctx); + cache->num_vals++; + + // sort values qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp); // return success @@ -108,7 +117,7 @@ sok_cache_init( const size_t capacity ) { // alloc memory, check for error - uint64_t * const vals = malloc(sizeof(uint64_t) * capacity); + uint64_t * const vals = malloc(capacity * sizeof(uint64_t)); if (!vals) { // return failure return false; diff --git a/src/libsok/sok-ctx-hash.c b/src/libsok/sok-ctx-hash.c new file mode 100644 index 0000000..a3a32c7 --- /dev/null +++ b/src/libsok/sok-ctx-hash.c @@ -0,0 +1,72 @@ +#include <stdint.h> // uint16_t +#include <stdio.h> // debug +#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; +} + +#if 0 +uint64_t +sok_ctx_hash( + const sok_ctx_t * const ctx +) { + uint8_t buf[1024] = { + (ctx->home.x) & 0xff, + (ctx->home.x >> 16) & 0xff, + (ctx->home.y) & 0xff, + (ctx->home.y >> 16) & 0xff, + 0, + }; + + for (size_t i = 0; i < ctx->level.num_boxes; i++) { + buf[(4 * (i + 1) + 0)] = ctx->boxes[i].x & 0xff; + buf[(4 * (i + 1) + 1)] = (ctx->boxes[i].x >> 16) & 0xff; + buf[(4 * (i + 1) + 2)] = ctx->boxes[i].y & 0xff; + buf[(4 * (i + 1) + 3)] = (ctx->boxes[i].y >> 16) & 0xff; + } + + // 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); + + const uint64_t hash = fnv1a((uint8_t*) buf, len); + fprintf(stderr, "hash = %lx, used = %zu, len = %zu\n", hash, used, len); + return hash; +} +#endif /* 0 */ + +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-solve.c b/src/libsok/sok-solve.c index 6637feb..225ce9b 100644 --- a/src/libsok/sok-solve.c +++ b/src/libsok/sok-solve.c @@ -9,36 +9,40 @@ sok_solve_step( 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; + } + for (size_t dir = 0; dir < SOK_DIR_LAST; dir++) { if (!sok_ctx_move(ctx, dir)) { continue; } - if (!sok_cache_has(cache, ctx)) { - // check for success - if (sok_ctx_is_done(ctx)) { - // return success - return true; - } - - // add to cache - if (!sok_cache_add(cache, ctx)) { - if (on_error) { - // log error - on_error("sok_cache_add() failed"); - } - - // return failure - return false; - } - - // recurse, check for success - if (sok_solve_step(ctx, cache, on_error)) { - // return success - return true; - } + // 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 diff --git a/src/libsok/sok.h b/src/libsok/sok.h index 074fbf6..54e6c93 100644 --- a/src/libsok/sok.h +++ b/src/libsok/sok.h @@ -36,12 +36,12 @@ typedef struct { typedef struct sok_level_parser_t_ sok_level_parser_t; -typedef bool (*sok_level_parser_pos_cb_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)( +typedef _Bool (*sok_level_parser_junk_cb_t)( const sok_level_parser_t * const, const size_t, const char @@ -67,7 +67,7 @@ void sok_level_parser_init( void * const user_data ); -bool sok_level_parser_parse( +_Bool sok_level_parser_parse( sok_level_parser_t * const parser, const char * const buf, const size_t buf_len @@ -175,6 +175,12 @@ _Bool sok_ctx_walk( void * const ); +/****************/ +/* context hash */ +/****************/ + +uint64_t sok_ctx_hash(const sok_ctx_t * const); + /*********/ /* cache */ /*********/ diff --git a/src/text/main.c b/src/text/main.c index 80bdc65..de5b5f3 100644 --- a/src/text/main.c +++ b/src/text/main.c @@ -752,6 +752,42 @@ print_level( printf("%s\n", print_buf); } +static void +solve_on_error( + const char * const err +) { + fprintf(stderr, "Error solving level: %s\n", err); + exit(EXIT_FAILURE); +} + +static void +print_moves( + const sok_ctx_t * const ctx, + const size_t skip_moves +) { + printf("Moves (%zu): ", ctx->num_moves - skip_moves); + for (size_t i = skip_moves; i < ctx->num_moves; i++) { + switch (ctx->moves[i].dir) { + case SOK_DIR_UP: + fputs("u", stdout); + break; + case SOK_DIR_DOWN: + fputs("d", stdout); + break; + case SOK_DIR_LEFT: + fputs("l", stdout); + break; + case SOK_DIR_RIGHT: + fputs("r", stdout); + break; + default: + fprintf(stderr, "Error: invalid move: %u", ctx->moves[i].dir); + exit(EXIT_FAILURE); + } + } + printf("\n"); +} + int main(int argc, char *argv[]) { size_t level = (argc > 1) ? atoi(argv[1]) : 0; @@ -836,6 +872,22 @@ int main(int argc, char *argv[]) { return EXIT_FAILURE; } } + + break; + case 's': + { + // get current number of moves + const size_t old_num_moves = ctx.num_moves; + + if (sok_solve(&ctx, solve_on_error)) { + // found solution, print it + print_moves(&ctx, old_num_moves); + } else { + fprintf(stderr, "W: Couldn't solve level\n"); + } + } + + break; default: // ignore break; |