I figured I only need to do some simple filtering then I can get the true result. It takes less than 500 microseconds on my laptop.

  # 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}
  }


  # `sensors` is a list of {xc, yc, r}
  # where `xc` and `yc` is the coordinate of the center of a sensor,
  # and `r` is its manhattan radius.
  def part2_v2(sensors) do
    sensors =
      sensors
      |> Enum.map(fn {xc, yc, 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, &cover?(&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

I did the same for part 2, took 12 seconds. On reddit someone suggested quad trees, I tried it and I’m down to less than 1.5 second.

On slack someone suggested an even better way (~4 ms) but I’m too lazy to try it

I came up with an idea that involves a little bit of linear algebra:

1. Rotate the whole map by 45 degrees to the left, so that the diamond-shaped sensor coverages become square.
2. If there is a point covered by no sensor, there must be a sqrt(2)-unit-wide gap between some pair of the vertical edges of those squares, and a sqrt(2)-unit-high gap between some pair of the horizontal edges of those squares. (by the way, I can do this because there’s no 2x2 sensor)
3. Find that point and convert it back to its original position.

The problem is, there are multiple such gaps

The good news is, there are not so many such gaps. I can just try all the results util I pass the quiz

Here’s my new code:

  # matrix for turning left 45 degrees 
  # and stretch by the factor sqrt(2).
  # It's not a unit matrix because I don't want to deal with irrational numbers.
  @m {
    {1, -1},
    {1,  1}
  }

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

  # `sensors` is a list of {xc, yc, r}
  # where `xc` and `yc` is the coordinate of the center of a sensor,
  # and `r` is its manhattan radius.
  def part2_v2(sensors) do
    sensors =
      sensors
      |> Enum.map(fn {xc, yc, r} ->
        {
          mul(@m, {xc - r, yc}),  # left corner --> bottom-left corner
          mul(@m, {xc + r, yc})   # right corner --> top-right corner
        }
      end)

    x_pairs =
      sensors
      |> Enum.flat_map(fn {{x1, _}, {x2, _}} ->
        [x1, x2]
      end)
      |> Enum.uniq()
      |> Enum.sort()
      |> Enum.chunk_every(2, 1, :discard)
      # because the map is stretched by factor sqrt(2),
      # the sqrt(2)-unit-wide gaps become 2-unit wide.
      |> 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 do
      x = (x1 + x2) / 2
      y = (y1 + y2) / 2
  
      {x, y} = mul(@inv_m, {x, y})
      IO.inspect(x * 4_000_000 + y)
    end
  end

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