Unions d'intervalles

Voilà, avec une implémentation des unions d'intervalles sécants.

from __future__ import annotations
import re
from collections import namedtuple
from typing import Tuple, Iterable, List, Optional, Type
import aoc
Coords = Tuple[int, int]
class Point(namedtuple('Point', ['x', 'y'])):
 __slots__ = ()
 def __str__(self) -> str:
 return "({},{})".format(self.x, self.y)
 def dist(self, other: Point) -> int:
 return abs(self.x - other.x) + abs(self.y - other.y)
class Interval:
 def __init__(self, start: int, end: int) -> None:
 if start >= end:
 raise ValueError("unsupported empty or negative interval")
 self.start = start
 self.end = end
 def __str__(self) -> str:
 return "[{},{}[".format(self.start, self.end)
 def __len__(self) -> int:
 return self.end - self.start
 def __contains__(self, value: int) -> bool:
 return value >= self.start and value < self.end
 def intersects(self, other: Interval) -> bool:
 return max(self.start, other.start) < min(self.end, other.end)
 def union_update(self, other: Interval) -> bool:
 if not self.intersects(other):
 return False
 self.start = min(self.start, other.start)
 self.end = max(self.end, other.end)
 return True
class Sensor:
 def __init__(self, position: Point, beacon: Point):
 self.position = position
 self.beacon = beacon
 self.range = position.dist(beacon)
 def covers(self, y: int) -> bool:
 dist = abs(y - self.position.y)
 return dist <= self.range
 def coverage(self, y: int) -> Optional[Interval]:
 if not self.covers(y):
 return None
 else:
 dist = abs(y - self.position.y)
 return Interval(self.position.x - self.range + dist,
 self.position.x + self.range + 1 - dist)
 re_line = re.compile(r'^Sensor at x=(-?\d+), y=(-?\d+): '
 + r'closest beacon is at x=(-?\d+), y=(-?\d+)\n?$')
 @classmethod
 def import_line(class_, line: str) -> Sensor:
 match = class_.re_line.match(line)
 if match is None:
 raise ValueError("invalid sensor description")
 position = Point(int(match.group(1)), int(match.group(2)))
 beacon = Point(int(match.group(3)), int(match.group(4)))
 return class_(position, beacon)
class SensorArray:
 def __init__(self, sensors: Iterable[Sensor]):
 self.sensors = list(sensors)
 @classmethod
 def import_lines(class_, lines: Iterable[str]) -> SensorArray:
 return class_(Sensor.import_line(line) for line in lines)
 def coverage(self, y: int) -> List[Interval]:
 intervals: List[Interval] = []
 for sensor in self.sensors:
 if not sensor.covers(y):
 continue
 new_interval = sensor.coverage(y)
 if new_interval is None:
 continue
 new_intervals: List[Interval] = []
 for interval in intervals:
 if not new_interval.union_update(interval):
 # new_interval did not absorb interval
 new_intervals.append(interval)
 new_intervals.append(new_interval)
 intervals = new_intervals
 return intervals
def solve1(lines: Iterable[str]) -> int:
 """Solve part 1 of today's puzzle"""
 array = SensorArray.import_lines(lines)
 beacons = {sensor.beacon for sensor in array.sensors}
 y = 2000000
 coverage = array.coverage(y)
 total = 0
 for interval in coverage:
 total += len(interval)
 total -= sum((beacon.y == y and beacon.x in interval)
 for beacon in beacons)
 return total
def solve2(lines: Iterable[str]) -> int:
 """Solve part 2 of today's puzzle"""
 array = SensorArray.import_lines(lines)
 position: Optional[Point] = None
 for y in range(4000000):
 if y % 100000 == 0:
 print(y)
 coverage = array.coverage(y)
 if len(coverage) < 2:
 continue
 return min(interval.end for interval in coverage) * 4000000 + y
 raise ValueError("no solution found")