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.