# 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 ``` 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 ```