Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3


# Python imports

import numpy as np
import re

from collections import defaultdict
from pathlib import Path


test = Path("data/day15_test.txt")  # test data
data = Path("data/day15_data.txt")  # puzzle data


def parse_input(fpath: Path) -> list[tuple[tuple, tuple, tuple]]:
    """Parse puzzle input: list of sensor/beacon location pairs and distances
    
    :param fpath: path to puzzle input
    
    Returns (sensor_location, beacon_location, distance vector) where
    the distance vector is that between the sensor and the beacon
    """
    pattern = re.compile("Sensor at x=([\-0-9]*), y=([\-0-9]*): closest beacon is at x=([\-0-9]*), y=([\-0-9]*)")
    output = []
    
    with fpath.open() as ifh:
        for line in [_.strip() for _ in ifh.readlines()]:
            data = [int(_) for _ in pattern.match(line).groups()]
            output.append(((data[0], data[1]), (data[2], data[3]),
                           (abs(data[2] - data[0]), abs(data[3] - data[1]))))
            
    return output
            
    
def part1(fpath: Path, row: int) -> int:
    """Solve the puzzle
    
    :param fpath:  path to puzzle input
    :param row:  row number named in the puzzle - we're returning the
                 number of locations on that row at which a beacon
                 cannot exist
    """
    excluded_all = set()  # hold all excluded points on the query row
    
    data = parse_input(fpath)
    for sensor, beacon, dist in data:  # Iterate over sensor/beacon/distance data
        # Calculate locations in excluded region on target row for each
        # sensor/beacon combination
        # Excluded region at sensor[1] + ydist has width (xdist * 2) + 1, centred on sensor[0]
        # Each row further from sensor reduces width by 2, each closer row increases width by 2
        # Width at sensor is then (xdist * 2) + 1 + (2 * ydist)
        # Width at row is then (xdist * 2) + 1 + (2 * ydist) - 2 * abs(row - sensor[1])
        senswidth = (dist[0] * 2) + 1 + (2 * dist[1])
        row_width = senswidth - 2 * abs(row - sensor[1])  # width of excluded region
        # Define locations on query row where there's no beacon, as a set
        excluded_x = set(range(sensor[0] - row_width//2, sensor[0] + row_width//2 + 1))
        excluded_all = excluded_all.union(excluded_x)
    
    # Remove any beacon locations present in excluded_all
    for sensor, beacon, dist in data:
        if beacon[1] == row:
            excluded_all.discard(beacon[0])
    
    return len(excluded_all)


part1(test, 10)

26


part1(data, 2000000)

4827924


def part2(fpath: Path, lim: int) -> int:
    """Solve the puzzle
    
    :param fpath:  path to puzzle input
    :param lim:  upper bound on x/y coords (all points within (0, 0) -> (lim, lim))
    
    This solution is rather slow. There must be a more efficient way to do this.
    Could we get there with simultaneous equations?
    """    
    data = parse_input(fpath)  # Load puzzle data
    all_candidates = defaultdict(int)  # holds locations in scope (within limits) that might be distress beacon
    
    # The point we're looking for is exactly dist+1 away from any nearest sensor
    # The solution is isolated, so must be bounded by at least four sensors at dist-1
    # We iterate over all sensors, generating dist+1 points, and see which of those
    # points is dist+1 points from at least 4 sensors
    for sensor, beacon, dist in data:
        dist = sum(dist)
        # Scan from leftmost sensor-excluded region, populating with
        # the points dist + 1 from the sensor
        for xpos in range(max(0, sensor[0] - (dist + 1)), min(sensor[0] + (dist + 1), lim)):
            yshift = abs(abs(xpos - sensor[0]) - abs(dist + 1))  # distance up/down to candidate
            if 0 <= (sensor[1] + yshift) <= lim:
                all_candidates[(xpos, sensor[1] + yshift)] += 1
            if 0 <= (sensor[1] - yshift) <= lim:
                all_candidates[(xpos, sensor[1] - yshift)] += 1

    # Identify locations with four dist+1 sensors, that are within the limits
    # These are our candidate solutions
    locations = {_[0] for _ in all_candidates.items() if _[1] >= 4}
    if len(locations) == 1:  # We have found the only solution
        x, y = tuple(list(locations)[0])
        return 4000000 * x + y

    # If we've more than one solution, we need to exclude disallowed options
    # Exclude those within range of a sensor
    for sensor, beacon, dist in data:
        dist = sum(dist)
        exclude = set()
        for location in locations:
            if abs(sensor[0] - location[0]) + abs(sensor[1] - location[1]) <= dist:
                exclude.add(location)
        locations = locations.difference(exclude)    
    
    # Return the solution (we trust there is only one)
    x, y = tuple(list(locations)[0])
    return 4000000 * x + y


part2(test, 20)

56000011


import time

t0 = time.time()
print(part2(data, 4000000))
print(f"{time.time() - t0}s")

12977110973564
41.07965898513794s

Day 15: Beacon Exclusion Zone¶

Part 1¶

Part 2¶