Yth a écrit 2615 commentaires

Donc je vire mon iteration2 puis :

import sys
import re
import sympy

def iteration(data):
    reg = re.compile(r"^([a-z]{4}): ([^a-z]+?)$", re.MULTILINE)
    while True:
        numbers = {
            a: f"({b})"
            for a, b in reg.findall(data)
        }
        if "root" in numbers:
            return numbers['root']
        data = reg.sub("", data)
        for name, value in numbers.items():
            data = data.replace(name, value)

data = sys.stdin.read().strip()
# Exercice 1
print(eval(iteration(data)))

# 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))
print(sympy.solve(iteration(data2), 'X'))

Et voilà !
Finalement c'était facile à utiliser :D

• Yth.

Nope, si j'avais connu sympy je l'aurais utilisé.
Jadis j'avais un truc qui faisait ça sur ma HP48GX !

Je savais qu'un truc du genre existait en Python, mais j'ai jugé que le chercher et apprendre à l'utiliser serait plus long que de bourriner :)

• Yth.

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.

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.

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.

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.

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.

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.

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.

@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)}")

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.

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

Merci !

• Yth.

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.