Forum Programmation.autre Advent of Code 2023, jour 23

• # Solution en Haskell

  Posté par Guillaume.B le 23 décembre 2023 à 09:37. Évalué à 4.

  

  100 ms pour la partie 1, 4s pour la partie 2.

  J'ai trouvé le problème assez simple aujourd'hui. En tout cas plus simple que les jours précédents. Dommage que je me sois levé tard.

  Tout d'abord, remarquons que le problème qu'on essaie de résoudre (Longest Path) est NP-difficile. Ce qui ne veut pas dire qu'on ne va réussir car il n'y a pas tellement de choix et donc de backtrack à faire.

  La première partie est du backtracking classique. Dans la deuxième partie, l'espace d'exploration augmente considérablement. Mais on se rend qu'il y a de longs couloirs, c'est à dire une suite de sommets de degré 2.

  On va dans compresser la grille de cette manière:
  on dit qu'une tuile est intéressante si c'est la tuile de départ, d'arrivée ou si c'est une jonction, c'est à dire un sommet de degré au moins 3.
  Et pour chaque tuile intéressante, on va chercher dans chaque direction la prochaine tuile intéssante ainsi que la distance qui les sépare.
  On va appliquer notre algo de backtracking sur cette instance.

  Voici le code:
  comme d'habitude, on va essayer d'être le plus générique possible et on va définir une fonction longestPath qui prend en entrée un sommet de départ, un sommet d'arrivée et une fonction de voisinages. Elle s'applique donc à n'importe quelle strucutre et pas seulement aux grilles. On va la mettre dans ma librairie de fonctions de recherche dans un graphe.

  longestPath :: Hashable a => (a -> [(a, Int)]) -> a -> a -> Int
  longestPath neighbors start dest = go Set.empty 0 start where
      go visited len pos 
          | pos == dest = len
          | otherwise = maximumDef 0 [ go (Set.insert pos visited) (len+len') next
                                     | (next, len') <- neighbors pos
                                     , not $ next `Set.member` visited
                                     ]

  Ensuite, vient le code du problème à proprement parler.
  Tout d'abord les types utilisés et le parsing. Rien de bien compliqué.

  data Tile = Path | Forest | North | South | West | East deriving (Eq)
  type Grid = Matrix B Tile
  
  parser :: Parser Grid
  parser = fromLists' Seq <$> some tile `sepEndBy1` eol where
      tile = choice [Path <$ ".", Forest <$ "#", North <$ "^", South <$ "v", West <$ "<", East <$ ">"]

  Ensuite, on définit une fonction de voisnage pour la partie 1.

  neighbors1 :: Grid -> V2 Int -> [(V2 Int, Int)]
  neighbors1 grid p = case grid ! toIx2 p of
      Path -> [ (p', 1)
              | p' <- adjacent p
              , let tile = grid !? toIx2 p'
              , tile /= Nothing && tile /= Just Forest
              ]
      North -> [(p - V2 1 0, 1)]
      South -> [(p + V2 1 0, 1)]
      West -> [(p - V2 0 1, 1)]
      East -> [(p + V2 0 1, 1)]
      _ -> error "neighbors: cannot happen"
  
  part1 :: Grid -> Int
  part1 grid = longestPath neighbors start dest where
      neighbors = neighbors1 grid
      Sz2 h w = size grid
      start = V2 0 1
      dest = V2 (h-1) (w-2)

  Pour la partie 2, on définit une fonction de voisinage qui ne prend pas en compte les pentes.

  neighbors2 :: Grid -> V2 Int -> [V2 Int]
  neighbors2 grid p = [ p' 
                      | p' <- adjacent p
                      , let tile = grid !? toIx2 p'
                      , tile /= Nothing && tile /= Just Forest
                      ]

  et on définit la fonction de compression de grille.

  compressGrid :: Grid -> V2 Int -> V2 Int -> Matrix B [(V2 Int, Int)]
  compressGrid grid start end = makeArray Seq (Sz2 h w) \(Ix2 r c) ->
          let pos = V2 r c
              neighbors = neighbors2 grid pos
          in
          if pos == start || pos == dest || length neighbors > 2 then
              [followPath next pos 1 | next <- neighbors]
          else
              []
      where
      followPath pos pred len =
          case neighbors2 grid pos of
              [next1, next2] | next1 == pred -> followPath next2 pos (len+1)
                             | otherwise     -> followPath next1 pos (len+1)
              _ -> (pos, len)
  
      Sz2 h w = size grid
  
  part2 :: Grid -> Int
  part2 grid = longestPath neighbors start dest where
      compressed = compressGrid grid start end
      neighbors p = compressed ! toIx2 p
      Sz2 h w = size grid
      start = V2 0 1
      dest = V2 (h-1) (w-2)

• # Brut force pour la partie 2

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

  

  Pour la partie 1 , j'ai appliqué un bête parcours en profondeur.
  Pour la partie 2, j'ai laissé tourner ma solution de partie 1 pour trouver la max de la partie 2.
  Environ 1h de calcul.

  J'aurai bien essayé de faire un truc plus intelligent mais je n'avais pas le temps.

  Il faut quand même lancer ce code -Xss1g pour avoir une stack conséquence qui permet une récursivité aussi profonde.

  package aoc2023;
  
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Scanner;
  
  public class Aoc2023s23 {
      public static Point[] DIRECTIONS = new Point[] { new Point(1, 0), new Point(-1, 0), new Point(0, -1),
              new Point(0, 1) };
  
      public record Point(int x, int y) {
      }
  
      public static class Path {
          boolean[][] walked;
          int[] pathX;
          int[] pathY;
          int step = -1;
  
          public Path(World world) {
              walked = new boolean[world.height][world.width];
              this.pathX = new int[world.width * world.height];
              this.pathY = new int[world.width * world.height];
          }
  
          public void move(int x, int y) {
              walked[y][x] = true;
              step++;
              this.pathX[step] = x;
              this.pathY[step] = y;
  
          }
  
          public void back() {
  
              if (step >= 0) {
                  int x = getX();
                  int y = getY();
                  walked[y][x] = false;
              }
              step--;
          }
  
          private int getY() {
              return this.pathY[step];
          }
  
          private int getX() {
              return this.pathX[step];
          }
  
      }
  
      public static class World {
          List<String> rows;
          int width;
          int height;
  
          int endx;
          int endy;
  
          int maxPath =0;
  
  
          public World(List<String> rows) {
              this.rows = rows;
              this.height = rows.size();
              this.width = rows.get(0).length();
              this.endx = width - 2;
              this.endy = height - 1;
          }
  
          public final char cell(int x, int y) {
              return rows.get(y).charAt(x);
          }
  
          public boolean canWalkFrom(int sx, int sy, int dx, int dy) {
              if (dx < 0 || dx >= width || dy < 0 || dy >= height) {
                  return false;
              }
              char dest = cell(dx, dy);
              if (dest == '#') {
                  return false;
              }
  
              char start = cell(sx, sy);
              return true;
              /*
              if (start == '.') {
                  return true;
              } else if (start == '>') {
                  return dx > sx;
              } else if (start == '<') {
                  return dx < sx;
              } else if (start == '^') {
                  return dy < sy;
              } else if (start == 'v') {
                  return dy > sy;
              }
              throw new RuntimeException("Unsupported " + start);
              */
          }
  
          public void explore(Path path) {
              int sx = path.getX();
              int sy = path.getY();
  
              if(sx == endx && sy == endy) {
                  System.out.println("Size:" + path.step);
                  if(path.step > maxPath ) {
                      maxPath = path.step;
                  }
                  return ;
              }
  
              for (int i = 0; i < DIRECTIONS.length; i++) {
                  Point p = DIRECTIONS[i];
  
                  int dx = sx + p.x;
                  int dy = sy + p.y;
  
                  if (canWalkFrom(sx, sy, dx, dy) && !path.walked[dy][dx]) {
                      path.move(dx, dy);
                      explore(path);
                      path.back();
                  }
              }
          }
      }
  
      public static void main(String[] args) {
  
          try (Scanner in = new Scanner(Aoc2023s23.class.getResourceAsStream("res/t23.txt"))) {
              List<String> rows = new ArrayList<>();  
              while (in.hasNext()) {
                  String row = in.nextLine();
                  rows.add(row);
              }           
              World world = new World(rows);
  
              Path path = new Path(world);
              path.move(1, 0);
              world.explore(path);
  
              System.out.println("max=" +  world.maxPath);
          }
  
      }
  }

• # Les ennuis commencent...

  Posté par Yth (Mastodon) le 02 janvier 2024 à 18:08. Évalué à 2.

  

  Pour moi, les ennuis ont commencés : pas d'ordinateur, pas de clavier, juste mon petit téléphone qui ne permet pas vraiment de voir les données avec du recul, et l'extrême pénibilité de coder avec un clavier tactile, toujours à basculer pour chercher les chiffres, les opérations, les =, :, les (), [] et {}.
  Bref, pénible, donc on code avec des variables à une ou deux lettres, on fait les algos les plus courts à écrire, et on tâtonne.

  La première partie reste assez simple, je n'ai pas mis bien longtemps et le temps de calcul sur téléphone est assez ridicule.
  Pour la seconde j'ai tenté de laisser tourner des heures avec l'algo brute-force bête et méchant, mais à part flinguer la batterie on n'arrive pas à grand chose, soyons honnêtes.

  Donc être malins.
  Et là je l'ai pas été, j'ai tout de suite tenté de réduire le problème aux nœuds d'exploration : les cases où il y a 3 ou 4 directions possibles, et je note les distances entre ces nœuds, puis j'explore le graphe réduit des nœuds.
  Sauf que j'ai cru ce problème trop complexe pour mon téléphone, et cherché à simplifier : trouver des nœuds qui sont des passages obligés.
  J'étais encouragé par le fait qu'il y en a dans les données de test.
  Ça veut dire qu'on peut découper le graphe simplifié en plusieurs graphes qui s'enchaînent.
  Donc je code, je débugge, ça marche, je lance sur les données réelles, il me laisse avec comme seul noeud intermédiaire le noeud d'arrivée, et tout ça n'a servi à rien.
  Sauf que la réponse tombe malgré tout sans trop d'attente, le problème réduit est suffisamment simple pour que la force brute s'en empare.
  Ça met ~10s sur mon PC (avec pypy bien sûr, pour le coup), pas loin de 2 minutes sur le téléphone.
  Je n'ai pas cherché plus loin, et j'ai juste remis le code au propre, en virant l'exploration inutile des nœuds intermédiaires, avant de le poster.
  La première passe, sur la carte complète, permet aussi de lister les nœuds et la distance les séparant. Techniquement, il pourrait en manquer, puisque l'exploration se fait avec les contraintes de glissement, ça n'est pas le cas, j'ai misé sur cette simplification parce que la denrée qui me manquait vraiment c'était du temps pour coder correctement les choses.

  Je me rappelle cependant avoir tenté plein de trucs et finalement avoir été déçu de la simplicité du bidule qui fournit finalement la solution, bref.
  Au passage, j'utilise une pile de chemins en cours d'exploration, un deque() bien utile pour ça, plutôt qu'une fonction récursive, on fait exploser la limite de récursivité bien trop vite sur le téléphone. Donc j'ai une boucle et une FIFO d'états à faire avancer, c'est pas trop violent sur la RAM, et on n'atteint pas les limites.

  Donc je commence, et j'ai pas fini, les codes dont je n'ai aucune réelle certitude de l'exactitude en toutes circonstances, ça sera pire dans les jours qui viennent.

  from sys import stdin
  from collections import deque
  data = stdin.read().strip().splitlines()
  
  W = len(data[0])
  H = len(data)
  MAX = W * H
  M = "".join(data) + "#" * W
  S = M.index(".")
  F = data[-1].index(".") + MAX - W
  D = {"<": (-1,), ">": (1,), "v": (W,), "^": (-W,), ".": (1, -1, W, -W)}
  NODES = {}
  
  def rexplore(start, end, nodes):
    """Exploring full problem, storing path length between nodes
    A node is a crossroad in the maze : where 3 or 4 destinations are possible.
    Start and End are also nodes.
    """
    def nextpos(pos, previous):
      for d in D.get(M[pos], 0):
        y = pos + d
        if y >= 0 and y not in previous and M[y] != "#":
          yield pos + d
    nodes[start] = {}
    nodes[end] = {}
    stack = deque()
    # Current exploring position, [previous positions leading there], last node visited
    stack.append((start + W, [start], start))
    while stack:
      x, path, last = stack.pop()
      yy = list(nextpos(x, path + [x]))
      if x == end or len(yy) > 1:  # We are on a node
        if x not in nodes:
          nodes[x] = {}
        nodes[last][x] = max(nodes[last].get(x, 0), len(path) - path.index(last))
        nodes[x][last] = nodes[last][x]
        last = x
      if x == end:  # End of the path, yielding it
        yield path
        continue
      for y in yy:  # following all available paths
        stack.append((y, path + [x], last))
  
  ex1 = max(len(q) for q in rexplore(S, F, NODES))
  
  def explore2(start, end):
    """Dumb exploration of node graph
    Small enough that brute-force wins the day fast enough (~10s)
    """
    stack = deque([(start, [], 0)])
    while stack:
      pos, path, score = stack.pop()
      if pos == end:
        yield (score, path)
        continue
      for node, val in [_ for _ in NODES[pos].items() if _[0] not in path]:
        stack.append((node, path + [pos], score + val))
  
  ex2, P = max(explore2(S, F))

  • Yth.

Suivre le flux des commentaires

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