day 12 complete, memoization utility added

6 files changed, 84 insertions, 12 deletions

diff --git a/aoc2023/gleam.toml b/aoc2023/gleam.toml
index 8fc812a..8e0eb9c 100644
--- a/aoc2023/gleam.toml
+++ b/aoc2023/gleam.toml
@@ -15,6 +15,7 @@ gleam_stdlib = "~> 0.32"
 simplifile = "~> 1.0"
 gleam_erlang = "~> 0.23"
 gleam_community_maths = "~> 1.0"
+gleam_otp = "~> 0.8"
 
 [dev-dependencies]
 gleeunit = "~> 1.0"
diff --git a/aoc2023/manifest.toml b/aoc2023/manifest.toml
index 8e87d48..5e75cac 100644
--- a/aoc2023/manifest.toml
+++ b/aoc2023/manifest.toml
@@ -2,9 +2,9 @@
 # You typically do not need to edit this file
 
 packages = [
-  { name = "adglent", version = "1.2.0", build_tools = ["gleam"], requirements = ["simplifile", "gleam_otp", "gleam_erlang", "gleam_community_ansi", "tom", "gleam_httpc", "gleam_http", "snag", "gleam_stdlib", "glint", "gap"], otp_app = "adglent", source = "hex", outer_checksum = "A20D35001061F8AD602E3B92FB3AC0E1E4EEC642AD2AAE0ACEAD3A85F37DA7F0" },
+  { name = "adglent", version = "1.2.0", build_tools = ["gleam"], requirements = ["gap", "gleam_erlang", "gleam_community_ansi", "gleam_httpc", "glint", "gleam_http", "simplifile", "tom", "snag", "gleam_otp", "gleam_stdlib"], otp_app = "adglent", source = "hex", outer_checksum = "A20D35001061F8AD602E3B92FB3AC0E1E4EEC642AD2AAE0ACEAD3A85F37DA7F0" },
   { name = "gap", version = "1.0.1", build_tools = ["gleam"], requirements = ["gleam_community_ansi", "gleam_stdlib"], otp_app = "gap", source = "hex", outer_checksum = "5E369751DB547BFBDA7735878DC04DA31FCA3112193D61D5D7566010C7C8BA98" },
-  { name = "gleam_community_ansi", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_community_colour", "gleam_stdlib"], otp_app = "gleam_community_ansi", source = "hex", outer_checksum = "8B5A9677BC5A2738712BBAF2BA289B1D8195FDF962BBC769569976AD5E9794E1" },
+  { name = "gleam_community_ansi", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_community_colour"], otp_app = "gleam_community_ansi", source = "hex", outer_checksum = "8B5A9677BC5A2738712BBAF2BA289B1D8195FDF962BBC769569976AD5E9794E1" },
   { name = "gleam_community_colour", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_community_colour", source = "hex", outer_checksum = "036C206886AFB9F153C552700A7A0B4D2864E3BC96A20C77E5F34A013C051BE3" },
   { name = "gleam_community_maths", version = "1.0.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_community_maths", source = "hex", outer_checksum = "1B9DB313E94A0E4674CA84C5D29F45ECFE211BFB38ABBD8B23737395F47D08B3" },
   { name = "gleam_erlang", version = "0.23.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_erlang", source = "hex", outer_checksum = "C21CFB816C114784E669FFF4BBF433535EEA9960FA2F216209B8691E87156B96" },
@@ -13,7 +13,7 @@ packages = [
   { name = "gleam_otp", version = "0.8.0", build_tools = ["gleam"], requirements = ["gleam_erlang", "gleam_stdlib"], otp_app = "gleam_otp", source = "hex", outer_checksum = "18EF8242A5E54BA92F717C7222F03B3228AEE00D1F286D4C56C3E8C18AA2588E" },
   { name = "gleam_stdlib", version = "0.33.0", build_tools = ["gleam"], requirements = [], otp_app = "gleam_stdlib", source = "hex", outer_checksum = "539E37A2AA5EBE8E75F4B74755E4CC604BD957C3000AC8D705A2024886A2738B" },
   { name = "gleeunit", version = "1.0.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleeunit", source = "hex", outer_checksum = "D3682ED8C5F9CAE1C928F2506DE91625588CC752495988CBE0F5653A42A6F334" },
-  { name = "glint", version = "0.13.0", build_tools = ["gleam"], requirements = ["gleam_community_ansi", "gleam_community_colour", "snag", "gleam_stdlib"], otp_app = "glint", source = "hex", outer_checksum = "46E56049CD370D61F720D319D0AB970408C9336EEB918F08B5DCB1DCE9845FA3" },
+  { name = "glint", version = "0.13.0", build_tools = ["gleam"], requirements = ["gleam_community_colour", "gleam_stdlib", "gleam_community_ansi", "snag"], otp_app = "glint", source = "hex", outer_checksum = "46E56049CD370D61F720D319D0AB970408C9336EEB918F08B5DCB1DCE9845FA3" },
   { name = "simplifile", version = "1.0.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "simplifile", source = "hex", outer_checksum = "0BD6F0E7DA1A7E11D18B8AD48453225CAFCA4C8CFB4513D217B372D2866C501C" },
   { name = "snag", version = "0.2.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "snag", source = "hex", outer_checksum = "8FD70D8FB3728E08AC425283BB509BB0F012BE1AE218424A597CDE001B0EE589" },
   { name = "tom", version = "0.2.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "tom", source = "hex", outer_checksum = "5C5A9B8586C547F1F39542B1A3BBD9FEE17AFEAB51CE53B32B13D0D46B421249" },
@@ -23,6 +23,7 @@ packages = [
 adglent = { version = "~> 1.2" }
 gleam_community_maths = { version = "~> 1.0" }
 gleam_erlang = { version = "~> 0.23" }
+gleam_otp = { version = "~> 0.8" }
 gleam_stdlib = { version = "~> 0.32" }
 gleeunit = { version = "~> 1.0" }
 simplifile = { version = "~> 1.0" }
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
+}