Day 15

Section

defmodule Day15 do
  def part1(input) do
    y = 2_000_000

    sensors = Enum.filter(input, &match?({_, {:sensor, _}}, &1))

    ranges = ranges_at_y(sensors, y)

    covered =
      ranges
      |> Enum.map(fn s..e ->
        e - s + 1
      end)
      |> Enum.sum()

    beacons =
      Enum.count(input, fn {{_, yb}, type} ->
        type == :beacon and yb == y
      end)

    covered - beacons
  end

  def part2(input) do
    sensors = Enum.filter(input, &match?({_, {:sensor, _}}, &1))

    {y, ranges} =
      0..4_000_000
      |> Stream.map(&{&1, ranges_at_y(sensors, &1)})
      |> Enum.find(&match?({_, [_, _]}, &1))

    [_..x1, x2.._] = Enum.sort(ranges)

    # This statement is an assertion
    2 = x2 - x1

    IO.inspect({div(x1 + x2, 2), y})

    div(x1 + x2, 2) * 4_000_000 + y
  end

  # matrix for turning left 45 degrees 
  # and stretch by the factor sqrt(2)
  @m {
    {1, -1},
    {1, 1}
  }

  # inverse of @m
  @inv_m {
    {0.5, 0.5},
    {-0.5, 0.5}
  }

  def part2_v2(input) do
    sensors =
      input
      |> Enum.filter(&match?({_, {:sensor, _}}, &1))
      |> Enum.map(fn {{xc, yc}, {:sensor, r}} ->
        {
          # left corner --> bottom-left corner
          mul(@m, {xc - r, yc}),
          # right corner --> top-right corner
          mul(@m, {xc + r, yc})
        }
      end)

    x_pairs =
      sensors
      |> Enum.flat_map(fn {{x1, _}, {x2, _}} ->
        [x1, x2]
      end)
      |> Enum.uniq()
      |> Enum.sort()
      |> Enum.chunk_every(2, 1, :discard)
      |> Enum.filter(fn [x1, x2] -> x2 - x1 == 2 end)

    y_pairs =
      sensors
      |> Enum.flat_map(fn {{_, y1}, {_, y2}} ->
        [y1, y2]
      end)
      |> Enum.uniq()
      |> Enum.sort()
      |> Enum.chunk_every(2, 1, :discard)
      |> Enum.filter(fn [y1, y2] -> y2 - y1 == 2 end)

    for [x1, x2] <- x_pairs,
        [y1, y2] <- y_pairs,
        x = div(x1 + x2, 2),
        y = div(y1 + y2, 2),
        p = {x, y},
        !Enum.any?(sensors, &amp;cover?(&amp;1, p)),
        {x, y} = mul(@inv_m, p),
        do: x * 4_000_000 + y
  end

  defp cover?({{x1, y1}, {x2, y2}}, {x, y}) do
    x in x1..x2 and y in y1..y2
  end

  defp mul(
         {
           {a, b},
           {c, d}
         },
         {x, y}
       ) do
    {
      trunc(a * x + b * y),
      trunc(c * x + d * y)
    }
  end

  defp ranges_at_y(sensors, y) do
    sensors
    |> Stream.reject(fn {{_xc, yc}, {:sensor, radius}} ->
      abs(y - yc) > radius
    end)
    |> Stream.map(fn {{xc, yc}, {:sensor, radius}} ->
      (xc - (radius - abs(y - yc)))..(xc + (radius - abs(y - yc)))
    end)
    |> merge_ranges()
  end

  defp merge_ranges(ranges) do
    [h | t] = Enum.sort(ranges)
    do_merge_ranges(t, [h])
  end

  defp do_merge_ranges([s2..e2 | t2], [s1..e1 | t1]) when s2 <= e1 + 1 do
    do_merge_ranges(t2, [s1..max(e1, e2) | t1])
  end

  defp do_merge_ranges([range2 | t2], acc) do
    do_merge_ranges(t2, [range2 | acc])
  end

  defp do_merge_ranges([], acc), do: acc

  def parse_input(path) do
    path
    |> File.stream!()
    |> Enum.flat_map(&amp;parse_line/1)
    |> Map.new()
  end

  defp parse_line(line) do
    ~r/(?<=[xy]=)[^,:\s]+/
    |> Regex.scan(line)
    |> List.flatten()
    |> Enum.map(&amp;String.to_integer/1)
    |> then(fn [xs, ys, xb, yb] ->
      [{{xs, ys}, {:sensor, manhattan({xs, ys}, {xb, yb})}}, {{xb, yb}, :beacon}]
    end)
  end

  defp manhattan({x1, y1}, {x2, y2}) do
    abs(x1 - x2) + abs(y1 - y2)
  end
end

input = Day15.parse_input("#{__DIR__}/day15.txt")

Day15.part1(input)

Day15.part2_v2(input)

Day15.part2(input)