sorting by language

1 files changed, 0 insertions, 287 deletions

diff --git a/aoc2021/day-15/day-15.livemd b/aoc2021/day-15/day-15.livemd
deleted file mode 100644
index 2495c32..0000000
--- a/aoc2021/day-15/day-15.livemd
+++ /dev/null
@@ -1,287 +0,0 @@
-<!-- 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
-```