diff options
Diffstat (limited to 'aoc2023/src/day17')
-rw-r--r-- | aoc2023/src/day17/.gitignore | 1 | ||||
-rw-r--r-- | aoc2023/src/day17/solve.gleam | 143 |
2 files changed, 0 insertions, 144 deletions
diff --git a/aoc2023/src/day17/.gitignore b/aoc2023/src/day17/.gitignore deleted file mode 100644 index ae40cea..0000000 --- a/aoc2023/src/day17/.gitignore +++ /dev/null @@ -1 +0,0 @@ -input.txt
\ No newline at end of file diff --git a/aoc2023/src/day17/solve.gleam b/aoc2023/src/day17/solve.gleam deleted file mode 100644 index 7a01c4d..0000000 --- a/aoc2023/src/day17/solve.gleam +++ /dev/null @@ -1,143 +0,0 @@ -import adglent.{First, Second} -import gleam/bool -import gleam/dict.{type Dict} -import gleam/io -import gleam/list -import gleam/result -import gleam/string -import gleam/set.{type Set} -import utilities/array2d.{type Posn, Posn} -import utilities/prioqueue.{type PriorityQueue} - -type State { - State(posn: Posn, heatloss: Int, previous: Posn, history: List(Posn)) -} - -const deltas = [Posn(-1, 0), Posn(1, 0), Posn(0, -1), Posn(0, 1)] - -fn make_key(s: State) { - #(s.posn, same_dir(s)) -} - -fn same_dir(s: State) { - case s.history { - [] -> [] - [first, ..] as deltas -> - list.take_while(deltas, fn(d) { d == first }) - |> list.take(10) - } -} - -fn is_goal(s: State, min_run: Int, goal: Posn) { - goal == s.posn && list.length(same_dir(s)) >= min_run -} - -fn find_good_neighbors(max: Int, min: Int, s: State, grid) { - deltas - |> list.filter(eliminate_bad_neighbors(_, s, max, min, grid)) - |> list.map(make_state(_, s, grid)) -} - -fn eliminate_bad_neighbors(d: Posn, s: State, max, min, grid) { - let neighbor = array2d.add_posns(d, s.posn) - - use <- bool.guard( - neighbor == s.previous || !dict.has_key(grid, neighbor), - False, - ) - case same_dir(s), list.length(same_dir(s)) { - [prev, ..], l if l == max -> d != prev - _, 0 -> True - [prev, ..], l if l < min -> d == prev - _, _ -> True - } -} - -fn make_state(d: Posn, s: State, grid) { - let neighbor = array2d.add_posns(d, s.posn) - let assert Ok(heat_lost) = dict.get(grid, neighbor) - State( - posn: neighbor, - heatloss: s.heatloss + heat_lost, - previous: s.posn, - history: [d, ..s.history], - ) -} - -fn find_path( - grid: Dict(Posn, Int), - queue: PriorityQueue(State), - seen: Set(#(Posn, List(Posn))), - get_neighbors: fn(State) -> List(State), - is_goal: fn(State) -> Bool, -) { - let assert Ok(#(state, rest)) = prioqueue.pop(queue) - let key = - make_key( - state - |> io.debug, - ) - case set.contains(seen, key) { - True -> find_path(grid, rest, seen, get_neighbors, is_goal) - False -> { - let now_seen = set.insert(seen, key) - let neighbors = get_neighbors(state) - case list.find(neighbors, is_goal) { - Ok(final) -> final.heatloss - _err -> { - let now_queue = - list.fold(neighbors, rest, fn(acc, n) { - prioqueue.insert(acc, n, n.heatloss) - }) - find_path(grid, now_queue, now_seen, get_neighbors, is_goal) - } - } - } - } -} - -pub fn part1(input: String) { - let raw_grid = - input - |> array2d.to_list_of_lists - - let grid = array2d.to_2d_intarray(raw_grid) - - let rmax = list.length(raw_grid) - let assert Ok(cmax) = - raw_grid - |> list.first - |> result.map(list.length) - - let start = State(Posn(0, 0), 0, Posn(0, 0), []) - let goal = Posn(rmax, cmax) - - find_path( - grid, - prioqueue.insert(prioqueue.new(), start, 0), - set.new(), - find_good_neighbors(0, 3, _, grid), - is_goal(_, 1, goal), - ) - |> string.inspect -} - -pub fn part2(input: String) { - input - |> string.inspect -} - -pub fn main() { - let assert Ok(part) = adglent.get_part() - let assert Ok(input) = adglent.get_input("17") - case part { - First -> - part1(input) - |> adglent.inspect - |> io.println - Second -> - part2(input) - |> adglent.inspect - |> io.println - } -} |