Simple et qui rappelle des souvenirs.

Aujourd'hui, j'ai fait assez simple, et c'est passé immédiatement pour la seconde partie.

Il me semble qu'on a déjà fait un bidule similaire l'an passé, avec des expansions de galaxies, et peut-être même des distances de Manhattan aussi, mais c'était peut-être dans deux problèmes différents...

Bref, je n'ai jamais cherché à doubler les lignes vides, mais à doubler les espaces vides.
En fait j'ai considéré la liste des galaxies, avec leurs positions.
Ensuite je travaille sur les abscisses, puis les ordonnées, l'un après l'autre, donc j'ai une liste de nombres, croissants, d'abord en Y puis en X.
Et pour chaque espace non nul entre deux de ces nombres, j'ajoute la taille de cet espace à tout ce qui est après : galaxies (en X ou en Y selon l'étape) et aux nombres restants. Bref, j'étends vers le bas, puis vers la droite.

Ajouter la taille à la taille ça double.
Pour l'exercice 2, on n'ajoute pas la taille mais (1 million moins 1) de fois cette taille. Exercice terminé.

import sys
data = sys.stdin.read().strip().splitlines()
def run(starmap, mult):
 stars = [(x, y) for y, line in enumerate(starmap) for x, _ in enumerate(line) if _ == "#"]
 Xs = sorted({x for x, y in stars})
 Ys = sorted({y for x, y in stars})
 y0 = 0
 while Ys:
 adding = (Ys[0] - y0) * mult
 stars = [(x, y if y < y0 else y + adding) for x, y in stars]
 Ys = [y + adding for y in Ys]
 y0 = Ys.pop(0) + 1
 x0 = 0
 while Xs:
 adding = (Xs[0] - x0) * mult
 stars = [(x if x < x0 else x + adding, y) for x, y in stars]
 Xs = [x + adding for x in Xs]
 x0 = Xs.pop(0) + 1
 return sum(
 abs(x2 - x1) + abs(y2 - y1)
 for x1, y1 in stars
 for x2, y2 in stars
 )//2
ex1 = run(data, 1)
ex2 = run(data, 1000000-1)

• Yth.