Advent of Code Day 15 — Beacon Exclusion Zone

Wow, okay, this same sort of puzzle came up last year, Day 19, and I really, really hated it. I took all day without making much progress and I finally went to the r/adventofcode subreddit for help. One of only twice I had to do so.

Anyway, in today’s puzzle, we have to find the one spot in a 4,000,000 x 4,000,000 grid that is not within scanning distance of one of 32 sensors scattered around the grid.

Calculating every one of these 160,000,000,000,000 positions would take awhile. In essence, this is really a problem with ray tracing — find the one pixel on a 1.6×10¹³ pixel screen that doesn’t have something displayed on it. It is possible — someone on the subreddit seems to have used a 20 core computer to solve it in this brute force way in 200ms. Other people probably thought about using a GPU to do it, but I’m not gonna learn all about programming GPUs for this puzzle (though it might be handy to know).

I got hints for this from Reddit, but not code. But the hint was: Find all the points on the peripheries of all the sensors, and find a point that was just beyond four of them. I wrote a small version of this on their small test data and verified it worked, and then I collected sets of all those points, and tried all 32! combinations of sensor peripheries to look for common ones, and then at the end, keeping track of the duplicates I found, I ran through the list of those that had four or more shared coordinates and checked them individually to see if they were open. Only one was, and that was the solution.

Part 1 (which was a misdirection, you couldn’t really solve it using the method they floated there on any normal computer), took about 1.8 seconds. Part 2 took fully 5 minutes. Coding and debugging the solution took hours.

This is the kind of puzzle I do not like. Thankfully, there weren’t a lot of these last year, but there’s always a couple. This wont be the last time I get stuck.

Python 3.11

Here’s the Python solution. I don’t want to spend any more time on this puzzle than I have to, so again, no Java solution. I was even thinking of doing the Java solution first… until I got online this morning and saw just what the puzzle was.

from time import time_ns
import re
from collections import defaultdict
from itertools import combinations


def manhattan_distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)


def read_input():
    sensor_data = []
    with open(r"2022\puzzle15.txt") as f:
        data = f.read().splitlines()
        for line in data:
            sx, sy, bx, by = map(int, re.findall(r"([\-\d]+)", line))
            sensor_data.append(
                (sx, sy, bx, by, manhattan_distance(sx, sy, bx, by)))

    return sensor_data


def query_sensors(sensor_data, row):
    scanned_positions = set()

    for sx, sy, bx, by, mdist in sensor_data:
        md = manhattan_distance(sx, sy, sx, row)

        if md <= mdist:
            bloc = (bx, by)
            for x in range(sx - (mdist - md), sx + (mdist - md) + 1):
                if (x, row) != bloc:
                    scanned_positions.add(x)

    return len(scanned_positions)


def bounds_add(s, x, y):
    if x >= 0 and x <= 4000000 and y >= 0 and y <= 4000000:
        s.add((x, y))


def periphery(sensor):
    p = set()
    # return the list of points on the periphery of the sensor
    sx, sy, _, _, mdist = sensor
    for i in range(mdist+2):
        bounds_add(p, sx-mdist-1+i, sy-i)
        bounds_add(p, sx+mdist+1-i, sy-i)
        bounds_add(p, sx-mdist-1+i, sy+i)
        bounds_add(p, sx+mdist+1-i, sy+i)
    return p


def is_inside(sensor_data, x, y):
    for sx, sy, _, _, mdist in sensor_data:
        if manhattan_distance(sx, sy, x, y) <= mdist:
            return True
    return False


def find_gaps(sensor_data):
    peripheries = {}
    candidates = defaultdict(int)

    for s in sensor_data:
        peripheries[s] = periphery(s)

    # intersection of sensor peripheries
    for s1, s2 in combinations(sensor_data, 2):
        # print (s1, s2, s3, s4)
        p1, p2 = peripheries[s1], peripheries[s2]
        z = p1.intersection(p2)
        if z:
            for zz in z:
                candidates[zz] += 1

    # find the candidate with the most sensors
    for c in candidates:
        if candidates[c] >= 4:
            if not is_inside(sensor_data, *c):
                return c[0] * 4000000 + c[1]

    return 0


sensor_data = read_input()

start = time_ns()
part1 = query_sensors(sensor_data, 2000000)
print(f"Part 1: {part1} in {(time_ns() - start)/1e6}ms")

start = time_ns()
part2 = find_gaps(sensor_data)
print(f"Part 2: {part2} in {(time_ns() - start)/1e9}s")