From eb492eea3adbba1995d870c6c4a9c22d09a4c96f Mon Sep 17 00:00:00 2001 From: "J.J" Date: Sat, 23 Dec 2023 15:24:05 -0500 Subject: day 23 gleam complete --- aoc2023/src/day23/solve.gleam | 181 +++++++++++++++++++++++++++++++++++- aoc2023/src/utilities/array2d.gleam | 28 +++++- aoc2023/test/day23/day23_test.gleam | 62 +++++++++++- 3 files changed, 263 insertions(+), 8 deletions(-) (limited to 'aoc2023') 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 -- cgit v1.2.3