Forum Programmation.autre Advent of Code, jour 17

• # Solution en Haskell

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

  

  Je trouve que ce problème ressemble à celui d'hier.
  Il s'agit encore d'un parcours dans un graphe.
  Ici, le graphe est pondéré. On va donc utiliser l'algorithme de Dijkstra au lieu d'un simple parcours en profondeur/largeur.
  Comme hier, la direction est importante. Les sommets du graphe seront donc les paires (Position, Direction).
  Les voisins d'un sommet ne seront pas les positions adjacentes dans la grille mais celle à distance entre 1 et 3 pour la partie 1 et entre 4 et 10 pour la partie 2.
  La direction devra également changer à chaque fois.
  Le poids des arêtes sera la somme des chiffres indiqués sur chacune des tuiles que l'on a parcouru durant ce déplacement.

  Dans mon code, j'utilise la fonction dijkstra' que j'ai également écrite pour des problèmes des années précédentes.
  Voici sa signature

  dijkstra' :: (Hashable v, Real w) => (v -> [(v, w)]) -> (v -> Bool) -> [v] -> Maybe w

  Le type v est celui des sommets et le type w est celui des poids des arêtes.
  La fonction prend en entrée
  - une fonction de voisinage qui à chaque sommet associe une liste des sommets voisins ainsi que le poids de l'arête entre les deux sommets,
  - une fonction de prédicat pour le sommet de fin,
  - un ensemble de sommets de départ.
  et renvoit la distance entre un des sommets de départs et un des sommets de fin si un chemin existe.

  Voici le code (sans les imports)

  import           AOC.Prelude
  import           Data.Char (digitToInt)
  import           Data.Massiv.Array (Matrix, (!), (!?), U, Comp(Seq), Sz(Sz2))
  import qualified Data.Massiv.Array as A
  import           AOC (aoc)
  import           AOC.V2 (V2(..), adjacent, toIx2)
  import           AOC.Parser (Parser, sepEndBy1, eol, digitChar, some)
  import           AOC.Search (dijkstra')
  
  type Grid = Matrix U Int
  type Position = V2 Int
  type Direction = V2 Int
  
  directions :: [V2 Int]
  directions = adjacent (V2 0 0)
  
  parser :: Parser Grid
  parser = A.fromLists' Seq <$> some (digitToInt <$> digitChar) `sepEndBy1` eol
  
  neighbors :: [Int] -> Grid -> (Position, Direction) -> [((Position, Direction), Int)]
  neighbors nbSteps grid (pos, dir) =
      [ ((nextPos, nextDir), weight)
      | i <- nbSteps
      , nextDir <- directions
      , nextDir /= dir && nextDir /= -dir
      , let nextPos = pos + fmap (*i) nextDir
      , isJust (grid !? toIx2 nextPos)
      , let weight = sum [grid ! toIx2 (pos + fmap (*j) nextDir) | j <- [1..i]]
      ]
  
  solveFor :: [Int] -> Grid -> Maybe Int
  solveFor nbSteps grid = dijkstra' (neighbors nbSteps grid) (`elem` ends) starts where
      Sz2 h w = A.size grid
      starts = [(V2 0 0, V2 1 0), (V2 0 0, V2 0 1)]
      ends = [(V2 (h-1) (w-1), V2 0 1), (V2 (h-1) (w-1), V2 1 0)]
  
  solve :: Text -> IO ()
  solve = aoc parser (solveFor [1..3]) (solveFor [4..10])

  • [^] # Re: Solution en Haskell

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

    

    J'ai oublié dire:
    450ms pour la partie et 2s pour la partie 2.
    Pas très satisfait mais je pense que c'est améliorable.

  • [^] # Re: Solution en Haskell

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

    

    Après quelques optimisations
    200ms pour la partie 1 et 800ms pour la partie 2.

    L'idée est qu'au lieu de dire qu'un noeud du graphe est un couple (position, direction) avec 4 directions possibles, je dis qu'un noeud est un couple (position, booléen)
    ou le booléen m'indique si je me déplace horizontalement ou verticalement.
    Ca fait 2 fois moins de noeuds dans le graphe. Du coup, logiquement, ça divise le temps d'exécution par deux (et même plus avec quelques autres optimisations).

    Le code qui change:

    type Grid = Matrix U Int
    type Position = V2 Int
    type Direction = Bool -- True -> horizontal | False -> vertical
    
    neighbors :: [Int] -> Grid -> (Position, Direction) -> [((Position, Direction), Int)]
    neighbors nbSteps grid (pos, dir) =
        [ ((nextPos, not dir), weight)
        | i <- nbSteps
        , let vDir = if dir then V2 0 1 else V2 1 0
        , let nextPos = pos + fmap (*i) vDir
        , isJust (grid !? toIx2 nextPos)
        , let range = if i > 0 then [1..i] else [i..(-1)]
        , let weight = sum [grid ! toIx2 (pos + fmap (*j) vDir) | j <- range]
        ]
    
    solveFor :: [Int] -> Grid -> Maybe Int
    solveFor nbSteps grid = dijkstra' (neighbors nbSteps' grid) (`elem` ends) starts where
        nbSteps' = nbSteps ++ map negate nbSteps
        Sz2 h w = A.size grid
        starts = (V2 0 0,) <$> [True, False]
        ends = (V2 (h-1) (w-1),) <$> [True, False]

    • [^] # Re: Solution en Haskell

      Posté par Yth (Mastodon) le 17 décembre 2023 à 16:27. Évalué à 2. Dernière modification le 17 décembre 2023 à 16:31.

      

      J'ai encore codé sur téléphone aujourd'hui, et ça m'a encore pas trop réussi. Le weekend est pas mon ami cette année, et je sais pas comment je vais faire les 23, 24 et 25, mais bon.

      J'ai donc tout fait de tête, à inventer des algos avec mes gros doigts sur mon petit écran, sans rien réutiliser de pratique que du python chocolat, ou vanille peut-être…

      Et ça a bien bien foiré.
      Parce que le coup de la position et du booléen horizontal/vertical je l'ai vu direct, mais pour l'implémentation, j'ai tout raté, et laissé tomber.
      J'arrivais pas à modéliser, trop long, trop chiant d'écrire sur le petit écran fêlé.
      Et pourtant j'avais presque le résultat de la partie 1 très vite, mais j'avais 104, 107, 111, jamais 102, donc un bug fondamental dans l'algo quelque part.

      Et au bout du compte, sur données réelles, j'ai 12s sur l'exo 1 et 5s sur l'exo 2, donc un algo absurde mais qui roule mieux sur le second exercice que sur le premier.
      J'ai eu très très peu à adapter pour résoudre l'exo 2, et le rendre efficace pour les deux exercices, ce truc m'a pris 5 minutes et j'ai eu directement la bonne réponse.

      Mais à l'évidence, il y a un truc dans mon approche que j'ai raté, parce que ça a beaucoup planté quand même, et je n'ai jamais réussi à raccrocher le fait qu'on s'en moque d'arriver par la droite ou la gauche puisqu'on va à la fois en haut et en bas après dans les deux cas.

      Bref, code pourri, beaucoup de temps passé à me casser les orteils, et les dents, sur le périphérique mobile, et une conclusion : c'est vraiment pas un bon outil de programmation.

      Bilan j'ai repris mon truc au propre, sur un ordinateur, et j'ai réussi ma modélisation avec uniquement horizontal ou vertical, en refaisant ça calmement, et avec un vrai clavier.

      Bah ça fonctionne, et je tombe à 7s et 4s.
      On notera que j'ai tellement mal codé mon bidule que PyPy est indispensable , en CPython on monte à 1 minute 42, c'est dire si c'est moche.
      Et après, au lieu de stocker mes scores dans un dictionnaire d'états (un dataclass(int x, int y, bool horizontal)) j'ai repris un tableau en x*y*horizontal, et l'indexation étant nettement plus efficace comme ça on tombe à 6s au total.
      Ça reste pourri.
      Avec un petit compteur pour comptabiliser les appels à mon itérateur d'Explorateur, j'en ai 1 100 226 sur la partie 1 et 247 885 sur la 2.

      from sys import stdin
      from dataclasses import dataclass
      data = stdin.read().strip().splitlines()
      plan = [[int(_) for _ in line] for line in data]
      WIDTH = len(plan[0])
      HEIGHT = len(plan)
      MAX = sum(sum(_) for _ in plan)
      @dataclass(frozen=True)
      class Explorer:
        x: int = 0
        y: int = 0
        h: bool = True
        SKIP = 0
        NB = 3
        @property
        def val(self):
          return plan[self.y][self.x]
        @property
        def score(self):
          return SCORE[self.y][self.x][self.h]
        def __repr__(self):
          return f"{self.x:02}:{self.y:02}{'↔' if self.h else '↕'}{self.score:03}"
        def __bool__(self):
          return self.x >= 0 and self.y >= 0 and self.x < WIDTH and self.y < HEIGHT
        def __add__(self, n):
          v = not self.h
          return Explorer(self.x + n * self.h, self.y + n * v, v)
        def __sub__(self, n):
          v = not self.h
          return Explorer(self.x - n * self.h, self.y - n * v, v)
        def __call__(self, score):
          score += self.val
          if self.score < score:
            return False, score
          SCORE[self.y][self.x][self.h] = score
          return True, score
        def up(self, n=1):
          x = self
          s = self.score
          for _ in range(1, n + 1):
            x = self + _
            if not x:
              return False
            s += x.val
          return s
        def down(self, n=1):
          x = self
          s = self.score
          for _ in range(1, n + 1):
            x = self - _
            if not x:
              return False
            s += x.val
          return s
        def __iter__(self):
          s = self.up(self.SKIP)
          if s is not False:
            n = [self + i for i in range(self.SKIP + 1, self.SKIP + self.NB + 1) if self + i]
            for x in n:
              b, s = x(s)
              if b:
                yield x
          s = self.down(self.SKIP)
          if s is not False:
            n = [self - i for i in range(self.SKIP + 1, self.SKIP + self.NB + 1) if self - i]
            for x in n:
              b, s = x(s)
              if b:
                yield x
      
      def run(skip, nb):
        Explorer.SKIP = skip
        Explorer.NB = nb
        states = {Explorer(0, 0, True), Explorer(0, 0, False)}
        SCORE[0][0] = [0, 0]
        while states:
          states = set(ns for s in states for ns in s)
        return min(SCORE[-1][-1])
      
      SCORE = [[[MAX, MAX] for __ in range(WIDTH)] for _ in range(HEIGHT)]
      ex1 = run(0, 3)
      
      SCORE = [[[MAX, MAX] for __ in range(WIDTH)] for _ in range(HEIGHT)]
      ex2 = run(3, 7)

      Allez, demain, je dois tout faire entre 9h30 et 10h30, sur un PC qui n'est pas à moi :)

      • Yth.

  • [^] # Re: Solution en Haskell

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

    

    Moi, je suis arrivé à descendre à 300ms mais je pense pas faire beaucoup mieux.
    J'ai tenté des heuristiques pour A* mais rien de concluant.
    Enfin, j'en avais une bien mais elle prenait trop de temps à être calculer.

• # J'étais fatigué, j'ai fait un algo moisie, j'ai du corrigé des bug moisie

  Posté par syj le 17 décembre 2023 à 23:50. Évalué à 1.

  

  Mauvais cocktail pour coder :)
  - S'être couché à 3h
  - Être fatigué, limite reste de gueule bois
  - Regarder les conneries à la télé en même temps qu'on code.

  Conséquences:
  - çà donne un code très long à déboguer
  - un problème pris de travers.

  Mon code est tellement moche que je ne vais pas le partager :)

  Honnêtement , je ne voyais pas comment appliquer un algo traditionnel de pathfinding avec les règles de déplacement.
  Je suis donc partie sur une fonction récursive dans un premier temps. Mauvaise pioche entre les bogues, je suis arrivé après 3h à me dire que çà ne pouvait pas marcher.
  Je change de stratégie. Je pars de l'arrivé et je remonte progressivement en mettant à jour les noeuds adjacents, j'y ai passé encore bien 3h au total sur la journée.

  3min pour donner la réponse de la partie 2.

• # Trois dimensions

  Posté par 🚲 Tanguy Ortolo (site web personnel) le 18 décembre 2023 à 20:14. Évalué à 3. Dernière modification le 18 décembre 2023 à 20:15.

  

  Pour ce problème, j'ai considéré qu'on n'était pas vraiment en deux dimensions, mais plutôt en trois. Parce que l'état d'un creuset, ce n'est pas seulement sa position sur le terrain, mais aussi le nombre de cases qu'il a parcouru dans une direction donnée… ce qui se représente également très bien par un nombre, que je considère comme une troisième coordonnée.

  Ça permet de se ramener à un problème de parcours de proche en proche, avec une définition bien particulière des voisins d'un point.

  Voici le code :

  from collections.abc import Iterable, Iterator, Sequence
  from typing import Self
  
  import numpy as np
  import numpy.typing as npt
  
  
  import aoc
  
  
  class City:
      def __init__(self, array: Sequence[Sequence[int]]):
          self.matrix: npt.NDArray[np.ubyte] = np.array(array, dtype=np.ubyte)
          self.ly, self.lx = self.matrix.shape
  
      @classmethod
      def import_lines(cls, lines: Iterable[str]) -> Self:
          array = [[int(char) for char in line if char != '\n']
                   for line in lines]
          return cls(array)
  
      def walk(self, minturn, maxturn) -> int:
          # We will be using a matrix with three coordinates:
          # * z indicates how many steps were made in which direction:
          #   -             z <         0: starting, no previous steps!
          #   -         0 ≤ z <   maxturn: 1 to maxturn steps up ↑
          #   -   maxturn ≤ z < 2*maxturn: 1 to maxturn steps down ↓
          #   - 2*maxturn ≤ z < 3*maxturn: 1 to maxturn steps left ←
          #   - 3*maxturn ≤ z < 4*maxturn: 1 to maxturn steps right →
          visits: npt.NDArray[np.int_] = np.full(
                  (4 * maxturn, self.ly, self.lx), -1, dtype=np.int_)
  
          def _neighs(z: int, y: int, x: int) -> Iterator[tuple[int, int, int]]:
              """Yield all directly accessible neighbors of a point, including
              points outside the limits of the city."""
              if z < 0:
                  # Special case for start
                  yield (0 * maxturn, y - 1, x)
                  yield (1 * maxturn, y + 1, x)
                  yield (2 * maxturn, y, x - 1)
                  yield (3 * maxturn, y, x + 1)
                  return
              div, mod = divmod(z, maxturn)
              if div == 0:
                  if mod < maxturn - 1:
                      yield (z + 1, y - 1, x)
                  if mod + 1 >= minturn:
                      yield (2 * maxturn, y, x - 1)
                      yield (3 * maxturn, y, x + 1)
                  return
              if div == 1:
                  if mod < maxturn - 1:
                      yield (z + 1, y + 1, x)
                  if mod + 1 >= minturn:
                      yield (2 * maxturn, y, x - 1)
                      yield (3 * maxturn, y, x + 1)
                  return
              if div == 2:
                  if mod + 1 >= minturn:
                      yield (0 * maxturn, y - 1, x)
                      yield (1 * maxturn, y + 1, x)
                  if mod < maxturn - 1:
                      yield (z + 1, y, x - 1)
                  return
              if div == 3:
                  if mod + 1 >= minturn:
                      yield (0 * maxturn, y - 1, x)
                      yield (1 * maxturn, y + 1, x)
                  if mod < maxturn - 1:
                      yield (z + 1, y, x + 1)
                  return
  
          def neighs(z: int, y: int, x: int) -> Iterator[tuple[int, int, int]]:
              for z_, y_, x_ in _neighs(z, y, x):
                  if 0 <= x_ < self.lx and 0 <= y_ < self.ly:
                      yield z_, y_, x_
  
          currents: dict[tuple[int, int, int], int] = {(-1, 0, 0): 0}
          while len(currents) > 0:
              nexts: dict[tuple[int, int, int], int] = {}
              for current_pos, current_total in currents.items():
                  for next_pos in neighs(*current_pos):
                      z, y, x = next_pos
                      loss = self.matrix[y, x]
                      next_total = current_total + loss
                      if (visits[next_pos] < 0
                              or next_total < visits[next_pos]):
                          visits[next_pos] = next_total
                          nexts[next_pos] = next_total
              currents = nexts
          loss = -1
          for div in range(4):
              for mod in range(minturn - 1, maxturn):
                  z = div * maxturn + mod
                  pos = (z, self.ly - 1, self.lx - 1)
                  if loss < 0 or 0 < visits[pos] < loss:
                      loss = visits[pos]
          return loss
  
  
  def part1(lines: aoc.Data) -> int:
      """Solve puzzle part 1: determine the minimum total heat loss from start to
      end, using normal crucibles"""
      city = City.import_lines(lines)
      return city.walk(1, 3)
  
  
  def part2(lines: aoc.Data) -> int:
      """Solve puzzle part 2: determine the minimum total heat loss from start to
      end, using ultra crucibles"""
      city = City.import_lines(lines)
      return city.walk(4, 10)

Suivre le flux des commentaires

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