Day 15

Input

Mix.install([{:kino, github: "livebook-dev/kino"}])

textarea = Kino.Input.textarea("Input:")

Common

defmodule Common do
  def parse_input(raw_input) do
    raw_input
    |> String.split()
    |> Enum.with_index()
    |> Enum.flat_map(fn {line, y} ->
      line
      |> String.split("", trim: true)
      |> Enum.with_index()
      |> Enum.map(fn {num_as_str, x} ->
        {
          {x, y},
          %{
            position: {x, y},
            weight: String.to_integer(num_as_str),
            distance: 999_999_999_999
          }
        }
      end)
    end)
    |> Enum.into(%{})
  end

  def dijkstra(%{position: finish, distance: distance}, finish, queue) do
    IO.puts("finished at #{inspect(finish)}")
    distance
  end

  def dijkstra(_current_node, _finish, queue) when map_size(queue) == 0 do
    raise "Queue is empty"
  end

  def dijkstra(current_node, finish, queue) do
    # IO.puts("Visiting #{inspect(current_node)}")

    queue =
      queue
      |> neighbours(current_node.position)
      |> Enum.reduce(queue, fn neighbour, queue ->
        potential_distance = current_node.distance + neighbour.weight

        if neighbour.distance > potential_distance do
          neighbour = %{neighbour | distance: potential_distance}
          Map.put(queue, neighbour.position, neighbour)
        else
          queue
        end
      end)
      |> Map.delete(current_node.position)

    case queue do
      [] ->
        raise "nowhere to go"

      _ ->
        {_key, next_node} = Enum.min_by(queue, fn {_key, %{distance: distance}} -> distance end)
        dijkstra(next_node, finish, queue)
    end
  end

  def neighbours(queue, {x, y}) do
    [
      queue[{x + 1, y}],
      queue[{x - 1, y}],
      queue[{x, y + 1}],
      queue[{x, y - 1}]
    ]
    |> Enum.reject(&is_nil/1)
    |> Enum.sort_by(& &1.weight)
  end

  def shortest_path(_input, to, to), do: [to]

  def shortest_path(input, from, to) do
    next =
      input
      |> neighbours(from)
      |> Enum.min_by(& &1.distance)

    [from | shortest_path(input, next.position, to)]
  end
end

raw_input = Kino.Input.read(textarea)
input = Common.parse_input(raw_input)

Part 1

defmodule Part1 do
  def run(input) do
    {max, _} = Enum.max_by(input, &Tuple.product(elem(&1, 0)))
    input = Map.update!(input, {0, 0}, fn n -> %{n | distance: 0} end)
    Common.dijkstra(input[{0, 0}], max, Map.delete(input, {0, 0}))
  end
end

Part1.run(input)
# [
#   input[{0, 0}],
#   input[{0, 1}],
#   input[{0, 2}],
#   input[{1, 2}],
#   input[{2, 2}],
#   input[{3, 2}],
#   input[{4, 2}],
#   input[{5, 2}],
#   input[{6, 2}],
#   input[{6, 3}],
#   input[{7, 3}],
#   input[{7, 4}],
#   input[{7, 5}],
#   input[{8, 5}],
#   input[{8, 6}],
#   input[{8, 7}],
#   input[{8, 8}],
#   input[{9, 8}],
#   input[{9, 9}]
# ]
# Enum.reverse(Common.shortest_path(input, {9, 9}, {0, 0}))

Part 2

defmodule Part2 do
  def run(input) do
    times = 4

    {_key, %{position: {_, height}}} = Enum.max_by(input, fn {_key, %{position: {_, y}}} -> y end)
    {_key, %{position: {width, _}}} = Enum.max_by(input, fn {_key, %{position: {x, _}}} -> x end)

    width = width + 1
    height = height + 1

    transform = fn original, offset ->
      case original + offset do
        number when number > 9 -> number - 9
        number -> number
      end
    end

    matrix =
      for y <- 0..times do
        for x <- 0..times do
          case {x, y} do
            {0, 0} -> nil
            z -> Tuple.sum(z)
          end
        end
      end

    input =
      matrix
      |> Enum.with_index()
      |> Enum.reduce(input, fn {offsets, y}, acc ->
        offsets
        |> Enum.with_index()
        |> Enum.reduce(acc, fn
          {nil, _x}, acc ->
            acc

          {offset, x}, acc ->
            Enum.reduce(input, acc, fn {_key, item}, acc ->
              new_weight = transform.(item.weight, offset)
              {old_x, old_y} = item.position

              new_position = {
                old_x + x * width,
                old_y + y * height
              }

              new_item = %{item | weight: new_weight, position: new_position}

              Map.put(acc, new_position, new_item)
            end)
        end)
      end)

    {max, _} = Enum.max_by(input, &amp;Tuple.product(elem(&amp;1, 0))) |> IO.inspect(label: :max)
    input = Map.update!(input, {0, 0}, fn n -> %{n | distance: 0} end)
    Common.dijkstra(input[{0, 0}], max, Map.delete(input, {0, 0}))
  end
end

Part2.run(input)