simplify move logic, add cache and solver

5 files changed, 328 insertions, 313 deletions

diff --git a/meson.build b/meson.build
index 9ae6cb6..1a52bbe 100644
--- a/meson.build
+++ b/meson.build
@@ -3,6 +3,8 @@ project('sok', 'c', default_options: ['c_std=c11'])
 sources = [
   'src/libsok/sok-level-parser.c',
   'src/libsok/sok-ctx.c',
+  'src/libsok/sok-cache.c',
+  'src/libsok/sok-solve.c',
 ]
 
 # text interface
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 */