🎄 Year 2024 🔔 Day 20

Mix.install([
  {:arrays, "~> 2.1"}
])

Setup

map_array =
  File.read!("#{__DIR__}/../../../inputs/2024/day20.txt")
  # """
  # ###############
  # #...#...#.....#
  # #.#.#.#.#.###.#
  # #S#...#.#.#...#
  # #######.#.#.###
  # #######.#.#...#
  # #######.#.###.#
  # ###..E#...#...#
  # ###.#######.###
  # #...###...#...#
  # #.#####.#.###.#
  # #.#...#.#.#...#
  # #.#.#.#.#.#.###
  # #...#...#...###
  # ###############
  # """
  |> String.split("\n", trim: true)
  |> Enum.map(&String.split(&1, "", trim: true))
  |> List.zip()
  |> Enum.map(&Tuple.to_list/1)
  |> Enum.map(&Arrays.new/1)
  |> Arrays.new()

{max_x, max_y} = {Arrays.size(map_array) - 1, Arrays.size(map_array[0]) - 1}

[{start_x, start_y}] =
  for x <- 0..max_x, y <- 0..max_y, map_array[x][y] == "S", do: {x, y}

[{end_x, end_y}] =
  for x <- 0..max_x, y <- 0..max_y, map_array[x][y] == "E", do: {x, y}

map_array =
  map_array |> put_in([start_x, start_y], ".") |> put_in([end_x, end_y], ".")

Part 1

steps = 20
for x <- -steps..steps, y <- (-steps + abs(x))..(steps - abs(x)), do: {x, y}

defmodule Part1 do
  def djikstra(map_array, nodes_to_visit) when nodes_to_visit == %{} do
    map_array
  end

  def djikstra(map_array, nodes_to_visit) do
    {{x, y}, score} =
      next_node =
      nodes_to_visit
      |> Enum.min_by(&elem(&1, 1))

    adjacent_nodes =
      get_adjacent_nodes(next_node, map_array)

    nodes_to_visit =
      Enum.reduce(adjacent_nodes, nodes_to_visit, fn {coord, score}, nodes_to_visit ->
        Map.update(nodes_to_visit, coord, score, fn current_score ->
          min(current_score, score)
        end)
      end)
      |> Map.delete({x, y})

    map_array = put_in(map_array[x][y], score)
    djikstra(map_array, nodes_to_visit)
  end

  def get_adjacent_nodes({{x, y}, score}, map_array) do
    {max_x, max_y} = {Arrays.size(map_array) - 1, Arrays.size(map_array[0]) - 1}

    [
      {{x, y - 1}, score + 1},
      {{x + 1, y}, score + 1},
      {{x, y + 1}, score + 1},
      {{x - 1, y}, score + 1}
    ]
    |> Enum.filter(fn {{x, y}, _score} ->
      coords_in_map = x >= 0 and y >= 0 and x <= max_x and y <= max_y
      coords_in_map and map_array[x][y] == "."
    end)
  end

  def get_cheats(map_array) do
    {max_x, max_y} = {Arrays.size(map_array) - 1, Arrays.size(map_array[0]) - 1}

    for(x <- 0..max_x, y <- 0..max_y, map_array[x][y] != "#", do: {x, y})
    |> Enum.flat_map(fn {x, y} ->
      [
        [{x, y}, {x, y - 1}, {x, y - 2}],
        [{x, y}, {x + 1, y}, {x + 2, y}],
        [{x, y}, {x, y + 1}, {x, y + 2}],
        [{x, y}, {x - 1, y}, {x - 2, y}]
      ]
      |> Enum.filter(fn [_, _, {x3, y3}] ->
        x3 >= 0 and x3 <= max_x and y3 >= 0 and y3 <= max_y
      end)
    end)
    |> Enum.map(&amp;Enum.map(&amp;1, fn {x, y} -> {{x, y}, map_array[x][y]} end))
    |> Enum.filter(fn [{_, e1}, {_, e2}, {_, e3}] ->
      e1 != "#" and e2 == "#" and e3 != "#" and e1 < e3
    end)
    |> Enum.map(fn [{_, e1}, {_, "#"}, {_, e3}] ->
      e3 - e1 - 2
    end)
  end
end

Part1.djikstra(map_array, %{{start_x, start_y} => 0})
|> Part1.get_cheats()
|> Enum.filter(fn e -> e >= 100 end)
|> Enum.count()

Part 2

defmodule Part2 do
  def get_cheats(map_array, steps) do
    {max_x, max_y} = {Arrays.size(map_array) - 1, Arrays.size(map_array[0]) - 1}

    for(x <- 0..max_x, y <- 0..max_y, map_array[x][y] != "#", do: {x, y})
    |> Enum.flat_map(fn {sx, sy} ->
      se = map_array[sx][sy]

      for mx <- -steps..steps,
          my <- (-steps + abs(mx))..(steps - abs(mx)),
          x = sx + mx,
          y = sy + my,
          x >= 0 and x <= max_x and y >= 0 and y <= max_y,
          steps_taken = abs(mx) + abs(my),
          e = map_array[x][y],
          e != "#",
          e > se + steps_taken do
        e - se - steps_taken
      end
    end)
  end
end

Part1.djikstra(map_array, %{{start_x, start_y} => 0})
|> Part2.get_cheats(20)
|> Enum.filter(fn e -> e >= 100 end)
|> Enum.count()