aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJ.J <thechairman@thechairman.info>2023-12-23 15:24:05 -0500
committerJ.J <thechairman@thechairman.info>2023-12-23 15:24:05 -0500
commiteb492eea3adbba1995d870c6c4a9c22d09a4c96f (patch)
tree1c1cb795dbe362eefa6ce58a4fd5ecbf85212d77
parent75b519b90cbdae6cba83e60c1fe6f5ac27132e4b (diff)
downloadgleam_aoc-eb492eea3adbba1995d870c6c4a9c22d09a4c96f.tar.gz
gleam_aoc-eb492eea3adbba1995d870c6c4a9c22d09a4c96f.zip
day 23 gleam complete
-rw-r--r--aoc2023/src/day23/solve.gleam181
-rw-r--r--aoc2023/src/utilities/array2d.gleam28
-rw-r--r--aoc2023/test/day23/day23_test.gleam62
3 files changed, 263 insertions, 8 deletions
diff --git a/aoc2023/src/day23/solve.gleam b/aoc2023/src/day23/solve.gleam
index 90ab62d..916ef17 100644
--- a/aoc2023/src/day23/solve.gleam
+++ b/aoc2023/src/day23/solve.gleam
@@ -1,12 +1,189 @@
import adglent.{First, Second}
+import gleam/int
import gleam/io
+import gleam/dict.{type Dict}
+import gleam/list
+import gleam/option.{type Option, None, Some}
+import gleam/string
+import gleam/set.{type Set}
+import gleam/bool
+import utilities/array2d.{type Array2D, type Posn, Posn}
+
+type Path {
+ Unknown
+ Straight
+ Junction
+}
+
+type Route {
+ Route(to: Posn, distance: Int)
+}
+
+fn append_to_key(v: Option(List(a)), new: a) -> List(a) {
+ case v {
+ None -> [new]
+ Some(xs) -> [new, ..xs]
+ }
+}
+
+fn first_parse_path(c: String) -> Result(Path, Nil) {
+ case c {
+ "#" -> Error(Nil)
+ _ -> Ok(Unknown)
+ }
+}
+
+fn junction_neighbors(p: Posn) -> List(Posn) {
+ [Posn(..p, r: p.r + 1), Posn(..p, c: p.c + 1)]
+}
+
+fn mark_junctions(trails: Array2D(Path)) -> Array2D(Path) {
+ use trail, _ <- dict.map_values(trails)
+
+ let valid_neighbors =
+ trail
+ |> array2d.ortho_neighbors
+ |> list.filter(dict.has_key(trails, _))
+
+ case list.length(valid_neighbors) {
+ 2 -> Straight
+ _ -> Junction
+ }
+}
+
+fn start_walking_to_next_junction(
+ start: Posn,
+ next: Posn,
+ trails: Array2D(Path),
+) {
+ let seen =
+ set.new()
+ |> set.insert(start)
+ |> set.insert(next)
+ walk_to_next_junction(start, next, 1, seen, trails)
+}
+
+fn walk_to_next_junction(
+ start: Posn,
+ current: Posn,
+ length: Int,
+ seen: Set(Posn),
+ trails: Array2D(Path),
+) -> #(Posn, Route) {
+ let assert [next] =
+ current
+ |> array2d.ortho_neighbors
+ |> list.filter(fn(n) { dict.has_key(trails, n) && !set.contains(seen, n) })
+
+ case dict.get(trails, next) {
+ Ok(Junction) -> #(start, Route(to: next, distance: length + 1))
+ _ -> {
+ let seen = set.insert(seen, current)
+ walk_to_next_junction(start, next, { length + 1 }, seen, trails)
+ }
+ }
+}
+
+fn generate_routes(
+ junctions: List(Posn),
+ trails: Array2D(Path),
+) -> Dict(Posn, List(Route)) {
+ {
+ use junction <- list.flat_map(junctions)
+ use neighbor <- list.filter_map(junction_neighbors(junction))
+ case dict.has_key(trails, neighbor) {
+ True -> Ok(start_walking_to_next_junction(junction, neighbor, trails))
+ False -> Error(Nil)
+ }
+ }
+ |> list.fold(dict.new(), fn(acc, edge) {
+ let #(from, route) = edge
+ use v <- dict.update(acc, from)
+ case v {
+ None -> [route]
+ Some(routes) -> [route, ..routes]
+ }
+ })
+}
+
+fn generate_2way_routes(
+ junctions: List(Posn),
+ trails: Array2D(Path),
+) -> Dict(Posn, List(Route)) {
+ let routes = {
+ use junction <- list.flat_map(junctions)
+ use neighbor <- list.filter_map(junction_neighbors(junction))
+ case dict.has_key(trails, neighbor) {
+ True -> Ok(start_walking_to_next_junction(junction, neighbor, trails))
+ False -> Error(Nil)
+ }
+ }
+ use acc, r <- list.fold(routes, dict.new())
+ let #(from, Route(to, dist)) = r
+ acc
+ |> dict.update(from, append_to_key(_, Route(to, dist)))
+ |> dict.update(to, append_to_key(_, Route(from, dist)))
+}
+
+fn dfs(routes, from, to) {
+ let seen = set.insert(set.new(), from)
+ do_dfs(routes, from, to, 0, seen)
+}
+
+fn do_dfs(
+ routes: Dict(Posn, List(Route)),
+ from: Posn,
+ to: Posn,
+ acc: Int,
+ seen: Set(Posn),
+) -> Int {
+ use <- bool.guard(to == from, acc)
+
+ let assert Ok(all_routes) = dict.get(routes, from)
+ let neighbors = list.filter(all_routes, fn(r) { !set.contains(seen, r.to) })
+
+ case neighbors {
+ [] -> 0
+ neighbors ->
+ list.fold(neighbors, acc, fn(inner_acc, n) {
+ let score =
+ do_dfs(routes, n.to, to, acc + n.distance, set.insert(seen, n.to))
+ int.max(score, inner_acc)
+ })
+ }
+}
+
+fn solve_using(
+ input: String,
+ using: fn(List(Posn), Dict(Posn, Path)) -> Dict(Posn, List(Route)),
+) -> Int {
+ let min_row = 0
+ let max_row = list.length(string.split(input, "\n")) - 1
+
+ let trails =
+ input
+ |> array2d.parse_grid_using(first_parse_path)
+ |> mark_junctions
+
+ let junctions =
+ trails
+ |> dict.filter(fn(_, v) { v == Junction })
+ |> dict.keys
+
+ let assert Ok(start) = list.find(junctions, fn(j) { j.r == min_row })
+ let assert Ok(end) = list.find(junctions, fn(j) { j.r == max_row })
+
+ let routes = using(junctions, trails)
+
+ dfs(routes, start, end)
+}
pub fn part1(input: String) {
- todo as "Implement solution to part 1"
+ solve_using(input, generate_routes)
}
pub fn part2(input: String) {
- todo as "Implement solution to part 2"
+ solve_using(input, generate_2way_routes)
}
pub fn main() {
diff --git a/aoc2023/src/utilities/array2d.gleam b/aoc2023/src/utilities/array2d.gleam
index 9d3b966..8538129 100644
--- a/aoc2023/src/utilities/array2d.gleam
+++ b/aoc2023/src/utilities/array2d.gleam
@@ -2,6 +2,7 @@ import gleam/list
import gleam/dict.{type Dict}
import gleam/string
import gleam/int
+import gleam/result
pub type Posn {
Posn(r: Int, c: Int)
@@ -16,13 +17,29 @@ pub fn add_posns(p1: Posn, p2: Posn) -> Posn {
}
}
+pub fn ortho_neighbors(p: Posn) -> List(Posn) {
+ let Posn(r, c) = p
+ [Posn(r + 1, c), Posn(r - 1, c), Posn(r, c + 1), Posn(r, c - 1)]
+}
+
pub fn to_2d_array(xss: List(List(a))) -> Array2D(a) {
+ to_2d_array_using(xss, fn(x) { Ok(x) })
+}
+
+pub fn to_2d_array_using(
+ xss: List(List(a)),
+ f: fn(a) -> Result(b, Nil),
+) -> Array2D(b) {
{
use r, row <- list.index_map(xss)
use c, cell <- list.index_map(row)
- #(Posn(r, c), cell)
+ case f(cell) {
+ Ok(contents) -> Ok(#(Posn(r, c), contents))
+ Error(Nil) -> Error(Nil)
+ }
}
|> list.flatten
+ |> result.values
|> dict.from_list
}
@@ -44,7 +61,14 @@ pub fn to_list_of_lists(str: String) -> List(List(String)) {
}
pub fn parse_grid(str: String) -> Array2D(String) {
+ parse_grid_using(str, fn(x) { Ok(x) })
+}
+
+pub fn parse_grid_using(
+ str: String,
+ f: fn(String) -> Result(a, Nil),
+) -> Array2D(a) {
str
|> to_list_of_lists
- |> to_2d_array
+ |> to_2d_array_using(f)
}
diff --git a/aoc2023/test/day23/day23_test.gleam b/aoc2023/test/day23/day23_test.gleam
index eb9496f..206571c 100644
--- a/aoc2023/test/day23/day23_test.gleam
+++ b/aoc2023/test/day23/day23_test.gleam
@@ -4,22 +4,76 @@ import adglent.{type Example, Example}
import day23/solve
type Problem1AnswerType =
- String
+ Int
type Problem2AnswerType =
- String
+ Int
/// Add examples for part 1 here:
/// ```gleam
///const part1_examples: List(Example(Problem1AnswerType)) = [Example("some input", "")]
/// ```
-const part1_examples: List(Example(Problem1AnswerType)) = []
+const part1_examples: List(Example(Problem1AnswerType)) = [
+ Example(
+ "#.#####################
+#.......#########...###
+#######.#########.#.###
+###.....#.>.>.###.#.###
+###v#####.#v#.###.#.###
+###.>...#.#.#.....#...#
+###v###.#.#.#########.#
+###...#.#.#.......#...#
+#####.#.#.#######.#.###
+#.....#.#.#.......#...#
+#.#####.#.#.#########v#
+#.#...#...#...###...>.#
+#.#.#v#######v###.###v#
+#...#.>.#...>.>.#.###.#
+#####v#.#.###v#.#.###.#
+#.....#...#...#.#.#...#
+#.#########.###.#.#.###
+#...###...#...#...#.###
+###.###.#.###v#####v###
+#...#...#.#.>.>.#.>.###
+#.###.###.#.###.#.#v###
+#.....###...###...#...#
+#####################.#",
+ 94,
+ ),
+]
/// Add examples for part 2 here:
/// ```gleam
///const part2_examples: List(Example(Problem2AnswerType)) = [Example("some input", "")]
/// ```
-const part2_examples: List(Example(Problem2AnswerType)) = []
+const part2_examples: List(Example(Problem2AnswerType)) = [
+ Example(
+ "#.#####################
+#.......#########...###
+#######.#########.#.###
+###.....#.>.>.###.#.###
+###v#####.#v#.###.#.###
+###.>...#.#.#.....#...#
+###v###.#.#.#########.#
+###...#.#.#.......#...#
+#####.#.#.#######.#.###
+#.....#.#.#.......#...#
+#.#####.#.#.#########v#
+#.#...#...#...###...>.#
+#.#.#v#######v###.###v#
+#...#.>.#...>.>.#.###.#
+#####v#.#.###v#.#.###.#
+#.....#...#...#.#.#...#
+#.#########.###.#.#.###
+#...###...#...#...#.###
+###.###.#.###v#####v###
+#...#...#.#.>.>.#.>.###
+#.###.###.#.###.#.#v###
+#.....###...###...#...#
+#####################.#",
+ 154,
+ ),
+]
pub fn part1_test() {
part1_examples