aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/libsok/sok-cache.c53
-rw-r--r--src/libsok/sok-ctx-hash.c72
-rw-r--r--src/libsok/sok-solve.c50
-rw-r--r--src/libsok/sok.h12
-rw-r--r--src/text/main.c52
5 files changed, 191 insertions, 48 deletions
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;
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-21 19:39:51 +0000