day 12 complete, memoization utility added

1 files changed, 19 insertions, 8 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) {