How to solve Advent of Code 2022 - Day 15 with Python

If you missed any previous days, click here for all my content about that: Advent of Code, if you want to know why you should participate and try to code the solution for yourself, click here: Advent Of Code 2022 – 7 Reasons why you should participate. If you're here to see the solution of Day 15, continue reading ;)

GitHub Repository

https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2022

I will upload all of my solutions there - in the form of Python (or Scala alternatives) notebooks. You have to use your own input for the "input.txt" since everyone gets their own and everyone needs to provide a different solution based on their input.

Day 15 Puzzle

On day 15 of Advent of Code, we had to find a beacon?! Look, normally I explain my solution here, but this part 2 wrecked me and it's now too late, I hope to update this with my explanation tomorrow.

Here is an example input of this puzzle:

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

Part 1

This was comparatively okay, here the trick is to not draw a full map, but instead just check the required row:

def solve1(file, y_index): 
    with open(file, 'r') as f:
        lines = f.readlines()
        lines = [entry.strip() for entry in lines]

    line_overlaps = set()
    device_line_overlaps = set()

    for i, line in enumerate(lines):
        #print(line)
        parts_with_numbers = [word for word in line.split(' ') if '='in word]
        parts_with_numbers_cleaned = [word.replace(',', '').replace(':', '') for word in parts_with_numbers]
        sensor_x, sensor_y, beacon_x, beacon_y = list(map(lambda x: int(x.split('=')[1]), parts_with_numbers_cleaned))

        if sensor_y == y_index:
            device_line_overlaps.add(sensor_x)
        if beacon_y == y_index:
            device_line_overlaps.add(beacon_x)

        distance_to_beacon = abs(sensor_x - beacon_x) + abs(sensor_y - beacon_y)
        if y_index in range(sensor_y - distance_to_beacon, sensor_y + distance_to_beacon):
            save_no_beacon_zone(line_overlaps, sensor_x, sensor_y, distance_to_beacon, y_index)
    print(len(line_overlaps - device_line_overlaps))

where the overlap of the sensor's no-beacon-zone is calculated in:

def save_no_beacon_zone(grid, sensor_x, sensor_y, distance, y_index):
    half_width = 0
    for y in range(sensor_y - distance, sensor_y + distance + 1):
        if y == y_index:
            for x in range(sensor_x - half_width, sensor_x + half_width + 1):
                grid.add(x)
        if y < sensor_y:
            half_width += 1
        else:
            half_width -= 1

Here I went through one of the diamond shapes, updated the width at each height and only added the affected indices to my "grid" (I should have renamed this after removing the grid functionality) if it's the requested line.

Part 2

This took me forever. The example was fine of course because you can brute-force it, but the real input with 4 million x 4 million entries was way too big to visit every coordinate and check it. I tried in multiple ways.

Finally I did some drawing and thinking and eating and thinking and finally noticed something about the description of the problem: There is only one free possible square!

Which also means... This free square has to be right next to the border of one of the sensor-diamond-shapes. Because next to the free square has to start a new shape, otherwise there would be more free squares.

So if we only traverse the outside of the sensor-fields, we significantly cut down on fields to check:

def manhatten_distance(a_x, a_y, b_x, b_y):
    return abs(a_x - b_x) + abs(a_y - b_y)


def check_field_empty(y_index, x_index, sensors, beacons):
    for sensor in sensors:
        if manhatten_distance(x_index, y_index, sensor[0], sensor[1]) <= sensor[2]:
            return False
    for beacon in beacons:
        if y_index == beacon[1] and x_index == beacon[0]:
            return False
    return True


def traverse_border(sensor_x, sensor_y, distance, max_zone, sensors, beacons):
    if sensor_y - distance < 0:
        half_width = - (sensor_y - distance)
    else: 
        half_width = 0
    #top
    top = sensor_y-distance-1
    if top > 0:
        if check_field_empty(top, sensor_x, sensors, beacons):
            print('omg finally', 'y', top, 'x', sensor_x)
            print('solution', sensor_x * 4000000 + top)
            return True
    #bottom
    bottom = sensor_y+distance+1
    if bottom <= max_zone + 1:
        if check_field_empty(bottom, sensor_x, sensors, beacons):
            print('omg finally', 'y', bottom, 'x', sensor_x)
            print('solution', sensor_x * 4000000 + bottom)
            return True
    #left and right
    for y in range(max(0, sensor_y - distance), min(sensor_y + distance + 1, max_zone+1)):
        # left 
        left = sensor_x - half_width - 1
        if left > 0:
            if check_field_empty(y, left, sensors, beacons):
                print('omg finally', 'y', y, 'x', left)
                print('solution', left * 4000000 + y)
                return True
        right = sensor_x + half_width + 1
        if right <= max_zone+1:
            if check_field_empty(y, right, sensors, beacons):
                print('omg finally', 'y', y, 'x', right)
                print('solution', right * 4000000 + y)
                return True
        if y < sensor_y:
            half_width += 1
        else:
            half_width -= 1
    return False

def save_no_beacon_zone(grid, sensor_x, sensor_y, distance, y_index):
    if sensor_y - distance < 0:
        half_width = - (sensor_y - distance)
    else:
        half_width = 0
    for y in range(sensor_y - distance, sensor_y + distance + 1):
        if y == y_index:
            for x in range(sensor_x - half_width, sensor_x + half_width + 1):
                grid.add(x)
        if y < sensor_y:
            half_width += 1
        else:
            half_width -= 1

def solve2(file, max_zone): 
    with open(file, 'r') as f:
        lines = f.readlines()
        lines = [entry.strip() for entry in lines]

    sensors = []
    beacons = []
    for i, line in enumerate(lines):
        #print(line)
        parts_with_numbers = [word for word in line.split(' ') if '='in word]
        parts_with_numbers_cleaned = [word.replace(',', '').replace(':', '') for word in parts_with_numbers]
        sensor_x, sensor_y, beacon_x, beacon_y = list(map(lambda x: int(x.split('=')[1]), parts_with_numbers_cleaned))

        distance_to_beacon = abs(sensor_x - beacon_x) + abs(sensor_y - beacon_y)
        
        sensors.append([sensor_x, sensor_y, distance_to_beacon])
        beacons.append([beacon_x, beacon_y])

    for i, sensor in enumerate(sensors):
        print('sensor', i)
        if traverse_border(sensor[0], sensor[1], sensor[2], max_zone, sensors, beacons):
            return

Conclusion

This almost ruined me. But: streak is intact, onward to Day 16 we go.