Yth a écrit 2678 commentaires

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

• Y.

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.

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.

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.

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.

Jolie la visualisation !
Tu fais ça comment ?

• Yth.

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.

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.

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.

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

Pfff.

• Yth.

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.

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…

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.

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.

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.

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…

Pour le second tu dis qu'en prenant la solution du premier et en envoyant l'éléphant jouer avec les vannes non ouvertes par le premier, ça marche ?

Dingue ça…
Bon, 2min20 ça va au final, mais bigre… 37 millions de chemins testés !!!

• Yth.

Ah, c'est pas mal en effet !
Plus d'init ou de repr, voire un triage automatiquement généré, ça va faire gagner du temps ce truc…

• Yth, mon implémentation des intersection est sérieusement buggée…

Côté algo :
* on crée nos valves (ou vannes, osef) ;
* on lie les objets les uns aux autres pour les liaisons directes ;
* on explore de proche en proche pour enregistrer la liste des autres valves avec la distance pour y aller depuis chaque valve ;
* on n'optimise pas en stockant la distance retour dans la valve distante, vu mon algo ça pouvait empêcher la valve distante de calculer certaines distances, modélisation fausse, résultat faux, et les données de test ne sont pas affectées ;
* on parcours à nouveau nos valves et on supprime les chemins vers les valves à flux nul, on réduit le problème aux seules valves utiles (15 en situation réelle, 6 en test), mais avec des distances complètes.

Là on ne cherche plus à se déplacer, juste à mesurer le temps qui passe à partir d'ici ou de là.
Et donc pour chaque situation :
* valve où on se trouve
* temps restant
* score final actuel (dès qu'on ouvre une valve on calcule directement toute la vapeur dégagée jusqu'au bout du temps imparti)
* liste des valves ouvertes

On calcule le score final en allant ouvrir chaque vanne accessible.

On récurse à partir de chaque destination possible (vannes encore ouvertes), et une fois au bout, soit du temps disponible (données réelles), soit de vannes à ouvrir (données de test), on a un chemin avec un score.

On ne retourne que le meilleur score, et pas tous les chemins trouvés, sinon on explose la RAM et la durée.
Et à la fin on a notre résultat.

class Valve:
    def __init__(self, name, flow, links):
        self.name = name
        self.flow = int(flow)
        self.locallinks = links.strip().split(", ")
        self.links = dict()
        # considering valve with no flow as already opened
        self.open = self.flow == 0

    def __repr__(self):
        return f"{self.name}@{self.flow}: {' '.join(f'{n.name}:{d}' for n, d in sorted(self.links.items()))}"

    def __lt__(self, other):
        return self.name < other.name

    def linkvalves(self, valves):
        self.valves = valves
        self.locallinks = [valves[link] for link in self.locallinks]
        # self.links = {link: 1 for link in self.locallinks}
        self.links[self] = 0

    def graph(self):
        explore = {self, }
        distance = 0
        while explore:
            distance += 1
            step = set(
                link
                for valve in explore
                for link in valve.locallinks
                if link not in self.links
            )
            for valve in step:
                self.links[valve] = distance
            explore = step

    def reducegraph(self):
        self.links = {
            link: score
            for link, score in self.links.items()
            if link.flow
        }

    def getscores(self, timeleft, currentscore, opened):
        self.scores = dict()
        for link, distance in self.links.items():
            timeafter = timeleft - distance - 1
            # valve already opened or too far to be useful
            if link in opened or timeafter <= 0:
                continue
            self.scores[link] = currentscore + timeafter * link.flow, timeafter
        return self.scores

regex = re.compile(
    r"Valve ([A-Z]+) has flow rate=(\d+); "
    r"tunnels? leads? to valves? ([A-Z, ]+)")
valves = {
    v.name: v
    for v in (
        Valve(*regex.match(line).groups())
        for line in sys.stdin
    )
}
for valve in valves.values():
    valve.linkvalves(valves)
for valve in valves.values():
    valve.graph()
for valve in valves.values():
    valve.reducegraph()

def nextscores(valve, currentscore, timeleft, opened, currentpath):
    path = valve.getscores(timeleft, currentscore, opened)
    if not path:  # end of the line !
        return currentscore, timeleft, currentpath, 1
    explored = 0
    r = (0, 0, "", 0)
    for link, (score, time) in path.items():
        x = nextscores(
            link,
            score,
            time,
            opened + [link],
            currentpath + "->" + link.name
        )
        explored += x[-1]
        r = x if x > r else r
    return r[0], r[1], r[2], explored

score, time, path, explored = nextscores(valves['AA'], 0, 30, [], 'AA')
print(f"Score {score}, explored {explored} paths : {path}")

Pour l'exercice 2 on conserve la même modélisation, aucun changement.
La fonction d'exploration change : on lui fourni deux explorateurs, chacun avec son chemin parcouru, et son temps restant.
Et on travaille sur l'explorateur qui a le plus de temps disponible à chaque itération.

class explorer:  # pour se simplifier la vie
    def __init__(self, valve, timeleft, path=None):
        self.valve = valve
        self.timeleft = timeleft
        self.path = path or valve.name

    def __call__(self, s):
        return f"{self.path}->{s}"

    def __repr__(self):
        return f"time remaining {self.timeleft} {self.path}"

    def __lt__(self, other):
        return self.timeleft < other.timeleft

def doublescores(e1, e2, currentscore, opened):
    if e1 < e2:  # look using the explorer with the most time remaining
        e2, e1 = e1, e2
    path = e1.valve.getscores(e1.timeleft, currentscore, opened)
    if not path:  # end of the line !
        return (currentscore, e1, e2, 1)
    explored = 0
    r = (0, 0, "", 0)
    for link, (score, time) in path.items():
        x = doublescores(
            explorer(link, time, e1(link.name)),
            e2,
            score,
            opened + [link],
        )
        explored += x[-1]
        r = x if x > r else r
    return r[0], r[1], r[2], explored

score, p1, p2, explored = doublescores(
    explorer(valves['AA'], 26),
    explorer(valves['AA'], 26),
    0,
    [],
)
print(f"Score {score}, explored {explored} paths, {p1} {p2}")

Et voilà, on a bien perdu du temps et fait chauffer la machine.

• Yth.

Ça prend du temps là, je vais avoir du mal ce week-end.
Et faut que je rattrape le temps perdu au boulot…
À un moment ça va craquer aussi.

• Yth.

Et 6h30 après la publication du problème, il n'y avait que 2500 personnes à avoir eu une solution complète.
Pour ma part j'ai mis 25 minutes à coder la seconde partie à partir de la première, et la valider sur les données de test, en pleine visio boulot.
Puis 5 minutes à installer pypy et vérifier comment ça marche (réponse : bien).
Et 15 minutes de calculs pour avoir une solution… (J'ai killé la version cpython au bout de 20 minutes)
J'ai laissé tourner en espérant que ça allait marcher.

À noter que je stocke tous les chemins, puis je trie et je pond le dernier.
C'est utile pour le débuggage, mais complètement crétin : on peut toujours comparer au fur et à mesure et ne conserver que le dernier !

Fallait s'en douter déjà : sur les données de test, j'explore toujours les 720 possibilités, donc il y a sûrement une optimisation possible, pourtant aujourd'hui j'ai suivi mon conseil : réfléchir avant d'agir.
Pas assez…

J'ai recodé pour ne garder en mémoire que le meilleur chemin, et pas tous les chemins triés après coup.
Données de test, avec python3, plus rapide que pypy3 sur un délais aussi court :
Ex1 en 0.05s : Score 1651, 720 chemins explorés
AA->DD->BB->JJ->HH->EE->CC
Ex2 en 0,07s : Score 1707, 720 chemins explorés
AA->JJ->BB->CC AA->DD->HH->EE

Données réelles, avec pypy :
Ex1 en 0,5s : Score 1871, 106 839 chemins explorés
Ex2 en 2min21 : Score 2416, 37 306 254 chemins explorés

Et là, je réalise que les 15 minutes c'était 13 minutes pour afficher 37 millions de foutues lignes dans mon terminal débile, et peut-être un peu de temps pour gérer la RAM explosive de la liste de 37 millions d'entrées, et la trier à la fin…

Non mais sérieux…

Au passage cpython prends 2,1 secondes pour l'exo 1 réel contre 0,5 secondes pour pypy3.
Mais pour l'exo 2, pypy prend 2min21 quand cpython monte à plus de 20 minutes (il a pas terminé là).
pypy3 prend 108Mo de RAM, fixe quand on fait pas le crétin.
cpython3 reste à 12Mo de RAM, là aussi quand on ne fait pas l'idiot.
Et j'ai découvert que quand la RAM se réduit, Firefox décharge naturellement les onglets ouverts, pour rétrécir plutôt que de mourir !

Donc merci à Steph pour l'idée d'utiliser pypy :)

• Yth.

Alors j'ai un bug : il faut écrire if s > xmax + 1: à la place de if s > xmax:.

Paradoxalement ça ne pose aucun problème avec les données réelles, mais ça bugge avec les données de test, où sur un bord entre deux zone, adjacentes sur 6 cases, je trouve des trous que je ne devrais pas trouver.

Bref.

• Yth.

D'ailleurs, en utilisant la technique de l'exercice 2 on peut refaire l'exercice 1 en immédiat :

# Pas de zone comme pour l'exo1, on retourne les intervalles comme pour l'exo2
class RobotSensor:
    def __init__(self, *args):
        self.sx, self.sy, self.bx, self.by, *self.other = args
        self.distance = manhattan(*args)

    def __contains__(self, line):
        return abs(self.sy-line) <= self.distance

    def __getitem__(self, line):
        deltax = self.distance - abs(self.sy-line)
        return self.sx-deltax, self.sx+deltax

sensors = [RobotSensor(*(int(x) for x in line)) for line in data]
r = sorted([sensor[line_to_check] for sensor in sensors if line_to_check in sensor])

xmin, xmax, holes = r[0][0], 0, 0
for s, e in r:
    if s > xmax:
        holes += s - xmax
    xmax = max(xmax, e)
beacons = len(set(s.bx for s in sensors if s.by == line_to_check))
result1 = xmax - xmin + 1 - holes - beacons
print(f"No beacon on {result1} positions"
      f" [{xmin}->{xmax}, {holes} holes and {beacons} beacons]\n")

Le calcul est immédiat.

• Yth.

Ah, c'est joli ça, oui !
Comme quoi on ferait mieux de réfléchir avant d'agir hein…

• Yth.

En très pythonesque, l'itération par nombre premier se fait comme ça :

def iter():
    step, line = 747319, zone
    while True:
        yield line
        line = (line + step) % zone

for line in iter():
    ...

• Yth.