Strike

Bon, aujourd'hui nous sommes dans le cas d'un problème avec une solution naïve qui ne passe pas à l'échelle. Mais personnellement, comme l'optimisation de la première partie était quand même assez simple, j'ai fait un strike, la deuxième partie était résolue en changeant simplement une constante.

import itertools
from collections.abc import Iterable
from typing import Self
import aoc
Coords = tuple[int, int]
class Image:
 def __init__(self, galaxies: Iterable[Coords], factor: int):
 ys: set[int] = set()
 xs: set[int] = set()
 self.galaxies: set[Coords] = set()
 for galaxy in galaxies:
 self.galaxies.add(galaxy)
 ys.add(galaxy[0])
 xs.add(galaxy[1])
 # Space expansion factor: 2 everywhere...
 self.yfactor = [factor] * (max(ys) + 1)
 self.xfactor = [factor] * (max(xs) + 1)
 # ... except where galaxies were found.
 for y in ys:
 self.yfactor[y] = 1
 for x in xs:
 self.xfactor[x] = 1
 def distance(self, g1: Coords, g2: Coords) -> int:
 y1, x1 = g1
 y2, x2 = g2
 ymin, ymax = min(y1, y2), max(y1, y2)
 xmin, xmax = min(x1, x2), max(x1, x2)
 return (sum(self.yfactor[y] for y in range(ymin, ymax))
 + sum(self.xfactor[x] for x in range(xmin, xmax)))
 @classmethod
 def import_lines(cls, lines: Iterable[str], factor: int) -> Self:
 return cls(((y, x)
 for y, line in enumerate(lines)
 for x, char in enumerate(line.rstrip())
 if char == '#'),
 factor)
def part1(lines: aoc.Data) -> int:
 """Solve puzzle part 1: determine total galaxy distances considering an
 expansion factor of 2."""
 image = Image.import_lines(lines, 2)
 total = 0
 for g1, g2 in itertools.combinations(image.galaxies, 2):
 total += image.distance(g1, g2)
 return total
def part2(lines: aoc.Data) -> int:
 """Solve puzzle part 2: determine total galaxy distances considering an
 expansion factor of 1000000."""
 image = Image.import_lines(lines, 1000000)
 total = 0
 for g1, g2 in itertools.combinations(image.galaxies, 2):
 total += image.distance(g1, g2)
 return total