[Advent Of Code 2022] Day 15: Beacon Exclusion Zone [SPOILERS]

Programming
1

This was an interesting problem! It took me about 45 minutes to work out. Part two was interesting to think about and work out.

I played around with a few configurations to optimize runtimes and managed to solve part two in anywhere from 110s to 1.5s.

Code: Latest – Just Solve It

Runtime Details
  • Take 1, using the NUC and dataclass for the Sensor: 110s
  • Take 2, using the NUC and a tuple for the Sensor, reducing function calls: 53s
  • Take 3, same code as take 2 but on the desktop: 37s.
  • Take 4, same code and hardware as take 3, switching cython for mypy3: 1.5s.
Python Solution 
    def part1(self, parsed_input: InputType) -> int:
        """Return the number of coordinates on a given row which cannot contain the beacon.

        For each sensor, find the x-range the sensor covers on the given row.
        """
        row = 10 if self.testing else 2000000

        x_positions = set()
        for sensor_x, sensor_y, sensor_range in parsed_input:
            y_dist = abs(row - sensor_y)
            if y_dist > sensor_range:
                continue
            covered_x_range_start = sensor_x - (sensor_range - y_dist)
            covered_x_range_end = sensor_x + (sensor_range - y_dist)
            x_positions.update(range(covered_x_range_start, covered_x_range_end))
        return len(x_positions)

    def part2(self, parsed_input: InputType) -> int:
        """Locate the distress beacon.

        For each row, start a cursor at the left.
        Iterate through sensors in order, and move the cursor to just past the right
        edge of the sensor (if the cursor is within sensor range).
        When all sensors were applied, if the cursor is within the boundaries of the board,
        that is where the distress beacon is located.
        """
        dims = 20 if self.testing else 4000000
        sensor_tuples = parsed_input
        # Sort sensors, left to right.
        sensor_tuples.sort()

        # Test each row until we find the beacon.
        for candidate_y in range(dims + 1):
            candidate_x = 0
            # For each sensor, move the cursor to just past the right end, if it is in sensor range.
            for sensor_x, sensor_y, sensor_range in sensor_tuples:
                y_dist = abs(sensor_y - candidate_y)
                point_dist = abs(sensor_x - candidate_x) + y_dist
                if point_dist <= sensor_range:
                    candidate_x = sensor_x + sensor_range - y_dist + 1
            if candidate_x <= dims:
                self.debug(f"Solved!!! {candidate_x, candidate_y}")
                return candidate_x * 4000000 + candidate_y

    def line_parser(self, line: str) -> tuple[int, int, int]:
        """Parse a line into a tuple of sensor's coordinates and range."""
        a, b, c, d = (int(i) for i in aoc.RE_INT.findall(line))
        return a, b, abs(a - c) + abs(b - d)
2

I completely redid how I solved this exercise and now both parts run in 1ms.

New and Improved

def flatten_ranges(ranges: list[tuple[int, int]]) → list[tuple[int, int]]:
“”“Flatten a list of ranges into a set of non-overlapping ranges.”“”
out = []
ranges = sorted(ranges)
start_a, end_a = ranges[0]
for start_b, end_b in ranges[1:]:
if end_b < start_a:
# Distinct ranges, range b occurs before range a.
raise RuntimeError(“Ranges not sorted!”)
if start_b > end_a:
# Distinct ranges, range b occurs after range a.
out.append((start_a, end_a))
start_a, end_a = start_b, end_b
else:
# Ranges overlap. Combine ranges.
start_a = min(start_a, start_b)
end_a = max(end_a, end_b)
out.append((start_a, end_a))
return out

def input_parser(self, puzzle_input: str) -> InputType:
    data = []
    for line in puzzle_input.splitlines():
        a, b, c, d = (int(i) for i in aoc.RE_INT.findall(line))
        data.append((a, b, abs(a - c) + abs(b - d)))
    data.sort()
    return data

def part1(self, parsed_input: InputType) -> int:
    row = 10 if self.testing else 2000000

    ranges = []
    for sensor_x, sensor_y, sensor_range in parsed_input:
        y_dist = abs(row - sensor_y)
        if y_dist > sensor_range:
            continue
        start = sensor_x - (sensor_range - y_dist)
        end = sensor_x + (sensor_range - y_dist)
        ranges.append((start, end))

    covered_points = sum(end - start for start, end in flatten_ranges(ranges))
    return covered_points
def part2_line_intersections(self, sensors: InputType):
    """Use line intersections to locate the distress beacon.
    * For each (sorted) sensor combination, check if their distance is one more
      than their combined range, i.e. they have space for exactly one unit of space
      between them.
    * Based on the relative `y` positions, this is either a 45 degree line
      up-and-right or down-and-right. The slope is either `+1` or `-1`.
      These lines can be stored as `y = mx + b` or just `b`
      if using two containers for the different slopes.
    * For each combination of `m = +1` and `m = -1` lines, compute the intersection.
      Filter out intersections outside the bounding box, `(0, 4,000,000) x (0, 4,000,000)`
      (optional if there are multiple lines).
    * The intersection gives the coordinates of the distress beacon.
    """

    x_intersects: dict[int, set[int]] = {+1: set(), -1: set()}
    # Find sensor pairs with borders 2 units apart.
    for pairs in itertools.combinations(sensors, 2):
        sensor_a_x, sensor_a_y, sensor_a_range = pairs[0]
        sensor_b_x, sensor_b_y, sensor_b_range = pairs[1]
        sensor_dist = abs(sensor_a_x - sensor_b_x) + abs(sensor_a_y - sensor_b_y)
        # Check the distance between sensor range edges.
        if sensor_dist != sensor_a_range + sensor_b_range + 2:
            continue

        # Compute and store the slope-intersect values.
        slope = +1 if sensor_a_y > sensor_b_y else -1
        b = sensor_a_x + sensor_a_range + 1 + (-slope * sensor_a_y)
        x_intersects[slope].add(b)

    self.debug(x_intersects)

    # For all intersecting lines, compute the intersection point.
    candidate_points = set()
    for ur, dr in itertools.product(x_intersects[1], x_intersects[-1]):
        diff = (dr - ur)
        if diff % 2 == 1:
            continue
        x_intersect = (dr + ur) // 2
        y_intersect = diff // 2
        # Ignore points out of bounds.
        if not all(0 <= intersect <= 4000000 for intersect in (x_intersect, y_intersect)):
            continue
        candidate_points.add((x_intersect, y_intersect))

    # Return the answer.
    if len(candidate_points) != 1:
        raise RuntimeError("Want one point, found {len(candidate_points)}")
    x_intersect, y_intersect = candidate_points.pop()
    return x_intersect * 4000000 + y_intersect
3

@IsaacG The title of the topic used the previous day’s title. I’ve updated

1 Like