aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/libsok/sok-cache.c135
-rw-r--r--src/libsok/sok-ctx.c400
-rw-r--r--src/libsok/sok-solve.c77
-rw-r--r--src/libsok/sok.h27
4 files changed, 326 insertions, 313 deletions
diff --git a/src/libsok/sok-cache.c b/src/libsok/sok-cache.c
new file mode 100644
index 0000000..748614e
--- /dev/null
+++ b/src/libsok/sok-cache.c
@@ -0,0 +1,135 @@
+#include <stdbool.h> // bool
+#include <stdint.h> // uint64_t
+#include <stdlib.h> // bsearch(), qsort()
+#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 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);
+ 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
+) {
+ return !!bsearch(
+ &hash,
+ cache->vals,
+ cache->num_vals,
+ sizeof(uint64_t),
+ u64_cmp
+ );
+}
+
+bool
+sok_cache_has(
+ const sok_cache_t * const cache,
+ const sok_ctx_t * const ctx
+) {
+ return sok_cache_has_hash(cache, hash_ctx(ctx));
+}
+
+bool
+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;
+ }
+
+ // check capacity
+ if (cache->num_vals >= cache->capacity) {
+ // grow cache
+ if (!sok_cache_grow(cache)) {
+ // return failure
+ return false;
+ }
+ }
+
+ // append hash, sort values
+ cache->vals[cache->num_vals++] = hash_ctx(ctx);
+ qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp);
+
+ // 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(sizeof(uint64_t) * capacity);
+ 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.c b/src/libsok/sok-ctx.c
index cc6b1ce..d9985d7 100644
--- a/src/libsok/sok-ctx.c
+++ b/src/libsok/sok-ctx.c
@@ -191,116 +191,37 @@ tile_is_floor(
);
}
-static bool
-tile_is_box(
- const sok_ctx_t * const ctx,
- const sok_pos_t pos
+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 < ctx->level.num_boxes; i++) {
- if (POINTS_EQUAL(ctx->boxes[i], pos)) {
- return true;
+ for (size_t i = 0; i < len; i++) {
+ if (POINTS_EQUAL(pos, set[i])) {
+ return i;
}
}
- return false;
+ return len;
}
static bool
-tile_is_goal(
+tile_is_box(
const sok_ctx_t * const ctx,
const sok_pos_t pos
) {
- for (size_t i = 0; i < ctx->level.num_goals; i++) {
- if (POINTS_EQUAL(pos, ctx->level.goals[i])) {
- return true;
- }
- }
-
- return false;
+ const size_t num_boxes = ctx->level.num_boxes;
+ return pos_find(pos, ctx->boxes, num_boxes) < num_boxes;
}
static bool
-sok_can_move(
- sok_ctx_t * const ctx,
- const sok_dir_t dir
+tile_is_goal(
+ const sok_ctx_t * const ctx,
+ const sok_pos_t pos
) {
- if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) {
- // no more move slots available
- return false;
- }
-
- if (dir == SOK_DIR_UP) {
- const sok_pos_t ps[2] = {
- { .x = ctx->home.x, .y = ctx->home.y - 1 },
- { .x = ctx->home.x, .y = ctx->home.y - 2 },
- };
-
- return ((
- (ctx->home.y > 0) &&
- tile_is_floor(ctx, ps[0]) &&
- !tile_is_box(ctx, ps[0])
- ) || (
- (ctx->home.y > 1) &&
- tile_is_floor(ctx, ps[0]) &&
- tile_is_box(ctx, ps[0]) &&
- tile_is_floor(ctx, ps[1]) &&
- !tile_is_box(ctx, ps[1])
- ));
- } else if (dir == SOK_DIR_DOWN) {
- const sok_pos_t ps[2] = {
- { .x = ctx->home.x, .y = ctx->home.y + 1 },
- { .x = ctx->home.x, .y = ctx->home.y + 2 },
- };
-
- return ((
- (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 1) &&
- tile_is_floor(ctx, ps[0]) &&
- !tile_is_box(ctx, ps[0])
- ) || (
- (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 2) &&
- tile_is_floor(ctx, ps[0]) &&
- tile_is_box(ctx, ps[0]) &&
- tile_is_floor(ctx, ps[1]) &&
- !tile_is_box(ctx, ps[1])
- ));
- } else if (dir == SOK_DIR_LEFT) {
- const sok_pos_t ps[2] = {
- { .x = ctx->home.x - 1, .y = ctx->home.y },
- { .x = ctx->home.x - 2, .y = ctx->home.y },
- };
-
- return ((
- (ctx->home.x > 0) &&
- tile_is_floor(ctx, ps[0]) &&
- !tile_is_box(ctx, ps[0])
- ) || (
- (ctx->home.x > 1) &&
- tile_is_floor(ctx, ps[0]) &&
- tile_is_box(ctx, ps[0]) &&
- tile_is_floor(ctx, ps[1]) &&
- !tile_is_box(ctx, ps[1])
- ));
- } else if (dir == SOK_DIR_RIGHT) {
- const sok_pos_t ps[2] = {
- { .x = ctx->home.x + 1, .y = ctx->home.y },
- { .x = ctx->home.x + 2, .y = ctx->home.y },
- };
-
- return ((
- (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 1) &&
- tile_is_floor(ctx, ps[0]) &&
- !tile_is_box(ctx, ps[0])
- ) || (
- (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 2) &&
- tile_is_floor(ctx, ps[0]) &&
- tile_is_box(ctx, ps[0]) &&
- tile_is_floor(ctx, ps[1]) &&
- !tile_is_box(ctx, ps[1])
- ));
- }
-
- // return failure
- return false;
+ const size_t num_goals = ctx->level.num_goals;
+ return pos_find(pos, ctx->level.goals, num_goals) < num_goals;
}
static bool
@@ -349,11 +270,12 @@ sok_ctx_move_box(
const sok_pos_t old_pos,
const sok_pos_t new_pos
) {
- for (size_t i = 0; i < ctx->level.num_boxes; i++) {
- if (POINTS_EQUAL(ctx->boxes[i], old_pos)) {
- ctx->boxes[i] = new_pos;
- return true;
- }
+ const size_t num_boxes = ctx->level.num_boxes,
+ box_ofs = pos_find(old_pos, ctx->boxes, num_boxes);
+
+ if (box_ofs < num_boxes) {
+ ctx->boxes[box_ofs] = new_pos;
+ return true;
}
return false;
@@ -364,17 +286,7 @@ sok_ctx_is_done(
sok_ctx_t * const ctx
) {
for (size_t i = 0; i < ctx->level.num_goals; i++) {
- bool on_goal = false;
-
- for (size_t j = 0; !on_goal && j < ctx->level.num_boxes; j++) {
- if (POINTS_EQUAL(ctx->level.goals[i], ctx->boxes[j])) {
- // found box on this goal
- on_goal = true;
- }
- }
-
- if (!on_goal) {
- // no box on this goal, return false
+ if (!tile_is_box(ctx, ctx->level.goals[i])) {
return false;
}
}
@@ -388,186 +300,75 @@ sok_ctx_move(
sok_ctx_t * const ctx,
const sok_dir_t dir
) {
- if (!sok_can_move(ctx, dir)) {
+ if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) {
+ // no more move slots available
return false;
}
- if (dir == SOK_DIR_UP) {
- const sok_pos_t ps[2] = {
- { .x = ctx->home.x, .y = ctx->home.y - 1 },
- { .x = ctx->home.x, .y = ctx->home.y - 2 },
- };
-
- if (
- (ctx->home.y > 0) &&
- 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.y--;
-
- // return success
- return true;
- } else if (
- (ctx->home.y > 1) &&
- 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.y--;
-
- // return success
- return true;
+ 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;
}
- } else if (dir == SOK_DIR_DOWN) {
- const sok_pos_t ps[2] = {
- { .x = ctx->home.x, .y = ctx->home.y + 1 },
- { .x = ctx->home.x, .y = ctx->home.y + 2 },
- };
- if (
- (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 1) &&
- 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.y++;
-
- // return success
- return true;
- } else if (
- (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 2) &&
- 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.y++;
-
- // return success
- return true;
+ // 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;
}
- } else if (dir == SOK_DIR_LEFT) {
- const sok_pos_t ps[2] = {
- { .x = ctx->home.x - 1, .y = ctx->home.y },
- { .x = ctx->home.x - 2, .y = ctx->home.y },
- };
-
- if (
- (ctx->home.x > 1) &&
- 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--;
-
- // return success
- return true;
- } else if (
- (ctx->home.x > 1) &&
- 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--;
-
- // return success
- return true;
+ // move box
+ if (!sok_ctx_move_box(ctx, ps[0], ps[1])) {
+ return false;
}
- } else if (dir == SOK_DIR_RIGHT) {
- const sok_pos_t ps[2] = {
- { .x = ctx->home.x + 1, .y = ctx->home.y },
- { .x = ctx->home.x + 2, .y = ctx->home.y },
- };
-
- if (
- (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 1) &&
- 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++;
-
- // return success
- return true;
- } else if (
- (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 2) &&
- 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);
- // update position
- ctx->home.x++;
- // return success
- return true;
- }
+ // return success
+ return true;
}
// return failure
@@ -585,39 +386,12 @@ sok_ctx_undo(
}
if (move.is_push) {
- switch (move.dir) {
- case SOK_DIR_UP:
- {
- const sok_pos_t box_pos = { move.pos.x, move.pos.y - 2 };
- sok_ctx_move_box(ctx, box_pos, ctx->home);
- }
-
- break;
- case SOK_DIR_DOWN:
- {
- const sok_pos_t box_pos = { move.pos.x, move.pos.y + 2 };
- sok_ctx_move_box(ctx, box_pos, ctx->home);
- }
-
- break;
- case SOK_DIR_LEFT:
- {
- const sok_pos_t box_pos = { move.pos.x - 2, move.pos.y };
- sok_ctx_move_box(ctx, box_pos, ctx->home);
- }
-
- break;
- case SOK_DIR_RIGHT:
- {
- const sok_pos_t box_pos = { move.pos.x + 2, move.pos.y };
- sok_ctx_move_box(ctx, box_pos, ctx->home);
- }
+ 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)),
+ };
- break;
- default:
- // never reached
- return false;
- }
+ sok_ctx_move_box(ctx, box_pos, ctx->home);
}
// update position
diff --git a/src/libsok/sok-solve.c b/src/libsok/sok-solve.c
new file mode 100644
index 0000000..6637feb
--- /dev/null
+++ b/src/libsok/sok-solve.c
@@ -0,0 +1,77 @@
+#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)
+) {
+ 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;
+ }
+ }
+
+ 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
index 7635ead..074fbf6 100644
--- a/src/libsok/sok.h
+++ b/src/libsok/sok.h
@@ -6,6 +6,7 @@ extern "C" {
#endif /* __cplusplus */
#include <stdint.h> // uint16_t
+#include <stddef.h> // size_t
/*********/
/* types */
@@ -174,6 +175,32 @@ _Bool sok_ctx_walk(
void * 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 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 05:01:19 +0000