Re: Plus cool que les jours précédents

J'ai jamais appris les algos classiques, Djikstra, BFS, A* etc, tendance à réinventer la roue à chaque fois.
Mais je faisais pareil en prépa avec les preuves de théorèmes à apprendre par cœur : jamais réussi, je voyais pas l'intérêt quand il suffisait de refaire la preuve en direct au tableau...

Bref, des set(), des unions, des différences, des intersections, pas besoin d'aller bien plus loin en Python, l'espace à analyser est tout petit, 10k cases, c'est rien, quand on sort d'une tour infernale de mille milliards de cube Tetris empilés sur une hauteur de quelques 1500 milliards...

Mon alog part des faces externes du pavé contenant notre rocher de lave en fusion, donc les 6 faces x=xmin, x=xmax, y=ymin, y=ymax, z=zmin, z=zmax.
Puis j'agrandis vers l'intérieur (si x < xmax/2 alors (x+1, y, z), sinon (x-1, y, z), pareil pour y et z), donc on a trois adjacents au lieu de six et on ne sort jamais de la zone.
On vire les cubes du bout de lave, on itère.
En 6 itérations c'est fini, on a tous les cubes de vide à l'extérieur, sur zone.
On prends les adjacents à la lave, on difference(lave), on intersection(exterieur), on remet dedans les cubes vides qui étaient hors zone.

Sinon on pouvait partir d'une zone de 1 plus grande dans chaque direction, et faire une itération de plus, mais bon, j'ai pas trouvé ça plus simple dans le code, et ça faisait passer à un espace de presque 13k au lieu de 10k, soit tout aussi négligeable, mais un peu moins.

J'ai modélisé une class Cube(tuple) pour mes triplets de coordonnées avec les property suivantes :
* adjacent pour les 6 cubes autour ;
* interior pour les 3 cubes vers le centre de la zone ;
* inside qui dit si un Cube est hors zone ou pas.
J'altère ma classe Cube une fois les données entièrement lues, pour fournir les bornes, et le milieu arrondi à l'entier pour marginalement gagner du temps de calcul en évitant les comparaisons entre entier et flottant. À noter que dans mon cas la division par deux est entière donc ça ne change rien. Et que le gain est marginal vu la taille des données.
Donc pas mal de préparation avant de lancer des calculs très simples au bout du compte.

class Cube(tuple):
 @property
 def adjacent(self):
 x, y, z = self
 yield Cube([x + 1, y, z])
 yield Cube([x - 1, y, z])
 yield Cube([x, y + 1, z])
 yield Cube([x, y - 1, z])
 yield Cube([x, y, z + 1])
 yield Cube([x, y, z - 1])
 @property
 def interior(self):
 x, y, z = self
 if x < self.mx:
 yield Cube([x + 1, y, z])
 elif x > self.mx:
 yield Cube([x - 1, y, z])
 if y < self.my:
 yield Cube([x, y + 1, z])
 elif y > self.my:
 yield Cube([x, y - 1, z])
 if z < self.mz:
 yield Cube([x, y, z + 1])
 elif z > self.mz:
 yield Cube([x, y, z - 1])
 @property
 def inside(self):
 for a, b, c in zip(self.minimum, self, self.maximum):
 if not (a <= b <= c):
 return False
 return True
cubes = {
 Cube(map(int, _.split(',')))
 for _ in sys.stdin.read().strip().splitlines()
}
x0 = min(x for x, y, z in cubes)
y0 = min(y for x, y, z in cubes)
z0 = min(z for x, y, z in cubes)
x1 = max(x for x, y, z in cubes)
y1 = max(y for x, y, z in cubes)
z1 = max(z for x, y, z in cubes)
rx = list(range(x0, x1 + 1))
ry = list(range(y0, y1 + 1))
rz = list(range(z0, z1 + 1))
Cube.minimum = (x0, y0, z0)
Cube.maximum = (x1, y1, z1)
Cube.mx = (x1 - x0) // 2
Cube.my = (y1 - y0) // 2
Cube.mz = (z1 - z0) // 2
# exo 1, une liste parce qu'on a des doublons, on veut les faces, pas les cubes.
exposed = [
 face
 for cube in cubes
 for face in cube.adjacent
 if face not in cubes
]
adjacent = set(exposed)
# Cubes adjacent au rocher, mais hors zone
adjacent_outside = {face for face in adjacent if not face.inside}
# Faces extérieures de la zone, hors cubes du rocher.
exterior = {Cube((x, y, z0)) for x in rx for y in ry}.union(
 {Cube((x, y, z1)) for x in rx for y in ry},
 {Cube((x, y0, z)) for x in rx for z in rz},
 {Cube((x, y1, z)) for x in rx for z in rz},
 {Cube((x0, y, z)) for y in ry for z in rz},
 {Cube((x1, y, z)) for y in ry for z in rz},
).difference(cubes)
# Algo de parcours de zone
interior = True
while interior:
 interior = {
 x
 for c in exterior
 for x in c.interior
 }.difference(exterior).difference(cubes)
 exterior.update(interior)
# Les cubes adjacent au rocher, mais pas à l'intérieur !
adjacent2 = adjacent.intersection(exterior).union(adjacent_outside)
# Et recalcul des faces exposées, mais uniquement à l'extérieur
exposed2 = len([1 for face in exposed if face in adjacent2])
print(f"{len(cubes)} Cubes")
print(f"{len(exposed)} Exposed faces (4604)")
print(f"{exposed2} Exterior faces (2604)")

Et voilà, à demain !

• Yth.