d18

Section

defmodule D18 do
  defstruct width: 0, height: 0, bytes: [], blocked: MapSet.new()

  def parse(input, dim \\ 71) do
    bytes =
      for line <- String.split(input), into: [] do
        String.split(line, ",")
        |> Enum.map(&String.to_integer/1)
        |> List.to_tuple()
      end

    blocked =
      for {xrange, yrange} <- [
            {-1..-1, -1..dim},
            {-1..dim, dim..dim},
            {dim..dim, -1..dim},
            {-1..dim, -1..-1}
          ],
          x <- xrange,
          y <- yrange,
          into: MapSet.new() do
        {x, y}
      end

    %D18{bytes: bytes, width: dim, height: dim, blocked: blocked}
  end

  defp vec_add({r, c}, {dr, dc}), do: {r + dr, c + dc}

  defp pop_min(distance, frontier) do
    key = Enum.min_by(frontier, &Map.get(distance, &1))
    {key, MapSet.delete(frontier, key)}
  end

  defp dijkstra(blocked, distance, frontier, goal) do
    if Enum.empty?(frontier) do
      distance
    else
      {pos, frontier} = pop_min(distance, frontier)

      cond do
        pos == goal ->
          distance

        true ->
          {distance, frontier} =
            for delta <- [{-1, 0}, {0, 1}, {1, 0}, {0, -1}],
                reduce: {distance, frontier} do
              {distance, frontier} ->
                dest = vec_add(pos, delta)
                new_distance = Map.get(distance, pos) + 1
                old_distance = Map.get(distance, dest)

                if !MapSet.member?(blocked, dest) and
                     (is_nil(old_distance) or
                        new_distance < old_distance) do
                  {Map.put(distance, dest, new_distance), MapSet.put(frontier, dest)}
                else
                  {distance, frontier}
                end
            end

          dijkstra(blocked, distance, frontier, goal)
      end
    end
  end

  def part1(%D18{width: width, height: height, bytes: bytes, blocked: blocked}, steps \\ 1024) do
    start = {0, 0}
    goal = {width - 1, height - 1}
    blocked = bytes |> Enum.take(steps) |> MapSet.new() |> MapSet.union(blocked)
    distance = dijkstra(blocked, %{start => 0}, MapSet.new([start]), goal)
    Map.get(distance, goal)
  end

  def part2(%D18{width: width, height: height, bytes: bytes, blocked: blocked}) do
    start = {0, 0}
    goal = {width - 1, height - 1}

    Stream.from_index(1)
    |> Stream.drop_while(fn steps ->
      blocked = bytes |> Enum.take(steps) |> MapSet.new() |> MapSet.union(blocked)
      distance = dijkstra(blocked, %{start => 0}, MapSet.new([start]), goal)
      Map.has_key?(distance, goal)
    end)
    |> Enum.at(0)
    |> then(&Enum.at(bytes, &1 - 1))
    |> Tuple.to_list()
    |> Enum.join(",")
  end
end

ExUnit.start()

defmodule D18.Test do
  use ExUnit.Case

  test "sample" do
    input = "5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0
"
    assert 22 == D18.parse(input, 7) |> D18.part1(12)
    assert "6,1" == D18.parse(input, 7) |> D18.part2()
  end
end

ExUnit.run()

input = File.read!(__DIR__ <> "/input")
D18.parse(input) |> D18.part1()

D18.parse(input) |> D18.part2()