diff options
Diffstat (limited to 'racket/aoc2021/day-15/day-15.livemd')
| -rw-r--r-- | racket/aoc2021/day-15/day-15.livemd | 287 |
1 files changed, 287 insertions, 0 deletions
diff --git a/racket/aoc2021/day-15/day-15.livemd b/racket/aoc2021/day-15/day-15.livemd new file mode 100644 index 0000000..2495c32 --- /dev/null +++ b/racket/aoc2021/day-15/day-15.livemd @@ -0,0 +1,287 @@ +<!-- vim: set syntax=markdown: --> +<!-- livebook:{"persist_outputs":true} --> + +# Advent of Code 2021, Day 15 + +## Short summary + +**Parts 1 and 2.** Find the least "risky" path through a grid of nodes, +where each node has a "risk" cost to enter. Part 1's grid is the given data, +while Part 2's is the data after undergoing a transformation. +Only orthogonal travel is possible. + +## Setup + +Using the `libgraph` library to build the graph +and use its implementation of the Dijkstra algorithm: + +```elixir +Mix.install([ + {:libgraph, github: "bitwalker/libgraph"} +]) +``` + +```output +* Getting libgraph (https://github.com/bitwalker/libgraph.git) +remote: Enumerating objects: 783, done. +remote: Counting objects: 100% (64/64), done. +remote: Compressing objects: 100% (52/52), done. +remote: Total 783 (delta 27), reused 24 (delta 10), pack-reused 719 +origin/HEAD set to main +==> libgraph +Compiling 14 files (.ex) +Generated libgraph app +``` + +```output +:ok +``` + +```elixir +floor = + with {:ok, data} <- File.read("./2021/day-15/input") do + data + |> String.split() + |> Enum.map(fn xs -> + String.graphemes(xs) + |> Enum.map(&String.to_integer/1) + end) + end +``` + +```output +[ + [4, 5, 5, 2, 2, 8, 5, 9, 8, 9, 4, 4, 1, 1, 2, 4, 7, 1, 9, 7, 9, 8, 4, 6, 5, 8, 2, 5, 7, 7, 3, 3, + 1, 8, 2, 5, 2, 2, 6, 9, 4, 2, 2, 6, 2, 5, 7, 3, 1, ...], + [8, 3, 1, 1, 8, 2, 6, 9, 1, 7, 6, 7, 7, 2, 9, 5, 5, 6, 1, 3, 9, 5, 7, 1, 6, 2, 4, 5, 4, 2, 6, 1, + 8, 4, 2, 1, 2, 4, 7, 1, 3, 1, 1, 2, 1, 4, 8, 5, ...], + [3, 1, 3, 4, 1, 5, 5, 5, 2, 8, 2, 3, 1, 2, 9, 6, 3, 1, 3, 2, 9, 2, 9, 5, 1, 6, 8, 9, 3, 7, 1, 6, + 7, 1, 6, 1, 1, 3, 5, 5, 1, 9, 9, 4, 2, 9, 3, ...], + [7, 1, 3, 4, 1, 5, 9, 6, 8, 1, 5, 3, 3, 3, 3, 1, 1, 7, 2, 9, 9, 1, 9, 3, 2, 8, 1, 9, 1, 2, 8, 7, + 1, 8, 1, 3, 1, 1, 2, 1, 4, 2, 8, 7, 1, 5, ...], + [3, 2, 9, 1, 6, 2, 2, 1, 2, 1, 8, 9, 3, 8, 2, 1, 2, 5, 8, 2, 1, 5, 1, 1, 1, 5, 3, 1, 6, 1, 4, 2, + 3, 3, 9, 9, 9, 6, 6, 1, 6, 4, 9, 2, 7, ...], + [9, 1, 1, 6, 1, 9, 7, 3, 1, 9, 9, 9, 2, 2, 2, 3, 7, 8, 4, 9, 7, 3, 7, 4, 9, 1, 5, 9, 9, 1, 2, 9, + 1, 8, 9, 4, 8, 5, 1, 4, 8, 5, 5, 2, ...], + [4, 9, 6, 8, 4, 3, 9, 1, 1, 4, 1, 3, 5, 9, 9, 6, 9, 2, 3, 9, 3, 9, 6, 2, 1, 5, 2, 1, 2, 2, 7, 4, + 3, 8, 6, 1, 6, 4, 3, 2, 2, 6, 2, ...], + [6, 2, 3, 9, 2, 1, 9, 7, 8, 5, 2, 3, 4, 6, 7, 5, 3, 9, 1, 2, 8, 1, 6, 4, 1, 1, 1, 4, 1, 4, 8, 2, + 2, 5, 9, 4, 2, 6, 2, 2, 1, 9, ...], + [1, 9, 3, 9, 2, 7, 3, 1, 5, 2, 1, 1, 4, 1, 6, 5, 8, 1, 5, 6, 2, 1, 8, 9, 8, 1, 3, 1, 7, 4, 1, 6, + 2, 5, 1, 4, 2, 2, 7, 3, 7, ...], + [3, 8, 1, 6, 2, 9, 5, 1, 2, 1, 2, 1, 1, 7, 1, 3, 9, 1, 9, 9, 1, 8, 1, 2, 9, 1, 4, 1, 5, 2, 1, 7, + 4, 8, 3, 1, 5, 5, 7, 9, ...], + [2, 8, 5, 2, 1, 7, 4, 3, 9, 2, 1, 7, 5, 2, 1, 7, 8, 9, 1, 2, 9, 2, 7, 6, 9, 2, 9, 7, 3, 2, 9, 7, + 3, 4, 1, 4, 1, 5, 2, ...], + [8, 1, 8, 3, 4, 1, 1, 9, 8, 1, 1, 3, 6, 7, 1, 8, 4, 2, 8, 8, 2, 3, 1, 2, 7, 6, 8, 1, 4, 1, 1, 2, + 4, 6, 5, 2, 8, 2, ...], + [3, 3, 3, 8, 4, 1, 8, 9, 5, 8, 8, 1, 8, 2, 2, 9, 3, 3, 1, 3, 9, 9, 5, 1, 3, 6, 9, 1, 9, 2, 1, 9, + 2, 1, 8, 6, 9, ...], + [6, 1, 1, 8, 5, 8, 2, 7, 6, 5, 3, 7, 5, 5, 4, 1, 1, 4, 4, 4, 9, 1, 5, 1, 9, 8, 7, 1, 1, 2, 3, 1, + 2, 1, 1, 7, ...], + [1, 4, 6, 9, 2, 5, 7, 4, 1, 8, 3, 1, 3, 2, 1, 8, 9, 5, 1, 2, 1, 1, 5, 1, 1, 5, 9, 1, 2, 2, 4, 2, + 8, 1, 8, ...], + [1, 4, 2, 2, 1, 1, 8, 4, 1, 9, 3, 1, 9, 5, 1, 5, 4, 9, 6, 1, 8, 9, 3, 9, 1, 1, 5, 8, 5, 1, 6, 4, + 6, 2, ...], + [8, 1, 6, 2, 5, 4, 6, 1, 3, 9, 9, 5, 2, 1, 3, 6, 1, 8, 9, 9, 1, 1, 1, 7, 7, 5, 3, 3, 3, 5, 7, 8, + 2, ...], + [1, 4, 8, 8, 2, 3, 9, 6, 1, 1, 4, 6, 1, 4, 9, 1, 9, 7, 3, 8, 6, 5, 1, 8, 5, 2, 4, 2, 9, 5, 9, 5, + ...], + [2, 2, 1, 8, 9, 1, 7, 6, 6, 1, 8, 6, 8, 1, 3, 3, 1, 4, 1, 2, 4, 3, 8, 1, 9, 9, 6, 2, 4, 1, 3, ...], + [5, 7, 3, 4, 3, 2, 6, 7, 3, 2, 8, 8, 4, 7, 9, 2, 4, 2, 8, 1, 9, 1, 2, 4, 1, 1, 2, 1, 1, 9, ...], + [1, 5, 1, 1, 9, 3, 5, 1, 1, 1, 8, 6, 1, 1, 2, 1, 9, 3, 5, 7, 4, 1, 7, 6, 8, 3, 3, 8, 9, ...], + [9, 6, 9, 1, 5, 6, 2, 1, 8, 3, 5, 1, 3, 3, 8, 8, 2, 2, 1, 7, 2, 6, 4, 9, 3, 8, 2, 1, ...], + [2, 7, 2, 9, 2, 3, 7, 5, 3, 2, 9, 5, 9, 4, 4, 4, 7, 3, 3, 2, 2, 5, 4, 3, 5, 9, 9, ...], + [7, 3, 1, 2, 5, 5, 9, 1, 8, 1, 3, 2, 3, 7, 4, 3, 9, 3, 8, 2, 2, 1, 2, 1, 2, 2, ...], + [9, 4, 1, 5, 7, 4, 7, 7, 3, 8, 3, 4, 6, 1, 4, 1, 6, 9, 1, 4, 1, 8, 8, 2, 5, ...], + [1, 7, 1, 6, 2, 6, 3, 1, 2, 1, 1, 1, 5, 6, 3, 1, 1, 4, 1, 7, 8, 4, 2, 5, ...], + [2, 1, 1, 3, 4, 1, 4, 9, 1, 1, 7, 3, 1, 1, 6, 4, 9, 6, 2, 3, 4, 2, 2, ...], + [5, 6, 1, 1, 9, 1, 2, 3, 3, 4, 9, 2, 7, 2, 2, 1, 2, 5, 2, 7, 1, 1, ...], + [1, 2, 3, 2, 3, 1, 3, 2, 7, 1, 1, 1, 3, 5, 5, 4, 1, 8, 9, 9, 5, ...], + [2, 9, 2, 8, 1, 2, 3, 1, 2, 1, 1, 9, 1, 2, 6, 7, 7, 2, 1, 3, ...], + [3, 7, 3, 8, 1, 5, 2, 5, 4, 4, 6, 2, 5, 5, 1, 6, 9, 1, 6, ...], + [4, 9, 7, 8, 9, 3, 2, 2, 3, 7, 3, 1, 2, 6, 1, 5, 4, 5, ...], + [3, 9, 1, 2, 8, 9, 9, 1, 8, 2, 7, 9, 8, 9, 1, 6, 6, ...], + [1, 1, 9, 2, 9, 2, 7, 4, 2, 1, 3, 7, 2, 5, 8, 4, ...], + [3, 9, 1, 1, 1, 8, 5, 2, 1, 5, 5, 8, 2, 4, 3, ...], + [2, 9, 5, 3, 2, 1, 6, 7, 2, 2, 8, 1, 5, 2, ...], + [1, 1, 9, 8, 3, 8, 2, 7, 6, 7, 2, 1, 8, ...], + [2, 7, 2, 1, 8, 8, 4, 4, 1, 2, 9, 4, ...], + [3, 1, 1, 5, 1, 1, 8, 2, 2, 6, 2, ...], + [1, 4, 6, 6, 1, 3, 8, 1, 5, 2, ...], + [9, 1, 2, 2, 1, 3, 4, 4, 5, ...], + [6, 6, 1, 9, 4, 1, 3, 2, ...], + [1, 5, 9, 1, 8, 4, 5, ...], + [9, 1, 4, 5, 6, 7, ...], + [1, 7, 5, 6, 3, ...], + [7, 1, 1, 5, ...], + [1, 5, 9, ...], + [1, 5, ...], + [2, ...], + [...], + ... +] +``` + +Give each node a label based on its coordinates: + +```elixir +floor_nodes = + for {row, i} <- Enum.with_index(floor), + {col, j} <- Enum.with_index(row), + into: %{} do + {{i, j}, col} + end +``` + +```output +%{ + {76, 13} => 1, + {37, 47} => 2, + {65, 63} => 5, + {38, 2} => 1, + {1, 26} => 4, + {83, 76} => 2, + {32, 15} => 6, + {89, 14} => 1, + {35, 30} => 7, + {37, 53} => 7, + {4, 5} => 2, + {8, 50} => 7, + {78, 98} => 7, + {95, 56} => 7, + {74, 12} => 9, + {11, 39} => 2, + {65, 43} => 4, + {22, 38} => 1, + {14, 86} => 4, + {20, 41} => 1, + {29, 25} => 1, + {86, 10} => 1, + {83, 36} => 3, + {29, 26} => 3, + {47, 27} => 9, + {4, 81} => 3, + {31, 42} => 1, + {9, 34} => 3, + {90, 0} => 3, + {67, 98} => 1, + {13, 85} => 1, + {63, 81} => 4, + {82, 60} => 4, + {47, 38} => 1, + {15, 92} => 1, + {58, 58} => 1, + {20, 3} => 1, + {61, 95} => 7, + {23, 67} => 4, + {78, 75} => 1, + {79, 17} => 2, + {75, 0} => 7, + {16, 73} => 2, + {76, 2} => 8, + {58, 84} => 1, + {58, 33} => 7, + {47, 44} => 2, + {54, 31} => 6, + {13, ...} => 1, + {...} => 9, + ... +} +``` + +We can travel in the four cardinal directions from each node, so we need +a function to identify a node's neighbors: + +```elixir +neighbors = fn {i, j}, nodes -> + [{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}] + |> Enum.filter(&Map.has_key?(nodes, &1)) +end + +[neighbors.({0, 0}, floor_nodes), neighbors.({50, 50}, floor_nodes)] +``` + +```output +[[{1, 0}, {0, 1}], [{51, 50}, {49, 50}, {50, 51}, {50, 49}]] +``` + +## Part 1 + +Now we fold all the edges into a `Graph`: + +```elixir +make_graph = fn nodes -> + for {coord, _} <- nodes, + neighbor <- neighbors.(coord, nodes), + risk = Map.get(nodes, neighbor), + reduce: Graph.new(vertex_identifier: fn v -> v end) do + acc -> Graph.add_edge(acc, coord, neighbor, weight: risk) + end +end + +floor_graph = make_graph.(floor_nodes) +``` + +```output +#Graph<type: directed, num_vertices: 10000, num_edges: 39600> +``` + +Now we just need to use Dijkstra's algorithm to find the best path from the upper left to the lower right, +and use the map of each node's risk value to sum up the total risk for the path. + +```elixir +get_lowest_risk_path = fn nodes -> + with {{min_c, _}, {max_c, _}} <- Enum.min_max_by(nodes, fn {{i, j}, _} -> i + j end) do + nodes + |> then(make_graph) + |> Graph.dijkstra(min_c, max_c) + |> tl() + |> Enum.reduce(0, fn coord, sum -> sum + Map.get(nodes, coord) end) + end +end + +get_lowest_risk_path.(floor_nodes) +``` + +```output +403 +``` + +## Part 2 + +The process for Part 2 will be similar; the only difference +is that the graph is five times bigger after the transform. + +If the transformed risk is greater than 9, it rolls over to 1, so a +`Stream.cycle` can be used to easily get the rolled-over values. + +```elixir +expanded_floor_nodes = + with {{max_i, max_j}, _} <- Enum.max_by(floor_nodes, fn {{i, j}, _} -> i + j end), + nine_cycle = Stream.cycle(1..9) do + for {{i, j}, risk} <- floor_nodes, + x <- 0..4, + y <- 0..4, + into: %{} do + {{i + x * (max_i + 1), j + y * (max_j + 1)}, Enum.at(nine_cycle, risk - 1 + x + y)} + end + end + +Enum.count(expanded_floor_nodes) +``` + +```output +250000 +``` + +We repeat the same steps as before: building the graph, +using Dijkstra's algorithm and summing up the risks along the best path. + +```elixir +get_lowest_risk_path.(expanded_floor_nodes) +``` + +```output +2840 +``` |