Forum Programmation.autre Advent of Code 2023, jour 22

Posté par  . Licence CC By‑SA.
Étiquettes :
1
22
déc.
2023

Dans le problème du jour, on a des briques, comme au Tetris mais en 3 dimensions.
Chaque brique est composée de plusieurs cubes tous alignés dans une certaine direction (selon la hauteur, la largeur ou la profondeur).
Voici l'exemple

1,0,1~1,2,1
0,0,2~2,0,2
0,2,3~2,2,3
0,0,4~0,2,4
2,0,5~2,2,5
0,1,6~2,1,6
1,1,8~1,1,9

Chaque brique est donnée par les coordonnées x,y,z de ses deux extrémités et séparés par un "~".
La première ligne représente une brique composé de 3 cubes de coordonnées (1, 0, 1), (1, 1, 1), (1, 2, 1) et est orienté dans le sens de la coordonnée y c'est à dire la profondeur.

Le but de la partie 1 est d'abord de simuler la chute de chaque brique sachant il y a un sol à la hauteur 0.
Ensuite, on doit déterminer le nombre de briques qui peuvent être désintégrées.
Une brique peut être désintégrée si aucune autre brique ne tombe si on la retire.

Dans la partie 2, on doit compter, pour chaque brique, le nombre de briques qui vont chuter si on la retire et faire la somme totale.

  • # Solution en Haskell

    Posté par  . Évalué à 1. Dernière modification le 22 décembre 2023 à 11:46.

    5ms pour la partie 1 et 15ms pour la partie 2.

    Le problème d'aujourd'hui n'est pas très dur conceptuellement mais j'ai un peu galéré à cause de bugs. Heureusement que l'exemple est là pour nous aider contrairement à hier et avant-hier.

    Tout d'abord, on va trier les briques selon la coordonnée z. Ca rend les choses plus à traiter.
    On va ensuite simuler la chute de chaque pièce par ordre d'apparition, ce qui ne pose pas de problème grâce au tri que l'on vient de faire.

    On va ensuite calculer support et supported.
    support est un dictionnaire qui, à une brique i, associe les index des pièces qui la supportent.
    De même supported est un dictionnaire qui, à une brique i, associe les index des pièces supportées par elle.

    On dira qu'une brique est stable si elle est supportée par au moins deux autres pièces.

    Du coup, une pièce peut être désintégrée si les pièces supportées par elle sont toutes stables.

    Pour la partie 2, il s'agit pour chaque pièce de faire un parcours en profondeur (en largeur marche aussi) pour simuler la cascade entrainée par la désintégration d'une pièce.
    Une pièce chute si les pièces qui la supportent sont soi la pièce qui est désintégrée soit vont chuter.

    J'avais écrit une fonction DFS générique qui m'a déjà servie dans plusieurs exemples.
    Cette fonction prenait comme paramètre un sommet de départ et une fonction qui a un sommet associe son voisinage, c'est à dire ses sommets successeurs.

    Problème: on a besoin ici de connaitre les sommets déjà parcourus (qui correspondent aux briques qui vont être désintégrées) pour calculer le voisinage.

    J'ai donc écrit une fonction BFS générique mais qui prend en compte ce paramètre: la fonction de voisinage prend en paramètre un sommet ainsi que l'ensemble des sommets déjà visités.

    Voici le code:

    data Brick = Brick { _begin :: !(V3 Int), _end :: !(V3 Int) } deriving (Show)
    type Cube = V3 Int
    type Space = HashMap (V2 Int) Int
    
    parser :: Parser [Brick]
    parser = brick `sepEndBy1` eol where
        brick = Brick <$> coord <* "~" <*> coord
        coord = V3 <$> decimal <* "," <*> decimal <* "," <*> decimal
    
    sortBricks :: [Brick] -> [Brick]
    sortBricks = sortOn (view _z . _begin) 
                . map (\(Brick p1 p2) -> Brick (min p1 p2) (max p1 p2))
    
    cubesOf :: Brick -> [Cube]
    cubesOf (Brick (V3 x1 y1 z1) (V3 x2 y2 z2)) = V3 <$> [x1..x2] <*> [y1..y2] <*> [z1,z2]
    
    fallOne :: (Space, Brick) -> (Space, Brick)
    fallOne (space, brick) = (space', brick') where
        cubes = cubesOf brick
        height = maximum [HMap.findWithDefault 0 (V2 x y) space | (V3 x y _) <- cubes]
        Brick start@(V3 _ _ z) end = brick
        brick' = Brick (start - V3 0 0 (z - height))  (end - V3 0 0 (z - height)) 
        space' = foldl' go space (cubesOf brick')
        go spc (V3 x y z') = HMap.insert (V2 x y) (z'+1) spc
    
    fall :: [Brick] -> [Brick]
    fall = go HMap.empty where
        go _ [] = []
        go space (brick:bricks) = brick' : go space' bricks where
            (space', brick') = fallOne (space, brick) 
    
    cubeOwners :: [Brick] -> HashMap (V3 Int) Int
    cubeOwners = foldl' go HMap.empty . zip [0..] where
        go owners (i, brick) = foldl' 
                                (\owners' cube -> HMap.insert cube i owners')
                                owners
                                (cubesOf brick)
    
    precomp :: [Brick] -> ([Brick], IntMap [Int], IntMap [Int])
    precomp bricks = (bricks', support, supported) where
        bricks' = fall (sortBricks bricks)
        owners = cubeOwners bricks'
        supportOf i brick =
            if view _z (_begin brick) == 0
                then [-1]
                else ordNub .catMaybes $ 
                    [  j
                    | cube <- cubesOf brick
                    , let j = owners HMap.!? (cube - V3 0 0 1)
                    , j /= Just i
                    ]
        support = Map.fromList [(i, supportOf i brick) | (i, brick) <- zip [0..] bricks']
        supportedBy i brick =
            ordNub . catMaybes $ [ j 
                                 | cube <- cubesOf brick
                                 , let j = owners HMap.!? (cube + V3 0 0 1)
                                 , Just i /= j
                                 ]
        supported = Map.fromList [(i, supportedBy i brick) | (i, brick) <- zip [0..] bricks']
    
    part1 :: ([Brick], IntMap [Int], IntMap [Int]) -> Int
    part1 (bricks, support, supported) = length disintegrated where
        isStable i = length (support Map.! i) >= 2
        canBeDisintegrated i = all isStable (supported Map.! i)
        disintegrated = [i | (i, _) <- zip [0..] bricks, canBeDisintegrated i]
    
    dfs :: Hashable a => (a -> HashSet a -> [a]) -> a -> HashSet a
    dfs nborFunc start = go HSet.empty [start] where
        go visited [] = visited
        go visited (v:queue)
            | v `HSet.member` visited = go visited queue
            | otherwise =
                let visited' = HSet.insert v visited
                    nbors = nborFunc v visited' 
                in go visited' (nbors ++ queue)
    
    part2 :: ([Brick], IntMap [Int], IntMap [Int]) -> Int
    part2 (bricks, support, supported) = res where
        nborFunc v disintegrated =
            [ next 
            | next <- supported Map.! v
            , all (`HSet.member` disintegrated) (support Map.! next)
            ]
        res = sum [HSet.size (dfs nborFunc i) - 1 | (i, _) <- zip [0..] bricks]
    
    solve :: Text -> IO ()
    solve = aoc' parser (Just . precomp) part1 part2
    • [^] # Re: Solution en Haskell

      Posté par  . Évalué à 1.

      Je viens de me rendre compte que support et supported pouvaient être des tableaux plutôt que des dictionnaires. Avec quelques autres trucs, je descend à 10ms pour la partie 2.

  • # On fait tomber des trucs, mais on fait pas de Tetris.

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

    C'est le dernier jour où je vais avoir le temps de la faire, la suite ça sera peut-être dans une semaine…

    J'ai inventé un algo un peu tordu, assez efficace, rude à piger, donc à débugger.
    Déjà les coordonnées sont en 1 dimension : x+y*10+z*100, on va simplifier, surtout qu'on ne fait que des mouvements vers le bas, aucun test aux bornes à faire.
    J'ajoute un bloc de 10x10 en 0 pour poser le bazar.
    Une structure de Blocs assez modélisée, une autre pour l'Univers bien plus simple et à la fin un algo tordu.

    from sys import stdin
    from functools import total_ordering
    from collections import deque
    from itertools import chain
    data = deque(stdin.read().strip().splitlines())
    
    @total_ordering
    class Bloc:
      def __init__(self, blocdef=None, blocname=None, cubes=None):
        self.name = blocname
        if cubes:
          self.cubes = cubes
          self.alt = min(cubes) // 100
          return
        x, y, z = zip(*((int(__) for __ in _.split(",")) for _ in blocdef.split("~")))
        self.cubes = {
          a + b * 10 + c * 100
          for a in range(min(x), max(x) + 1)
          for b in range(min(y), max(y) + 1)
          for c in range(min(z), max(z) + 1)
        }
        self.alt = min(z)
      def __iter__(self):
        for p in self.cubes:
          yield p
      def __eq__(self, o):
        return self.alt == o.alt
      def __lt__(self, o):
        return self.alt < o.alt
      def __contains__(self, _):
        return _ in self.cubes
      def __repr__(self):
        return f"Bloc#{self.name}({self.cubes})"
      def __neg__(self):
        alt = min(_ // 100 for _ in self.cubes) * 100 - 100
        return Bloc(blocname=self.name, cubes={alt + _ % 100 for _ in self.cubes})
      def __pos__(self):
        alt = max(_ // 100 for _ in self.cubes) * 100 + 100
        return Bloc(blocname=self.name, cubes={alt + _ % 100 for _ in self.cubes})
      def __sub__(self, x):
        self.cubes = {_ - 100 * x for _ in self.cubes}
    
    class Universe:
      def __init__(self):
        self.zone = set(range(100))
        self.blocs = {}
      def __contains__(self, _):  # True if bloc can be placed in universe
        return not self.zone.intersection(_.cubes)
      def add(self, _):
        self.zone.update(_)
        for p in _:
          self.blocs[p] = _.name
    
    data.extendleft(["0,0,0~9,9,0"])
    blocs = sorted(Bloc(line, i) for i, line in enumerate(data))
    ground = blocs.pop(0)
    universe = Universe()
    universe.add(ground)
    for bloc in blocs:
      while -bloc in universe:
        bloc - 1
      universe.add(bloc)
    
    # Blocs under each bloc
    down = {
      bloc.name: {universe.blocs[p] for p in -bloc if p in universe.blocs}
      for bloc in blocs
    }
    cannot = {bloc for _ in down.values() if len(_) == 1 for bloc in _}.difference({0})
    ex1 = len(blocs) - len(cannot)

    Et l'exercice 2, prenez peur !

    topof = {}
    partial = {}
    for bloc in sorted(blocs, reverse=True):
      name = bloc.name
      if name not in topof:
        topof[name] = set()
      # Handling partially supported blocks
      mypartial = partial.pop(name, set())
      if mypartial:
        replay = True
        while replay:
          replay = False
          newpart = set()
          # All blocs partially supported elsewhere
          otherpart = set(chain.from_iterable(
            v
            for k, v in partial.items()
            if k not in topof[name]
          ))
          for _ in mypartial:
            if _ not in otherpart:
              # That bloc isn't supported by someone else elsewhere, it is mine!
              topof[name].add(_)
              topof[name].update(topof.get(_, []))
              replay = True  # We'll have to restart the search here, because the world changed.
            else:
              newpart.add(_)
          mypartial = newpart
        if mypartial:
          partial[name] = mypartial
      # Sending down my informations
      up = topof.get(name, set()).union({name})
      downward = list(down.get(name, []))
      if len(downward) == 1:  # Supported by only one other bloc, sending what I'm actively supporting
        topof[downward[0]] = topof.get(downward[0], set()).union(up)
      # Sending known partial information down
      for bloc in downward:
        partial[bloc] = partial.get(bloc, set()).union({name}).union(partial.get(name, {}))
      partial.pop(name, None)
    
    ex2 = sum(len(topof[bloc]) for bloc in cannot)

    J'ai pas vraiment le temps de remettre au propre, en gros je pars du haut, et je « pose » les blocs les uns sur les autres, en notant ceux qui sont partiellement posés, et où.
    Et puis à chaque bloc, j'essaie de simplifier par ceux qui ne sont partiellement posés plus que sur lui.
    Et… bah ça marche, en tapant bien sur le code.

    • Yth.

Suivre le flux des commentaires

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