Forum Programmation.autre Advent of Code, jour 16

• # Solution en Haskell

  Posté par Guillaume.B le 16 décembre 2023 à 17:29. Évalué à 2. Dernière modification le 16 décembre 2023 à 17:31.

  

  C'est un problème qui peut se faire un parcours en longueur ou largeur.
  Problème: selon la direction du faisceau, les cases à visiter suivantes peuvent être différentes.
  Du coup un sommet du graphe que l'on veut parcourir ne sera pas seulement une position dans la grille mais un couple (position, direction).

  Je commence par importer mes fonctions nécessaires et définir les types utilisés dans le problème.
  Les positions et directions sont des vecteurs de dimension 2.
  J'appelerai le couple (Position, Direction) est un Beam.

  import           AOC.Prelude
  import           Data.List (maximum)
  import qualified Data.HashSet as Set
  import           Data.Massiv.Array (Matrix, (!), (!?), B, Comp(Seq), Sz(Sz2))
  import qualified Data.Massiv.Array as A
  import           Control.Parallel.Strategies (parMap, rdeepseq)
  import           AOC (aoc)
  import           AOC.V2 (V2(..), toIx2)
  import           AOC.Parser (Parser, sepEndBy1, eol, choice, some)
  import           AOC.Search (reachableFrom)
  
  data Tile = Empty | Horizontal | Vertical | Slash | Antislash
  type Position = V2 Int
  type Direction = V2 Int
  type Beam = (Position, Direction)
  type Grid = Matrix B Tile

  Ensuite, le parsing, rien de bien intéressant

  parser :: Parser Grid 
  parser = A.fromLists' Seq <$> some tile `sepEndBy1` eol where
      tile = choice [ Empty <$ "."
                    , Horizontal <$ "-"
                    , Vertical <$ "|"
                    , Slash <$"/"
                    , Antislash <$ "\\"
                    ]

  Ensuite, vient le parcours en largeur. Je réutilise une fonction reachableFrom définie pour des problèmes précédents.
  Elle prend deux arguments
  - une fonction qui étant donné renvoit la liste des sommets voisins
  - un sommet de départ
  et renvoit l'ensemble des sommets accessibles depuis le sommet de départ.

  reachableFrom :: Hashable a => (a -> [a]) -> a -> HashSet a
  reachableFrom nborFunc start = go HSet.empty [start] where
      go visited [] = visited
      go visited (v : stack)
          | v `HSet.member` visited = go visited stack
          | otherwise = go (HSet.insert v visited) (nborFunc v ++ stack)

  Pour utiliser reachableFrom, je dois calculer, étant donné un beam, les beams suivants.
  Je le fais en deux temps en définissant d'abord une fonction nextDirections qui étant donné une direction et une tuile me renvoit les directions suivantes.

  nextDirections :: Direction -> Tile -> [Direction]
  nextDirections (V2 drow dcol) = \case
      Slash -> [V2 (-dcol) (-drow)]
      Antislash -> [V2 dcol drow]
      Horizontal | drow /= 0 -> [V2 0 (-1), V2 0 1]
      Vertical | dcol /= 0 -> [V2 (-1) 0, V2 1 0]
      _ -> [V2 drow dcol]

  A partir de ça, je peux définir ma fonction neighbors nécessaire à `reachableFrom

  neighbors :: Grid -> Beam -> [Beam]
  neighbors grid (pos, dir) = [ (nextPos, nextDir)
                              | nextDir <- nextDirections dir (grid ! toIx2 pos)
                              , let nextPos = pos + nextDir
                              , isJust (grid !? toIx2 nextPos)
                              ]

  Je peux maintenant définir ma fonction energized qui me renvoit le nombre de tuiles énergisées en utilisant les fonctions reachableFrom et neighbors définis plus haut.

  energized :: Grid -> Beam -> Int
  energized grid start = Set.size $ Set.map fst reachable where
      reachable = reachableFrom (neighbors grid) start
  
  part1 :: Grid -> Int
  part1 grid = energized grid (V2 0 0, V2 0 1)

  Pour la partie 2, c'est du brute-force sur toutes les positions de départ possibles, j'ai pas trouvé mieux.
  Ca se parallélise bien, j'utilise parMap qui est une version parallèle de map.

  part2 :: Grid -> Int
  part2 grid = maximum $ parMap rdeepseq (energized grid) starts where
      Sz2 h w = A.size grid
      starts = concat $
                  [[(V2 r 0, V2 0 1), (V2 r (w-1), V2 0 (-1))] | r <- [0 .. h-1]]
               ++ [[(V2 0 c, V2 1 0), (V2 (h-1) c, V2 (-1) 0)] | c <- [0 .. w-1]]

  1400ms sur un seul core et 800ms en multicore pour la partie 2. Pas terrible le parallélisme, j'aurais espéré mieux. Je ne me suis peut-être pas pris comme il fallait.

  • [^] # Re: Solution en Haskell

    Posté par Yth (Mastodon) le 16 décembre 2023 à 22:30. Évalué à 2.

    

    J'ai encore codé en marchant, sur mon téléphone.
    D'ailleurs, pour les masochistes dans mon genre, je conseille : Qpython, on ne le trouve pas sur fdroid, je ne l'ai pas non plus trouvé sur Aurora, mais on peut installer l'apk depuis github. Il ne demande aucune autorisation, mais ne fonctionnera pas sans un accès aux fichiers, qu'on doit activer soi-même : il installe des trucs dans un répertoire accessible ([userdata]/qpython/).
    C'est bien moins casse-pied qu'un éditeur en ligne, plus rapide, et on peut partager facilement les fichiers avec un PC par exemple avec Syncthing

    Trêve de publicités, ce genre d'algo, à débugger comme un brontosaure, sur un téléphone, c'est galère, et je n'ai vraiment pu le finir qu'une fois devant un vrai clavier, mais j'étais pas loin !
    Par contre, pas lourd d'optimisations, j'avais pas le temps d'y réfléchir, par chance le code tourne malgré tout en 3,5 secondes, donc ça va.
    Après trois secondes de réflexion, je me suis dis qu'un cache serait inutile, en pratique un cache n'est pas entièrement inutile, et me fait redescendre à 1,95s, sachant qu'il est assez crétinement utilisé.

    Bref, voici du code :

    from sys import stdin
    from dataclasses import dataclass
    from functools import cache
    data = stdin.read().strip().splitlines()
    WIDTH = len(data[0])
    HEIGHT = len(data)
    
    @dataclass(frozen=True)
    class coord:
      x: int = 0
      y: int = 0
      def __add__(self, o):
        return coord(self.x + o.x, self.y + o.y)
      def __bool__(self):
        return self.x >= 0 and self.y >= 0 and self.x < WIDTH and self.y < HEIGHT
      def __repr__(self):
        return f"{self.x}:{self.y}"
    
    class direction(coord):
      def __repr__(self):
        return self.s
    
    @cache
    def move(*beams):
      for b, d in beams:
        m = data[b.y][b.x]
        if m == ".":
          yield b + d, d
        elif m == "|":
          if d.y:
            yield b + d, d
          else:
            yield b + N, N
            yield b + S, S
        elif m == "-":
          if d.x:
            yield b + d, d
          else:
            yield b + E, E
            yield b + W, W
        elif m == "/":
          d = {N: E, S: W, E: N, W: S}.get(d)
          yield b + d, d
        elif m == "\\":
          d = {N: W, S: E, E: S, W: N}.get(d)
          yield b + d, d
    
    def energize(p, d):
      beams = [(p, d)]
      visited = set()
      while beams:
        visited.update(beams)
        beams = set((b, d) for b, d in move(*beams) if b)
        beams.difference_update(visited)
      return len(set(p for p, d in visited))
    
    # cleaner code, cleaner debug using Direction class
    N, S, E, W = direction(0, -1), direction(0, 1), direction(1, 0), direction(-1, 0)
    N.s, S.s, E.s, W.s = "N", "S", "E", "W"
    
    ex1 = energize(coord(0, 0), E)
    ex2 = max([
      max(energize(coord(x, 0), S) for x in range(WIDTH)),
      max(energize(coord(x, HEIGHT - 1), N) for x in range(WIDTH)),
      max(energize(coord(0, y), E) for y in range(HEIGHT)),
      max(energize(coord(WIDTH - 1, y), W) for y in range(HEIGHT)),
    ])

    Donc l'idée est un peu la même : on stocke des couples (position, direction), une coordonnée est True si elle n'est pas hors champs, on peut additionner deux coordonnées, les directions sont des coordonnées qui se représentent avec une autre valeur à définir soi-même, et j'ai donc quatre instances N, S, E et W, qui vont simplement s'afficher en N, S, E et W lors des débuggages.
    La fonction energize prend un rayon de départ (position, direction), et retourne le nombre de cases allumées, donc c'est la résolution d'un problème n°1, on en a 440 à résoudre pour le n°2.

    Après c'est un poil du brute force : on teste vraiment toutes les positions de départ possible.
    Et le cache est sur un ensemble de rayons (couple position/direction), donc il n'y a pas tellement de chances de retomber exactement sur le même ensemble (en fait c'est pas si mal), et ça n'optimise pas du tout sur un trajet qu'on retrouverait dans pleins de parcours.
    Mais ça divise le temps quasiment par deux, donc ce n'est pas entièrement inutile !

    Une meilleure approche serait une fonction qui retourne tous les rayons générés à partir d'un rayon, et là, on sait qu'on va repasser par les mêmes endroits lors de chaque exploration, rayon par rayon quand il y a bifurcation, et ça peut accélérer énormément.
    Le terrain faisant 110*110, soit 12100 cases, donc 48400 rayons possibles, la plus grosse exploration en générant déjà 12246 chez moi, on a rapidement fait le tour quand même, et ça peut certainement aller plus vite au bout du compte.

    En pratique, ma fonction move est appelée 167654 fois sans cache et 61561 fois avec cache, donc entre 48200 et 61561, ya pas si lourd à gagner que ça. Allez, je passerais allègrement sous la seconde et voilà, rien de plus. Peut-être que l'implémentation réelle montrerait que pas mal de rayons n'existent pas (sont inaccessibles depuis le bord), et qu'on pourrait vraiment y gagner.

    Après, c'est assez marrant d'utiliser un cache sur une fonction qui yield, il doit cacher un générateur, ou peut-être toutes les valeurs, sinon ça cache pas, puisqu'un générateur c'est transitoire. Franchement je ne sais pas comment il se débrouille en interne, mais ça fonctionne !

    • Yth.

• # Du rust pour ma part

  Posté par YetiBarBar le 16 décembre 2023 à 22:59. Évalué à 1. Dernière modification le 16 décembre 2023 à 23:00.

  

  Mon code est par ici

  Rien de bien inventif et assez brutal: on propage le rayon lumineux comme indiqué dans l'énoncé jusqu'à sa sortie du tableau, en mémorisant les couples (x, y, direction de propagation) pour éviter de tourner en rond. Un algo très ressemblant à un bfs…

  Pour la partie 2, du "brute-force" basique en testant toutes les entrées possibles.

  Sans multithread, ça tourne en 620ms (parsing, partie 1 et 2) sur un seul core de mon Core i7 de 10 ans d'âge.

  • [^] # Re: Du rust pour ma part

    Posté par Guillaume.B le 17 décembre 2023 à 14:37. Évalué à 1.

    

    Faudrait que je m'y mettre au Rust, un jour.

Suivre le flux des commentaires

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