Yth a écrit 2613 commentaires

  • # Pas de force brute, mais soyons bourrins, oh oui, bourrins !

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 21. Évalué à 2.

    Pour l'exo 1 je fais du re.findall, str.replace, re.sub, et un gros eval dès que j'ai root.
    Youpi, bourrin :)

    Pour le 2, bah non.
    On remplace root: truc * much par root: truc - much, et humn: ???? par humn: X
    À la fin on a une grosse opération bourrée de parenthèses, avec au fond du fond (X), il faut résoudre ce truc = 0.
    Donc on remonte en inversant les opérations, chaque parenthèse est (nombre opération (trucs...)) ou ((trucs...) opération nombre), des gros if tout moches, et à la fin le résultat.

    Sans finesse ça va assez vite : une demi seconde.

    import re
    def iteration1(data):
        reg=re.compile(r"^([a-z]{4}): ([^a-z]+?)$",re.MULTILINE)
        while True:
            numbers = {
                a: f"({b})" if 'X' in b else str(eval(b))
                for a, b in reg.findall(data)
            }
            if "root" in numbers:
                yield numbers['root']
                return
            data = reg.sub("", data)
            for name, value in numbers.items():
                data = data.replace(name, value)
            yield data
    
    
    def iteration2(data, r=0):
        reg1 = re.compile(r"^\((.*) (.) ([\d.]+)\)$")
        reg2 = re.compile(r"^\(([\d.]+) (.) (.*)\)$")
        while True:
            # r = a o b
            a, o, b = (reg1.findall(data) + reg2.findall(data))[0]
            if 'X' in a:
                data = a
                if o == '+':
                    r = r - float(b)
                if o == '-':
                    r = r + float(b)
                if o == '*':
                    r = r / float(b)
                if o == '/':
                    r = r * float(b)
            else:
                data = b
                if o == '+':
                    r = r - float(a)
                if o == '-':
                    r = float(a) - r
                if o == '*':
                    r = r / float(a)
                if o == '/':
                    r = float(a) / r
            yield data, r
            if data == "(X)":
                return
    
    data = sys.stdin.read().strip()
    # Exercice 1
    r = 0
    for d in iteration1(data):
        r = d
    print(eval(d))
    
    # Exercice 2
    data2 = re.sub(r"root: ([a-z]{4}) . ([a-z]{4})", r"root: \1 - \2", re.sub(r"humn: \d+", "humn: X", data))
    for d in iteration1(data2):
        r = d
    
    for d in iteration2(r, 0):
        r = d
    print(r[1])

    Zéro modélisation, à peine de la réflexion, zéro optimisations sauf l'eval ajouté dans l'iteration1 quand on peut réduire à un nombre, basta.

    • Yth.
  • [^] # Re: pour les raleurs : Que disent les conditions d'utilisation sur la fiabilité du service fourni ?

    Posté par  (Mastodon) . En réponse au journal La Poste pas nette a encore du mal avec le courrier. Évalué à 4.

    Je n'ai jamais écrit que laposte.net était responsable de ce qui se passe :

    on constate que laposte.net ne se foule pas beaucoup beaucoup pour essayer d'arranger la situation de leur côté, d'où la grogne…

    Ce n'est pas rendre laposte.net responsable.
    C'est l'explication des mécontentements.
    Et oui, ils sont mal dirigés les mécontentements, mais on est en France, c'est vachement plus facile de tape sur La Poste que sur un MAGAF, c'est limite culturel !

    Par contre Ferrari serait un peu responsable de continuer à te vendre une voiture qui ne peut plus rouler nulle part…

    • Yth.
  • [^] # Re: Erreur bete

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 19. Évalué à 2.

    Parcourir en largeur et virer les chemins pourraves, c'pas mal.
    Mon algo parcours en profondeur, j'ai pas cette possibilité sauf à le refaire…

    Une idée de comment être raisonnablement sûr que tu as la meilleure solution en limitant à 100 ?

    • Yth.
  • [^] # Re: Modélisation trop longue à débugger

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 19. Évalué à 2.

    C'est pas mal de ne pas aller jusqu'au bout si on sait déjà qu'on sera en-dessous du meilleur temps.
    J'ai ajouté un truc comme ça sur mon code, ça fonctionne nickel, et je divise le temps par deux, je suis à 5s pour les deux exercices.
    Je passe de 492 462 chemins à 46 859 sur l'exo 1.
    Et au total de 4 661 927 à 755 262 sur l'exo 2.

    Vu la réduction sévère du nombre de chemins, je me demande où le temps est perdu tout de même…

    • Yth.
  • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 20. Évalué à 2. Dernière modification le 20 décembre 2022 à 15:18.

    Faut aussi que 0 reste (0, 0), pour le retrouver à la fin.
    Mais ça gagne 35% de temps :)

    Bravo, j'admire la simplicité !

    • Yth, je note list.index() c'est pas pourri en vrai, peut-être si on a des listes de millions d'éléments, mais là c'est 5000, c'est petit.
  • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 20. Évalué à 4. Dernière modification le 20 décembre 2022 à 15:02.

    C'est tellement plus intelligent que ce que j'ai fait, je suis jaloux !
    Je ne pensais pas que les listes seraient assez performantes, j'aurais dû essayer.

    Bravo !

    Tu peux pas faire ça plutôt ?

        for id, data in enumerate(f):
            n = int(data.rstrip()) * (811589153 if is_part_2 else 1)
            original_sequence.append((id, c))

    Tu t'en fous du nombre d'occurrence, ce que tu veux c'est que chaque élément de la liste soit unique.

    • Yth.
  • [^] # Re: pour les raleurs : Que disent les conditions d'utilisation sur la fiabilité du service fourni ?

    Posté par  (Mastodon) . En réponse au journal La Poste pas nette a encore du mal avec le courrier. Évalué à 10.

    Alors, juste comme ça, j'ai aussi une adresse @laposte.net, depuis une vingtaine d'années, que j'utilise de moins en moins.

    Le service rendu pendant 15 ans était parfait, c'est à dire que je pouvais envoyer des mails à des gens, et en recevoir.

    Donc je n'ai pas souscrits une adresse mail pour utiliser une Ferrari dans la gadoue ou forer de la pierre avec un forêt à métal, et le service a été parfaitement adapté au besoin - qui n'a pas changé - pendant 15 années.
    Mais force est de constater que ça n'est pas le cas : ça fonctionne mais moins bien, c'est comme si ma voiture ne pouvait plus dépasser le 110 sur l'autoroute, alors que c'est la même voiture et qu'elle faisait ça très bien avant.

    Aujourd'hui les Google, Microsoft et Cie essaient de flinguer le mail.
    Google en faisant un immense silo Gmail vers lequel il est difficile de communiquer quand on n'est pas dedans, mais qui envoie sans soucis : utilisateur@gmail = chez-moi-ça-marche, viens ici !
    Microsoft en remplaçant le mail par Exchange, ce qui fait une autre forme de silo partiellement incompatible. On a moins de difficulté à communiquer depuis l'extérieur, mais ça noyaute énormément d'entreprise qui de fait n'utilise plus le mail mais un service propriétaire nommé Exchange.

    laposte.net c'est du mail.
    Et aujourd'hui ça fonctionne moins bien parce que Google, Microsoft et Cie essaient de tuer le mail.

    Voilà le cœur du problème.
    Et on constate que laposte.net ne se foule pas beaucoup beaucoup pour essayer d'arranger la situation de leur côté, d'où la grogne…

    • Yth.
  • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 20. Évalué à 4.

    @dataclass(frozen=False)
    class Number:
        v: int
        p: int
        n: int
    
        def __call__(self):
            return self.v, self.p, self.n
    
        @property
        def next(self):
            return self.problem[self.n]
    
        @property
        def previous(self):
            return self.problem[self.p]
    
        @cached_property
        def moves(self):
            return self.value % (len(self.problem) - 1)
    
        @cached_property
        def value(self):
            return self.v * self.decryptionkey
    
    # Input handling
    def numbers(data):
        lastid = len(data) - 1
        yield Number(data[0], lastid, 1)
        for i in range(1, lastid):
            yield Number(data[i], i - 1, i + 1)
        yield Number(data[-1], lastid - 1, 0)
    
    def result(problem):
        number = [x for x in problem if x.v == 0][0]
        for _ in range(1000):
            number = number.next
        n1000 = number.value
        for _ in range(1000):
            number = number.next
        n2000 = number.value
        for _ in range(1000):
            number = number.next
        n3000 = number.value
        r = n1000 + n2000 + n3000
        return r
    
    def decrypt(problem):
        for i, number in enumerate(problem):
            if number.v == 0:
                continue
            # removes number from list
            number.previous.n = number.n
            number.next.p = number.p
            search = number
            for _ in range(number.moves):
                search = search.next
            # search is now the new previous
            number.n = search.n
            number.p = search.next.p
            # Inserting number
            number.next.p = i
            number.previous.n = i
    
    data = [int(x) for x in sys.stdin.read().strip().splitlines()]
    # Problème n°1
    problem = list(numbers(data))
    Number.problem = problem
    Number.decryptionkey = 1
    decrypt(problem)
    print(f"First answer = {result(problem)}")
    
    # Problème n°2
    problem = list(numbers(data))
    Number.problem = problem
    Number.decryptionkey = 811589153
    for _ in range(10):
        decrypt(problem)
    print(f"Final answer = {result(problem)}")
  • # Un bug que j'ai résolu sans jamais le trouver.

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 20. Évalué à 3. Dernière modification le 20 décembre 2022 à 11:43.

    J'ai codé ma propre liste chaînée, j'ai été intelligent avec mes modulos, j'ai une réponse sans ultra-optimiser en 4 secondes pour les données de test et les données réelles.

    Et j'ai un bug.
    Tout fonctionne au poil sur les données de test, les deux exercices, et les données réelles, mais pas le second sur données réelles !
    Mauvais résultat.
    Et j'ai beau triturer, je tombe toujours sur le mauvais résultat.

    Alors j'ai recodé un peu différemment mes quelques lignes qui servent à déplacer un nombre dans la liste, je suis persuadé que fonctionnellement c'est identique, et ça fonctionne au super poil avec les données de test.
    Mais je suis malade, ça explique peut-être.
    En tout cas : résultat différent et correct cette fois-ci, avec un code un zest plus propre, mais à peine.

    Sauf que dans le cas où le mouvement est de zéro, modulo, ben j'avais un effet de bord débile, je cassais ma liste…

    Bref, ça aurait dû aller vite, mais pas.

    • Yth.
  • [^] # Re: python tranquille

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 18. Évalué à 2.

    Ah, super idée OpenSCAD !
    Je connais un poil…

    Merci !

    • Yth.
  • [^] # Re: pour les raleurs : Que disent les conditions d'utilisation sur la fiabilité du service fourni ?

    Posté par  (Mastodon) . En réponse au journal La Poste pas nette a encore du mal avec le courrier. Évalué à 4.

    Ouais !
    Et pis c'est toujours mieux quand c'est la faute de la victime en plus !

    • Y.
  • [^] # Re: Côté code

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 17. É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.
  • # Côté code

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 17. É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.
  • # Du code, du code, du code !

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 19. Évalué à 4.

    D'abord la modélisation, avec des opérations sur triplets de matière Matters(ore, clay, obsidian). Dans un premier temps j'avais aussi geode, mais en vrai on ne produit, ne consomme, ni ne stocke de geode : c'est le score, on le gère à part.
    En vrai ça change pas grand chose…
    Un frozen dataclass, et les opérations retournent une nouvelle instance, ça permet d'éviter des risques de modifier un truc référencé ailleurs, et on y gagne en bugs et en perfs au bout du compte.

    Chaque blueprint génère une Factory qui ne sert pas à grand chose, c'est des données, c'est figé, ça bouge pas.

    Ensuite une classe d'état, State, qui stocke le temps restant, les stocks, la production, et le nombre de géodes à la fin si on touche plus à rien, donc le score actuel de cet état à la fin du temps imparti. Aussi un dataclass, je découvre, j'en mets partout, selon le biais bien connu de waooouh-nouveauté !

    import sys
    import re
    import math
    from dataclasses import dataclass
    from functools import cached_property
    
    @dataclass(frozen=True)
    class Matters():
        ore: int = 0
        clay: int = 0
        obsidian: int = 0
        def __add__(self, other):
            return Matters(
                self.ore + other.ore,
                self.clay + other.clay,
                self.obsidian + other.obsidian,
            )
        def __sub__(self, other):
            return Matters(
                self.ore - other.ore,
                self.clay - other.clay,
                self.obsidian - other.obsidian,
            )
        def __mul__(self, t):
            # Calculate production in t minutes
            return Matters(
                self.ore * t,
                self.clay * t,
                self.obsidian * t,
            )
        def __call__(self, name):
            return self.__dict__[name]
    
    @dataclass(frozen=True)
    class Factory:
        id: int
        robots: dict[Matters]
        @cached_property
        def maxproduction(self):
            return Matters(*(
                max(x)
                for x in zip(*[
                    (m.ore, m.clay, m.obsidian)
                    for m in self.robots.values()
                ])
            ))
    
    @dataclass
    class State:
        timeleft: int
        stock: Matters = Matters()
        production: Matters = Matters(1, 0, 0)
        geode: int = 0
    
        def __lt__(self, other):
            return self.geode < other.geode
    
        def buildable(self):
            return [
                (robot, self.factory.robots[robot], self.test_build_time)
                for robot in ["geode", "obsidian", "clay", "ore"]
                if self.isbuilduseful(self.factory.robots[robot])
            ]
    
        def isbuilduseful(self, cost):
            t = self.timetobuild(cost)
            if t is False:
                return False
            # This robot should have the time to produce something
            if t >= self.timeleft:
                return False
            self.test_build_time = t
            return True
    
        def timetobuild(self, cost):
            t = 0
            if cost.ore > self.stock.ore:
                t = max(math.ceil((cost.ore - self.stock.ore) / self.production.ore), t)
            if cost.clay > self.stock.clay:
                if not self.production.clay:
                    return False
                t = max(math.ceil((cost.clay - self.stock.clay) / self.production.clay), t)
            if cost.obsidian > self.stock.obsidian:
                if not self.production.obsidian:
                    return False
                t = max(math.ceil((cost.obsidian - self.stock.obsidian) / self.production.obsidian), t)
            return t + 1  # Time to collect enough resources, +1 to build the robot
    
        def buildrobot(self, robot, cost, time):
            stock = self.stock + self.production * time - cost
            time = self.timeleft - time
            if robot == "geode":
                return State(time, stock, self.production, self.geode + time)
            return State(time, stock, self.production + Matters(**{robot: 1}), self.geode)
    
        def __str__(self):
            return f"State Score={self.geode}, TimeLeft={self.timeleft}, "\
                f"Production={self.production}, Stocks={self.stock}"

    Ensuite le code en lui-même :

    def iteration(state):
        buildable = state.buildable()
        if not buildable:  # end of the line !
            return state, 1
        explored = 0
        r = state
        if buildable[0][0] == "geode" and buildable[0][2] == 1:
            buildable = buildable[:1]
        for robot, cost, time in buildable:
            if robot != "geode" and state.production(robot) >= state.factory.maxproduction(robot):
                continue
            s, e = iteration(state.buildrobot(robot, cost, time))
            explored += e
            r = s if r < s else r
        if not explored:  # robot limit attained
            state, 1
        return r, explored
    
    
    def input():
        rematter = r"ore|clay|obsidian|geode"
        rerobot = re.compile(fr"Each ({rematter}) robot costs (.*)")
        recost = re.compile(fr"(\d+) ({rematter})")
        for blueprint in sys.stdin:
            id, blueprint = blueprint.strip().split(":")
            yield Factory(
                int(id.split()[-1]), {
                    build: Matters(**{b: int(a) for a, b in recost.findall(cost)})
                    for robot in blueprint.strip(".").split(".")
                    for build, cost in (rerobot.match(robot.strip()).groups(),)
                })
    
    
    def ex1(factories):
        score = 0
        expl = 0
        for f in factories:
            State.factory = f
            beststate, explored = iteration(State(timeleft=24))
            print(f"Blueprints#{f.id} Best of {explored} State {str(beststate)}")
            score += f.id * beststate.geode
            expl += explored
        print(f"Score final = {score} (33, 1599) {expl} chemins explorés")
    
    
    def ex2(factories):
        score = 1
        expl = 0
        for f in factories:
            State.factory = f
            beststate, explored = iteration(State(timeleft=32))
            print(f"Blueprints#{f.id} Best of {explored} State {str(beststate)}")
            score *= beststate.geode
            expl += explored
        print(f"Score final = {score} ({56*62}, {49*18*16}) {expl} chemins explorés")
    
    
    factories = list(input())
    ex1(factories)
    ex2(f for f in factories if f.id <= 3)

    Voilà voilà…

    • Yth.
  • [^] # Re: Modélisation trop longue à débugger

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 19. Évalué à 2. Dernière modification le 19 décembre 2022 à 15:24.

    Non, on n'a qu'une seule usine de robots, donc c'est un par tour…

    À noter ici que la différence entre cpython et pypy est assez délirante.
    J'ai nettoyé le code, je suis à 8 secondes avec pypy3, et 2 minutes 30 avec python3 !

    • Yth.
  • [^] # Re: python tranquille

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 18. Évalué à 2.

    Jolie la visualisation !
    Tu fais ça comment ?

    • Yth.
  • [^] # Re: Modélisation trop longue à débugger

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 19. Évalué à 3.

    Et en optimisant un pouille mes structures de données (dataset immutable, ne pas recopier les données statiques dans les nouvelles instances de classes, mais les mettre en dur dans la classe, etc), je descends à 29 secondes pour les données de test et 10s pour les données réelles !

    • Yth.
  • # Modélisation trop longue à débugger

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 19. Évalué à 4. Dernière modification le 19 décembre 2022 à 11:44.

    J'ai passé un temps fou à débugger ma modélisation pourtant pas si complexe.
    Après j'ai rapidement constaté que l'approche naïve était idiote et explosive, donc j'ai testé deux limitation de l'exploration des possibilités :

    • Si on peut construire un extracteur de géode, on le fait, c'est capital si on peut produire un robot-géode par tour, on ne fait plus que ça.
    • On limite le nombre de robot de chaque type au coût maximal d'un robot pour ce type de ressources.

    C'est empirique, j'ai juste testé ces règles sans chercher plus loin : ça valide les données de test !
    Donc j'ai testé les données réelles et bingo.

    En terme de stats pour les données de test, le nombre de possibilités testées :

    • 85 156 pour le premier schéma en 24s.
    • 47 477 pour le second schéma en 24s.
    • 14 042 636 pour le premier schéma en 32s.
    • 3 778 241 pour le second schéma en 32s.

    Et 2 minutes 20 pour trouver ça, yuk…
    Sur les données réelles, j'explore au total 492 462 chemins sur l'exercice 1, avec 30 schémas, et 4 661 927 chemins sur l'exercice 2 avec 3 schémas (les éléphants ont bouffés les autres schémas).
    Ce qui ne prend que 44 secondes, donc les données réelles sont plus cool que les données de test, pour une fois.

    • Yth, mélange d'intuition, et de mains gauches aujourd'hui.
  • [^] # Re: Plus cool que les jours précédents

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 18. Évalué à 5.

    J'ai jamais appris les algos classiques, Djikstra, BFS, A* etc, tendance à réinventer la roue à chaque fois.
    Mais je faisais pareil en prépa avec les preuves de théorèmes à apprendre par cœur : jamais réussi, je voyais pas l'intérêt quand il suffisait de refaire la preuve en direct au tableau…

    Bref, des set(), des unions, des différences, des intersections, pas besoin d'aller bien plus loin en Python, l'espace à analyser est tout petit, 10k cases, c'est rien, quand on sort d'une tour infernale de mille milliards de cube Tetris empilés sur une hauteur de quelques 1500 milliards…

    Mon alog part des faces externes du pavé contenant notre rocher de lave en fusion, donc les 6 faces x=xmin, x=xmax, y=ymin, y=ymax, z=zmin, z=zmax.
    Puis j'agrandis vers l'intérieur (si x < xmax/2 alors (x+1, y, z), sinon (x-1, y, z), pareil pour y et z), donc on a trois adjacents au lieu de six et on ne sort jamais de la zone.
    On vire les cubes du bout de lave, on itère.
    En 6 itérations c'est fini, on a tous les cubes de vide à l'extérieur, sur zone.
    On prends les adjacents à la lave, on difference(lave), on intersection(exterieur), on remet dedans les cubes vides qui étaient hors zone.

    Sinon on pouvait partir d'une zone de 1 plus grande dans chaque direction, et faire une itération de plus, mais bon, j'ai pas trouvé ça plus simple dans le code, et ça faisait passer à un espace de presque 13k au lieu de 10k, soit tout aussi négligeable, mais un peu moins.

    J'ai modélisé une class Cube(tuple) pour mes triplets de coordonnées avec les property suivantes :
    * adjacent pour les 6 cubes autour ;
    * interior pour les 3 cubes vers le centre de la zone ;
    * inside qui dit si un Cube est hors zone ou pas.
    J'altère ma classe Cube une fois les données entièrement lues, pour fournir les bornes, et le milieu arrondi à l'entier pour marginalement gagner du temps de calcul en évitant les comparaisons entre entier et flottant. À noter que dans mon cas la division par deux est entière donc ça ne change rien. Et que le gain est marginal vu la taille des données.
    Donc pas mal de préparation avant de lancer des calculs très simples au bout du compte.

    class Cube(tuple):
        @property
        def adjacent(self):
            x, y, z = self
            yield Cube([x + 1, y, z])
            yield Cube([x - 1, y, z])
            yield Cube([x, y + 1, z])
            yield Cube([x, y - 1, z])
            yield Cube([x, y, z + 1])
            yield Cube([x, y, z - 1])
    
        @property
        def interior(self):
            x, y, z = self
            if x < self.mx:
                yield Cube([x + 1, y, z])
            elif x > self.mx:
                yield Cube([x - 1, y, z])
            if y < self.my:
                yield Cube([x, y + 1, z])
            elif y > self.my:
                yield Cube([x, y - 1, z])
            if z < self.mz:
                yield Cube([x, y, z + 1])
            elif z > self.mz:
                yield Cube([x, y, z - 1])
    
        @property
        def inside(self):
            for a, b, c in zip(self.minimum, self, self.maximum):
                if not (a <= b <= c):
                    return False
            return True
    
    cubes = {
        Cube(map(int, _.split(',')))
        for _ in sys.stdin.read().strip().splitlines()
    }
    x0 = min(x for x, y, z in cubes)
    y0 = min(y for x, y, z in cubes)
    z0 = min(z for x, y, z in cubes)
    x1 = max(x for x, y, z in cubes)
    y1 = max(y for x, y, z in cubes)
    z1 = max(z for x, y, z in cubes)
    rx = list(range(x0, x1 + 1))
    ry = list(range(y0, y1 + 1))
    rz = list(range(z0, z1 + 1))
    Cube.minimum = (x0, y0, z0)
    Cube.maximum = (x1, y1, z1)
    Cube.mx = (x1 - x0) // 2
    Cube.my = (y1 - y0) // 2
    Cube.mz = (z1 - z0) // 2
    
    # exo 1, une liste parce qu'on a des doublons, on veut les faces, pas les cubes.
    exposed = [
        face
        for cube in cubes
        for face in cube.adjacent
        if face not in cubes
    ]
    adjacent = set(exposed)
    
    # Cubes adjacent au rocher, mais hors zone
    adjacent_outside = {face for face in adjacent if not face.inside}
    # Faces extérieures de la zone, hors cubes du rocher.
    exterior = {Cube((x, y, z0)) for x in rx for y in ry}.union(
        {Cube((x, y, z1)) for x in rx for y in ry},
        {Cube((x, y0, z)) for x in rx for z in rz},
        {Cube((x, y1, z)) for x in rx for z in rz},
        {Cube((x0, y, z)) for y in ry for z in rz},
        {Cube((x1, y, z)) for y in ry for z in rz},
    ).difference(cubes)
    # Algo de parcours de zone
    interior = True
    while interior:
        interior = {
            x
            for c in exterior
            for x in c.interior
        }.difference(exterior).difference(cubes)
        exterior.update(interior)
    # Les cubes adjacent au rocher, mais pas à l'intérieur !
    adjacent2 = adjacent.intersection(exterior).union(adjacent_outside)
    # Et recalcul des faces exposées, mais uniquement à l'extérieur
    exposed2 = len([1 for face in exposed if face in adjacent2])
    
    print(f"{len(cubes)} Cubes")
    print(f"{len(exposed)} Exposed faces (4604)")
    print(f"{exposed2} Exterior faces (2604)")

    Et voilà, à demain !

    • Yth.
  • [^] # Re: Linuxfr ?

    Posté par  (Mastodon) . En réponse au lien Mort aux commentaires inutiles ! Écrivez des commentaires pertinents !. Évalué à 2.

    On t'as dis d'aller écrire de la doc ! Allez, du vent…

    Pfff.

    • Yth.
  • [^] # Re: Peu d'obstacle?

    Posté par  (Mastodon) . En réponse à la dépêche Le poste de travail Linux : un objectif gouvernemental ?. Évalué à 7.

    C'est sous estimer la tâche. Une montée de version de Windows est déjà un investissement technique et du courage pour une DSI! Quid d'un changement d'OS!

    C'est pareil, non ?

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

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 17. É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…

  • # Le Jour du Tetris

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 17. É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: Tetris style

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 17. É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.
  • [^] # Re: Tetris style

    Posté par  (Mastodon) . En réponse au message Avent du Code, jour 17. É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.