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.