2022-12-15 - Beacon Exclusion Zone
(original .ipynb)
Day 15 puzzle input is a sequence of sensors, their x/y positions and the x/y position of the closest "beacon" (by manhattan distance) to each sensor (mine is here). Part 1 involves using this information do determine how many positions on one line (on the grid where y=2_000_000) cannot contain a breacon. Part 2 involves assuming the beacon is somewhere between the x/y positions 0->4,000,000, and searching for the one position that isn't covered by a sensor.
puzzle_input_str = open("./puzzle_input/day15.txt").read()
test_input_str = open("./test_input/day15.txt").read()
def parse_coord(coord_str):
_, val = coord_str.split("=")
return int(val.rstrip(","))
def parse_sensor(sensor_str):
tokens = sensor_str.split(" ")
return parse_coord(tokens[2]), parse_coord(tokens[3])
def parse_beacon(beacon_str):
tokens = beacon_str.split(" ")
return parse_coord(tokens[4]), parse_coord(tokens[5])
def parse_line(line):
sensor_str, beacon_str = line.split(": ")
return parse_sensor(sensor_str), parse_beacon(beacon_str)
def manhattan_distance(x1, y1, x2, y2):
return abs(x1-x2) + abs(y1-y2)
def positions_within_range(sensor, beacon, target_y):
x1, y1 = sensor
x2, y2 = beacon
max_radius = manhattan_distance(x1, y1, x2, y2)
leftover = max_radius - abs(y1 - target_y)
while leftover >= 0:
if not (x2 == x1+leftover and y2 == target_y):
yield x1 + leftover
if not (x2 == x1-leftover and y2 == target_y):
yield x1 - leftover
leftover -= 1
def part_one(input_str, target_y=2_000_000):
sensors = [parse_line(line) for line in input_str.splitlines()]
solution = set()
for sensor, beacon in sensors:
for position in positions_within_range(sensor, beacon, target_y):
solution.add(position)
return len(solution)
assert 26 == part_one(test_input_str, 10)
print("part one:", part_one(puzzle_input_str))
part one: 5142231
%%time
def covered_range_at_y(sensor, beacon, target_y):
x1, y1 = sensor
x2, y2 = beacon
max_radius = manhattan_distance(x1, y1, x2, y2)
leftover = max_radius - abs(y1 - target_y)
if leftover < 0:
return None
return (x1 - leftover, x1 + leftover)
def add_safe(free_range, start, end):
if start <= end:
free_range.append((start, end))
def insert_range(free_range, start, end):
next_free_range = []
for f_start, f_end in free_range:
# if the free range is completely contained, delete it
if f_start >= start and f_end <= end:
continue
# if there's no overlaps, add it unmodified
elif (start < f_start and end < f_start) or (start > f_end and end > f_end):
next_free_range.append((f_start, f_end))
# if the range is completely contained within the free range, split it
elif (f_start <= start and end <= f_end):
add_safe(free_range, f_start, start-1)
add_safe(free_range, end+1, f_end)
# if there's an overlap, truncate it
else:
if start <= f_start and f_start <= end:
f_start = end + 1
if start <= f_end and f_end <= end:
f_end = start - 1
add_safe(free_range, f_start, f_end)
return next_free_range
def part_two(input_str, max_x=4_000_000, max_y=4_000_000):
sensors = [parse_line(line) for line in input_str.splitlines()]
for y in range(max_y):
free_range = [(0, max_x)]
for sensor, beacon in sensors:
if not free_range:
break
if x_range := covered_range_at_y(sensor, beacon, y):
start, end = x_range
free_range = insert_range(free_range, max(0, start), min(max_x, end))
if len(free_range) == 1 and free_range[0][0] == free_range[0][1]:
return free_range[0][0] * 4000000 + y
return None
assert 56000011 == part_two(test_input_str, 20, 20)
print("part two:", part_two(puzzle_input_str))
part two: 10884459367718 CPU times: user 2min 32s, sys: 23.2 ms, total: 2min 32s Wall time: 2min 32s