Advent of Code 2023

Mix.install([
  {:req, "~> 0.3.2"},
  {:libgraph, "~> 0.16.0"}
])

Day 17

input =
  "https://adventofcode.com/2023/day/17/input"
  |> Req.get!(headers: [cookie: "session=#{System.get_env("AOC_COOKIE")}"])
  |> Map.get(:body)

sample = """
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533
"""

sample2 = """
111111111111
999999999991
999999999991
999999999991
999999999991
"""

Section

defmodule Day17 do
  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> grid()
  end

  def grid(lines) do
    rows = lines |> Enum.count()
    cols = lines |> hd() |> String.length()

    grid =
      for {row, y} <- Enum.with_index(lines),
          {c, x} <- String.split(row, "", trim: true) |> Enum.with_index(),
          into: %{},
          do: {{x, y}, String.to_integer(c)}

    %{
      rows: rows,
      cols: cols,
      data: grid
    }
  end

  def expand(pq, seen, grid, path_fun) do
    {{:value, node}, pq} = PriorityQueue.pop(pq)
    # %{x: x, y: y, dir: {dir, n}} = node
    {cost, {x, y}, {dir, n}, path} = node

    path_fun.(dir, n)
    |> Enum.map(fn
      {:right, _} = dir -> {{x + 1, y}, dir}
      {:down, _} = dir -> {{x, y + 1}, dir}
      {:up, _} = dir -> {{x, y - 1}, dir}
      {:left, _} = dir -> {{x - 1, y}, dir}
    end)
    # out of bounds check
    |> Enum.reject(&amp;(!Map.has_key?(grid.data, elem(&amp;1, 0))))
    |> Enum.reduce({pq, seen}, fn {coord, dir}, {pq, seen} ->
      new_cost = cost + grid.data[coord]
      node = {new_cost, coord, dir, [{x, y} | path]}

      if MapSet.member?(seen, {coord, dir}) do
        {pq, seen}
      else
        {
          PriorityQueue.push(pq, node, new_cost),
          MapSet.put(seen, {coord, dir})
        }
      end
    end)
  end

  defp paths(dir, n) when n < 3 do
    [
      {turn_left(dir), 1},
      {turn_right(dir), 1},
      {dir, n + 1}
    ]
  end

  defp paths(dir, _n) do
    [
      {turn_left(dir), 1},
      {turn_right(dir), 1}
    ]
  end

  defp ultra_paths(dir, n) when n < 4, do: [{dir, n + 1}]
  defp ultra_paths(dir, 10), do: [{turn_left(dir), 1}, {turn_right(dir), 1}]

  defp ultra_paths(dir, n) do
    [
      {turn_left(dir), 1},
      {turn_right(dir), 1},
      {dir, n + 1}
    ]
  end

  def turn_left(dir) do
    %{left: :down, down: :right, right: :up, up: :left}[dir]
  end

  def turn_right(dir) do
    %{left: :up, down: :left, right: :down, up: :right}[dir]
  end

  def search(pq, dest, grid, seen, path_fun, part2? \\ false, draw? \\ false) do
    Stream.iterate(1, &amp;(&amp;1 + 1))
    |> Enum.reduce_while({pq, seen}, fn _, {pq, seen} ->
      {:value, node} = PriorityQueue.peek(pq)
      {cost, coord, {_dir, n}, path} = node

      if coord == dest do
        if part2? &amp;&amp; n < 4 do
          {:cont, expand(pq, seen, grid, path_fun)}
        else
          if draw? do
            grid2 =
              [coord | tl(path |> Enum.reverse())]
              |> Enum.reduce(grid.data, fn p, acc -> Map.put(acc, p, " ") end)

            for(y <- 0..(grid.rows - 1), x <- 0..(grid.cols - 1), do: grid2[{x, y}])
            |> Enum.chunk_every(grid.cols)
            |> Enum.map(&amp;Enum.join/1)
            |> Enum.join("\n")
            |> IO.puts()

            [coord | tl(Enum.reverse(path))]
            |> Enum.map(&amp;grid.data[&amp;1])
            |> Enum.sum()
            |> IO.inspect()
          end

          {:halt, cost}
        end
      else
        {:cont, expand(pq, seen, grid, path_fun)}
      end
    end)
  end

  def part1(input) do
    grid = parse(input)
    seen = MapSet.new()

    start = {0, 0}
    dest = {grid.cols - 1, grid.rows - 1}

    # {cost, {x, y}, direction}
    pq =
      PriorityQueue.new()
      |> PriorityQueue.push({0, start, {:right, 0}, []}, 0)
      |> PriorityQueue.push({0, start, {:down, 0}, []}, 0)

    search(pq, dest, grid, seen, &amp;paths/2)
  end

  def part2(input, draw? \\ false) do
    grid = parse(input)
    seen = MapSet.new()

    start = {0, 0}
    dest = {grid.cols - 1, grid.rows - 1}

    # {cost, {x, y}, direction}
    pq =
      PriorityQueue.new()
      |> PriorityQueue.push({0, start, {:right, 0}, []}, 0)
      |> PriorityQueue.push({0, start, {:down, 0}, []}, 0)

    search(pq, dest, grid, seen, &amp;ultra_paths/2, true, draw?)
  end
end

Day17.part1(input)

Day17.part2(sample)

Day17.part2(sample2)

Day17.part2(input, true)