diff options
author | Hunky Jimpjorps <thechairman@thechairman.info> | 2023-12-12 06:14:55 -0500 |
---|---|---|
committer | Hunky Jimpjorps <thechairman@thechairman.info> | 2023-12-12 06:14:55 -0500 |
commit | 6a634c91145fab5b8ddb3af79c393607cd6272b6 (patch) | |
tree | 8f197820b1dfd91ef3e5b9d90c101d95ba5203b8 /aoc2023/src | |
parent | 3587c46e155ff45aecfb728c29f14e9c8a108095 (diff) | |
download | gleam_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.gleam | 27 | ||||
-rw-r--r-- | aoc2023/src/day8/solve.gleam | 3 | ||||
-rw-r--r-- | aoc2023/src/day9/solve.gleam | 1 | ||||
-rw-r--r-- | aoc2023/src/utilities/memo.gleam | 57 |
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 +} |