Advent of Code 2022 - Day 15

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 didn’t find a smarter way for part 2 either, brute forcing it worked but took a while. I had some idea about calculating how much sensors overlap on a given row and then use that number to skip checking rows, but I didn’t get it to work

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

Quad tree is interesting, though I’m not sure how to solve this quiz with it.

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.

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

Part 2 just about broke me. Finally got what is basically a brute force method that works fast enough for me. 12-14 seconds to get the answer. I was really struggling, trying to use MapSet operations to track each row rather than a Range. Seeing @Aetherus use of Range.disjoint/2 was a huge help.

    def part2({sensors, _beacons_by_row}, limit) do
      {y, rng} =
        0..limit
        |> Stream.map(&{&1, sensors |> filter_for_row(&1) |> sensed_at_y(&1) |> unsensed(limit)})
        |> Enum.find(fn {_y, rngs} ->
          match?([{_a, _b}], rngs)
        end)

      [{y, rng}]
      |> Enum.map(fn {y, [{s, e}]} -> [{y, div(e + s, 2)}] end)
      |> Enum.map(fn [{y, x}] -> x * 4_000_000 + y end)
      |> hd()
    end

    defp filter_for_row(sensors, y) do
      sensors |> Enum.reject(fn {{_, s_y}, d} -> abs(y - s_y) > d end)
    end

    defp sensed_at_y(sensors, target_row) do
      sensors
      |> Enum.map(fn {{x, y}, taxi_dist} ->
        delta = taxi_dist - abs(target_row - y)

        {x - delta, x + delta}
      end)
    end

    defp unsensed(sensed_stream, limit) do
      sensed_stream
      |> Enum.sort()
      |> Enum.reduce_while([{0, limit}], fn {s, e}, unsensed ->
        case exclude_sensed({s, e}, unsensed) do
          [{a, b}] when b - a == 2 ->
            {:halt, div(b + a, 2)}

          acc ->
            {:cont, acc}
        end
      end)
    end

    defp exclude_sensed({_s, _e}, []), do: []

    defp exclude_sensed({s, e}, [{ss, ee} | ranges]) do
      if Range.disjoint?(s..e, ss..ee) do
        [{ss, ee} | ranges]
      else
        cond do
          s > ss and e < ee -> [{ss, s - 1} | exclude_sensed({e + 1, ee}, ranges)]
          s > ss -> [{ss, s - 1}]
          e < ee -> [{e + 1, ee}]
          true -> []
        end
      end
    end

Actually, using Range.disjoint?/2 was a mistake. Consider this situation, at some y, there are 3 ranges before merging: 0..10, 11..20, 21..30, how many ranges should there be after merging? There should be only one range, 0..30. But Range.disjoint?/2 will tell you all those ranges are disjoint to each other, so they won’t merge.

I think it works for this exercise b/c there is no difference between [{0..30}] and [{0..10}, {11..20}, {21..30}]. Both indicate a situation where there is more than one item remaining. Also contrary to your method of merging ranges, I was sort of breaking the full range 0..limit up into smaller ranges.