path: root/2021/day-15/day-15.livemd

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