Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2022 - Day 15
Useful Links
Concepts and Packages Demonstrated
dataclassregexmapDictionary comprehensionMerging Intervals
Page Navigation
Problem Intro
Oh, no… Not beacons and sensors again!
For me, this is the day that AoC 2022 escalated. Up until this day, I was feeling reasonably smug about my ability to solve these challenges in the early hours before starting work. I was thinking… “I think I’m getting better at this!”
And then today happened. I spent quite a few hours on this one.
Okay, so the background…
We’ve deployed sensors to specific locations. Each sensor detects the single beacon that it is closest to. Distance is measured in Manhattan distance, i.e. the absolute of the sum of the x and y components.
Our input data gives us the location of sensors and their respective beacons:
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
Part 1
In the row where y=2000000, how many positions CANNOT contain a beacon?
Since each sensor is paired up with its nearest beacon, each sensor is therefore surrounded by a “diamond” of locations that cannot possibly contain another beacon.
So what we need to do is find all the diamonds that occupy any positions in row 2000000. These locations cannot contain beacons.
If the coordinates we were given were small, then this would be a perfect problem for some set algebra. We could work out all the points for each sensor’s coverage area, turn them into sets, and then use set algebra to get our answer.
Alas, the coordinates we’re given are NOT small. For example:
Sensor at x=2829808, y=2206448: closest beacon is at x=2930045, y=2000000
The sets would just be too huge. So, the heart of my solution is to make use of intervals that represent the inclusive ranges in our row. Where we have overlapping intervals, we’ll merge them.
Here’s my solution strategy:
- Create a
Pointclass which knows how to:- Add a vector to create a new point.
- Determine Manhattan distance to another point.
- Read in input data, to create a
dictionarythat mapsSensor ->nearestbeacon. - Create a
SensorGridclass:- It store our
Sensor -> Beacondictionary. compress_intervals_for_row()determines the horizontal slice of the diamond created by every sensor in range of this row. These horizontal slices are returned as a set of overlapping intervals.- Count all the
xvalues that make up all of these intervals. These are not allowed. - Remove any
xvalues that actually contain a beacon.
- It store our
Now in a bit more details…
Here’s the Point class:
@dataclass(frozen=True)
class Point():
""" Point with x, y coords. Knows how to add a vector, remove a vector,
and calculate Manhattan distance to to another point. """
x: int
y: int
def __sub__(self, other):
""" Subtract other point from this point, returning new point vector """
return Point(self.x - other.x, self.y - other.y)
def __add__(self, other):
""" Subtract other point from this point, returning new point vector """
return Point(self.x + other.x, self.y + other.y)
def manhattan_distance_to(self, other: Point) -> int:
""" Manhattan distance between this Vector and another Vector """
diff = self - other
return sum((abs(diff.x), abs(diff.y)))
Note how this class overrides __sub__() and __add__() methods, such that we can use the - and + operators respectively. E.g. point_c = point_a + point_b.
Here’s how I read in the input:
def process_sensors(data) -> dict[Point, Point]:
# Find four digits, preceeded by "not digit"
pattern = re.compile(r"[\D]+x=(-?\d+)[\D]+y=(-?\d+)[\D]+x=(-?\d+)[\D]+y=(-?\d+)")
sensor_to_beacon: dict[Point,Point] = {}
for line in data:
sx, sy, bx, by = map(int, pattern.findall(line)[0])
sensor_to_beacon[Point(sx, sy)] = Point(bx, by)
return sensor_to_beacon
The main thing to note here is the use of regex. The regex expression identifies four different capture groups. I.e. groups surrounded by parentheses. All the capture groups are the same: (-?\d+). This means: capture at least one numeric digit, optionall preceeded by a -.
Each of these groups is returned as a str, so I’m using map() to convert them to int values. Finally, we can build our dictionary, where the key is the sensor Point, and the value is the beacon Point.
We can then create a SensorGrid object from this dictionary:
class SensorGrid():
""" Stores a grid of Sensors, and each sensor's nearest beacon. """
def __init__(self, sensor_to_beacon: dict[Point, Point]) -> None:
""" Takes a dictionary of Sensors and their beacons """
self.sensor_to_beacon = sensor_to_beacon
self.beacons = set(sensor_to_beacon.values())
self.sensor_range = {s: b.manhattan_distance_to(s)
for s, b in self.sensor_to_beacon.items()}
self._init_bounds()
def _init_bounds(self):
""" Get the bounds by finding min and max values of any scanner or beacon,
then adding to each edge the maximum distance we've found for any Scanner->Beacon """
max_distance = max(self.sensor_range.items(), key=lambda x: x[1])[1]
self.min_x = self.min_y = self.max_x = self.max_y = 0
for s, b in self.sensor_to_beacon.items():
self.min_x = min([self.min_x, s.x, b.x])
self.max_x = max([self.max_x, s.x, b.x])
self.min_y = min([self.min_y, s.y, b.y])
self.max_y = max([self.max_y, s.y, b.y])
self.min_x -= max_distance
self.min_y -= max_distance
self.max_y += max_distance
self.max_x += max_distance
def _get_row_coverage_intervals(self, row: int) -> list[list]:
""" For each nearby sensor, get all x interval for this row.
Each sensor will return a range of coverage, like [a, b].
So all sensors will return a list of ranges, like [[a, b][c, d][d, e]...] """
# Get only the sensors that are within range of this row
close_sensors = {s:r for s, r in self.sensor_range.items() if abs(s.y - row) <= r}
intervals: list[list] = [] # store start and end y for each sensor
for sensor, max_rng in close_sensors.items():
vert_dist_to_row = abs(sensor.y - row)
max_x_vector = (max_rng - vert_dist_to_row)
start_x = sensor.x - max_x_vector
end_x = sensor.x + max_x_vector
intervals.append([start_x, end_x])
return intervals
def compress_intervals_for_row(self, row: int) -> list:
""" Determines all intervals for a given row, in the form [[a, b][c, d][d, e]...]
Intervals can overlap. Compresses to minimum number of non-overlapping intervals. """
intervals = self._get_row_coverage_intervals(row) # In the form [[a, b][c, d][d, e]...]
intervals.sort()
stack = []
stack.append(intervals[0])
for interval in intervals[1:]:
# Check for overlapping interval
if stack[-1][0] <= interval[0] <= stack[-1][-1]:
stack[-1][-1] = max(stack[-1][-1], interval[-1])
else:
stack.append(interval)
return stack
def __str__(self) -> str:
rows = []
for y in range(self.min_y, self.max_y + 1):
row = ""
for x in range(self.min_x, self.max_x + 1):
point = Point(x,y)
if point in self.sensor_to_beacon.keys():
row += "S"
elif point in self.beacons:
row += "B"
else:
row += "."
rows.append(row)
return "\n".join(rows)
Things to say about this…
- The
__init__()method:- Stores the
sensor_to_beacondictionary. - Stores a set of all the
beacons. - Uses dictionary comprehension to create a
dictionarythat maps each sensor to it’s maximum range, by calculating the Manhattan distance between the sensor and its beacon. - Determines the minimum and maximum bounds for both
xandy. To achieve this, I’ve:- Determined the minimum and maximum
xandyvalues across all the beacons and scanners. - Determined the maximum sensor range given all the sensor ranges.
- Added this maximum sensor range to the min and max values we found previously.
- Determined the minimum and maximum
- Stores the
_get_row_coverage_intervals():- First returns only the sensors that are within range of our target row. I.e. each sensor has a range, and so we only include sensors where the distance beween the sensor and our target row is less than or equal to the sensor’s previously calculated range.
- Then, for each sensor:
- Determine the range for this sensor.
- Determine how far away the row is from this sensor.
- The difference between the range and distance to our row gives us the maximum possible
xdirection - either left or right - that this sensor can cover in our target row. This is how we determine the horinzontal slice of the diamond. This is returned as an interval that extends from the minimum value of x to the maximum value of x. Thus, each sensor gives gives us an interval in the form (start, end), representing a range on the row. - Take all the intervals, and merge them into the smallest number of non-overlapping intervals.
- Add up ((end+1)-start) for each interval, to find the total number of x locations where a beacon cannot be.
compress_intervals_for_row()then takes the intervals created by_get_row_coverage_intervals(), and merges them, thus removing any overlaps. I’m doing this using the algorithm described here.- Finally, I’ve included a
__str__()method to print the sensors and beacons to the console. This is mainly to help us verify that everyting has been read and processed correctly. With the sample data, the output looks like this:
................................................
................................................
................................................
................................................
................................................
................................................
................................................
................................................
................................................
................................................
..............S.................................
................................S...............
.........................S......................
..........................SB....................
................................................
................................................
................................................
....................S.......S...................
................................................
................................................
..............B.................................
............S...................................
................................................
................................................
........................S.......S...............
..........B.....................................
.....................SB.........................
..........................S..........B..........
..............S.................................
................................................
......................S......S..................
................................................
.................................B..............
................................................
................................................
................................................
................................................
................................................
................................................
................................................
................................................
................................................
................................................
Finally, we take every interval, subtract the beginning of the interval from the end, and then add up all the results. The result is the overlap of all intervals created by all the sensors. We then subtract any locations where a beacon is found.
grid = SensorGrid(process_sensors(data))
# Part 1
row_intervals = grid.compress_intervals_for_row(TARGET_ROW)
coverage_count = sum(interval[1]-interval[0]+1 for interval in row_intervals)
beacons_to_exclude = sum(1 for beacon in grid.beacons if beacon.y == TARGET_ROW)
print(f"Part 1 - row {TARGET_ROW}: {coverage_count - beacons_to_exclude}")
Part 2
We’re told that the distress beacon has not been detected by any of sensors. And we’re told it must have x and y coordinates that are each no lower than 0 and no larger than 4000000. Finally, we’re told there will only be one valid position.
Find the only possible position for the distress beacon. What is its tuning frequency?
The tuning frequency is given by multiplying its x coordinate by 4000000 and then adding its y coordinate.
My strategy:
- The distress beacon must be distance=1 outside an existing beacon.
- Iterate through each possible row. For each row:
- Determine the intervals, like we did in Part 1.
- Look for any gaps between the intervals. We’re told that there will only be one valid location,
so if we find a single 1-unit gap between coverage intervals, then this must be the
xwe’re looking for.
Here’s the code I added:
def test_points_outside_perimeter(self) -> Point:
""" The signal beacon must be one outside of the perimeter of existing sensor boundaries. """
for sensor_point, dist_to_nearest in self.sensor_range.items():
for dx in range(dist_to_nearest+2): # max dx is dist_to_nearest + 1
dy = (dist_to_nearest+1) - dx # To always be on perimeter, dx+dy must be dist_to_nearest + 1
for sign_x, sign_y in [(-1, -1), (-1, 1), (1, -1), (1, 1)]: # Add our dx and dy in all directions
x = sensor_point.x + (dx * sign_x)
y = sensor_point.y + (dy * sign_y)
# Check within the bounds defined; if not, try next dx and dy
if not (DISTRESS_X_BOUNDS[0] <= x <= DISTRESS_X_BOUNDS[1]
and DISTRESS_Y_BOUNDS[0] <= y <= DISTRESS_Y_BOUNDS[1]):
continue
coverage = self.compress_intervals_for_row(y) # get all disallowed intervals
# look for a gap between any intervals
if len(coverage) > 1:
for i in range(1, len(coverage)+1):
if coverage[i][0] > coverage[0][1] + 1:
x = coverage[i][0] - 1
print(f"x must be {x}")
return Point(x,y)
return None
def tuning_frequency(self, point: Point) -> int:
return point.x * TUNING_FREQ_MULTIPLIER + point.y
This solution runs in under 4 seconds, so it’s fairly optimal.
Results
The final code looks like this:
from __future__ import annotations
from dataclasses import dataclass
from pathlib import Path
import re
import time
SCRIPT_DIR = Path(__file__).parent
TUNING_FREQ_MULTIPLIER = 4000000
# Test data
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
# TARGET_ROW = 10
# DISTRESS_X_BOUNDS = (0, 20)
# DISTRESS_Y_BOUNDS = (0, 20)
# Real data
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
TARGET_ROW = 2000000
DISTRESS_X_BOUNDS = (0, 4000000)
DISTRESS_Y_BOUNDS = (0, 4000000)
@dataclass(frozen=True)
class Point():
""" Point with x, y coords. Knows how to add a vector, remove a vector,
and calculate Manhattan distance to to another point. """
x: int
y: int
def __sub__(self, other):
""" Subtract other point from this point, returning new point vector """
return Point(self.x - other.x, self.y - other.y)
def __add__(self, other):
""" Subtract other point from this point, returning new point vector """
return Point(self.x + other.x, self.y + other.y)
def manhattan_distance_to(self, other: Point) -> int:
""" Manhattan distance between this Vector and another Vector """
diff = self - other
return sum((abs(diff.x), abs(diff.y)))
class SensorGrid():
""" Stores a grid of Sensors, and each sensor's nearest beacon. """
def __init__(self, sensor_to_beacon: dict[Point, Point]) -> None:
""" Takes a dictionary of Sensors and their beacons """
self.sensor_to_beacon = sensor_to_beacon
self.beacons = set(sensor_to_beacon.values())
self.sensor_range = {s: b.manhattan_distance_to(s)
for s, b in self.sensor_to_beacon.items()}
self._init_bounds()
def _init_bounds(self):
""" Get the bounds by finding min and max values of any scanner or beacon,
then adding to each edge the maximum distance we've found for any Scanner->Beacon """
max_distance = max(self.sensor_range.items(), key=lambda x: x[1])[1]
self.min_x = self.min_y = self.max_x = self.max_y = 0
for s, b in self.sensor_to_beacon.items():
self.min_x = min([self.min_x, s.x, b.x])
self.max_x = max([self.max_x, s.x, b.x])
self.min_y = min([self.min_y, s.y, b.y])
self.max_y = max([self.max_y, s.y, b.y])
self.min_x -= max_distance
self.min_y -= max_distance
self.max_y += max_distance
self.max_x += max_distance
def test_points_outside_perimeter(self) -> Point:
""" The signal beacon must be one outside of the perimeter of existing sensor boundaries. """
for sensor_point, dist_to_nearest in self.sensor_range.items():
for dx in range(dist_to_nearest+2): # max dx is dist_to_nearest + 1
dy = (dist_to_nearest+1) - dx # To always be on perimeter, dx+dy must be dist_to_nearest + 1
for sign_x, sign_y in [(-1, -1), (-1, 1), (1, -1), (1, 1)]: # Add our dx and dy in all directions
x = sensor_point.x + (dx * sign_x)
y = sensor_point.y + (dy * sign_y)
# Check within the bounds defined; if not, try next dx and dy
if not (DISTRESS_X_BOUNDS[0] <= x <= DISTRESS_X_BOUNDS[1]
and DISTRESS_Y_BOUNDS[0] <= y <= DISTRESS_Y_BOUNDS[1]):
continue
coverage = self.compress_intervals_for_row(y) # get all disallowed intervals
# look for a gap between any intervals
if len(coverage) > 1:
for i in range(1, len(coverage)+1):
if coverage[i][0] > coverage[0][1] + 1:
x = coverage[i][0] - 1
print(f"x must be {x}")
return Point(x,y)
return None
def tuning_frequency(self, point: Point) -> int:
return point.x * TUNING_FREQ_MULTIPLIER + point.y
def _get_row_coverage_intervals(self, row: int) -> list[list]:
""" For each nearby sensor, get all x interval for this row.
Each sensor will return a range of coverage, like [a, b].
So all sensors will return a list of ranges, like [[a, b][c, d][d, e]...] """
# Get only the sensors that are within range of this row
close_sensors = {s:r for s, r in self.sensor_range.items() if abs(s.y - row) <= r}
intervals: list[list] = [] # store start and end y for each sensor
for sensor, max_rng in close_sensors.items():
vert_dist_to_row = abs(sensor.y - row)
max_x_vector = (max_rng - vert_dist_to_row)
start_x = sensor.x - max_x_vector
end_x = sensor.x + max_x_vector
intervals.append([start_x, end_x])
return intervals
def compress_intervals_for_row(self, row: int) -> list:
""" Determines all intervals for a given row, in the form [[a, b][c, d][d, e]...]
Intervals can overlap. Compresses to minimum number of non-overlapping intervals. """
intervals = self._get_row_coverage_intervals(row) # In the form [[a, b][c, d][d, e]...]
intervals.sort()
stack = []
stack.append(intervals[0])
for interval in intervals[1:]:
# Check for overlapping interval
if stack[-1][0] <= interval[0] <= stack[-1][-1]:
stack[-1][-1] = max(stack[-1][-1], interval[-1])
else:
stack.append(interval)
return stack
def __str__(self) -> str:
rows = []
for y in range(self.min_y, self.max_y + 1):
row = ""
for x in range(self.min_x, self.max_x + 1):
point = Point(x,y)
if point in self.sensor_to_beacon.keys():
row += "S"
elif point in self.beacons:
row += "B"
else:
row += "."
rows.append(row)
return "\n".join(rows)
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
grid = SensorGrid(process_sensors(data))
print(grid)
# Part 1
row_intervals = grid.compress_intervals_for_row(TARGET_ROW)
coverage_count = sum(interval[1]-interval[0]+1 for interval in row_intervals)
beacons_to_exclude = sum(1 for beacon in grid.beacons if beacon.y == TARGET_ROW)
print(f"Part 1 - row {TARGET_ROW}: {coverage_count - beacons_to_exclude}")
# # Part 2: we need to find the only non-coverage point in the given area
beacon_location = grid.test_points_outside_perimeter()
print(f"Part 2: point={beacon_location}, tuning freq={grid.tuning_frequency(beacon_location)}")
def process_sensors(data) -> dict[Point, Point]:
# Find four digits, preceeded by "not digit"
pattern = re.compile(r"[\D]+x=(-?\d+)[\D]+y=(-?\d+)[\D]+x=(-?\d+)[\D]+y=(-?\d+)")
sensor_to_beacon: dict[Point,Point] = {}
for line in data:
sx, sy, bx, by = map(int, pattern.findall(line)[0])
sensor_to_beacon[Point(sx, sy)] = Point(bx, by)
return sensor_to_beacon
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
The output looks like this:
Part 1 - row 2000000: 4961647
x must be 3068581
Part 2: point=Point(x=3068581, y=3017867), tuning freq=12274327017867
Execution time: 3.9901 seconds