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.