Advent of Code - 2022
This is a solution to Day 15 of Advent of Code 2022.
Day 15 - Beacon Exclusion Zone
You feel the ground rumble again as the distress signal leads you to a large network of subterranean tunnels. You don't have time to search them all, but you don't need to: your pack contains a set of deployable sensors that you imagine were originally built to locate lost Elves.
The sensors aren't very powerful, but that's okay; your handheld device indicates that you're close enough to the source of the distress signal to use them. You pull the emergency sensor system out of your pack, hit the big button on top, and the sensors zoom off down the tunnels.
Once a sensor finds a spot it thinks will give it a good reading, it attaches itself to a hard surface and begins monitoring for the nearest signal source beacon. Sensors and beacons always exist at integer coordinates. Each sensor knows its own position and can determine the position of a beacon precisely; however, sensors can only lock on to the one beacon closest to the sensor as measured by the Manhattan distance. (There is never a tie where two beacons are the same distance to a sensor.)
It doesn't take long for the sensors to report back their positions and closest beacons (your puzzle input). For example:
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=3So, consider the sensor at 2,18; the closest beacon to it is at -2,15. For the sensor at 9,16, the closest beacon to it is at 10,16.
Drawing sensors as S and beacons as B, the above arrangement of sensors and beacons looks like this:
1 1 2 2 0 5 0 5 0 5 0 ....S....................... 1 ......................S..... 2 ...............S............ 3 ................SB.......... 4 ............................ 5 ............................ 6 ............................ 7 ..........S.......S......... 8 ............................ 9 ............................ 10 ....B....................... 11 ..S......................... 12 ............................ 13 ............................ 14 ..............S.......S..... 15 B........................... 16 ...........SB............... 17 ................S..........B 18 ....S....................... 19 ............................ 20 ............S......S........ 21 ............................ 22 .......................B....This isn't necessarily a comprehensive map of all beacons in the area, though. Because each sensor only identifies its closest beacon, if a sensor detects a beacon, you know there are no other beacons that close or closer to that sensor. There could still be beacons that just happen to not be the closest beacon to any sensor. Consider the sensor at 8,7:
1 1 2 2 0 5 0 5 0 5 -2 ..........#................. -1 .........###................ 0 ....S...#####............... 1 .......#######........S..... 2 ......#########S............ 3 .....###########SB.......... 4 ....#############........... 5 ...###############.......... 6 ..#################......... 7 .#########S#######S#........ 8 ..#################......... 9 ...###############.......... 10 ....B############........... 11 ..S..###########............ 12 ......#########............. 13 .......#######.............. 14 ........#####.S.......S..... 15 B........###................ 16 ..........#SB............... 17 ................S..........B 18 ....S....................... 19 ............................ 20 ............S......S........ 21 ............................ 22 .......................B....This sensor's closest beacon is at 2,10, and so you know there are no beacons that close or closer (in any positions marked #).
None of the detected beacons seem to be producing the distress signal, so you'll need to work out where the distress beacon is by working out where it isn't. For now, keep things simple by counting the positions where a beacon cannot possibly be along just a single row.
So, suppose you have an arrangement of beacons and sensors like in the example above and, just in the row where y=10, you'd like to count the number of positions a beacon cannot possibly exist. The coverage from all sensors near that row looks like this:
1 1 2 2 0 5 0 5 0 5 9 ...#########################... 10 ..####B######################.. 11 .###S#############.###########.In this example, in the row where
y=10, there are 26 positions where a beacon cannot be present.Consult the report from the sensors you just deployed. In the row where y=2000000, how many positions cannot contain a beacon?
When I woke up and saw the word Beacon in the title, my first reaction was mild panic. I never managed to solve last year's 3D beacon puzzle and was afraid this would be similar.
It wasn't but it was still quite a challenge.
Read input
I figured we'll be doing some coordinate math today so I'm once again using the complex numbers coordinate system, explained here.
For each line, I use regex to find all numbers and use them to create a pair of sensor & beacon pair.
from utils import read_input
import re
def transformer(line):
numbers = re.findall('-?\d+', line)
sensor = int(numbers[0]) + int(numbers[1]) * 1j
beacon = int(numbers[2]) + int(numbers[3]) * 1j
return sensor, beacon
example = read_input(15, transformer, True)
data = read_input(15, transformer)Manhattan distance of two numbers follows the formula: |x1 - x0| + |y1 - y0|. With our Complex Coordinates, we can just subtract first from the second and then calculate the sum of its (absolute) real and imaginary parts.
def distance(sensor, beacon):
"""
Calculates Manhattan distance between two points
>>> distance(0, 3)
3
>>> distance(3, 0)
3
>>> distance(1+4j, 3+3j)
3
>>> distance((2+18j), (-2+15j))
7
"""
dist = beacon - sensor
return int(abs(dist.real) + abs(dist.imag))
I didn't want to populate the full grid with each sensor's reach because the puzzle is only interested in a single line.
overlaps checks if a given a sensor, knowing its beacon location, has reach on a given target line.
I do that by calculating the distance between sensor and beacon and then checking if the target y coordinate is within that distance from sensor's y coordinate.
def overlaps(sensor, beacon, target):
"""
>>> overlaps(8+7j, 2+10j, 15)
True
>>> overlaps(8+7j, 2+10j, 20)
False
>>> overlaps(8+7j, 2+10j, -2)
True
>>> overlaps(8+7j, 2+10j, -6)
False
"""
dist = distance(sensor, beacon)
if sensor.imag - dist <= target <= sensor.imag + dist:
return True
return FalseTo find out which coordinates a given sensor overlaps on a target line, I use points_on_line function.
It calculates the width (how many to left and to right from sensor's x coordinate it reaches on that y coordinate) and then adds all the points on that line. It's bit slow but did manage to solve the part 1 in a reasonable enough time that I didn't bother refactoring.
def points_on_line(sensor, distance, target):
"""
>>> points_on_line(8+7j, 9, 10)
{(2+10j), (3+10j), (4+10j), (5+10j), (6+10j), (7+10j), (8+10j), (9+10j), (10+10j), (11+10j), (12+10j), (13+10j), (14+10j)}
"""
points = set()
if target < sensor.imag:
dy = int(sensor.imag) - target
else:
dy = target - int(sensor.imag)
width = distance - dy
for x in range(int(sensor.real) - width, int(sensor.real) + width + 1):
points.add(x + target * 1j)
return pointsBecause the question was
In the row where y=2000000, how many positions cannot contain a beacon?
we need to then remove all the beacons already in that line. For that, remove_beacons loops through all beacons and removes their locations from the points set.
set.remove and set.discard
Python's set has two methods to take out items: remove and discard. It's crucial to know the difference:
set.removewill raise aKeyErrorif the given item does not exist in the set.set.discardwill not raise an error, so it's good to use if you don't care if it exists or not
def remove_beacons(points, sensors_and_beacons):
for _, beacon in sensors_and_beacons:
points.discard(beacon)
return pointsFor the actual solution, I loop over all sensors and beacons from the input and if it overlaps the desired line, we find all the points. Then we remove all the beacons and final result is the length of the set.
def solve(sensors_and_beacons, target):
points = set()
for sensor, beacon in sensors_and_beacons:
dist = distance(sensor, beacon)
if overlaps(sensor, beacon, target):
points = points | points_on_line(sensor, dist, target)
return remove_beacons(points, sensors_and_beacons)charted = solve(data, 2000000)
print(f'Part 1: {len(charted)}')
assert len(charted) == 5240818Part 2
Your handheld device indicates that the distress signal is coming from a beacon nearby. The distress beacon is not detected by any sensor, but the distress beacon must have x and y coordinates each no lower than 0 and no larger than 4000000.
To isolate the distress beacon's signal, you need to determine its tuning frequency, which can be found by multiplying its x coordinate by 4000000 and then adding its y coordinate.
In the example above, the search space is smaller: instead, the x and y coordinates can each be at most 20. With this reduced search area, there is only a single position that could have a beacon: x=14, y=11. The tuning frequency for this distress beacon is 56000011.
Find the only possible position for the distress beacon. What is its tuning frequency?
With 4M x 4M search space, it's clear my part 1 solution is waaaaay to slow. This one was a hard one to crack and even now, my solution takes a good few minutes to run. But for now, that's good enough!
In part 1, I found all the points on a given line. This time, to save memory and time, I'm only interested in the edges. So get_edges will give me that for any given line.
find_gaps then takes a list of those edges and finds if there's a missing piece.
get_line_edges finds the edges of each sensor's reach (are you noticing that I'm looping over each sensor way too many times?) on a given line and find all the edges.
To solve the puzzle, I loop over each line from 0 to 4M and if I find a gap, I return that gap. This implementation relies on the domain knowledge that there will only ever be on single gap in the grid.
from itertools import pairwise
def get_edges(sensor, dist, y):
width = dist - abs(int(sensor.imag) - y)
left = max(MIN_X, int(sensor.real) - width)
right = min(int(sensor.real) + width, MAX_X)
return (left, right)
def find_gaps(edges):
edges = sorted(edges)
one = edges.pop(0)
while len(edges) > 0:
other = edges.pop(0)
if one[1] < other[0] - 1:
return one[1] + 1
else:
one = (min(one[0], other[0]), max(one[1], other[1]))
return None
def get_line_edges(sensors_and_beacons, line):
edges = []
for sensor, beacon in sensors_and_beacons:
dist = distance(sensor, beacon)
if overlaps(sensor, beacon, line):
edges.append(get_edges(sensor, dist, line))
return edges
def solve2(sab):
for line in range(MIN_X, MAX_X):
gaps = find_gaps(get_line_edges(sab, line))
if gaps:
return gaps + line * 1j
raise Exception('No gaps found')MIN_X = 0
MAX_X = 4000000
gap = solve2(data)
solution = int(gap.real * 4000000 + gap.imag)
print(f'Part 2: {solution}')
assert solution == 13213086906101