Re: Sans géométrie

Le code :

import dataclasses
import enum
import io
import re
from collections.abc import Iterable, Iterator
from typing import ClassVar, Self
import numpy as np
import numpy.typing as npt
import aoc
Coords = tuple[int, int]
Vector = tuple[int, int]
class Direction(enum.Enum):
 UP = 'U'
 DOWN = 'D'
 LEFT = 'L'
 RIGHT = 'R'
 @property
 def vector(self) -> Vector:
 if self is self.UP:
 return (-1, 0)
 if self is self.DOWN:
 return (1, 0)
 if self is self.LEFT:
 return (0, -1)
 if self is self.RIGHT:
 return (0, 1)
 assert False, "we covered all cases"
 def translate(self, position: Coords) -> Coords:
 y, x = position
 dy, dx = self.vector
 return y + dy, x + dx
@dataclasses.dataclass(frozen=True)
class Instruction:
 direction: Direction
 length: int
 import_pattern1: ClassVar[re.Pattern] = re.compile(
 r'^([UDLR]) (\d+) \(#[0-9A-Fa-f]{6}\)\n?$')
 import_pattern2: ClassVar[re.Pattern] = re.compile(
 r'^[UDLR] \d+ \(#([0-9A-Fa-f]{5})([0-9A-Fa-f])\)\n?$')
 @classmethod
 def import_line1(cls, line: str) -> Self:
 if (m := cls.import_pattern1.match(line)) is not None:
 return cls(Direction(m[1]), int(m[2]))
 raise ValueError("invalid instruction line")
 @classmethod
 def import_line2(cls, line: str) -> Self:
 if (m := cls.import_pattern2.match(line)) is not None:
 length = int(m[1], 16)
 if m[2] == '0':
 direction = Direction.RIGHT
 elif m[2] == '1':
 direction = Direction.DOWN
 elif m[2] == '2':
 direction = Direction.LEFT
 elif m[2] == '3':
 direction = Direction.UP
 else:
 raise ValueError("invalid instruction line")
 return cls(direction, length)
 raise ValueError("invalid instruction line")
 def apply(self, position: Coords) -> Coords:
 y, x = position
 dy, dx = self.direction.vector
 return y + self.length * dy, x + self.length * dx
class Terrain1:
 def __init__(self, instructions: Iterable[Instruction]) -> None:
 position: Coords = (0, 0)
 excavated: set[Coords] = {(0, 0)}
 for instruction in instructions:
 for _ in range(instruction.length):
 position = instruction.direction.translate(position)
 excavated.add(position)
 ymin, ymax = 0, 0
 xmin, xmax = 0, 0
 for (y, x) in excavated:
 ymin = min(ymin, y)
 ymax = max(ymax, y)
 xmin = min(xmin, x)
 xmax = max(xmax, x)
 # Time to write a terrain matrix
 # It needs to span the entire excavated area, plus a margin:
 # * vertically: from ymin - 1 to ymax + 1 included;
 # * horizontally: fron xmin - 1 to xmax + 1 included.
 self.matrix: npt.NDArray[np.bool_] = np.zeros(
 (ymax - ymin + 3, xmax - xmin + 3), dtype=np.bool_)
 self.ly, self.lx = self.matrix.shape
 for (y, x) in excavated:
 y = y - ymin + 1
 x = x - xmin + 1
 self.matrix[y, x] = True
 def dig_pool(self) -> None:
 def neighs(coords: Coords) -> Iterator[Coords]:
 def _neighs(coords: Coords):
 y, x = coords
 yield y, x - 1
 yield y, x + 1
 yield y - 1, x
 yield y + 1, x
 for y, x in _neighs(coords):
 if 0 <= y < self.ly and 0 <= x < self.lx:
 yield y, x
 outside = np.zeros_like(self.matrix)
 visited = np.zeros_like(self.matrix)
 start = (0, 0)
 outside[start] = True
 visited[start] = True
 currents: set[Coords] = {(0, 0)}
 while len(currents) > 0:
 nexts: set[Coords] = set()
 for position in currents:
 for neigh in neighs(position):
 if visited[neigh]:
 continue
 if not self.matrix[neigh]:
 outside[neigh] = True
 nexts.add(neigh)
 visited[neigh] = True
 currents = nexts
 for position, _ in np.ndenumerate(self.matrix): # type: ignore
 if not outside[position]:
 self.matrix[position] = True
 def area(self) -> int:
 return np.sum(self.matrix) # type: ignore
 def __str__(self) -> str:
 s = io.StringIO()
 for line in self.matrix:
 for excavated in line:
 if excavated:
 s.write('█')
 else:
 s.write(' ')
 s.write('\n')
 return s.getvalue()
@dataclasses.dataclass(frozen=True)
class HSegment:
 x1: int
 x2: int
 y: int
 def cuts(self, x: int) -> bool:
 return self.x1 <= x <= self.x2
 def __len__(self) -> int:
 return self.x2 - self.x1 + 1
@dataclasses.dataclass(frozen=True)
class VSegment:
 x: int
 y1: int
 y2: int
 def cuts(self, y: int) -> bool:
 return self.y1 <= y <= self.y2
 def __len__(self) -> int:
 return self.y2 - self.y1 + 1
class Terrain2:
 def __init__(self, instructions: Iterable[Instruction]):
 hsegments: set[HSegment] = set()
 vsegments: set[VSegment] = set()
 ys: set[int] = {0, 1}
 xs: set[int] = {0, 1}
 ymin, ymax = 0, 1
 xmin, xmax = 0, 1
 y, x = 0, 0
 for instruction in instructions:
 y_, x_ = instruction.apply((y, x))
 ymin, ymax = min(ymin, y_), max(ymax, y_ + 1)
 xmin, xmax = min(xmin, x_), max(xmax, x_ + 1)
 ys.add(y_)
 ys.add(y_ + 1)
 xs.add(x_)
 xs.add(x_ + 1)
 if instruction.direction is Direction.UP:
 vsegments.add(VSegment(x, y_, y))
 elif instruction.direction is Direction.DOWN:
 vsegments.add(VSegment(x, y, y_))
 elif instruction.direction is Direction.LEFT:
 hsegments.add(HSegment(x_, x, y))
 elif instruction.direction is Direction.RIGHT:
 hsegments.add(HSegment(x, x_, y))
 else:
 assert False, "we covered all cases for instruction direction"
 y, x = y_, x_
 ys.add(ymin - 1)
 ys.add(ymax + 1)
 xs.add(xmin - 1)
 xs.add(xmax + 1)
 self.ys = sorted(ys)
 self.xs = sorted(xs)
 self.matrix: npt.NDArray[np.bool_] = np.zeros(
 (len(ys) - 1, len(xs) - 1), dtype=np.bool_)
 self.lj, self.li = self.matrix.shape
 for hsegment in hsegments:
 j = self.ys.index(hsegment.y)
 for i in range(self.xs.index(hsegment.x1),
 self.xs.index(hsegment.x2) + 1):
 self.matrix[j, i] = True
 for vsegment in vsegments:
 i = self.xs.index(vsegment.x)
 for j in range(self.ys.index(vsegment.y1),
 self.ys.index(vsegment.y2) + 1):
 self.matrix[j, i] = True
 def dig_pool(self) -> None:
 def neighs(coords: Coords) -> Iterator[Coords]:
 def _neighs(coords: Coords):
 j, i = coords
 yield j, i - 1
 yield j, i + 1
 yield j - 1, i
 yield j + 1, i
 for j, i in _neighs(coords):
 if 0 <= j < self.lj and 0 <= i < self.li:
 yield j, i
 outside = np.zeros_like(self.matrix)
 visited = np.zeros_like(self.matrix)
 start = (0, 0)
 outside[start] = True
 visited[start] = True
 currents: set[Coords] = {(0, 0)}
 while len(currents) > 0:
 nexts: set[Coords] = set()
 for position in currents:
 for neigh in neighs(position):
 if visited[neigh]:
 continue
 if not self.matrix[neigh]:
 outside[neigh] = True
 nexts.add(neigh)
 visited[neigh] = True
 currents = nexts
 for position, _ in np.ndenumerate(self.matrix): # type: ignore
 if not outside[position]:
 self.matrix[position] = True
 def area(self) -> int:
 count = 0
 for j in range(self.lj):
 for i in range(self.li):
 if self.matrix[j, i]:
 count += ((self.ys[j + 1] - self.ys[j])
 * (self.xs[i + 1] - self.xs[i]))
 return count
 def __str__(self) -> str:
 s = io.StringIO()
 for line in self.matrix:
 for excavated in line:
 if excavated:
 s.write('█')
 else:
 s.write(' ')
 s.write('\n')
 return s.getvalue()
def part1(lines: aoc.Data) -> int:
 """Solve puzzle part 1: determine the sum of stuff"""
 terrain = Terrain1(Instruction.import_line1(line) for line in lines)
 terrain.dig_pool()
 return terrain.area()
def part2(lines: aoc.Data) -> int:
 """Solve puzzle part 2: determine the sum of staff"""
 terrain = Terrain2(Instruction.import_line2(line) for line in lines)
 terrain.dig_pool()
 return terrain.area()