Forum Programmation.autre Advent of Code 2023, jour 23

Posté par  . Licence CC By‑SA.
Étiquettes :
2
23
déc.
2023

Ce jour ci, il faut trouver son chemin dans un labyrinthe.
Le labyrinthe est composé de plusieurs types de tuile:
des chemins ".", des forêts "#" et des pentes dans une direction "", ">", "v", "<".
Dans la partie 1, on n'a pas le droit d'aller dans le forêt et on n'a pas le droit de remonter une pente.

Le but n'est pas ici de trouver un plus court chemin mais un plus long chemin dans le labyrinthe. Évidemment, on n'a pas le droit de repasser plusieurs fois par la même tuile (sinon on ferait des cycles infinis).

Exemple de labyrinthe:

#.#####################
#.......#########...###
#######.#########.#.###
###.....#.>.>.###.#.###
###v#####.#v#.###.#.###
###.>...#.#.#.....#...#
###v###.#.#.#########.#
###...#.#.#.......#...#
#####.#.#.#######.#.###
#.....#.#.#.......#...#
#.#####.#.#.#########v#
#.#...#...#...###...>.#
#.#.#v#######v###.###v#
#...#.>.#...>.>.#.###.#
#####v#.#.###v#.#.###.#
#.....#...#...#.#.#...#
#.#########.###.#.#.###
#...###...#...#...#.###
###.###.#.###v#####v###
#...#...#.#.>.>.#.>.###
#.###.###.#.###.#.#v###
#.....###...###...#...#
#####################.#

La partie 2 est la même chose que la partie 1 sauf que l'on est autorisé à remonter les pentes.
Et mine de rien, ça complique pas mal le problème car l'espace d'exploration explose.

  • # Solution en Haskell

    Posté par  . É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  . É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  (Mastodon) . É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.