day 12 complete, memoization utility added

4 files changed, 79 insertions, 9 deletions

diff --git a/aoc2023/src/day12/solve.gleam b/aoc2023/src/day12/solve.gleam
index 578fa5f..06c7098 100644
--- a/aoc2023/src/day12/solve.gleam
+++ b/aoc2023/src/day12/solve.gleam
@@ -4,7 +4,10 @@ import gleam/string
 import gleam/list
 import gleam/int
 import gleam/result
-import gleam/dict.{type Dict}
+import utilities/memo.{type Cache}
+
+type ParserState =
+  #(String, List(Int), Int, Bool)
 
 fn parse_folds(input: String, folds: Int) {
   let records = string.split(input, "\n")
@@ -27,27 +30,35 @@ fn parse_folds(input: String, folds: Int) {
   #(template, sets)
 }
 
-fn do_count(template: String, groups: List(Int), left: Int, gap: Bool) -> Int {
+fn do_count(
+  template: String,
+  groups: List(Int),
+  left: Int,
+  gap: Bool,
+  cache: Cache(ParserState, Int),
+) -> Int {
+  use <- memo.memoize(cache, #(template, groups, left, gap))
   case template, groups, left, gap {
     "", [], 0, _ -> 1
     "?" <> t_rest, [g, ..g_rest], 0, False ->
-      do_count(t_rest, g_rest, g - 1, g == 1) + {
-        do_count(t_rest, groups, 0, False)
+      do_count(t_rest, g_rest, g - 1, g == 1, cache) + {
+        do_count(t_rest, groups, 0, False, cache)
       }
     "?" <> t_rest, [], 0, False
     | "?" <> t_rest, _, 0, True
-    | "." <> t_rest, _, 0, _ -> do_count(t_rest, groups, 0, False)
+    | "." <> t_rest, _, 0, _ -> do_count(t_rest, groups, 0, False, cache)
     "#" <> t_rest, [g, ..g_rest], 0, False ->
-      do_count(t_rest, g_rest, g - 1, g == 1)
+      do_count(t_rest, g_rest, g - 1, g == 1, cache)
     "?" <> t_rest, gs, l, False | "#" <> t_rest, gs, l, False ->
-      do_count(t_rest, gs, l - 1, l == 1)
+      do_count(t_rest, gs, l - 1, l == 1, cache)
     _, _, _, _ -> 0
   }
 }
 
 fn count_solutions(acc: Int, condition: #(String, List(Int))) -> Int {
+  use cache: Cache(ParserState, Int) <- memo.create()
   let #(template, groups) = condition
-  acc + do_count(template, groups, 0, False)
+  acc + do_count(template, groups, 0, False, cache)
 }
 
 pub fn part1(input: String) {
diff --git a/aoc2023/src/day8/solve.gleam b/aoc2023/src/day8/solve.gleam
index cbd2f6a..6b36e2d 100644
--- a/aoc2023/src/day8/solve.gleam
+++ b/aoc2023/src/day8/solve.gleam
@@ -17,7 +17,7 @@ type Maze =
   Dict(String, Paths)
 
 fn parse(input: String) -> #(Iterator(String), Dict(String, Paths)) {
-  let [directions_str, maze_str] = string.split(input, "\n\n")
+  let assert [directions_str, maze_str] = string.split(input, "\n\n")
 
   let directions =
     directions_str
@@ -52,6 +52,7 @@ fn to_next_step(
   case next_direction {
     "L" -> paths.to_left
     "R" -> paths.to_right
+    _ -> panic as "bad direction"
   }
   |> to_next_step(stop_at, count + 1, rest_directions, maze)
 }
diff --git a/aoc2023/src/day9/solve.gleam b/aoc2023/src/day9/solve.gleam
index ce061ae..a2cc7ae 100644
--- a/aoc2023/src/day9/solve.gleam
+++ b/aoc2023/src/day9/solve.gleam
@@ -35,6 +35,7 @@ fn extrapolate(ns: List(Int)) {
   case is_constant(ns), ns {
     True, [n, ..] -> n
     False, [n, ..] -> n + extrapolate(take_derivative(ns))
+    _, _ -> panic as "list empty when it shouldn't be"
   }
 }
 
diff --git a/aoc2023/src/utilities/memo.gleam b/aoc2023/src/utilities/memo.gleam
new file mode 100644
index 0000000..87ee475
--- /dev/null
+++ b/aoc2023/src/utilities/memo.gleam
@@ -0,0 +1,57 @@
+import gleam/dict.{type Dict}
+import gleam/otp/actor.{type Next, Continue, Stop}
+import gleam/erlang/process.{type Subject, Normal}
+import gleam/option.{None}
+
+const timeout = 1000
+
+type Message(k, v) {
+  Shutdown
+  Get(key: k, client: Subject(Result(v, Nil)))
+  Set(key: k, value: v)
+}
+
+type Server(k, v) =
+  Subject(Message(k, v))
+
+fn handle_message(
+  message: Message(k, v),
+  dict: Dict(k, v),
+) -> Next(Message(k, v), Dict(k, v)) {
+  case message {
+    Shutdown -> Stop(Normal)
+    Get(key, client) -> {
+      process.send(client, dict.get(dict, key))
+      Continue(dict, None)
+    }
+    Set(key, value) -> Continue(dict.insert(dict, key, value), None)
+  }
+}
+
+pub opaque type Cache(k, v) {
+  Cache(server: Server(k, v))
+}
+
+pub fn create(apply fun: fn(Cache(k, v)) -> t) -> t {
+  let assert Ok(server) = actor.start(dict.new(), handle_message)
+  let result = fun(Cache(server))
+  process.send(server, Shutdown)
+  result
+}
+
+pub fn set(in cache: Cache(k, v), for key: k, insert value: v) -> Nil {
+  process.send(cache.server, Set(key, value))
+}
+
+pub fn get(from cache: Cache(k, v), fetch key: k) -> Result(v, Nil) {
+  process.call(cache.server, fn(c) { Get(key, c) }, timeout)
+}
+
+pub fn memoize(with cache: Cache(k, v), this key: k, apply fun: fn() -> v) -> v {
+  let result = case get(from: cache, fetch: key) {
+    Ok(value) -> value
+    Error(Nil) -> fun()
+  }
+  set(in: cache, for: key, insert: result)
+  result
+}