Powered by AppSignal & Oban Pro
Would you like to see your link here? Contact us

Advent of Code 2024 - Day 16

elixir/2024/day_16.livemd

Advent of Code 2024 - Day 16

Mix.install([
  :kino_aoc,
  :prioqueue
])

Introduction

2024 - Day 16

Puzzle

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2024", "16", System.fetch_env!("LB_AOC_SESSION"))

Parser

Code - Parser

defmodule Parser do
  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.with_index()
    |> Enum.flat_map(fn {line, y} ->
      line
      |> String.graphemes()
      |> Enum.with_index()
      |> Enum.filter(fn {char, _} -> char != "." end)
      |> Enum.map(fn {char, x} -> {{x, y}, char} end)
    end)
    |> Map.new()
  end
end

Tests - Parser

ExUnit.start(autorun: false)

defmodule ParserTest do
  use ExUnit.Case, async: true
  import Parser

  @input """
  #####
  #S.E#
  #####
  """
  @expected %{
    {0, 0} => "#",
    {0, 1} => "#",
    {0, 2} => "#",
    {1, 0} => "#",
    {1, 1} => "S",
    {1, 2} => "#",
    {2, 0} => "#",
    {2, 2} => "#",
    {3, 0} => "#",
    {3, 1} => "E",
    {3, 2} => "#",
    {4, 0} => "#",
    {4, 1} => "#",
    {4, 2} => "#"
  }

  test "parse test" do
    actual = parse(@input)
    assert actual == @expected
  end
end

ExUnit.run()

Shared

defmodule Shared do
  def scan(map, visited, queue, distant) do
    if Prioqueue.empty?(queue) do
      distant
    else
      {{path = [node | _], node_distant, dir}, queue} = Prioqueue.extract_min!(queue)

      case neighbour(map, visited, path, dir) do
        [] ->
          scan(map, MapSet.put(visited, {node, dir}), queue, distant)

        neighbours ->
          {distant, queue} =
            neighbours
            |> Enum.reduce({distant, queue}, fn {path = [node | _], cost, dir},
                                                {distant, queue} ->
              cost = node_distant + cost

              queue = Prioqueue.insert(queue, {path, cost, dir})

              distant =
                case Map.get(map, node) do
                  "E" ->
                    {final_cost, paths} = distant

                    cond do
                      cost == final_cost -> {final_cost, [path | paths]}
                      less_than(cost, final_cost) -> {cost, [path]}
                      true -> distant
                    end

                  _ ->
                    distant
                end

              {distant, queue}
            end)

          scan(map, MapSet.put(visited, {node, dir}), queue, distant)
      end
    end
  end

  defp neighbour(map, visited, path = [{x, y} | _], curr_d = {dx, dy}) do
    [:none, :clock, :c_clock]
    |> Enum.map(fn dir ->
      next_dir = {dx, dy} = turn(dx, dy, dir)
      next = {x + dx, y + dy}
      {[next | path], cost(curr_d, next_dir), next_dir}
    end)
    |> Enum.filter(fn {[next | _], _, dir} ->
      Map.get(map, next) != "#" and
        !MapSet.member?(visited, {next, dir})
    end)
  end

  defp cost(d, d), do: 1
  defp cost(_, _), do: 1001

  defp turn(x, y, :none), do: {x, y}
  defp turn(x, y, :clock), do: {-y, x}
  defp turn(x, y, :c_clock), do: {y, -x}

  defp less_than(_, :infinity), do: true
  defp less_than(a, b), do: a < b
end

Part One

Code - Part 1

defmodule PartOne do
  def solve(input) do
    IO.puts("--- Part One ---")
    IO.puts("Result: #{run(input)}")
  end

  def run(input) do
    map = Parser.parse(input)

    curr =
      map
      |> Enum.find(fn {_, char} -> char == "S" end)
      |> then(&amp;elem(&amp;1, 0))

    queue =
      Prioqueue.new(
        [
          {[curr], 0, {1, 0}}
        ],
        cmp_fun: fn {_, a, _}, {_, b, _} -> Prioqueue.Helper.cmp(a, b) end
      )

    Shared.scan(
      map,
      MapSet.new(),
      queue,
      {:infinity, []}
    )
    |> elem(0)
  end
end

Tests - Part 1

ExUnit.start(autorun: false)

defmodule PartOneTest do
  use ExUnit.Case, async: true
  import PartOne

  @input """
  ###############
  #.......#....E#
  #.#.###.#.###.#
  #.....#.#...#.#
  #.###.#####.#.#
  #.#.#.......#.#
  #.#.#####.###.#
  #...........#.#
  ###.#.#####.#.#
  #...#.....#.#.#
  #.#.#.###.#.#.#
  #.....#...#.#.#
  #.###.#.#.#.#.#
  #S..#.....#...#
  ###############
  """
  @expected 7036

  test "part one" do
    actual = run(@input)
    assert actual == @expected
  end
end

ExUnit.run()

Solution - Part 1

PartOne.solve(puzzle_input)

Part Two

Code - Part 2

defmodule PartTwo do
  def solve(input) do
    IO.puts("--- Part Two ---")
    IO.puts("Result: #{run(input)}")
  end

  def run(input) do
    map = Parser.parse(input)

    curr =
      map
      |> Enum.find(fn {_, char} -> char == "S" end)
      |> then(&amp;elem(&amp;1, 0))

    queue =
      Prioqueue.new(
        [
          {[curr], 0, {1, 0}}
        ],
        cmp_fun: fn {_, a, _}, {_, b, _} -> Prioqueue.Helper.cmp(a, b) end
      )
    Shared.scan(
      map,
      MapSet.new(),
      queue,
      {:infinity, []}
    )
    |> elem(1)
    |> Enum.flat_map(&amp;Function.identity/1)
    |> Enum.uniq()
    |> Enum.count()
  end
end

Tests - Part 2

ExUnit.start(autorun: false)

defmodule PartTwoTest do
  use ExUnit.Case, async: true
  import PartTwo

  @input """
  ###############
  #.......#....E#
  #.#.###.#.###.#
  #.....#.#...#.#
  #.###.#####.#.#
  #.#.#.......#.#
  #.#.#####.###.#
  #...........#.#
  ###.#.#####.#.#
  #...#.....#.#.#
  #.#.#.###.#.#.#
  #.....#...#.#.#
  #.###.#.#.#.#.#
  #S..#.....#...#
  ###############
  """
  @expected 45

  test "part two" do
    actual = run(@input)
    assert actual == @expected
  end
end

ExUnit.run()

Solution - Part 2

PartTwo.solve(puzzle_input)