AoC 2022 D15: Beacon Exclusion Zone

| Problem statement | Source code | Tags: GeometryPuzzle

Part 1

This problem needs a tiny bit of geometric insight. Note that the detection range of each sensor is a circle in the Manhattan metric. The number of positions without a beacon is the number of positions in the union of these circles, minus the number of beacons. I just need to intersect each circle with the line $y=2000000$ and count the number of integer points in the union of these intervals.

Therefore, the first step is to compute the segments of intersection of each circle with the line $y=2000000$ . (BTW, I really don't like problems whose example uses a different parameter than the actual input; in this case the example uses $y=10$ instead of $y=2000000$ . If I want to make my code work on the example too, I have to pass $y$ as part of my input.)

A circle $(x, y, r)$ intersects a line $y = y_0$ if the distance $d$ from the center to the line is less than $r$ . We can measure the distance by $d=|y - y_0|$ . In this input we aren't given the radius directly, but we can compute it from the point $(x', y')$ which is the beacon that lies on the perimeter of the circle: $r = |x - x'| + |y - y'|$ . If $d < r$ , then the intersection is a line segment from $(x - (r - d), y_0)$ to $(x + (r - d), y_0)$ .

createSegments :: Int -> [(Int, Int, Int, Int)] -> [(Int, Int)]
createSegments targetY circles =
  circles
    & map (\(x1, y1, x2, y2) -> (abs (x1 - x2) + abs (y1 - y2), abs (y1 - targetY), x1, y1))
    & filter (\(r, dy, _, _) -> r >= dy)
    & map (\(r, dy, x1, _) -> (x1 - (r - dy), x1 + (r - dy)))

After getting one segment per circle, I need to get the total length of their union. I sort them by the left endpoint, and then iterate through them, keeping track of the rightmost point. If the next segment starts before the rightmost point, the current segment is extended; otherwise, a new segment is started.

mergeSegments :: [(Int, Int)] -> [(Int, Int)]
mergeSegments =
  reverse . foldl step [] . sortOn fst
  where
    step [] seg = [seg]
    step ((a, b) : acc) (c, d)
      | c <= b + 1 = (a, max b d) : acc
      | otherwise = (a, b) : (c, d) : acc

Finally I just sum the lengths of these segments (each one is $b - a + 1$ ) and subtract the number of beacons.

Part 2

Given our algorithm for part 1, which runs in time proportional to the number of circles (i.e., very fast since there are only 25), a simple algorithm is to scan through all $y$ values and compute the segments. If no gap exists, then there should be a single segment that covers $[0, 4000000]$ —i.e., if we search for a segment $(a, b)$ with $a>0$ , it should either not exist or have $a > 4000000$ . If we find a segment that has $0 < a \leq 4000000$ , then we know the gap is at $x = a - 1$ . This runs in 1.67s, which is okay.

But there's one observation: there's a unique uncovered point. This means it must be very precisely carved out from the union of the circles. Consider the 8 neighbors of the uncovered point:

We play the game of filling all blank cells by painting regions. The rules are: (1) the region must be diamond-shaped (including a single cell), (2) you can paint as many regions as you want, (3) the regions can overlap, (4) the red region must not be painted over. Focus on the 4 edge-adjacent neighbors of the red cell. Each one can either be covered by a single corner cell, or by a crossing edge, like this:

Reddit wisdom (the smart ones, not the brute-force ones) claims that if we extend the edges of these diamonds, they must intersect around the uncovered point—four of them. But this is not true. Consider the following configuration:

The blue and yellow diamonds' edges don't exactly go immediately around the uncovered point; rather, they are slightly farther away. But, there are still two conclusions we can draw: (1) we need at least 4 diamonds around the uncovered point (you can try to cover the neighbors with fewer, and (2) these diamonds' edges' lines must be no more than 4 cells away from each other. In the diagram above, the green and red diamonds' edges are 2 cells apart; the blue and yellow diamonds' edges are 4 cells apart.

Given the $(x, y, r)$ of a diamond, because the diamond's equation is $|x - x_0| + |y - y_0| = r$ , the lines of the four edges are just replacing the absolute value with positive or negative signs. We can find all such pairs of edges.

let circles = map parseLine $ tail input
let edges =
      concatMap
        ( \(x1, y1, x2, y2) ->
            let r = abs (x1 - x2) + abs (y1 - y2)
              in [ (-1, x1 + y1 + r), -- y - y1 + x - x1 = r => y = -x + x1 + y1 + r
                  (1, -x1 + y1 + r), -- y - y1 + x1 - x = r => y = x - x1 + y1 + r
                  (1, -x1 + y1 - r), -- y1 - y + x - x1 = r => y = x - x1 + y1 - r
                  (-1, x1 + y1 - r) -- y1 - y + x1 - x = r => y = -x + x1 + y1 - r
                ]
        )
        circles ::
        [(Int, Int)]
let pairs = [(s1, c1, s2, c2) | (s1, c1) <- edges, (s2, c2) <- edges, s1 == s2 && c1 - c2 <= 4 && c1 - c2 > 0]

This isn't exactly fool proof, because an adversarial input could have several diamonds that are all 2 or 4 cells apart, but it turns out that the input is very nice! In this code, it turns out that there are exactly 2 pairs of edges that are both 2 cells apart—one with positive slope and one with negative slope. The intersection of these two lines is the uncovered point:

x + c_1 = -x + c_2 \implies x = \frac{c_2 - c_1}{2}

let c1 = (\(_, c1, c1') -> (c1 + c1') `div` 2) $ fromJust $ find (\(s, _, _) -> s == 1) pairs
let c2 = (\(_, c2, c2') -> (c2 + c2') `div` 2) $ fromJust $ find (\(s, _, _) -> s == -1) pairs
let x = (c2 - c1) `div` 2
let y = x + c1

This isn't a completely satisfying solution for me because I don't think it works on every input, but it works for mine. And hey—it now runs in 10ms!

← Previous Back to AoC Index Next →