Forum Programmation.autre Advent of Code, jour 14

Posté par  (Mastodon) . Licence CC By‑SA.
Étiquettes :
1
14
déc.
2023

Jour 14, tout en haut des nuages

À partir de demain nous allons redescendre, il n'y a plus d'île au-dessus de l'île de lave, donc une fois que la lave se remettra à couler, on va retourner en arrière pour tout remettre en marche.
On imagine déjà devoir faire s'écouler la lave vers les bonnes sources chaudes, et activer les bonnes machines pour fabriquer les bonnes pièces, pour réparer les autres machines pour envoyer du sable pour filtrer l'eau, pour la refroidir et faire de la neige.

Trêve digressions, aujourd'hui on constate que les miroirs concaves sont désalignés, et ne concentrent donc plus efficacement la lumière du soleil pour faire fondre la montagne et s'écouler le magma.

Alors on va remettre tout ça en place.

Et pour ça on a des manettes pour faire pivoter la plateforme du miroir, ce qui va faire rouler des pierres, au nord, au sud, à l'est, à l'ouest.
On va devoir compte la mousse amassée, comme pierre qui roule n'amasse pas mousse, le résultat est zéro, exercice suivant.

Ah, pardon, non, c'est pas ça : on a peur que la rambarde de sécurité ne supporte pas le poids des pierres qui roulent, donc on a mesurer le poids supporté par la rambarde nord, après avoir fait glisser les pierres au nord.

Un dessin valant mieux qu'un long discours, parait-il, voici des dessins, avec notre plateforme d'entraînement, et son état une fois tout basculé au nord. On a besoin de comptabilisé le poids des pierres-qui-roulent sur la rambarde nord, et ça dépend de leur distance, c'est le chiffre tout à droite. La somme pour chaque pierre donne le poids total, ici de 136 :

O....#....  ->  OOOO.#.O.. 10
O.OO#....#  ->  OO..#....#  9
.....##...  ->  OO..O##..O  8
OO.#O....O  ->  O..#.OO...  7
.O.....O#.  ->  ........#.  6
O.#..O.#.#  ->  ..#....#.#  5
..O..#O..O  ->  ..O..#.O.O  4
.......O..  ->  ..O.......  3
#....###..  ->  #....###..  2
#OO..#....  ->  #....#....  1

Maintenant qu'on s'est entraîner, on va jouer !

C'est rigolo de mettre les pierres au nord, mais on va tourner : nord, ouest, sud, est, et on tourne, et on secoue, et on mélange, et on spirale, et on danse, puis, enfin, on pèse.
On pèse la même chose après un milliard de tours, et le poids final est de 64, croyez-moi sur parole.

Un milliard de tours de manivelle, allez, hophophop, faut commencer tôt, parce qu'on n'a pas fini hein !
Bon, par contre après on va redescendre, peut-être faire une pause aux bains chauds, et calculer le massage optimal pour se détendre…

  • Yth.

  • # Impossible de se cacher, va falloir tourner.

    Posté par  (Mastodon) . Évalué à 2. Dernière modification le 14 décembre 2023 à 12:42.

    Comme dans tout les films avec une action répétées pleins de fois, comme de lustrer et frotter, ou peindre des palissades, on a une option pointillés, qui permet de sauter des deux-trois premières itérations directement à la dernière, et de constater, ébahis, les résultats de l'entraînement des padawans, devenu des adultes.

    Tout ça pour dire que même avec un cache efficace, tester le cache un milliard de fois, même si on ne calcule vraiment que quelques centaines, ou milliers, d'opérations, ça va être très, très, très long.

    Ça ne veut pas dire que le cache est inutile, mais totalement insuffisant.
    En pratique, que je le mette ou pas, et ce coup-ci j'ai absolument pensé ma modélisation et toutes mes fonctions, pour avoir un cache le plus efficace possible, ben on gagne quedalle en vitesse, et on sagouine même pas sa RAM, en fait, comme j'ai fait ça super bien, le cache, les caches, ben ils utilisent rien en mémoire.

    En fait, tout ce qui compte, c'est de faire des cycles, et de voir quand est-ce qu'on retombe sur un état vu précédemment.
    Là on a deux informations : les étapes préalables au démarrage d'un cycle de cycles, et la longueur de ce cycle de cycles.
    Si quelqu'un pense, là, maintenant, que j'ai mal choisi mes appellations, il a sans doute raison, c'est bien toute la difficulté du choix d'un bon nom de variable, choix qui n'est pas toujours en O(temps disponible).

    Chez moi, on calcule 160 cycles, on boucle sur 77 cycles après 83 cycles de mise en jambe.
    Donc avec (1 000 000 000 - 83) modulo 77 = 70, on va chercher le 70ème cycle de notre cycle de cycles, soit le 83+70=153ème cycle calculé, c'est l'état final, on le pèse.
    Et avec les données de test, on retombe bien sur le 64 prévu, avec un cycle de 7 cycles, et 3 cycles de mise en route, donc 10 cycles calculés, et le milliardième est le 6ème, youpi !

    Mon code est pas super joli, je n'ai pas cherché à factoriser mes fonctions pour glisser vers le nord, sud, est et ouest, donc j'en ai quatre, presque identiques.
    Ce qui est plus intéressant, ce sont mes efforts (inutile, mais jolis) pour préparer un cache super efficace et peu gourmand, comme quoi j'ai à la fois appris de mes erreurs passées, et pas du tout appris à anticiper où la difficulté se trouve dans un exercice.
    Par contre ça résout l'exercice 1 fastoche avec le code du 2.

    Pour comprendre, je considère les problèmes remis à plat, donc une seule chaîne de caractères et on navigue en connaissant la largeur et la hauteur.
    Et je stocke ces problèmes dans une dictionnaire avec le hash() en clé. Donc j'appelle mes fonctions avec la valeur de platform qui est un hash(), donc un entier.
    Ça veut dire que chaque fonction qui fait glisser les pierres prend en entrée un unique entier, et sort un autre entier.
    Autant dire que le cache il pèse pas lourd, il est optimisé, il est efficace (et il est inutile).

    Allez, souffrez lecteurs :

    from sys import stdin
from functools import cache

def renumerate(sequence, start=None):
  """Reversed enumerate() function
  Can work with generators only if start is given
  """
  n = start
  if start is None:
    n = len(sequence) - 1
  for elem in sequence[::-1]:
    yield n, elem
    n -= 1

class Platform:
  def __init__(self, problem):
    self.width = len(problem[0])
    self.height = len(problem)
    self.size = self.width * self.height
    self.hashes = {}
    self.platform = self.hash("".join(problem))
    # self.print()

  def print(self, platform=None):
    problem = self.hashes[platform or self.platform]
    for y in range(self.height):
      print("|", problem[self.height * y:self.height * (y + 1)])

  def hash(self, problem):
    h = hash(problem)
    if h not in self.hashes:
      self.hashes[h] = problem
    return h

  def get_load(self, platform):
    problem = self.hashes[platform]
    total = [0] * self.width
    for pos, rock in enumerate(problem):
      if rock == "O":
        total[pos % self.width] += self.height - pos // self.width
    return sum(total)

  def turn(self, platform=None):
    @cache
    def _turn(platform):
      platform = self.push_north(platform)
      platform = self.push_west(platform)
      platform = self.push_south(platform)
      platform = self.push_east(platform)
      return platform
    return _turn(platform or self.platform)

  def push_north(self, platform=None):
    @cache
    def _north(platform):
      problem = list(self.hashes[platform])
      empty = list(range(self.width))
      for pos, rock in enumerate(problem):
        x = pos % self.width
        if rock == "O":
          if empty[x] != pos:
            problem[pos] = "."
            problem[empty[x]] = "O"
          empty[x] += self.width
        elif rock == "#":
          empty[x] = pos + self.width
      return self.hash("".join(problem))
    return _north(platform or self.platform)

  def push_south(self, platform=None):
    @cache
    def _south(platform):
      problem = list(self.hashes[platform])
      empty = [self.size - self.width + i for i in range(self.width)]
      for pos, rock in renumerate(problem, self.size - 1):
        x = pos % self.width
        if rock == "O":
          if empty[x] != pos:
            problem[pos] = "."
            problem[empty[x]] = "O"
          empty[x] -= self.width
        elif rock == "#":
          empty[x] = pos - self.width
      return self.hash("".join(problem))
    return _south(platform or self.platform)

  def push_west(self, platform=None):
    @cache
    def _west(platform):
      problem = list(self.hashes[platform])
      empty = [self.height * i for i in range(self.height)]
      for pos, rock in enumerate(problem):
        y = pos // self.width
        if rock == "O":
          if empty[y] != pos:
            problem[pos] = "."
            problem[empty[y]] = "O"
          empty[y] += 1
        elif rock == "#":
          empty[y] = pos + 1
      return self.hash("".join(problem))
    return _west(platform or self.platform)

  def push_east(self, platform=None):
    @cache
    def _east(platform):
      problem = list(self.hashes[platform])
      empty = [self.height * (i + 1) - 1 for i in range(self.height)]
      for pos, rock in renumerate(problem, self.size - 1):
        y = pos // self.width
        if rock == "O":
          if empty[y] != pos:
            problem[pos] = "."
            problem[empty[y]] = "O"
          empty[y] -= 1
        elif rock == "#":
          empty[y] = pos - 1
      return self.hash("".join(problem))
    return _east(platform or self.platform)


resolution = Platform(data)
# Exercice 1 tout facile
print(resolution.get_load(resolution.push_north()))
# Exercice 2
state = resolution.platform
states = [state]
while True:
  state = resolution.turn(state)
  if state in states:
    skip = states.index(state)
    loop = len(states) - skip
    print(f"looping in {loop} cycles after {skip} cycles")
    break
  states.append(state)
state = states[skip + (1000000000 - skip) % loop]
print(resolution.get_load(state))

    Bilan : 1,6 secondes et 15Mo de RAM, avec ou sans le cache, c'est pareil, et pas de mauvaise surprise, quand ça a validé les données de test, ça a validé le problème complet.

    • Yth.

    PS: pour faire plaisir à Tanguy, mon premier jet pour passer l'étape 1 modélisait avec un Enum Rock.RND/SQR/NOP, et ma fonction, unique, était un mix de mes méthodes north et load, tout en une passe, rapide, efficace, pour aller vite fait à l'étape 2.

    PPS: je suis resté sur des str au bout du compte, parce qu'une list c'est unhashable, donc je pouvais pas utiliser hash() pour optimiser mes caches (inutiles). Je suppose qu'en revenant à un truc qui fait moins d'explosion de str en list et vice-versa ça doit pouvoir marcher, voire en utilisant un tuple plutôt qu'une liste pour le cache, et une transformation tuple->list->roule_tes_pierres->tuple pour conserver le cache.

    • [^] # Re: Impossible de se cacher, va falloir tourner.

      Posté par  . Évalué à 1.

      Tu as eu de la chance que le 1er nombre de la liste soit unique dans la boucle sinon tu avais les mauvaises valeurs…

      Par exemple:

      1 2 3 10 5 6 11 10 11 12 13 14 10 11 12 13 14 10 11 12 13 14
      Les 2e 10 ou 11 sont bien déjà dans la liste states mais c'est pas une boucle !

      • [^] # Re: Impossible de se cacher, va falloir tourner.

        Posté par  (Mastodon) . Évalué à 3. Dernière modification le 14 décembre 2023 à 13:56.

        Non, non, j'enregistre un état après un tour complet nord, ouest sud, et est.
        Si on retombe sur un état rigoureusement identique, alors on a forcément bouclé, on ne conserve pas d'information d'un tour à l'autre, un tour de manivelle ne dépend que de l'état des pierres-qui-roulent au début du tour.

        Ça veut dire qu'après 10 on a forcément 11.

        Ya pas possible de se tromper là…

        • Yth.

    • [^] # Re: Impossible de se cacher, va falloir tourner.

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

      Par contre, on peut noter qu'ici PyPy fait descendre de 1,6s à 0,5s, ce qui n'est pas négligeable du tout, trois fois plus rapide, pas mal.
      Avec ou sans cache, on a bien vu qu'il ne servait rigoureusement à rien de toute façon, pas la peine de ressasser hein, j'ai compris.

      En modélisant avec un Enum Rock, et en utilisant un tuple au lieu d'une str pour gérer les données (on converti en liste avant de déplacer les pierres puis on remet en tuple, et on calcule un hash d'un tuple de Rock), c'est affreux.
      On passe à 4s en python !
      Mais on reste à 0,6s en PyPy.

      Conclusion: PyPy ne déteste pas la modélisation.

      Avec ou sans cache, puisque je vous dis qu'il ne sert absolument à rien, rhaaa !

      Et donc après m'être bien pris la tête à virer mes histoires de hashes, tout le cache et essayer de simplifier, on réalise que de toute façon on doit passer par des enregistrements d'états immuables (on ne peut pas states.append(mon état mutable), parce que ça stocke la référence, donc l'état stocké est modifié), et donc permettre à python de calculer un hash, par exemple en stockant un tuple().
      Et ça sert à rien, on n'y gagne rien, mon approche initiale était finalement la plus optimisée : rester sur des string, et les transformer en liste pour les modifier puis les recoller à la fin, est plus efficace.
      Sauf avec PyPy qui s'en fout, les hashes de str, tuple, les conversions dans un sens, l'autre, retour etc, c'est pareil pour lui, ça prend rien de temps, donc toutes les approches sont équivalentes.

      • Yth.

  • # Ca boucle !

    Posté par  . Évalué à 1.

    Salut,
    Pas trop de soucis ce matin avec celui la, mais j'ai triché un peu (bien que le reglement n'impose pas de n'utiliser qu'un prog et n'interdit pas d'utiliser une fichier texte contenant des valeurs :) ).

    Pour le 1er, j'ai pensé à tourner la grille sur la gauche pour prendre des lignes plutot que des colonnes: ca permet d'utiliser directement des for l in lines sans trop se prendre la tête avec les colonnes…
    Tiens, je vais me préparer un itérateur pour parcourir par colonne…
    Ensuite, je n'ai pas effectuer les déplacements de 'O' mais directement effectué le calcul. Je savais que ca ne tiendrait pas pour le 2e mais bon, au moins j'avais un 1er résultat.

    Et effectivement, au 2e, il fallait les bouger et pas seulement calculer la valeur.
    Je me suis douter ensuite que ca allait boucler après un certain temps.
    J'ai donc calculer 300 cycles et regarder les valeurs de chaque tableau, à la main (sans code) et j'ai ensuite donné la bonne réponse (mouais…).
    Il me reste à coder la recherche d'une série dans une liste maintenant !

  • # Solution en Haskell

    Posté par  . Évalué à 1. Dernière modification le 14 décembre 2023 à 13:20.

    Problème intéressant, il me rappelle le jour 17 de 2022.
    J'ai écrit une fonction tilt qui fait tomber les briques vers l'ouest.
    Pour cela, pour chaque ligne, je split la ligne selon # et pour chaque morceau du split, je sépare les O et les "." et je reconcatène tout en mettant les O d'abord et les "." ensuite.

    Ensuite j'ai une fonction tiltInDirection qui se ramène à tilt en faisant des rotate et des reverse selon le cas de figure.

    Pour la partie 2, je génère une suite infinie cyclique de North, West, South, East
    et à partir de celle ci, je génère une liste infinie des différentes configurations après avoir effectué les tilts dans la direction donnée.
    Dans cette liste, je cherche les indices x et y de la même configuration (fonction findRepetition) et la configuration qui nous intéresse est celle à l'indice x + (1000000000 - x) mod (y - x).

    La partie 2 tourne en 600ms. Pas très satisfait mais ça reste raisonnable.

    Voici le code

    import           AOC.Prelude hiding (empty)
import           Data.List ((!!))
import           AOC (aoc)
import qualified Data.HashMap.Strict as Map
import           AOC.Parser (Parser, sepEndBy1, eol, some)
import           AOC.Util (flattenWithIndex, splitWhen)

data Rock = Empty | Round | Cube deriving (Eq, Enum)
data Direction = West | East | North | South
type Grid = [[Rock]]

instance Hashable Rock where
    hashWithSalt s rock = s `hashWithSalt` fromEnum rock

parser :: Parser Grid
parser = some rock `sepEndBy1` eol where
    rock = Empty <$ "." <|> Round <$ "O" <|> Cube <$ "#"

-- tilt to West
tilt :: Grid -> Grid
tilt = map perRow where
    perRow = intercalate [Cube] . map go . splitWhen (==Cube)
    go xs = rounded ++ empty where (rounded, empty) = partition (==Round) xs

tiltInDirection :: Direction -> Grid -> Grid
tiltInDirection = \case
    West -> tilt
    East -> map reverse . tilt . map reverse
    North -> transpose . tilt . transpose
    South -> reverse . transpose . tilt . transpose . reverse

-- return the first two indices of the same element in a infinite list of elements
findRepetition :: Hashable a => [a] -> (Int, Int)
findRepetition = go Map.empty . zip [0..] where
    go m ((i, x) : xs) =
        case m Map.!? x of
            Just j -> (j, i)
            Nothing -> go (Map.insert x i m) xs
    go _ [] = error "findRepetition: not an infinite list"

-- compute the laod of a grid
load :: Grid -> Int
load grid = sum . map score $ flattenWithIndex grid where
    score (i, _, Round) = len - i
    score _ = 0
    len = length grid

part1 :: Grid -> Int
part1 = load . tiltInDirection North

part2 :: Grid -> Int
part2 grid = load (grids !! y') where 
    (x, y) = findRepetition grids
    y' = x + (1000000000 - x) `mod` (y-x)
    grids = scanl' (flip tiltInDirection) grid directions
    directions = cycle [North, West, South, East]

solve :: Text -> IO ()
solve = aoc parser part1 part2

    • [^] # Re: Solution en Haskell

      Posté par  . Évalué à 1.

      Je viens de me rendre compte que mon code n'était pas correct tout le temps même s'il marchait bien sur l'input. En effet, il se pourrait que deux configurations identiques apparaissent mais pas dans la même position dans le cycle des directions.

      Par exemple, une configuration alors que la prochaine instruction est d'aller vers l'ouest puis la même configuration alors que la prochaine instruction est d'aller au nord.

      Du coup, je l'ai corrigé (il y a juste à changer la fonction part2).

      Ca ne change pas le temps d'exécution.

      part2 :: Grid -> Int
part2 grid = load (grids !! y') where 
    (x, y) = findRepetition grids
    y' = x + (1000000000 - x) `mod` (y-x)
    grids = iterate' cycle grid
    cycle = tiltInDirection East
          . tiltInDirection South
          . tiltInDirection West
          . tiltInDirection North

      • [^] # Re: Solution en Haskell

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

        Ouais, faut enregistrer les états après un tour complet pour retourner dans une situation équivalente.
        Un tour complet ne dépend que de l'état initial, alors qu'un déplacement c'est l'état initial puis la direction.
        Ça marche mais faut enregistrer les deux infos, et comparer les deux infos.

        • Yth.

      • [^] # Re: Solution en Haskell

        Posté par  . Évalué à 1.

        En se rendant compte qu'un cycle est un enchainement tilt, rotation, tilt, rotation, tilt, rotation, tilt, rotation, on peut écrire le code plus simplement.

        part2 :: Grid -> Int
part2 grid = load . transpose $ grids !! y' where 
    (x, y) = findRepetition grids
    y' = x + (1000000000 - x) `mod` (y-x)
    grids = iterate' cycle (transpose grid)
    step = reverse . transpose . tilt
    cycle = step . step . step . step

        Et du coup, la fonction tiltInDirection ne sert plus à rien.
        On gagne même un peu en temps d'exécution: 400ms.

        • [^] # Re: Solution en Haskell

          Posté par  . Évalué à 1. Dernière modification le 15 décembre 2023 à 17:25.

          J'ai réécrit ma fonction tilt de manière plus maligne en m'inspirant de la solution d'une autre personne.

          tilt :: Grid -> Grid
tilt = map (go 0) where
    go n = \case
        (Empty:xs) -> go (n+1) xs
        (Round:xs) -> Round : go n xs
        (Cube:xs) -> replicate n Empty ++ Cube : go 0 xs
        _        -> replicate n Empty

          Maintenant, le temps d'exécution est passé à 200ms.

  • # Solution en Java 403ms

    Posté par  . Évalué à 1.

    Ci-dessous ma soluce en Java pour la partie 2. Elle met 403ms une fois Java lancé (c'est comme un bon diesel Java). Et encore, j'ai une vilaine boucle qui compte jusqu'à avant le milliard.
    J'optimise en utilisant des objets mutable & un bon vieux cache basé sur un Record.

    package aoc2023;

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

public class Aoc2023s14v2 {     
    enum Type {
        SPHERE,
        ROCK;
    }

    public static class Point {
        int x;
        int y;
        Type type;

        public Point(int x, int y, Type type) {
            this.x= x;
            this.y=y;
            this.type = type;
        }
    }

    public static class World {
        int width;
        int height;

        Point[][] map;
        List<Point> spheres = new ArrayList<>();


        public World(List<String> rows) {
            map = new Point[rows.size()][rows.get(0).length()];
            for(int y=0;y < rows.size();y++) {
                addRow(rows.get(y), y);
            }
            this.height = rows.size();
        }

        public void addRow(String row, int y) {
            this.width = row.length();

            for(int x=0;x < row.length();x++) {
                Point p = null;
                if(row.charAt(x) == 'O') {
                    p =new Point(x, y, Type.SPHERE);
                    spheres.add(p);
                } else if(row.charAt(x) == '#') {
                    p = new Point(x, y, Type.ROCK);
                }

                map[y][x] =p;
            }
        }

        public boolean isFree(int x, int y) {
            if(x < 0 || x >= width || y < 0 || y >= height ) {
                return false;
            }

            return this.map[y][x] == null;          
        }

        public Point find(int x, int y) {
            if(x < 0 || x >= width || y < 0 || y >= height ) {
                return null;
            }
            return this.map[y][x];      
        }

        public void move(int dx, int dy) {
            boolean change = false;
            do {
                change =false;
                for(Point p : spheres) {
                    if(isFree(p.x + dx, p.y +dy)) {
                        map[p.y][p.x] = null;
                        p.x += dx;
                        p.y += dy;
                        map[p.y][p.x] = p;
                        change =true;
                    }
                }               
            } while(change);            
        }

        public int computeWeight() {
            int sum = 0;
            for(Point sphere :spheres) {
                sum += (height-sphere.y);
            }
            return sum;
        }


        public List<String> toRows() {
            List<String> rows = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            for(int y=0;y < height;y++) {
                sb.setLength(0);
                for(int x=0;x < width;x++) {
                    Point p = find(x, y);
                    if(p == null) {
                        sb.append('.');
                    } else if(p.type == Type.ROCK) {
                        sb.append('#');
                    } else {
                        sb.append('O');
                    }
                }
                rows.add(sb.toString());
            }
            return rows;
        }
    }

    public static void main(String[] args) {        
        long startMs = System.currentTimeMillis();          
        try (Scanner in = new Scanner(Aoc2023s14v2.class.getResourceAsStream("res/t14.txt"))) {
            List<String> rows = new ArrayList<>();
            while (in.hasNext()) {
                rows.add(in.nextLine());
            }

            Integer startCycle = null;
            Integer cycleCount = null;
            World world = null;
            final long LOOPS = 1_000_000_000L;
            for(long x = 0 ;x < LOOPS;x++) {
                CacheKey current = new CacheKey(rows);
                if(keys[current.cacheIndex()] != null && keys[current.cacheIndex()].equals(current)) {
                    if(startCycle == null) {
                        startCycle = current.cacheIndex();
                        cycleCount = 0;
                    } else if(startCycle == current.cacheIndex()) {
                        System.out.println("Make cycle: " + cycleCount);
                        // Could be more elegant :)
                        while(x < (LOOPS-cycleCount)) {
                            x += (cycleCount+1);
                        }
                    } else {
                        cycleCount++;
                    }
                    world = cache_worlds[current.cacheIndex()];
                } else {
                    world = computeWorld(rows);
                    keys[current.cacheIndex()] = current;
                    cache_worlds[current.cacheIndex()] = world;
                    System.out.println("miss " + x);

                    startCycle = null;
                    cycleCount = null;
                }
                rows = world.toRows();              
            }

            System.out.println(world.computeWeight());
        }   
        System.out.println((System.currentTimeMillis() - startMs) + "ms");
    }

    private static World computeWorld(List<String> rows) {
        World world;
        world = new World(rows);
        world.move(0, -1);
        world.move(-1, 0);
        world.move(0, 1);
        world.move(1, 0);
        return world;
    }

    public static record CacheKey(List<String> rows) {

        public int cacheIndex() {
            return Math.abs(this.hashCode()) % CACHE_SIZE;
        }
    }

    public static final int CACHE_SIZE = 1_000_000;
    public static  CacheKey[] keys = new CacheKey[CACHE_SIZE];
    public static  World[] cache_worlds = new World[CACHE_SIZE];

}

  • # Pourquoi ça cycle

    Posté par  (site web personnel) . Évalué à 2.

    En voyant la partie 2, j'ai immédiatement pensé deux choses :

    1. il faudrait que j'optimise un minimum ma fonction de cycle d'essorage, parce qu'on va l'appeler un certain nombre de fois, même si ce ne sera pas un milliard de fois ;
    2. je vais finir par tomber sur un cycle de cycle en effet.

    Ce dernier point est une certitude absolue. Pourquoi donc ? Parce qu'il y a 100 ligne et 100 colonnes, donc moins de 100 × 100 = 10.000 positions possibles des pierres qui roulent. En fait, bien moins que ça, parce que les positions occupées par les pierres qui ne roulent pas ne sont pas utilisables, et que seules les dispositions stables par le nord – on se comprend – sont admissibles.

    Bref, en moins de 10.000 cycles je suis sûr d'avoir au moins deux fois la même disposition. Et retomber sur une disposition déjà vue, c'est aussi retomber sur la disposition suivante au cycle d'après, etc.

    Chez moi ça cycle en 64 cycles.

    Le code :

    from collections.abc import Iterable, Sequence
from typing import Optional, Self

import enum
import io
import itertools

import numpy as np
import numpy.typing as npt

import aoc


class Tile(enum.Enum):
    EMPTY = '.'
    CUBE  = '#'
    ROUND = 'O'

    def __str__(self) -> str:
        if self is self.EMPTY:
            return ' '
        if self is self.CUBE:
            return '■'
        if self is self.ROUND:
            return '○'
        assert False


class Platform:
    def __init__(self, array: Sequence[Sequence[Tile]]):
        self.matrix: npt.NDArray[np.object_] = np.array(array)
        self.ly, self.lx = self.matrix.shape
        self.spaces_horiz: list[list[range]] = []
        self.spaces_vert: list[list[range]] = []
        for y in range(self.ly):
            self.spaces_horiz.append([])
            xs = [-1] + [x for x in range(self.lx) if self.matrix[y, x] is Tile.CUBE] + [self.lx]
            for x1, x2 in itertools.pairwise(xs):
                if x2 - x1 > 1:
                    self.spaces_horiz[-1].append(range(x1 + 1, x2))
        for x in range(self.lx):
            self.spaces_vert.append([])
            ys = [-1] + [y for y in range(self.ly) if self.matrix[y, x] is Tile.CUBE] + [self.ly]
            for y1, y2 in itertools.pairwise(ys):
                if y2 - y1 > 1:
                    self.spaces_vert[-1].append(range(y1 + 1, y2))

    @classmethod
    def import_lines(cls, lines: Iterable[str]) -> Self:
        array = []
        for line in lines:
            array.append([Tile(char) for char in line.rstrip()])
        return cls(array)

    def __str__(self) -> str:
        s = io.StringIO()
        for line in self.matrix:
            for tile in line:
                s.write(str(tile))
            s.write('\n')
        return s.getvalue()

    def positions(self):
        return tuple((y, x) for (y, x), value in np.ndenumerate(self.matrix) if value is Tile.ROUND)

    def tilt_north(self) -> None:
        for x in range(self.lx):
            column = self.matrix[:, x]
            for space in self.spaces_vert[x]:
                rounds = 0
                for y in space:
                    if column[y] is Tile.ROUND:
                        rounds += 1
                        column[y] = Tile.EMPTY
                for y in range(space.start, space.start + rounds):
                    column[y] = Tile.ROUND

    def tilt_south(self) -> None:
        for x in range(self.lx):
            column = self.matrix[:, x]
            for space in self.spaces_vert[x]:
                rounds = 0
                for y in space:
                    if column[y] is Tile.ROUND:
                        rounds += 1
                        column[y] = Tile.EMPTY
                for y in range(space.stop - 1, space.stop - 1 - rounds, -1):
                    column[y] = Tile.ROUND

    def tilt_west(self) -> None:
        for y in range(self.ly):
            row = self.matrix[y]
            for space in self.spaces_horiz[y]:
                rounds = 0
                for x in space:
                    if row[x] is Tile.ROUND:
                        rounds += 1
                        row[x] = Tile.EMPTY
                for x in range(space.start, space.start + rounds):
                    row[x] = Tile.ROUND

    def tilt_east(self) -> None:
        for y in range(self.ly):
            row = self.matrix[y]
            for space in self.spaces_horiz[y]:
                rounds = 0
                for x in space:
                    if row[x] is Tile.ROUND:
                        rounds += 1
                        row[x] = Tile.EMPTY
                for x in range(space.stop - 1, space.stop - 1 - rounds, -1):
                    row[x] = Tile.ROUND

    def cycle(self) -> None:
        self.tilt_north()
        self.tilt_west()
        self.tilt_south()
        self.tilt_east()

    def load_north(self) -> int:
        load = 0
        for (y, x), tile in np.ndenumerate(self.matrix):
            if tile is Tile.ROUND:
                load += self.ly - y
        return load


def part1(lines: aoc.Data) -> int:
    """Solve puzzle part 1: determine the sum of stuff"""
    platform = Platform.import_lines(lines)
    platform.tilt_north()
    return platform.load_north()


def part2(lines: aoc.Data) -> int:
    """Solve puzzle part 2: determine the sum of staff"""
    platform = Platform.import_lines(lines)
    position_cycles: dict[Tuple[Tuple[int]], int] = {}
    target = 1000000000
    first: Optional[int] = None
    for cycle in range(platform.ly * platform.ly):
        positions = platform.positions()
        if positions in position_cycles:
            first = position_cycles[positions]
            break
        position_cycles[positions] = cycle
        platform.cycle()
    else:
        raise ValueError("cannot find a cycle‽")
    assert first is not None
    # `first` is the number of a cycle when, /before/ cycling, the positions
    # were the same as now.
    # `cycle` is the number of current cycle, /before/ cycling.
    loop = cycle - first
    remaining = target - first
    remaining %= loop
    for _ in range(remaining):
        platform.cycle()
    return platform.load_north()

    • [^] # Re: Pourquoi ça cycle

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

      Hmm, on a moins de 100x100 possibilités pour chaque pierre-qui-roule (chez moi c'est 8459).
      Mais comme on a quelques 2000 pierres-qui-roulent (2011 dans mes données), ça fait un paquet de combinaisons possibles.
      Chez moi ça a l'air d'être de l'ordre de 5e7784, soit… trop.

      Mais je pense que ton raisonnement sur pourquoi on en est absolument sûr, est faux.

      Perso, je n'ai qu'une double forte suspicion : ça à l'air de boucler à vue de nez, et si ça boucle pas on va flinguer notre CPU, or il y a une solution raisonnable en temps CPU, selon les principes de l'AoC.

      • Yth.

      • [^] # Re: Pourquoi ça cycle

        Posté par  (site web personnel) . Évalué à 3.

        En effet. Mais c'est moins que 100×100 pour chaque galet, tout simplement parce que peu importe la position de chaque galet, ils se ressemblent tous au point d'être interchangeables. C'est plutôt la combinaison de 2.000 parmi 10.000 qui majore le nombre de possibilités. Ça fait quand même vachement beaucoup trop.

        • [^] # Re: Pourquoi ça cycle

          Posté par  (Mastodon) . Évalué à 2. Dernière modification le 15 décembre 2023 à 15:44.

          J'ai en effet oublié un terme dans mon calcul de combinaison, qui m'amène plutôt vers les 7e2010.

          • Yth ^ ^

  • # python en 44 LoC, 110ms et 10MB RAM

    Posté par  . Évalué à 2. Dernière modification le 16 décembre 2023 à 02:22. 

    import sys

I = sys.stdin.read().splitlines()
G = [list(l) for l in I]
R = len(G)
C = len(G[0])

def rotate(G, F):
  for r in range(R):
    for c in range(C):
      F[c][R-1-r] = G[r][c]

def tilt(G):
    for x in range(C):
        for y in range(R):
            if G[y][x] == "O":
                for j in range(y-1,0-1,-1):
                    if G[j][x] == '.':
                        G[j][x] = "O"
                        G[j+1][x] = "."
                    else:
                        break

score = lambda: sum((R-y)*row.count('O') for y,row in enumerate(G))

cache = {}
F = [['?' for _ in range(C)] for _ in range(R)]  # pre-allocate saves 10% time (no GC)

end = 1_000_000_000
i = 0
while i<end:
    i += 1
    for j in range(4):
        tilt(G)
        if i == 1 and j == 0: print(score())  # part 1
        rotate(G, F); F, G = G, F
    h = ''.join(''.join(row) for row in G)
    if h in cache:
        period = i-cache[h]
        skip = (end-i) // period
        i += skip * period
    cache[h] = i

print(score())

  • # Python

    Posté par  . Évalué à 1.

    Voici ma solution, elle est rapide, mais elle m'a pris beaucoup de temps pour une et une seule raison : dans la première partie, j'ai codé une fonction qui calcule le poids si on bougeait les pierres vers le nord (en fait l'est puisque j'ai renversé le puzzle, je préfère les lignes aux colonnes).
    Dans ma deuxième partie, je me dis ; « Réutilisons gaiement cette fonction après avoir effectivement fait rouler les pierres ! » 😔

    #!/bin/python3

from functools import cache

def rotate90(lines):
    columns = [""]*len(lines[0])
    for i in range(len(lines[0])):
        columns[i] = "".join(reversed([ _[i] for _ in lines ]))
    return columns

@cache
def getWeight(rang,nb):
    return sum(range(rang-nb+1,rang+1))

@cache
def getLoad(line):
    count = 0
    total = 0
    for i, _ in enumerate(line):
        if _ == "#":
            total += getWeight(i,count)
            count = 0
        elif _ == "O":
            count += 1
    total += getWeight(len(line),count)
    return total

@cache
def getActualLoad(line):
    total = 0
    for i, _ in enumerate(line):
        if _ == "O":
            total += i+1
    return total

@cache
def fallLine(line):
    count = 0
    result = ""
    for i, _ in enumerate(line):
        if _ == "#":
            while len(result) < i - count:
                result += "."
            result += "O"*count + "#"
            count = 0
        elif _ == "O":
            count += 1
    while len(result) < len(line) - count :
        result += "."
    result += "O"*count
    return result

def cycle(puzzle,step):
    if step == 0:
        return puzzle, sum([getActualLoad(_) for _ in rotate90(puzzle)])
    return cycle([fallLine(_) for _ in rotate90(puzzle)],step-1)

def solve1(puzzle,testing=False):
    s=0
    s = sum([getLoad(_) for _ in rotate90(puzzle)])
    if testing:
        print(s)
    return s

def solve2(puzzle,testing=False):
    s = 0
    pastresult = []
    now = puzzle
    pastresult.append(now)
    i=1
    while True:
        now, r = cycle(now,4)
        if now in pastresult:
            i = pastresult.index(now)
            tosum = ((1000000000 - i ) % (len(pastresult) - i)) + i
            s = sum([getActualLoad(_) for _ in rotate90(pastresult[tosum])])
            break
        pastresult.append(now)
        i+= 1
    if testing:
        print(s)
    return s

    L'informatique n'est pas une science exacte, on n'est jamais à l'abri d'un succès

Suivre le flux des commentaires

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