Forum Programmation.autre Avent du Code, jour 18

Posté par  . Licence CC By‑SA.
Étiquettes :
2
18
déc.
2022

Aujourd'hui, il faut calculer la surface extérieur d'un ensemble de cube.

--- Day 18: Boiling Boulders ---

You and the elephants finally reach fresh air. You've emerged near the base of a large volcano that seems to be actively erupting! Fortunately, the lava seems to be flowing away from you and toward the ocean.

Bits of lava are still being ejected toward you, so you're sheltering in the cavern exit a little longer. Outside the cave, you can see the lava landing in a pond and hear it loudly hissing as it solidifies.

Depending on the specific compounds in the lava and speed at which it cools, it might be forming obsidian! The cooling rate should be based on the surface area of the lava droplets, so you take a quick scan of a droplet as it flies past you (your puzzle input).

Because of how quickly the lava is moving, the scan isn't very good; its resolution is quite low and, as a result, it approximates the shape of the lava droplet with 1x1x1 cubes on a 3D grid, each given as its x,y,z position.

To approximate the surface area, count the number of sides of each cube that are not immediately connected to another cube. So, if your scan were only two adjacent cubes like 1,1,1 and 2,1,1, each cube would have a single side covered and five sides exposed, a total surface area of 10 sides.

Texte du lien

  • # Plus cool que les jours précédents

    Posté par  . Évalué à 2.

    J'ai mis 45min pour les 2 étoiles.

    La première étape stockés les cubes dans un HashSet puis compter les faces non adjacente à une autre en checkant la présence dans le HashSet.

    Pour la deuxième, j'ai monté un dijkstra en partant d'un espace à l'extérieur à la structure de cube. Au final, je check si le côté du cube est adjacent à une zone accessible depuis l'air.

    • [^] # Re: Plus cool que les jours précédents

      Posté par  . Évalué à 3.

      A peu près pareil pour moi. Mais simple BFS a la place de Dijkstra.
      Code non cleané et non optimisé (pas besoin aujourd'hui, phew).

      def included(cube):
    for i in range(3):
        global max_coordinate
        if cube[i] < -1 or cube[i] > max_coordinate + 1:
            return False
    return True

def get_adjacents(cube):
    x, y, z = cube
    for adj in [
        (x, y, z + 1),  # up
        (x, y, z - 1),  # down
        (x - 1, y, z),  # left
        (x + 1, y, z),  # right
        (x, y - 1, z),  # back
        (x, y + 1, z),  # front
    ]:
        if included(adj):
            yield adj

droplet = []
max_coordinate = 0
with open("2022/input_files/day18") as f:
    for data in f:
        cube = tuple(map(int, data.rstrip().split(",")))
        max_coordinate = max(max_coordinate, max(cube))
        droplet.append(cube)

# Start BFS on top left corner to find exterior area
exterior = [(0, 0, 0)]
queue = []
queue.append((0, 0, 0))
while queue:
    cube = queue.pop(0)
    for adj in get_adjacents(cube):
        if adj not in exterior and adj not in droplet:
            exterior.append(adj)
            queue.append(adj)

part1_surface = 0
part2_surface = 0
for cube in droplet:
    for adj in get_adjacents(cube):
        if adj not in droplet:
            part1_surface += 1
            if adj in exterior:
                part2_surface += 1
print(f"{part1_surface=}")
print(f"{part2_surface=}")

      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

      • [^] # Re: Plus cool que les jours précédents

        Posté par  (Mastodon) . Évalué à 5.

        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.

  • # python tranquille

    Posté par  . Évalué à 4.

    Relativement facile ce jour

    La partie 1 étant un échauffement, parlons partie 2. Il faut "remplir" toutes les aspérités d'une boule constituée de petits cubes de 1x1x1 et dont la surface est irrégulière. Et compté les surfaces exposées au liquide.

    vizu

    La visualisation m'a bien aidé :

    On peut voir les creux qui doivent se remplir.

    code partie 2

    J'ai rempli par itération (while True) en m'arrêtant quand plus rien de nouveau ne se remplissait.

    Ensuite, pour chaque cube, on compte combien de face sont en contact avec de l'eau (6 voisins, 2 par dimension x, y, z).

    import sys

S = set()  # cubes
for l in sys.stdin.read().splitlines():
    S.add(tuple(map(int,l.split(','))))

A = 23
L = set()  # water
for x in range(-2,A+1):
    for y in range(-2,A+1):
        L.add((x,y,-2))
more = True
while more:
    c = 0
    for x in range(-2,A+1):
        for y in range(-2,A+1):
            for z in range(-2,A+1):
                if (x,y,z) not in S and (x,y,z) not in L: # water can only expand in air
                    for (i,j,k) in [(0,0,1),(0,0,-1),(0,1,0),(0,-1,0),(1,0,0),(-1,0,0)]:
                        if (x+i,y+j,z+k) in L: # if neighbour is water
                            L.add((x,y,z)) # water expand
                            c += 1
    more = (c>0)

N = 0
for (x,y,z) in S:
    for (i,j,k) in [(0,0,1),(0,0,-1),(0,1,0),(0,-1,0),(1,0,0),(-1,0,0)]:
        if (x+i,y+j,z+k) in L:
            N += 1
print(N)

    Exécution en 0.11s et 11MB RAM.

    • [^] # Re: python tranquille

      Posté par  (Mastodon) . Évalué à 2.

      Jolie la visualisation !
      Tu fais ça comment ?

      • Yth.

      • [^] # Re: python tranquille

        Posté par  . Évalué à 4.

        J'utilise AWK pour construire un fichier openscad.
        C'est un fichier texte qui décrit les formes à dessiner. exemple ici : translate([17.05,9.05,3.05]) cube([0.9,0.9,0.9]); Je laisse un petit espace entre chaque cube pour que ça ne fasse pas une grosse masse.
        Habituellement, je m'en sers pour faire des modèles pour de l'impression 3D.
        Je faisais un blocage avec le modeleur clicodrome, type Freecad. Openscad m'a sauvé :)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.