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

I solved part 1 by brute force.

For part 2, after brute-force not working on 4,000,000 x 4,000,000 (I wonder why?), I thought about “walking the edges”:

image1200×1151 58 KB

The idea is that for each pair of Sensor–Beacon, we can be sure the outlying (solution) beacon cannot be under the red line. Given that within x = 0..4M, y = 0..4M there is only one possible solution, the solution beacon would have to fall under the green line.

More specifically, it should be the point which falls under the most green lines:

image1200×718 52.3 KB

So my Part 2 solution is iterating over each sensor–beacon pair to trace the points under the green line (Manhattan distance + 1), and find the most overlap. The code can be further optimized, but I was just happy it worked…

  def part_2(input \\ "test") do
    coord =
      input
      |> load_data()
      |> Enum.map(&parse_structured_data/1)

    edges =
      for [{s_x, s_y}, {b_x, b_y}] <- coord do
        list_outside_edges({s_x, s_y}, {b_x, b_y})
      end

    edges
    |> List.flatten
    |> Enum.frequencies
    |> Enum.sort_by(fn {_, v} -> v  end, :desc)
    |> Enum.at(0)
  end

  def list_outside_edges({x, y}, {b_x, b_y}) do
    d = manhattan_distance({x, y}, {b_x, b_y}) + 1

    edges_no_top_corners = for i <- 0..d-1 do
      [
        {x-d+i, y+i},
        {x-d+i, y-i},
        {x+d-i, y-i},
        {x+d-i, y+i}
      ]
    end

    [{x, y-d} | [{x, y+d} | edges_no_top_corners]]
    |> List.flatten
    |> Enum.uniq
  end

Well to use quad trees at each step I checked if the four corners of a quad (a square) were in range of the same sensor. If yes then the quad is fully covered. Otherwise I would split the quad and check recursively.

At some point you end up with a quad of size 1x1 that is not covered, and that is the solution.

It is not very efficient, but at the time the solution is found there are only 33 different quads in my tree, with my input.