advent_!5_2022

day15_2022.py

"""

SPOILER ALERT

Puzzle at: https://adventofcode.com/2022/day/15

Part 2 could be brute-forced with the use of "part1" in less
than 10 minutes, I guess.

I opted for a rectangle-splitting approach, and checking if
all rectangle corners where covered by at least one sensor
or per none. 

This was not very fast either - took more than 2 min
but got there right.

I was delayed by "off-by-ones" : as I built on top
of the excelent terminedia.Rect class - but it is
"python-slice-like" open-ended on right and botton - 
I had to work with closed ends, and took a lot of
time to realize this is what was wrong there.

That said, terminedia.V2 and Rect classes are really awesome
(I should update the later with some of what I learned here)

And as far as part1 is concerned, I have the feeling that I left a
way simpler method sleep by - but it worked fast enough
"""

from terminedia import V2, Rect


class R2(Rect):
    """
    In [344]: a = R2(10,10)

    In [345]: a
    Out[345]: R2((0, 0), (10, 10))

    In [346]: b = list(a.split())

    In [347]: b
    Out[347]:
    [R2((0, 0), (5.0, 5.0)),
    R2((5.0, 0), (10, 5.0)),
    R2((5.0, 5.0), (10, 10)),
    R2((0, 5.0), (5.0, 10))]
    """

    c3 = property(lambda s: V2(s.right, s.top))
    c4 = property(lambda s: V2(s.left, s.bottom))
    corners = property(lambda s: (s.c1, s.c3, s.c2, s.c4))
    @property
    def inside_corners(self):
        """yield the coordinates at right, bottm that are actually inside the rect -"""
        yield self.c1
        yield self.c3 - (1, 0)
        yield self.c2 - (1, 1)
        yield self.c4 - (0, 1)

    def split(self):
        cls = type(self)
        center = self.center.as_int
        for c in self.corners:
            if c.x - center.x != 0 and c.y - center.y != 0:
                # terminedia.Rect accepts corners in any relative position
                yield cls(c, center)


def manh(p1, p2):
    return abs(p1[0] - p2[0])+ abs(p1[1] - p2[1])

class Map:
    def __init__(self, data):
        self.sensors = {}
        self.beacons = {}
        self.parse(data)
    def _pt(self, token):
        return int(token.strip(" ,:").split("=")[1])
    def parse(self, data):
        for line in data.splitlines():
            _, _, xs, ys, _,_,_,_,xb,yb = line.split()
            xs, ys = self._pt(xs), self._pt(ys)
            xb, yb = self._pt(xb), self._pt(yb)
            poss = V2(xs, ys)
            posb = V2(xb, yb)
            self.sensors[poss] = posb
            self.beacons.setdefault(posb, []).append(poss)
    def __repr__(self):
        return repr(self.sensors)
    def free_space(self, row):
        distances_from_row = {}
        occupancy = Discontiguous()
        for sensor, beacon in self.sensors.items():
            radius = manh(sensor, beacon)
            remaining = radius - abs(sensor.y - row)
            if remaining <= 0:
                continue
            range_ = (sensor.x - remaining, sensor.x + remaining )
            occupancy.add_range(range_)
        beacons_in_row = sum(beacon.y == row and beacon.x in occupancy for beacon in self.beacons)
        return len(occupancy) - beacons_in_row

    def rectangle_covered(self, rect: R2) -> list[R2]:
        """returns a list of all unconvered areas
        in the initial rectangle, if any.

        in the problem input, should return a single 1x1 rect
        at the missing beacon coordinates
        """

        all_complete = False
        all_empty = []
        for sensor, beacon in self.sensors.items():
            radius = manh(sensor, beacon)
            corners_status = [manh(corner, sensor) <= radius for corner in rect.inside_corners]
            if all(corners_status) or ((rect.height <= 1 and rect.width <= 1) and corners_status[0]):
                all_complete = True
                break
            if rect.width >= 1 and rect.height >= 1:
                all_empty.append(not any(corners_status) and sensor not in rect)
            elif sensor != rect.c1 and not corners_status[0]:
                all_empty.append(True)
        if all_complete:
            return []
        if all_empty and all(all_empty):
            return [rect]
        res = []
        for part in rect.split():
            res.extend(self.rectangle_covered(part))
        return res


class Discontiguous:
    def __init__(self, ranges=()):
        self.ranges = []
        for range_ in ranges:
            self.add_range(range_)
    def add_range(self, range_: tuple[int, int]):
        range_ = range_[0], range_[1] + 1
        insort(self.ranges, range_)
    def __contains__(self, pos):
        for range_ in self.ranges:
            if pos >= range_[0] and pos < range_[1]:
                return True
            if range_[1] >= pos:
                break
        return False

    def __len__(self):
        inside = []
        occupied = 0
        for r in self.ranges:
            start, stop = r
            tokill = []
            for i, r2 in enumerate(inside):
                if start > r2[1]:
                    tokill.append(i)
            for i in reversed(tokill):
                del inside[i]
            xx = max([start, *(r3[1] for r3 in inside)])
            occupied += (stop - xx) if stop > xx else 0
            inside.append(r)
        return occupied
    def __repr__(self):
        return repr(self.ranges)