Day 15 - Advent of Code 2022

""" day_15_01.py """

# usage: python3 day_15_01.py < input


import sys


def parse(data):
    """ parse sensor data """
    output = [line.removeprefix('Sensor at ') for line in data.splitlines()]
    output = [line.replace(': closest beacon is at ', ', ') for line in output]
    output = [[int(term[2:]) for term in line.split(', ')] for line in output]
    parsed_data = {(x1, y1): (x2, y2) for x1, y1, x2, y2 in output}
    return parsed_data


def manhattan(begin, end):
    """ calculate manhattan distance from begin to end """
    x1, y1 = begin
    x2, y2 = end
    return abs(x1 - x2) + abs(y1 - y2)


def in_range(target, _sensor, reach):
    """ is target in sensor reach """
    if manhattan(_sensor, (_sensor[0], target)) > reach:
        return False
    return True


def leftmost(target, data):
    """ calculate leftmost point scanned affecting target row """
    output = float('inf')
    for _sensor in data:
        reach = manhattan(_sensor, data[_sensor])
        if not in_range(target, _sensor, reach):
            continue
        output = min(output, _sensor[0] - reach)
    return output


def rightmost(target, data):
    """ calculate rightmost point scanned affecting target row """
    output = float('-inf')
    for _sensor in data:
        reach = manhattan(_sensor, data[_sensor])
        if not in_range(target, _sensor, reach):
            continue
        output = max(output, _sensor[0] + reach)
    return output


report = parse(sys.stdin.read())
objects = set(report.keys()) | set(report.values())
manhattans = {sensor: manhattan(sensor, report[sensor]) for sensor in report}

y = 2000000
left, right = leftmost(y, report), rightmost(y, report)

count = 0
for x in range(left, right + 1):
    if (x, y) in objects:
        continue
    possible = True
    for sensor in report:
        distance = manhattan(sensor, (x, y))
        if distance <= manhattans[sensor]:
            possible = False
    if not possible:
        count += 1
print(count)

""" day_15_02.py """

# usage: python3 day_15_02.py < input


import sys


def parse(data):
    """ parse sensor data """
    output = [line.removeprefix('Sensor at ') for line in data.splitlines()]
    output = [line.replace(': closest beacon is at ', ', ') for line in output]
    output = [[int(term[2:]) for term in line.split(', ')] for line in output]
    parsed_data = {(x1, y1): (x2, y2) for x1, y1, x2, y2 in output}
    return parsed_data


def manhattan(begin, end):
    """ calculate manhattan distance from begin to end """
    x1, y1 = begin
    x2, y2 = end
    return abs(x1 - x2) + abs(y1 - y2)


def outline(origin, radius, boundary):
    """ calculate points radius + 1 away from origin within boundary """
    def valid(coordinate):
        """ determine if coordinate is within boundary """
        x, y = coordinate
        if any([x < 0, x > boundary, y < 0, y > boundary]):
            return False
        return True

    output = []
    dx, dy = 1, 1
    point = origin[0], origin[1] - (radius + 1)
    while point[1] < origin[1]:
        if valid(point):
            output.append(point)
        point = point[0] + dx, point[1] + dy
    dx, dy = -1, 1
    point = origin[0] + radius + 1, origin[1]
    while point[0] > origin[0]:
        if valid(point):
            output.append(point)
        point = point[0] + dx, point[1] + dy
    dx, dy = -1, -1
    point = origin[0], origin[1] + radius + 1
    while point[1] > origin[1]:
        if valid(point):
            output.append(point)
        point = point[0] + dx, point[1] + dy
    dx, dy = 1, -1
    point = origin[0] - (radius + 1), origin[1]
    while point[0] < origin[0]:
        if valid(point):
            output.append(point)
        point = point[0] + dx, point[1] + dy
    return output


report = parse(sys.stdin.read())
manhattans = {sensor: manhattan(sensor, report[sensor]) for sensor in report}

limit = 4000000

px, py = None, None
loop = True
for sensor in report:
    points = outline(sensor, manhattans[sensor], limit)
    for px, py in points:
        for another in report:
            if another != sensor:
                if manhattan(another, (px, py)) <= manhattans[another]:
                    break
        else:
            loop = False
            break
    if not loop:
        break
print(px * 4000000 + py)