aboutsummaryrefslogtreecommitdiff
path: root/aoc2023/src
diff options
context:
space:
mode:
authorHunky Jimpjorps <thechairman@thechairman.info>2023-12-12 06:14:55 -0500
committerHunky Jimpjorps <thechairman@thechairman.info>2023-12-12 06:14:55 -0500
commit6a634c91145fab5b8ddb3af79c393607cd6272b6 (patch)
tree8f197820b1dfd91ef3e5b9d90c101d95ba5203b8 /aoc2023/src
parent3587c46e155ff45aecfb728c29f14e9c8a108095 (diff)
downloadgleam_aoc-6a634c91145fab5b8ddb3af79c393607cd6272b6.tar.gz
gleam_aoc-6a634c91145fab5b8ddb3af79c393607cd6272b6.zip
day 12 complete, memoization utility added
Diffstat (limited to 'aoc2023/src')
-rw-r--r--aoc2023/src/day12/solve.gleam27
-rw-r--r--aoc2023/src/day8/solve.gleam3
-rw-r--r--aoc2023/src/day9/solve.gleam1
-rw-r--r--aoc2023/src/utilities/memo.gleam57
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
+}