<!-- livebook:{"persist_outputs":true} -->

# Day 20

```elixir
Mix.install([:kino_aoc])
```

## Section

<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiIyMCIsInNlc3Npb25fc2VjcmV0IjoiQURWRU5UX09GX0NPREVfU0VTU0lPTiIsInllYXIiOiIyMDI0In0","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->

```elixir
{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2024", "20", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
```

<!-- livebook:{"output":true} -->

```
{:ok,
 "#############################################################################################################################################\n#...#...#...#...#.........#.........###...#.....#...#.....#...#.......#...#...###...#...#...###.......#.........#...#...#...#...............#\n#.#.#.#.#.#.#.#.#.#######.#.#######.###.#.#.###.#.#.#.###.#.#.#.#####.#.#.#.#.###.#.#.#.#.#.###.#####.#.#######.#.#.#.#.#.#.#.#############.#\n#.#.#.#.#.#...#.#.....#...#.#.......#...#.#...#.#.#.#...#...#.#.#.....#.#.#.#.#...#...#.#.#...#...#...#.....#...#.#.#.#...#...#.........#...#\n#.#.#.#.#.#####.#####.#.###.#.#######.###.###.#.#.#.###.#####.#.#.#####.#.#.#.#.#######.#.###.###.#.#######.#.###.#.#.#########.#######.#.###\n#.#.#.#.#...#...#...#.#...#.#.#.....#...#...#.#.#.#...#.#.....#.#.###...#.#.#.#.......#.#.#...#...#.....###.#.....#...#...#...#.......#...###\n#.#.#.#.###.#.###.#.#.###.#.#.#.###.###.###.#.#.#.###.#.#.#####.#.###.###.#.#.#######.#.#.#.###.#######.###.###########.#.#.#.#######.#######\n#.#.#.#.#...#...#.#.#.#...#.#.#.#...###...#.#.#.#.#...#.#...#...#...#...#...#.....###.#.#.#...#.....#...#...#.......#...#...#...#.....#.....#\n#.#.#.#.#.#####.#.#.#.#.###.#.#.#.#######.#.#.#.#.#.###.###.#.#####.###.#########.###.#.#.###.#####.#.###.###.#####.#.#########.#.#####.###.#\n#.#.#.#.#.....#.#.#...#.#...#...#.....#...#...#.#.#...#.#...#.....#...#...#.......#...#...#...#.....#...#...#.....#.#.........#...#.....#...#\n#.#.#.#.#####.#.#.#####.#.###########.#.#######.#.###.#.#.#######.###.###.#.#######.#######.###.#######.###.#####.#.#########.#####.#####.###\n#.#...#.....#.#.#.#.....#...#.....#...#...#.....#...#.#.#...#...#...#.#...#.......#.......#...#.......#.....#.....#...........#...#.....#...#\n#.#########.#.#.#.#.#######.#.###.#.#####.#.#######.#.#.###.#.#.###.#.#.#########.#######.###.#######.#######.#################.#.#####.###.#\n#.#...#...#...#...#...#####.#...#...#####.#.###...#.#.#.#...#.#.....#...#...#.....###...#.#...#...###...#...#.#...#...#.....###.#.###...#...#\n#.#.#.#.#.###########.#####.###.#########.#.###.#.#.#.#.#.###.###########.#.#.#######.#.#.#.###.#.#####.#.#.#.#.#.#.#.#.###.###.#.###.###.###\n#...#...#...#.......#...#...#...#...###...#...#.#.#.#.#.#.###.......#.....#...#...#...#.#.#.###.#.#...#.#.#.#...#...#...#...#...#...#...#...#\n###########.#.#####.###.#.###.###.#.###.#####.#.#.#.#.#.#.#########.#.#########.#.#.###.#.#.###.#.#.#.#.#.#.#############.###.#####.###.###.#\n#...###...#...#...#...#...#...#...#.#...#...#.#.#.#.#...#...###...#.#.....#.....#.#...#...#.#...#.#.#.#.#.#...#...........#...#.....#...#...#\n#.#.###.#.#####.#.###.#####.###.###.#.###.#.#.#.#.#.#######.###.#.#.#####.#.#####.###.#####.#.###.#.#.#.#.###.#.###########.###.#####.###.###\n#.#.#...#.....#.#...#.....#...#.#...#...#.#...#.#...#.......#...#.#.#.....#.....#.###.....#.#...#.#.#.#...#...#...........#...#.....#.#...###\n#.#.#.#######.#.###.#####.###.#.#.#####.#.#####.#####.#######.###.#.#.#########.#.#######.#.###.#.#.#.#####.#############.###.#####.#.#.#####\n#.#...#.....#.#.#...#...#...#...#.#...#.#...#...#.....#.....#...#.#.#.......#...#...#...#.#.....#.#.#.#.....#.............#...#.....#.#.#...#\n#.#####.###.#.#.#.###.#.###.#####.#.#.#.###.#.###.#####.###.###.#.#.#######.#.#####.#.#.#.#######.#.#.#.#####.#############.###.#####.#.#.#.#\n#.#...#.#...#...#.....#.....#.....#.#.#.#...#...#.#...#...#.....#.#.#.....#.#.....#...#.#...#.....#.#.#.....#.#...###...###.#...#...#.#.#.#.#\n#.#.#.#.#.###################.#####.#.#.#.#####.#.#.#.###.#######.#.#.###.#.#####.#####.###.#.#####.#.#####.#.#.#.###.#.###.#.###.#.#.#.#.#.#\n#.#.#...#.................#...#...#.#.#.#.#.....#.#.#.###.......#.#.#...#...#...#...#...#...#.#.....#.#...#.#.#.#.....#.....#.....#...#...#.#\n#.#.#####################.#.###.#.#.#.#.#.#.#####.#.#.#########.#.#.###.#####.#.###.#.###.###.#.#####.#.#.#.#.#.###########################.#\n#.#.....#.................#.###.#.#.#.#.#.#...#...#.#...#...#...#.#.#...#...#.#.#...#...#...#.#...#...#.#.#.#.#.#.....#.......#.....#...#...#\n#.#####.#.#################.###.#.#.#.#.#.###.#.###.###.#.#.#.###.#.#.###.#.#.#.#.#####.###.#.###.#.###.#.#.#.#.#.###.#." <> ...}
```

```elixir
#puzzle_input =
  """
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
  """
```

<!-- livebook:{"output":true} -->

```
warning: outdented heredoc line. The contents inside the heredoc should be indented at the same level as the closing """. The following is forbidden:

    def text do
      """
    contents
      """
    end

Instead make sure the contents are indented as much as the heredoc closing:

    def text do
      """
      contents
      """
    end

The current heredoc line is indented too little
└─ Workspace/hauleth/advent-of-code/2024/day20.livemd#cell:iyjl3w4kz3srtwoq:3:3

```

<!-- livebook:{"output":true} -->

```
"###############\n#...#...#.....#\n#.#.#.#.#.###.#\n#S#...#.#.#...#\n#######.#.#.###\n#######.#.#...#\n#######.#.###.#\n###..E#...#...#\n###.#######.###\n#...###...#...#\n#.#####.#.###.#\n#.#...#.#.#...#\n#.#.#.#.#.#.###\n#...#...#...###\n###############\n"
```

```elixir
map =
  puzzle_input
  |> String.split("\n")
  |> Enum.with_index()
  |> Enum.flat_map(fn {row, y} ->
    row
    |> String.split("", trim: true)
    |> Enum.with_index()
    |> Enum.map(fn {c, x} ->
      {{x, y}, c}
    end)
  end)
```

<!-- livebook:{"output":true} -->

```
[
  {{0, 0}, "#"},
  {{1, 0}, "#"},
  {{2, 0}, "#"},
  {{3, 0}, "#"},
  {{4, 0}, "#"},
  {{5, 0}, "#"},
  {{6, 0}, "#"},
  {{7, 0}, "#"},
  {{8, 0}, "#"},
  {{9, 0}, "#"},
  {{10, 0}, "#"},
  {{11, 0}, "#"},
  {{12, 0}, "#"},
  {{13, 0}, "#"},
  {{14, 0}, "#"},
  {{15, 0}, "#"},
  {{16, 0}, "#"},
  {{17, 0}, "#"},
  {{18, 0}, "#"},
  {{19, 0}, "#"},
  {{20, 0}, "#"},
  {{21, 0}, "#"},
  {{22, 0}, "#"},
  {{23, 0}, "#"},
  {{24, 0}, "#"},
  {{25, 0}, "#"},
  {{26, 0}, "#"},
  {{27, 0}, "#"},
  {{28, 0}, "#"},
  {{29, 0}, "#"},
  {{30, 0}, "#"},
  {{31, 0}, "#"},
  {{32, 0}, "#"},
  {{33, 0}, "#"},
  {{34, 0}, "#"},
  {{35, 0}, "#"},
  {{36, 0}, "#"},
  {{37, 0}, "#"},
  {{38, 0}, "#"},
  {{39, 0}, "#"},
  {{40, 0}, "#"},
  {{41, 0}, "#"},
  {{42, 0}, "#"},
  {{43, 0}, "#"},
  {{44, 0}, "#"},
  {{45, 0}, "#"},
  {{46, 0}, "#"},
  {{47, ...}, "#"},
  {{...}, ...},
  {...},
  ...
]
```

```elixir
%{"#" => walls, "." => road, "S" => [start], "E" => [finish]} =
  Enum.group_by(map, &elem(&1, 1), &elem(&1, 0))
```

<!-- livebook:{"output":true} -->

```
%{
  "#" => [
    {0, 0},
    {1, 0},
    {2, 0},
    {3, 0},
    {4, 0},
    {5, 0},
    {6, 0},
    {7, 0},
    {8, 0},
    {9, 0},
    {10, 0},
    {11, 0},
    {12, 0},
    {13, 0},
    {14, 0},
    {15, 0},
    {16, 0},
    {17, 0},
    {18, 0},
    {19, 0},
    {20, 0},
    {21, 0},
    {22, 0},
    {23, 0},
    {24, 0},
    {25, 0},
    {26, 0},
    {27, 0},
    {28, 0},
    {29, 0},
    {30, 0},
    {31, 0},
    {32, 0},
    {33, 0},
    {34, 0},
    {35, 0},
    {36, 0},
    {37, 0},
    {38, 0},
    {39, 0},
    {40, 0},
    {41, 0},
    {42, 0},
    {43, 0},
    {44, 0},
    {45, 0},
    {46, 0},
    {47, ...},
    {...},
    ...
  ],
  "." => [
    {1, 1},
    {2, 1},
    {3, 1},
    {5, 1},
    {6, 1},
    {7, 1},
    {9, 1},
    {10, 1},
    {11, 1},
    {13, 1},
    {14, 1},
    {15, 1},
    {17, 1},
    {18, 1},
    {19, 1},
    {20, 1},
    {21, 1},
    {22, 1},
    {23, 1},
    {24, 1},
    {25, 1},
    {27, 1},
    {28, 1},
    {29, 1},
    {30, 1},
    {31, 1},
    {32, 1},
    {33, 1},
    {34, 1},
    {35, 1},
    {39, 1},
    {40, 1},
    {41, 1},
    {43, 1},
    {44, 1},
    {45, 1},
    {46, 1},
    {47, 1},
    {49, 1},
    {50, 1},
    {51, 1},
    {53, 1},
    {54, 1},
    {55, 1},
    {56, 1},
    {57, 1},
    {59, ...},
    {...},
    ...
  ],
  "E" => [{27, 59}],
  "S" => [{49, 53}]
}
```

```elixir
defmodule Race do
  def distances(start, finish, walls) do
    do_distances(start, finish, 0, MapSet.new(walls), %{})
  end

  defp do_distances(finish, finish, n, _, acc),
    do: Map.put(acc, finish, n)

  defp do_distances(current, finish, n, walls, acc) do
    acc = Map.put(acc, current, n)

    current
    |> neigh()
    |> Enum.reject(&(&1 in walls or Map.has_key?(acc, &1)))
    |> hd()
    |> do_distances(finish, n + 1, walls, acc)
  end

  def neigh({x, y}, d \\ 1) do
    for {dx, dy} <- [{0, d}, {0, -d}, {d, 0}, {-d, 0}], do: {x + dx, y + dy}
  end

  def neighbours({x, y}, r \\ 1) do
    for dx <- -r..r,
        dy <- -r..r,
        {dx, dy} != {0, 0},
        d = abs(dx) + abs(dy),
        d <= r,
        do: {x + dx, y + dy}
  end

  def d({xa, ya}, {xb, yb}) do
    abs(xa - xb) + abs(ya - yb)
  end
end
```

<!-- livebook:{"output":true} -->

```
{:module, Race, <<70, 79, 82, 49, 0, 0, 17, ...>>, {:d, 2}}
```

```elixir
steps = Race.distances(start, finish, walls)
```

<!-- livebook:{"output":true} -->

```
%{
  {18, 103} => 8261,
  {61, 121} => 7060,
  {65, 63} => 2098,
  {77, 129} => 6964,
  {1, 26} => 695,
  {116, 69} => 4441,
  {83, 76} => 4281,
  {117, 125} => 5656,
  {103, 106} => 5785,
  {30, 113} => 8041,
  {89, 14} => 2511,
  {35, 30} => 1133,
  {37, 53} => 32,
  {11, 39} => 384,
  {131, 5} => 2998,
  {65, 43} => 1754,
  {139, 46} => 3615,
  {12, 135} => 7871,
  {65, 131} => 7046,
  {49, 117} => 7412,
  {29, 25} => 1108,
  {83, 36} => 2319,
  {47, 27} => 1556,
  {4, 81} => 8645,
  {13, 124} => 8295,
  {121, 77} => 4608,
  {103, 39} => 3756,
  {119, 60} => 4389,
  {13, 85} => 8604,
  {63, 81} => 6682,
  {111, 108} => 5755,
  {111, 103} => 5764,
  {15, 92} => 8587,
  {1, 101} => 8500,
  {20, 3} => 939,
  {61, 95} => 6878,
  {23, 67} => 9208,
  {78, 75} => 6545,
  {79, 17} => 2358,
  {17, 137} => 7852,
  {124, 93} => 4933,
  {138, 9} => 3283,
  {58, 33} => 1667,
  {67, 105} => 6818,
  {47, 44} => 1195,
  {122, 137} => 5595,
  {13, 55} => 154,
  {97, 138} => 6129,
  {75, ...} => 2165,
  {...} => 1616,
  ...
}
```

## Part 1

```elixir
Enum.reduce(steps, 0, fn {pos, start}, acc ->
  count =
    steps
    |> Map.take(Race.neighbours(pos, 2))
    |> Enum.count(fn {last, finish} ->
      finish - start - Race.d(pos, last) >= 100
    end)

  count + acc
end)
```

<!-- livebook:{"output":true} -->

```
1393
```

## Part 2

We can notice that we are looking for shortcuts in circle of radius $r$ defined in Taxicab metric ($d(a, b) = \sum_{i} |a_i - b_i|$). That makes code pretty simple and allows us to reuse ideas from Part 1.

```elixir
steps
|> Task.async_stream(
  fn {pos, start} ->
    steps
    |> Map.take(Race.neighbours(pos, 20))
    |> Enum.count(fn {last, finish} ->
      finish - start - Race.d(pos, last) >= 100
    end)
  end,
  ordered: false
)
|> Enum.reduce(0, fn {:ok, count}, acc ->
  count + acc
end)
```

<!-- livebook:{"output":true} -->

```
990096
```

<!-- livebook:{"offset":11400,"stamp":{"token":"XCP.ONwDp6zRpWXsXASH95Q0puANk15Li1hG2FDCrv6Gqu42Q7k9pb_Te_6RDoUE0dp3yYbG7jry8-6iHGJvcZtsDFstlznyVHk9HVhXRZiC2uQczaOfF4K8HQL9QuzNguTht7A","version":2}} -->