Forum Programmation.autre Advent of Code 2023, jour 21

Posté par  . Licence CC By‑SA.
Étiquettes :
1
21
déc.
2023

Pour le problème de ce jour, on se donne une grille composée de rochers, de jardins et d'un point de départ.

L'exemple est le suivant:

...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........

Les "." représentent les jardin, les "#" représentent les rochers et S est la position de départ.

Le but de la partie 1 est de compter le nombre de positions où le jardinier peut arriver en partant de la tuile de départ et en faisant exactement 64 mouvements dans les 4 directions possibles (nord, sud, ouest , est).

Dans la partie 2, on suppose que la grille est répétée dans les 4 directions un nombre infini de fois. Alors là, même question que la partie 1 mais avec 26501365 mouvements!!!

  • # Solution en Haskell

    Posté par  . Évalué à 3.

    300ms pour la partie 2.

    Pour la partie 1, il faut remarquer vu que la parité de la distance au point de départ change à chaque déplacement. La distance entre le point de départ et un sommet accessible après 64 mouvements est donc toujours pair.

    Du coup, les sommets à trouver sont ceux situés exactement à distance n où n est pair et n <= 64.
    Un simple parcours en largeur fait l'affaire.

    Pour la partie 2, ça se complique.
    Mais on repère que l'instance est assez particulière:
    - la grille de départ est carrée;
    - le point de départ se trouve au centre;
    - la ligne horizontale, la ligne verticale ainsi que les diagonales autour du centre sont vides.

    Notons f(n) le nombre de points accessibles après n mouvements et notons M la taille (verticale et horizontale) de la grille.
    On peut donc se dire qu'il doit y avoir une régularité entre f(n) et f(n+M).

    Notons r = 26501365 mod M et regardons la suite des u_i = f(r + iM) pour i entier naturel.
    Après avoir calculé les 5 ou 6 premières valeurs par ordinateur, on se rend compte que la suite est une séquence quadratique ou dit autrement que la suite des dérivées discrètes secondes est constante. Elle est donc de la forme u_n = a *n^2 + b * n + c.
    Il faut donc calculer u_n avec n = 26501365 // M où // désigne la division entière.

    Pour calculer u_n, on a besoin que des 3 premiers termes de la suite.
    Notons d1 = u1 - u0, d2 = u2 - u1 et d' = d2 - d1 alors
    u_n = u0 + n * d1 + n * (n-1) * d' / 2.
    Et voilà !

    Voici le code un peu commenté.

    Tout d'abord le parsing et un précalcul pour transformer l'entrée en matrice et repérer le sommet de départ.

    data Tile = Garden | Rock | Start deriving (Eq)
type Grid = Matrix U Bool

parser :: Parser [[Tile]]
parser = some tile `sepEndBy1` eol where
    tile = Garden <$ "." <|> Rock <$ "#" <|> Start <$ "S"

precomp :: [[Tile]] -> Maybe (Grid, V2 Int)
precomp tiles = do
    start <- listToMaybe [V2 i j | (i, j, Start) <- flattenWithIndex tiles]
    let tiles' = map (map (==Rock)) tiles
    let matrix = fromLists' Seq tiles'
    pure (matrix, start)

    Pour la partie 1, on définir une fonction nbors qui donne le voisinage d'une tuile.
    Comme on ne sort pas de la grille dans la partie 1 et pour factoriser avec la partie 2,
    on fait des modulo sur les coordonnées.

    nbors :: Grid -> V2 Int -> [V2 Int]
nbors grid = filter (not . (grid !) . toIx2 . mod2) . adjacent where 
    Sz2 h w = size grid
    mod2 (V2 r c) = V2 (r `mod` h) (c `mod` w)

part1 :: (Grid, V2 Int) -> Int
part1 (grid, start) = count even . takeWhile (<=64) . map fst $ bfs (nbors grid) start

    Pour la partie 2, on définit d'abord une fonction générique pour calculer le n-ième d'une séquence quadratique.

    -- given a quadratic sequence with first terms u0, u1, u0,  compute u_n
quadraticSequence :: Integer -> Integer -> Integer -> Integer -> Integer
quadraticSequence u0 u1 u2 n = u0 + n * d1 + n * (n-1) * d' `div` 2
    where
    d1 = u1 - u0
    d2 = u2 - u1
    d' = d2 - d1

    Ensuite, on peut l'appliquer à notre problème en calculant les trois premiers termes de la suite grâce à un parcours en largeur.

    part2 :: (Grid, V2 Int) -> Integer
part2 (grid, start) = result where
    nbSteps = 26_501_365
    Sz2 h _ = size grid
    r = nbSteps `mod` h
    bfsTrace = map fst $ bfs (nbors grid) start
    countParity x = fromIntegral . count (\y -> even (y - x)) 
    nbReachable x = countParity x $ takeWhile (<=x) bfsTrace
    u0 = nbReachable r
    u1 = nbReachable (r+h)
    u2 = nbReachable (r+2*h)
    result = quadraticSequence u0 u1 u2 (fromIntegral $ nbSteps `div` h)

    • [^] # Re: Solution en Haskell

      Posté par  (Mastodon) . Évalué à 2.

      Alors j'ai rien compris à ton explication, mais je crois que je suis en train de tomber malade.
      J'ai hyper galéré à débugger mon code, bourré de mauvaises bornes, jusqu'au bout du bout…

      Bon, d'une façon ou d'une autre je n'ai pas fait comme toi.
      Cf plus bas :)

      • Yth.

    • [^] # Re: Solution en Haskell

      Posté par  (Mastodon) . Évalué à 2.

      Ça y est, j'ai, compris ton explication, bien vu !

      Yth.

  • # Rhaaaaaa !!!

    Posté par  (Mastodon) . Évalué à 3.

    Un problème bien bien pénible aujourd'hui, où il faut être très précis pour éviter les effets de bords.
    encore une fois on « voit » des trucs dans les données, qui sont indispensables à la résolution…

    On explore en damier, soit les cases noires (x+y pairs) soit les cases blanches (x+y impairs).
    Une exploration type celle de l'exercice 1 que tout le monde a dû réussir, nous permet facilement de trouver le nombre de cases blanches et noires, chez moi c'est 7509 et 7566, ce qui additionné avec les rochers ne fait pas la taille du terrain, car il y a 4 cases inaccessibles (chez moi). Jusqu'ici tout va bien.

    Comme tu l'as fait remarquer, on peut aller en ligne droite vers les répétitions du terrain, donc l'exploration d'une zone répétée autour de la zone de départ se fait le plus efficacement à partir du point d'entrée : le milieu du côté.
    Pour les zones en diagonale, on va rentrer par la case au coin.
    Ya pas plus rapide.

    Le terrain fait 131x131, et le départ au centre en 65x65.
    Donc on peut explorer indépendamment les différentes zones, en notant simplement le temps nécessaire à les atteindre.
    65 + 1 + 131 * (distance - 1) quand on va en ligne droite nord, sud, est ou ouest.
    Et 65 + 1 + 65 + 1 + 131 * (distance de Manhattan - 2) pour les cases qui sont au moins un peu en diagonale.
    Bon, ya des +1, des +2, des -1, des -2, c'est les effets de bords ça.
    On rentre au nord en 66 mouvements, et deux fois au nord en 66+131 mouvements, etc.
    On rentre au nord-ouest en 65+1+65+1 = 132 mouvements, et de là on se décale horizontalement ou verticalement par paquets de 131.

    On sait donc rapidement combien d'étapes il nous reste quand on entre dans une zone. Ça va être plein tout du long, et on va soit valider les cases noires, soit les cases blanches, en alternance.
    Ben oui, si on entre dans une zone mettons via (0, 0), la case (0, 0) d'une zone adjacente est à 131 mouvements, qui est un nombre impair, donc on ne l'atteint pas.
    On a en fait un damier de damiers, yay !

    Là on va donc simplement regarder combien d'étape il reste à parcourir, ou combien on en a parcouru, et choisir sans se tromper la bonne valeur entre noir et blanc.
    On additionne.

    En pratique, une exploration en distance de zone par rapport à celle du départ est assez simple : on a 4 zones directement en face de la zone de départ, et (distance -1) * 4 zones qui forment une diagonale, on a un joli losange.

    ...●...
..●○●..
.●○●○●.
●○●○●○●
.●○●○●.
..●○●..
...●...

    En distance 0 on a la zone de départ.
    En distance 1 on a 4 zones directement liées.
    En distance 2 on a 4 zones directes, et 4 zones diagonales.
    En distance 3 c'est 4 et 8.
    En distance n, c'est 4 et (n-1)*4.
    Il se trouve que tout le monde à une distance donnée est soit blanc, soit noir (blanc = on considère les cases blanches à l'intérieur de la zone, noir = on considère les cases noires).
    Comme le nombre d'étape final est impair, on ne considère pas la case de départ, donc la case de départ sur mon schéma, dans une zone blanche, doit être noire.

    Ceci nous amène presque au bout, parce que là on va commencer à avoir des zones qu'on n'explorera plus entièrement, à cause des pas restants, trop courts.

    Dans mon code, je prends une marge suffisante, et je calcule les cases à partir des déplacements restants.
    Mais c'est assez facile, j'ai 8 zones : nord, sud, est, ouest et nord-est, nord-ouest, sud-est, sud-ouest, chacune explorée à partir d'un point de départ spécifique.
    Lors de l'exploration, je note pour chaque pas effectué les cases atteintes.
    Donc il me suffit de regarder quelle distance je peux parcourir dans mon exploration, avec les déplacements restants, et je sais quelles cases sont atteintes.
    Je dénombre, j'additionne.

    Et comme pour le reste du problème, on a les 4 directions cardinales uniques, et les 4 directions diagonales répétées (distance - 1) fois, donc on calcule 8 valeurs, on multiplie 4 d'entre elles, on additionne et c'est ok.
    On passe à la distance suivante.
    On s'arrête avec une petite marge où on va additionner des zéros.
    J'ai pas mal fait ça pour éviter d'être sûr de moi, vu que j'ai eu des quantités invraisemblables d'erreurs aux bornes…

    Et puis, voilà, résultat :)

    Ça permet aussi de résoudre l'exercice 1 avec le problème central, vu que pour chacune de mes zones, je ne regarde que ce qu'il se passe dedans, j'ai les infos pour le premier problème.

    from sys import stdin
from dataclasses import dataclass
from functools import cached_property
data = stdin.read().strip().splitlines()
LARGEUR = len(data[0])  # 131
HAUTEUR = len(data)  # 131
XMAX = LARGEUR - 1
YMAX = HAUTEUR - 1
MIDDLE = XMAX // 2  # 65
ROCKS = frozenset((x, y) for y, _ in enumerate(data) for x, t in enumerate(_) if t == '#')
START = "".join(data).index("S")
START = (START % LARGEUR, START // LARGEUR)  # 65x65
STEPS1, STEPS2 = (64, 26501365)
@dataclass
class exploration:
  sx: int = 0
  sy: int = 0
  def run(self):
    def dest(x, y):
      yield (x - 1), y
      yield (x + 1), y
      yield x, (y - 1)
      yield x, (y + 1)
    explored = {(self.sx, self.sy)}
    exploring = {(self.sx, self.sy)}
    steps = [{(self.sx, self.sy)}]
    overexplored = set()
    s = 0
    while exploring:
      s = s + 1
      exploring = {
        d
        for x, y in exploring
        for d in dest(x, y)
        if d not in ROCKS
      }.difference(explored).difference(overexplored)
      for x, y in exploring:
        if (x < 0 or x >= LARGEUR or y < 0 or y >= LARGEUR) and (x, y) not in overexplored:
          overexplored.add((x, y))
      exploring.difference_update(overexplored)
      steps.append(exploring)  # adds an empty set() at the end
      explored.update(exploring)
    self._exploration = steps
    self.even = self.explored(0, len(steps))
    self.odd = self.explored(1, len(steps))
  @cached_property
  def exploration(self):
    if not hasattr(self, '_exploration'):
      self.run()
    return self._exploration
  def explored(self, start=0, steps=None):
    steps = min(steps + 1, len(self.exploration))
    return sum(
      len(self.exploration[i])
      for i in range(start, steps, 2)
    )

exp1 = exploration(*START)
ex1 = exp1.explored(STEPS1 % 2, STEPS1)

    Voilà notre explorateur de zone, et la fonction explored qui retourne les cases explorées selon le parité (zone noire ou blanche), et le nombre de pas restant.
    Pour le premier problème, on démarre en START = (65, 65) et on fait 64 pas, on a un damier pair puisque 64 est pair, donc en particulier la case de départ est prise en compte.

    Pour le second problème on a une seconde exploration à faire. D'abord le paramétrage.

    N = exploration(MIDDLE, 0)
S = exploration(MIDDLE, YMAX)
E = exploration(XMAX, MIDDLE)
W = exploration(0, MIDDLE)
NE = exploration(XMAX, 0)
NW = exploration(0, 0)
SE = exploration(XMAX, YMAX)
SW = exploration(0, YMAX)
# nombre minimum de pas pour explorer entièrement n'importe quelle zone.
MAXEXPLORATION = max(len(x.exploration) - 1 for x in [N, S, E, W, NE, NW, SE, SW])
def bigexploration(x, y):
  bx = MIDDLE + 1 + LARGEUR * (abs(x) - 1)
  by = MIDDLE + 1 + HAUTEUR * (abs(y) - 1)
  bd = bx + by
  if y == 0:
    if x > 0:
      return E, bx
    if x < 0:
      return W, bx
    return exp1, 0
  elif x == 0:
    if y > 0:
      return S, by
    return N, by
  if x > 0 and y > 0:
    return SE, bd
  if x > 0 and y < 0:
    return SW, bd
  if x < 0 and y > 0:
    return NE, bd
  return NW, bd

FINESTEPS = STEPS2 - MAXEXPLORATION * 2
odd = STEPS2 % 2
score = exp1.odd if odd else exp1.even

    La fonction bigexploration retourne le type de zone, et le nombre de pas effectués, pour entrer dans la zone en (x, y) par rapport à celle de départ.
    FINESTEPS c'est la distance à partir de laquelle on va vraiment compter les pas dans chaque zone. J'ai mis * 2 pour avoir de la marge et ne pas avoir à réfléchir aux effets de bords, mais je peux valider que simplement STEPS2 - MAXEXPLORATION fonctionne.

    Après ça le code est moche et répétitif, dans l'esprit de bigexploration.

    for distance in range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2):
  for ex, steps in [
    bigexploration(0, -distance),
    bigexploration(0, distance),
    bigexploration(distance, 0),
    bigexploration(-distance, 0),
  ]:
    remaining = STEPS2 - steps
    odd = remaining % 2
    if steps > STEPS2:
      continue
    s = ex.odd if odd else ex.even
    if steps > FINESTEPS:
      s2 = ex.explored(odd, remaining)
      print(f"Finescore({remaining}) {s2} / {s} {s!=s2}")
      s = s2
    score += s
  if distance <= 1:
    continue
  for ex, steps in [
    bigexploration(1, 1 - distance),
    bigexploration(-1, 1 - distance),
    bigexploration(1, distance - 1),
    bigexploration(-1, distance - 1),
  ]:
    remaining = STEPS2 - steps
    odd = remaining % 2
    if steps > STEPS2:
      continue
    s = ex.odd if odd else ex.even
    if steps > FINESTEPS:
      s2 = ex.explored(odd, remaining)
      print(f"FineDiago({remaining}) {s2} / {s} {s!=s2}")
      s = s2
    score += s * (distance - 1)

ex2 = score

    Et bigre, même le range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2) m'a causé 2h de prise de tête, j'avais oublié de ne pas commencer à 0, mais bien à 1, donc je comptais 5 fois la zone de départ, comme j'ai lutté pour trouver ça, rhaaa !

    On vérifie l'intérêt de nos FINESTEPS avec les sorties :

    Finescore(130) 5635 / 7509 True
Finescore(130) 5661 / 7509 True
Finescore(130) 5624 / 7509 True
Finescore(130) 5672 / 7509 True
FineDiago(195) 6610 / 7509 True
FineDiago(195) 6571 / 7509 True
FineDiago(195) 6560 / 7509 True
FineDiago(195) 6573 / 7509 True
FineDiago(64) 957 / 7566 True
FineDiago(64) 958 / 7566 True
FineDiago(64) 946 / 7566 True
FineDiago(64) 957 / 7566 True

    On voit bien qu'on a les 4 sommets qui sont incomplets, et pour les diagonales on a deux couches de diagonales à considérer. Et à chaque fois, le résultat pratique dépend de la direction qu'on considère, parce que la distribution des rochers met le bazar.

    C'est officiellement celui qui m'a le plus résisté jusqu'à présent, mais au final, l'algo était là assez rapidement, il était juste buggé de partout :(

    • Yth, vivement les vacances.

  • # Méthode de Guillaume

    Posté par  . Évalué à 1. Dernière modification le 23 décembre 2023 à 02:37.

    J'ai implémenté la méthode avec séquence quadratique de Guillaume B.
    Je suis un peu décu de ne pas avoir trouvé par moi-même

    Mais je suis très heureux d'avoir découvert ce point des maths que je ne connaissais pas.

    package aoc2023;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Aoc2023s21s3 {
    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 State {     
        Set<Point> current = new HashSet<>();;
        Set<Point> next = new HashSet<>();;

        char[][] map;
        int width;
        int height;

        List<Long> quadraticsSeries = new ArrayList<>();

        public void propagate(Point p) {
            for (Point move : DIRECTIONS) {
                int dx = p.x + move.x;
                int dy = p.y + move.y;

                int rx = dx % width;
                if (rx < 0) {
                    rx += width;
                }
                int ry = dy % height;
                if (ry < 0) {
                    ry += height;
                }

                Point np = new Point(dx, dy);               
                if (map[ry][rx] == '.') {
                    next.add(np);
                }
            }

        }

        public long propagate(World world, int step) {
            map = world.map;
            width = world.width;
            height = world.height;

            // gridSize d'une taille arbitaire suffisant propage au moins une grille complète (à priori)
            int gridSize = width * 2;

            // étape pour lesquels on va récupérer les valeurs de  u(n) pour la séquence quadratique.
            int same = (step-1) % gridSize;
            int end = same + gridSize*2+1;                              

            // Boucle de propagation (très inefficace)         
            System.out.println("Propagation maximum à calculer :" + end);
            for (int i = 0; i < end; i++) {
                next.clear();


                current.forEach(p -> propagate(p));
                // switch
                Set<Point> tmp = next;
                next = current;
                current = tmp;

                if(i >= 0 && (i % (gridSize)) == same) {                    
                    System.out.println("u(" + current.size() + ") = " + current.size());
                    quadraticsSeries.add((long)current.size());
                }                               
            }

            long d1 = quadraticsSeries.get(1) - quadraticsSeries.get(0);  
            long d2 = quadraticsSeries.get(2) - quadraticsSeries.get(1);        
            //long d3 = quadraticsSeries.get(3) - quadraticsSeries.get(2);

            System.out.println("dp:" + (d2-d1));
            //System.out.println("dp:" + (d3-d2)); // si la séquence est quadratique d2-d1 == d3-d2 == d4-d3 ...

            long a = (d2-d1)/2;

            long c = quadraticsSeries.get(0);
            // a n^2 + b n + c = u(n)           
            // b = (u(n) - a n^2 - c)/n
            int n = 2;
            double b = (quadraticsSeries.get(n) - a * n * n - c)/n;


            System.out.println(quadraticsSeries);
            System.out.println(a + "," + b + "," + c);

            /*
            // Vérifie via la propagation jusqu'à u(3) que la formule u(n) = a*x^2 + bx+c  est bien paramétré.
            n = 3;          
            long control3 = (long)(a * n * n + n * b + c);
            System.out.println("Control3:" + control3);
            if(control3 != quadraticsSeries.get(3)) {
                throw new RuntimeException("Failed to compute u(n) = a*x^2 + bx+c ");
            }*/

            n = ((step)/gridSize);

            return (long)(a * n * n + n * b + c);       
        }       

        public boolean match(int x, int y) {
            return current.contains(new Point(x, y));
        }
    }

    public static class World {
        final int width;
        final int height;

        char[][] map;

        State state = new State();

        public World(List<String> rows) {
            height = rows.size();
            width = rows.get(0).length();
            map = new char[height][width];

            for (int y = 0; y < height; y++) {
                String row = rows.get(y);
                for (int x = 0; x < width; x++) {
                    if (row.charAt(x) == 'S') {
                        state.current.add(new Point(x, y));
                        map[y][x] = '.';
                    } else {
                        map[y][x] = row.charAt(x);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        try (Scanner in = new Scanner(Aoc2023s21s3.class.getResourceAsStream("res/t21.txt"))) {
            List<String> rows = new ArrayList<>();
            while (in.hasNext()) {
                rows.add(in.nextLine());
            }
            World world = new World(rows);          
            System.out.println(world.state.propagate(world, 26501365));                     
        }           
    }
}

Suivre le flux des commentaires

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