Forum Programmation.autre Avent du Code, jour 17

Post√©¬†par¬† (site web personnel) . Licence CC¬†By‚ÄĎSA.
√Čtiquettes¬†:
4
17
déc.
2022

Suite de l'Avent du Code, jour 17.

En fait, avec nos √©l√©phants de compagnie, nous ne sommes pas perdus dans n'importe quel volcan : c'est la console de jeu de Vulcain, qui a commenc√© une partie de Tetris avec des blocs de rocher et des jets de gaz br√Ľlants dans la caverne o√Ļ nous nous trouvons.

Mais pas de panique, la meilleure chose à faire, c'est de prendre le temps de bien modéliser ça, et tout va bien se passer.

Pas encore de solution de mon c√īt√©, √ßa attendra lundi je pense.

  • # Tetris style

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†3.

    J'ai bien galéré encore sur celui-ci ~ 4h.

    La première partie est relativement simple. Je joue à Tetris dans un tableau de char.

    La deuxième partie est galère car si j'utilise la méthode de la première partie ,avec un clear du tableau quand c'est possible après une ligne pleine.
    Il me fallait ~20j de calcul pour approcher 1000000000000L piece.

    J'ai donc identifié quand le pattern d'empilement se répète. De cette manière, j'ai rapidement le test unit de la 2eme partie qui marchait.
    pour trouver 1514285714288.

    Seulement, quand j'appliquais la méthode sur mon input, çà ne marchait pas.
    Je suis revenu sur un jeu plus petite et j'ai comparé la première méthode et la deuxième méthode avec le raccourcis quand je détecte la répétition.
    J'ai constaté qu'il me manquait 9 à chaque application de la répétition.

    En ajoutant, le nombre de répétition fois 9 ,j'ai obtenu le résultat attendu.

    • [^] # Re: Tetris style

      Post√©¬†par¬† . √Čvalu√©¬†√†¬†3.

      Je viens de le finir, et il m'a fallu plusieurs heures aussi.

      Ma premiere idee d'optimisation apres la partie 1 c'etait d'utiliser @functools.lru_cache pour gagner du temps au cas ou certains des inputs se repetaient. La suite de 'jets' est tres longue, mais sur une quantite si enorme d'essais j'avais un peu d'espoir.
      Le cache aidait, mais pas suffisamment pour avoir une reponse suffisamment rapide. Je voulais voir a quel point le cache etait utilise donc j'ai trouve que lru_cache ajoute une method cache_info() sur la method cachee, qui renvoit les statistiques de cache hit/cache miss.
      Et je me suis rendu compte que le cache etait systematiquement utilise apres la 1927e pierre, indiquant la presence d'une boucle.
      J'ai aussi perdu du temps avec le fait que le tout premier cycle donnait une hauteur legerement au dessus des suivantes, mais j'ai finalement trouve.

      Par contre je cale toujours sur la deuxieme partie du jour 16, je ne me suis pas encore resolu a regarder l'entree de forum d'hier, mais je crois que je vais m'y resoudre.

      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

      • [^] # Re: Tetris style

        Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4.

        Je n'ai pas encore commencé, mais vu l'énoncé de la première partie, je dirais que l'incrément de hauteur doit se répéter au bout du PPCM du nombre de formes et du nombre de d'instructions de direction du vent.

        Avec la première série de tant de blocs qui doit monter un petit peu plus haut puisqu'elle est posée sur un sol plat et non sur une tour qui sommet irrégulier.

        • [^] # Re: Tetris style

          Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2. Derni√®re modification le 17 d√©cembre 2022 √† 19:23.

          C'est plus compliqué que ça a priori.
          Je n'ai pas de méthode de calcul du cycle, je le mesure en prenant des bornes assez grandes.

          On a plusieurs problèmes :

          • Trouver en combien de blocs on cycle, c'est √† dire qu'en partant de l'ajout du premier bloc avec la premi√®re instruction, on revient √† l'ajout du premier bloc avec la premi√®re instruction. Dans mon cas c'est en 1705 blocs, dans les donn√©es de test c'est en 35 blocs.
          • Constater que le d√©but de partie ne correspond pas du tout √† un cycle r√©p√©titif, la situation est particuli√®re, et le premier cycle commence‚Ķ plus tard. Sur mes donn√©es il faut passer quelque chose entre 200 et 300 blocs pour d√©marrer le premier cycle.
          • mesurer la hauteur ajout√©e par un cycle complet normal en milieu de tour (donc pas le d√©but, pas la fin).
          • Et mesurer la fin, en haut, soit mille milliards modulo le cycle.

          En pratique, il suffit de faire une tour de deux cycles plus la fin, on a un cycle normal et complet au milieu, donc on sait qu'on peut en rajouter autant qu'on veut, ça agrandira linéairement.

          Le principe c'est ça, avec la fonction simulation() qui fait une simulation (ouais ouais ! Promis !), en paramètres les data, et le nombre de blocs à faire tomber. Elle retourne la hauteur finale. L'exercice 1 c'est l'appel avec 2022 blocs, et voilà.

          Cas particulier, si je fournis un 3√® param√®tre, je laisse passer ce nombre de blocs, et je prend l'√©tat (n¬į de bloc, n¬į d'instruction), et d√®s que je retrouve le m√™me √©tat, j'ai mon cycle, je sors la valeur¬†!
          Après on mesure, on calcule, ça marche.

          data = sys.stdin.read().strip()
          h1 = simulation(data, 2022)
          print(f"Height of 2022 blocks: {h1}")
          
          # Finding cycle length, knowing this limits would be enough
          cycle = simulation(data, 1000000, 2000)
          repeat, remain = divmod(1000000000000, cycle)
          # Measuring 1 cycle, and 2 cycles, to determine what is the height added by one cycle in the middle.
          h1c = simulation(data, cycle)
          h2c = simulation(data, cycle * 2)
          # All extremities with full cycle in the middle
          # We can add any number of full cycles in the middle of this simulation, they'll add a fixed height.
          hr = simulation(data, cycle * 2 + remain)
          total = (h2c - h1c) * (repeat - 2) + hr
          print(f"Cycle of {cycle} blocks, 1 Cycle {h1c}, 2 Cycles {h2c}, Cycle height {h2c-h1c}, Extremities height {hr}")
          print(f"Total Height = {total}")
          • Yth, comme pr√©vu le samedi, j'ai moins de temps, commenc√© tard, mais c'√©tait pas trop long‚Ķ
          • [^] # Re: Tetris style

            Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

            Sachant que j'ai deux valeurs en dur pour la calcul du cycle :
            1 million d'itérations max, et 2000 blocs à laisser passer.
            Je n'ai aucune idée de comment déterminer des valeurs propres a priori, la boucle sort à la 3705è itération, donc j'ai de la marge avec 1 million…

            Je sais que le cycle vaut 1705 et que je dois passer plus de 200, mais qu'à 300 ça passe, mais quid d'autres données ?
            Donc j'ai pris large, passer 2000 lignes, et avoir un cycle de moins de 1 millions de blocs, mais en vrai, j'en sais rien.
            Pas d'algo en t√™te pour ces valeur, ou m√™me de calcul de maximum o√Ļ je peux affirmer qu'avec ces valeurs l√† j'aurais forc√©ment une r√©ponse.

            • Yth.
            • [^] # Re: Tetris style

              Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

              Ah !
              J'ai trouvé comment tout résoudre (ex 1 et 2) avec la simulation d'une seule tour, d'environ 3600 de haut pour mes données.
              Je valide demain, ou lundi selon les exos de demain…

              • Yth, dodo.
  • # Le Jour du Tetris

    Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

    Suite à mes messages précédents, j'ai avancé dans la résolution efficace du problème, mais en réalité pas terminé.

    Mon id√©e c'√©tait qu'on cycle d√®s qu'on revient √† un couple (n¬įblock, n¬įinstruction) qui est d√©j√† pass√©, n¬įblock c'est de 1 √† 5, et n¬įinstruction de 0 √† 10091 chez moi (taille des donn√©es en entr√©e), et 0 √† 39 pour les donn√©es de test.
    Comme si ce seul état était déterministe, et que l'état du terrain n'entrait pas en ligne de compte.
    Fourbement, ça suffit avec les données de test.

    L'idée donc c'est générer des blocs en enregistrant à chaque itération la hauteur, on en aura besoin de quelques-unes à la fin.
    Mais aussi on enregistre l'historique de l'√©tat (n¬įblock, n¬įinstruction) et l'it√©ration o√Ļ elle s'est produite.

    D√®s qu'on a le sentiment de cycler, c'est √† dire que notre √©tat est d√©j√† pass√©, on note l'it√©ration o√Ļ √ßa s'est produit la premi√®re fois, et la seconde.
    La différence c'est la durée de notre cycle.
    On a donc :

    • la base non cyclique¬†;
    • la dur√©e d'un cycle¬†;
    • la portion finale : (10**12-base)//cycle¬†;
    • le nombre de cycle complet √† inclure : (10**12-base)%cycle¬†;
    • la hauteur ajout√©e par un cycle hauteur[base+cycle] - hauteur[base]¬†;

    En données de test ça fait une base de 14 blocs, un cycle de 35, une hauteur par cycle de 53.

    Là on va simuler une tour complète en enlevant un maximum de cycles entiers au milieu, soit une hauteur de base + 2 cycles + fin, parce que avec un seul cycle on a des effets de bords.
    Et on continue si nécessaire jusqu'à une hauteur de 2022 pour le premier exercice.

    Là on a la hauteur à 2022, la hauteur ajoutée par un cycle, et la hauteur des extrémités avec deux cycles, on multiplie, on ajoute, on mélange à la bave de crapaud et hop, 1514285714288 sur les données de test.

    En données réelles j'ai ce résultat :
    Base de 39 blocs (?!?), cycle de 1725 (mais non c'est 1705 !!), et score final de 1555942028979 au lieu de 1553665689155.

    L'idée est bonne, mais la réalisation craint un peu, la supposition de départ est fausse, je rappelle :

    Comme si ce seul état était déterministe, et que l'état du terrain n'entrait pas en ligne de compte.

    En pratique, je stocke comme √©tat (n¬įblock, n¬įinstruction, repr√©sentation des X derni√®res lignes du terrain).
    Et avec 995 lignes, j'atteins la vraie stabilité, la vraie base non cyclique, même si 14 suffisent pour trouver le résultat avec mes données.

    Donc encore un peu de travail pour trouver vraiment le r√©sultat sans le conna√ģtre √† l'avance.

    Par contre une unique construction de tour de 4995 blocs !

    • Yth.
    • [^] # Re: Le Jour du Tetris

      Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

      Et la solution, enfin, nous appara√ģt avec un m√©lange de brutalit√© et de finesse.

      On reprend o√Ļ on en √©tait quand on croyait avoir raison : on vient de reboucler sur un √©tat (n¬įblock, n¬įinstruction).
      On compare avec un éventuel hash et snapshot enregistré pour cet état. La première fois qu'on boucle : on n'en a pas.
      Donc on prend une photo, c'est à dire l'état du terrain sur l'ensemble des lignes qui forment le cycle potentiel, et uniquement elles (en gros : str(board[-(hauteur actuelle - hauteur d'avant):]).
      On calcule le hash de cette photo pour comparer plus vite.
      On stocke ces deux valeurs dans deux tableaux.

      On continue, et maintenant on va revenir une troisième fois sur le même état ! Sauf que là on a un hash et une photo, on compare.
      Si c'est différent, on remplace et on poursuit.
      Si c'est identique, on valide en comparant la photo complète hein, faudrait pas planter sur une peu probable collision, et on a enfin trouvé un vrai cycle authentique et prouvé par une photo certifiée, avec signature !

      On reprend l'algo l√† o√Ļ on en √©tait.
      Et on constate que le premier vrai cycle commence au bloc 59 (!?!?! Mais… Pourquoi si peu ?), avec un cycle de 1705 blocs.
      On a trouvé deux cycles rigoureusement identiques, le premier de 60 à 1764 et le second de 1765 à 3469.
      Ils ont une hauteur de 2649 lignes, et on a donc comparé deux blocs de 2649 lignes de Tetris qui se suivent, et ils étaient rigoureusement identiques, et chacun des deux commence avec le même bloc à la même instruction. On cycle, c'est acquis.

      La zone début + 2 cycles + fin fait toujours 4995 blocs, on ne simule pas un bloc de plus.
      Et on a toujours un r√©sultat valide, mais l√† on en est s√Ľrs.

      • Yth, et ben, m'auras pris la t√™te celui-l√†¬†!

      PS : Je nettoie un peu le code et je poste ça…

  • # C√īt√© code

    Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

    Ici j'ai pas mal de modélisation de mon Block Tétris.
    Vu l'ampleur de la t√Ęche avant grosse r√©duction, cf messages pr√©c√©dents, je pr√©voyais de gagner le moindre micro-cycle d'horloge.
    Donc quand on déplace à gauche, on teste les blocs de gauche, à droite ceux de droite, en bas ceux du bas.

    La Simulation par contre devient complexe entre ma première version et la seconde…

    Le code en brut. C'est bourré d'itérateurs de partout

    import sys
    from collections import deque
    
    def left(block, board=None):
        block.left(board)
        return True
    
    def right(block, board=None):
        block.right(board)
        return True
    
    def down(block, board=None):
        return block.down(board)
    
    class Block:
        x, y, w, h, X = 2, 0, 0, 0, 6
        color = 1
        def __init__(self, *tiles, color=None):
            self.color = color or self.color
            self.all = tiles
            self.w = max(x for x, y in tiles) + 1
            self.h = max(y for x, y in tiles) + 1
            self.X = 7 - self.w
            self._left = set()
            self._right = set()
            self._down = set()
            for x in range(self.w):
                down = None
                for y in range(self.h):
                    if down is None and (x, y) in tiles:
                        down = (x, y)
                self._down.add(down)
            for y in range(self.h):
                left = None
                right = None
                for x in range(self.w):
                    if left is None and (x, y) in tiles:
                        left = (x, y)
                self._left.add(left)
                for x in reversed(range(self.w)):
                    if right is None and (x, y) in tiles:
                        right = (x, y)
                self._right.add(right)
        def __call__(self, y):
            """Reinit Block position at specific height, x always starts at 2"""
            self.y = y
            self.x = 2
            return self
        def __iter__(self):
            for x, y in self.all:
                yield x + self.x, y + self.y
        @property
        def iright(self):
            for x, y in self._right:
                yield x + self.x, y + self.y
        @property
        def ileft(self):
            for x, y in self._left:
                yield x + self.x, y + self.y
        @property
        def idown(self):
            for x, y in self._down:
                yield x + self.x, y + self.y
        def right(self, board):  # move right
            if self.x == self.X:
                return False
            self.x += 1
            if board and self.iright in board:
                self.x -= 1
                return False
            return True
        def left(self, board):  # move left
            if self.x == 0:
                return False
            self.x -= 1
            if board and self.ileft in board:
                self.x += 1
                return False
            return True
        def down(self, board):  # move down
            if self.y == 0:
                return False
            self.y -= 1
            if board and self.idown in board:
                self.y += 1
                return False
            return True
    
    
    class Board:
        def __init__(self, w=7, h=0):
            self.w = w
            self.h = h
            self.dy = 0
            self.map = []
            self.resize()
        def __call__(self, x, y):
            return self.map[y][x]
        def resize(self):
            for _ in range(len(self.map) + self.dy, self.h + 4):  # buffer of 4 blank lines
                self.map.append([0 for x in range(self.w)])
            if len(self.map) > 1000:
                self.dy += len(self.map) - 1000
                self.map = self.map[-1000:]
        def insert(self, block):
            for x, y in block:
                self.map[y - self.dy][x] = block.color
            self.h = max(self.h, block.y + block.h)
            self.resize()
        def __contains__(self, block):
            for x, y in block:
                if self.map[y - self.dy][x]:
                    return True
            return False
    
    class Simulation:
        def __init__(self, data, minblocks=2022, maxblocks=1000000000000):
            # Initialize things
            self.maxblocks = maxblocks
            self.minblocks = minblocks
            self.imoves = self.itermoves(data)
            self.iblocks = self.iterblocks()
            self.board = Board()
            self.heights = deque([0])
            self.history = dict()
            self.boardhash = dict()
            self.boardsnapshot = dict()
            self.count = 0
            self.start()
        def start(self):
            # Search for the first repeated full cycle
            self.searchfirstcycle()
            self.startlen = self.cycleend - 2 * self.cyclelen
            self.nbcycle, self.endlen = divmod(
                self.maxblocks - self.cycleend,
                self.cyclelen
            )
            self.extremities = self.cycleend + self.endlen
            while self.count < max(self.extremities, self.minblocks):
                self.iteration()
            self.startheight = self.heights[self.startlen]
            self.cycleheight = self.heights[self.cycleend] - self.heights[self.cyclestart]
        def searchfirstcycle(self):
            while True:
                status = self.iteration()  # , str(self.board.map[-999:-5])
                if status in self.history:
                    # We may have a cycle, take a full snapshot !
                    heightstart = self.heights[self.history[status]]
                    heightend = self.heights[self.count]
                    cycleboard = str(self.board.map[heightstart - heightend - 5:-5])
                    cyclehash = hash(cycleboard)
                    if(self.boardhash.get(status, False) == cyclehash
                       and self.boardsnapshot.get(status, False) == cycleboard):
                        self.cyclestart = self.history[status] - 1
                        self.cycleend = self.count - 1
                        self.cyclelen = self.cycleend - self.cyclestart
                        return
                    self.boardhash[status] = cyclehash
                    self.boardsnapshot[status] = cycleboard
                self.history[status] = self.count
        def iteration(self):
            block = self.nextblock(self.board.h + 3)
            for _ in range(7):  # 7 automatic moves, no board implied
                self.nextmove(block)
            while self.nextmove(block, self.board):
                pass
            self.board.insert(block)
            self.count += 1
            self.heights.append(self.board.h)
            return self.idblock, self.idmove
        def itermoves(self, input):
            _moves = [left if c == '<' else right for c in input]
            while True:
                for id, move in enumerate(_moves):
                    self.idmove = id
                    yield move
                    yield down
        @property
        def nextmove(self):
            return next(self.imoves)
        def iterblocks(self):
            b1 = Block((0, 0), (1, 0), (2, 0), (3, 0), color=1)
            b2 = Block((0, 1), (1, 0), (1, 1), (1, 2), (2, 1), color=2)
            b3 = Block((0, 0), (1, 0), (2, 0), (2, 1), (2, 2), color=3)
            b4 = Block((0, 0), (0, 1), (0, 2), (0, 3), color=4)
            b5 = Block((0, 0), (0, 1), (1, 0), (1, 1), color=5)
            while True:
                self.idblock = 0
                yield b1
                self.idblock = 1
                yield b2
                self.idblock = 2
                yield b3
                self.idblock = 3
                yield b4
                self.idblock = 4
                yield b5
        @property
        def nextblock(self):
            return next(self.iblocks)
    
    s = Simulation(sys.stdin.read().strip())
    print("""
    [demo] Height of 2022 blocks: 3068
    [demo] Cycle of 35 blocks, 1 Cycle 60, 2 Cycles 113, Cycle height 53, Extremities height 131
    [demo] Total Height = 1514285714288
    [real] Height of 2022 blocks: 3153
    [real] Cycle of 1705 blocks, 1 Cycle 2648, 2 Cycles 5297, Cycle height 2649, Extremities height 7766
    [real] Total Height = 1553665689155
    """)
    print(f"2022 Blocks : {s.heights[2022]}")
    print(f"First part  : {s.startlen}[{s.heights[s.startlen]}]")
    print(f"One Cycle   : {s.cyclelen}[{s.cycleheight}]")
    print(f"Extremities : {s.extremities}[{s.heights[s.extremities]}]")
    s.totalheight = s.heights[s.extremities] + s.nbcycle * s.cycleheight
    print(f"Total Height : {s.totalheight}")
    • Yth.
    • [^] # Re: C√īt√© code

      Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

      et le Block.color sert à un truc :

      colors = [f"\033[38;5;{c}m‚Ėą" for c in range(7)]
      for line in reversed(s.board.map[-20:-4]):
          print("".join(colors[c] for c in line))
      print("\033[0m")

      On affiche en couleur le Tetris des n-4 dernières lignes (les 4 du haut sont toujours vides).

      • Yth.

Suivre le flux des commentaires

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