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.
importredefiteration1(data):reg=re.compile(r"^([a-z]{4}): ([^a-z]+?)$",re.MULTILINE)whileTrue:numbers={a:f"({b})"if'X'inbelsestr(eval(b))fora,binreg.findall(data)}if"root"innumbers:yieldnumbers['root']returndata=reg.sub("",data)forname,valueinnumbers.items():data=data.replace(name,value)yielddatadefiteration2(data,r=0):reg1=re.compile(r"^\((.*) (.) ([\d.]+)\)$")reg2=re.compile(r"^\(([\d.]+) (.) (.*)\)$")whileTrue:# r = a o ba,o,b=(reg1.findall(data)+reg2.findall(data))[0]if'X'ina:data=aifo=='+':r=r-float(b)ifo=='-':r=r+float(b)ifo=='*':r=r/float(b)ifo=='/':r=r*float(b)else:data=bifo=='+':r=r-float(a)ifo=='-':r=float(a)-rifo=='*':r=r/float(a)ifo=='/':r=float(a)/ryielddata,rifdata=="(X)":returndata=sys.stdin.read().strip()# Exercice 1r=0fordiniteration1(data):r=dprint(eval(d))# Exercice 2data2=re.sub(r"root: ([a-z]{4}) . ([a-z]{4})",r"root: \1 - \2",re.sub(r"humn: \d+","humn: X",data))fordiniteration1(data2):r=dfordiniteration2(r,0):r=dprint(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.
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…
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…
Posté par Yth (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.
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…
@dataclass(frozen=False)classNumber:v:intp:intn:intdef__call__(self):returnself.v,self.p,self.n@propertydefnext(self):returnself.problem[self.n]@propertydefprevious(self):returnself.problem[self.p]@cached_propertydefmoves(self):returnself.value%(len(self.problem)-1)@cached_propertydefvalue(self):returnself.v*self.decryptionkey# Input handlingdefnumbers(data):lastid=len(data)-1yieldNumber(data[0],lastid,1)foriinrange(1,lastid):yieldNumber(data[i],i-1,i+1)yieldNumber(data[-1],lastid-1,0)defresult(problem):number=[xforxinproblemifx.v==0][0]for_inrange(1000):number=number.nextn1000=number.valuefor_inrange(1000):number=number.nextn2000=number.valuefor_inrange(1000):number=number.nextn3000=number.valuer=n1000+n2000+n3000returnrdefdecrypt(problem):fori,numberinenumerate(problem):ifnumber.v==0:continue# removes number from listnumber.previous.n=number.nnumber.next.p=number.psearch=numberfor_inrange(number.moves):search=search.next# search is now the new previousnumber.n=search.nnumber.p=search.next.p# Inserting numbernumber.next.p=inumber.previous.n=idata=[int(x)forxinsys.stdin.read().strip().splitlines()]# Problème n°1problem=list(numbers(data))Number.problem=problemNumber.decryptionkey=1decrypt(problem)print(f"First answer = {result(problem)}")# Problème n°2problem=list(numbers(data))Number.problem=problemNumber.decryptionkey=811589153for_inrange(10):decrypt(problem)print(f"Final answer = {result(problem)}")
Posté par Yth (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…
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
importsysfromcollectionsimportdequedefleft(block,board=None):block.left(board)returnTruedefright(block,board=None):block.right(board)returnTruedefdown(block,board=None):returnblock.down(board)classBlock:x,y,w,h,X=2,0,0,0,6color=1def__init__(self,*tiles,color=None):self.color=colororself.colorself.all=tilesself.w=max(xforx,yintiles)+1self.h=max(yforx,yintiles)+1self.X=7-self.wself._left=set()self._right=set()self._down=set()forxinrange(self.w):down=Noneforyinrange(self.h):ifdownisNoneand(x,y)intiles:down=(x,y)self._down.add(down)foryinrange(self.h):left=Noneright=Noneforxinrange(self.w):ifleftisNoneand(x,y)intiles:left=(x,y)self._left.add(left)forxinreversed(range(self.w)):ifrightisNoneand(x,y)intiles:right=(x,y)self._right.add(right)def__call__(self,y):"""Reinit Block position at specific height, x always starts at 2"""self.y=yself.x=2returnselfdef__iter__(self):forx,yinself.all:yieldx+self.x,y+self.y@propertydefiright(self):forx,yinself._right:yieldx+self.x,y+self.y@propertydefileft(self):forx,yinself._left:yieldx+self.x,y+self.y@propertydefidown(self):forx,yinself._down:yieldx+self.x,y+self.ydefright(self,board):# move rightifself.x==self.X:returnFalseself.x+=1ifboardandself.irightinboard:self.x-=1returnFalsereturnTruedefleft(self,board):# move leftifself.x==0:returnFalseself.x-=1ifboardandself.ileftinboard:self.x+=1returnFalsereturnTruedefdown(self,board):# move downifself.y==0:returnFalseself.y-=1ifboardandself.idowninboard:self.y+=1returnFalsereturnTrueclassBoard:def__init__(self,w=7,h=0):self.w=wself.h=hself.dy=0self.map=[]self.resize()def__call__(self,x,y):returnself.map[y][x]defresize(self):for_inrange(len(self.map)+self.dy,self.h+4):# buffer of 4 blank linesself.map.append([0forxinrange(self.w)])iflen(self.map)>1000:self.dy+=len(self.map)-1000self.map=self.map[-1000:]definsert(self,block):forx,yinblock:self.map[y-self.dy][x]=block.colorself.h=max(self.h,block.y+block.h)self.resize()def__contains__(self,block):forx,yinblock:ifself.map[y-self.dy][x]:returnTruereturnFalseclassSimulation:def__init__(self,data,minblocks=2022,maxblocks=1000000000000):# Initialize thingsself.maxblocks=maxblocksself.minblocks=minblocksself.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=0self.start()defstart(self):# Search for the first repeated full cycleself.searchfirstcycle()self.startlen=self.cycleend-2*self.cyclelenself.nbcycle,self.endlen=divmod(self.maxblocks-self.cycleend,self.cyclelen)self.extremities=self.cycleend+self.endlenwhileself.count<max(self.extremities,self.minblocks):self.iteration()self.startheight=self.heights[self.startlen]self.cycleheight=self.heights[self.cycleend]-self.heights[self.cyclestart]defsearchfirstcycle(self):whileTrue:status=self.iteration()# , str(self.board.map[-999:-5])ifstatusinself.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)==cyclehashandself.boardsnapshot.get(status,False)==cycleboard):self.cyclestart=self.history[status]-1self.cycleend=self.count-1self.cyclelen=self.cycleend-self.cyclestartreturnself.boardhash[status]=cyclehashself.boardsnapshot[status]=cycleboardself.history[status]=self.countdefiteration(self):block=self.nextblock(self.board.h+3)for_inrange(7):# 7 automatic moves, no board impliedself.nextmove(block)whileself.nextmove(block,self.board):passself.board.insert(block)self.count+=1self.heights.append(self.board.h)returnself.idblock,self.idmovedefitermoves(self,input):_moves=[leftifc=='<'elserightforcininput]whileTrue:forid,moveinenumerate(_moves):self.idmove=idyieldmoveyielddown@propertydefnextmove(self):returnnext(self.imoves)defiterblocks(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)whileTrue:self.idblock=0yieldb1self.idblock=1yieldb2self.idblock=2yieldb3self.idblock=3yieldb4self.idblock=4yieldb5@propertydefnextblock(self):returnnext(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.cycleheightprint(f"Total Height : {s.totalheight}")
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é !
importsysimportreimportmathfromdataclassesimportdataclassfromfunctoolsimportcached_property@dataclass(frozen=True)classMatters():ore:int=0clay:int=0obsidian:int=0def__add__(self,other):returnMatters(self.ore+other.ore,self.clay+other.clay,self.obsidian+other.obsidian,)def__sub__(self,other):returnMatters(self.ore-other.ore,self.clay-other.clay,self.obsidian-other.obsidian,)def__mul__(self,t):# Calculate production in t minutesreturnMatters(self.ore*t,self.clay*t,self.obsidian*t,)def__call__(self,name):returnself.__dict__[name]@dataclass(frozen=True)classFactory:id:introbots:dict[Matters]@cached_propertydefmaxproduction(self):returnMatters(*(max(x)forxinzip(*[(m.ore,m.clay,m.obsidian)forminself.robots.values()])))@dataclassclassState:timeleft:intstock:Matters=Matters()production:Matters=Matters(1,0,0)geode:int=0def__lt__(self,other):returnself.geode<other.geodedefbuildable(self):return[(robot,self.factory.robots[robot],self.test_build_time)forrobotin["geode","obsidian","clay","ore"]ifself.isbuilduseful(self.factory.robots[robot])]defisbuilduseful(self,cost):t=self.timetobuild(cost)iftisFalse:returnFalse# This robot should have the time to produce somethingift>=self.timeleft:returnFalseself.test_build_time=treturnTruedeftimetobuild(self,cost):t=0ifcost.ore>self.stock.ore:t=max(math.ceil((cost.ore-self.stock.ore)/self.production.ore),t)ifcost.clay>self.stock.clay:ifnotself.production.clay:returnFalset=max(math.ceil((cost.clay-self.stock.clay)/self.production.clay),t)ifcost.obsidian>self.stock.obsidian:ifnotself.production.obsidian:returnFalset=max(math.ceil((cost.obsidian-self.stock.obsidian)/self.production.obsidian),t)returnt+1# Time to collect enough resources, +1 to build the robotdefbuildrobot(self,robot,cost,time):stock=self.stock+self.production*time-costtime=self.timeleft-timeifrobot=="geode":returnState(time,stock,self.production,self.geode+time)returnState(time,stock,self.production+Matters(**{robot:1}),self.geode)def__str__(self):returnf"State Score={self.geode}, TimeLeft={self.timeleft}, "\
f"Production={self.production}, Stocks={self.stock}"
Ensuite le code en lui-même :
defiteration(state):buildable=state.buildable()ifnotbuildable:# end of the line !returnstate,1explored=0r=stateifbuildable[0][0]=="geode"andbuildable[0][2]==1:buildable=buildable[:1]forrobot,cost,timeinbuildable:ifrobot!="geode"andstate.production(robot)>=state.factory.maxproduction(robot):continues,e=iteration(state.buildrobot(robot,cost,time))explored+=er=sifr<selserifnotexplored:# robot limit attainedstate,1returnr,exploreddefinput():rematter=r"ore|clay|obsidian|geode"rerobot=re.compile(fr"Each ({rematter}) robot costs (.*)")recost=re.compile(fr"(\d+) ({rematter})")forblueprintinsys.stdin:id,blueprint=blueprint.strip().split(":")yieldFactory(int(id.split()[-1]),{build:Matters(**{b:int(a)fora,binrecost.findall(cost)})forrobotinblueprint.strip(".").split(".")forbuild,costin(rerobot.match(robot.strip()).groups(),)})defex1(factories):score=0expl=0forfinfactories:State.factory=fbeststate,explored=iteration(State(timeleft=24))print(f"Blueprints#{f.id} Best of {explored} State {str(beststate)}")score+=f.id*beststate.geodeexpl+=exploredprint(f"Score final = {score} (33, 1599) {expl} chemins explorés")defex2(factories):score=1expl=0forfinfactories:State.factory=fbeststate,explored=iteration(State(timeleft=32))print(f"Blueprints#{f.id} Best of {explored} State {str(beststate)}")score*=beststate.geodeexpl+=exploredprint(f"Score final = {score} ({56*62}, {49*18*16}) {expl} chemins explorés")factories=list(input())ex1(factories)ex2(fforfinfactoriesiff.id<=3)
Posté par Yth (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 !
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 !
Posté par Yth (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.
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.
classCube(tuple):@propertydefadjacent(self):x,y,z=selfyieldCube([x+1,y,z])yieldCube([x-1,y,z])yieldCube([x,y+1,z])yieldCube([x,y-1,z])yieldCube([x,y,z+1])yieldCube([x,y,z-1])@propertydefinterior(self):x,y,z=selfifx<self.mx:yieldCube([x+1,y,z])elifx>self.mx:yieldCube([x-1,y,z])ify<self.my:yieldCube([x,y+1,z])elify>self.my:yieldCube([x,y-1,z])ifz<self.mz:yieldCube([x,y,z+1])elifz>self.mz:yieldCube([x,y,z-1])@propertydefinside(self):fora,b,cinzip(self.minimum,self,self.maximum):ifnot(a<=b<=c):returnFalsereturnTruecubes={Cube(map(int,_.split(',')))for_insys.stdin.read().strip().splitlines()}x0=min(xforx,y,zincubes)y0=min(yforx,y,zincubes)z0=min(zforx,y,zincubes)x1=max(xforx,y,zincubes)y1=max(yforx,y,zincubes)z1=max(zforx,y,zincubes)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)//2Cube.my=(y1-y0)//2Cube.mz=(z1-z0)//2# exo 1, une liste parce qu'on a des doublons, on veut les faces, pas les cubes.exposed=[faceforcubeincubesforfaceincube.adjacentiffacenotincubes]adjacent=set(exposed)# Cubes adjacent au rocher, mais hors zoneadjacent_outside={faceforfaceinadjacentifnotface.inside}# Faces extérieures de la zone, hors cubes du rocher.exterior={Cube((x,y,z0))forxinrxforyinry}.union({Cube((x,y,z1))forxinrxforyinry},{Cube((x,y0,z))forxinrxforzinrz},{Cube((x,y1,z))forxinrxforzinrz},{Cube((x0,y,z))foryinryforzinrz},{Cube((x1,y,z))foryinryforzinrz},).difference(cubes)# Algo de parcours de zoneinterior=Truewhileinterior:interior={xforcinexteriorforxinc.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érieurexposed2=len([1forfaceinexposediffaceinadjacent2])print(f"{len(cubes)} Cubes")print(f"{len(exposed)} Exposed faces (4604)")print(f"{exposed2} Exterior faces (2604)")
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!
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.
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 !
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…
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.
# Pas de force brute, mais soyons bourrins, oh oui, bourrins !
Posté par Yth (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
parroot: truc - much
, ethumn: ????
parhumn: X
À la fin on a une grosse opération bourrée de parenthèses, avec au fond du fond
(X)
, il faut résoudrece 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.
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.
[^] # Re: pour les raleurs : Que disent les conditions d'utilisation sur la fiabilité du service fourni ?
Posté par Yth (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 :
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…
[^] # Re: Erreur bete
Posté par Yth (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 ?
[^] # Re: Modélisation trop longue à débugger
Posté par Yth (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…
[^] # Re: Un bug que j'ai résolu sans jamais le trouver.
Posté par Yth (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é !
[^] # Re: Un bug que j'ai résolu sans jamais le trouver.
Posté par Yth (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 ?
Tu t'en fous du nombre d'occurrence, ce que tu veux c'est que chaque élément de la liste soit unique.
[^] # Re: pour les raleurs : Que disent les conditions d'utilisation sur la fiabilité du service fourni ?
Posté par Yth (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…
[^] # Re: Un bug que j'ai résolu sans jamais le trouver.
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 20. Évalué à 4.
# Un bug que j'ai résolu sans jamais le trouver.
Posté par Yth (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.
[^] # Re: python tranquille
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 18. Évalué à 2.
Ah, super idée OpenSCAD !
Je connais un poil…
Merci !
[^] # Re: pour les raleurs : Que disent les conditions d'utilisation sur la fiabilité du service fourni ?
Posté par Yth (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 !
[^] # Re: Côté code
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 17. Évalué à 2.
et le Block.color sert à un truc :
On affiche en couleur le Tetris des n-4 dernières lignes (les 4 du haut sont toujours vides).
# Côté code
Posté par Yth (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
# Du code, du code, du code !
Posté par Yth (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é !
Ensuite le code en lui-même :
Voilà voilà…
[^] # Re: Modélisation trop longue à débugger
Posté par Yth (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 !
[^] # Re: python tranquille
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 18. Évalué à 2.
Jolie la visualisation !
Tu fais ça comment ?
[^] # Re: Modélisation trop longue à débugger
Posté par Yth (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 !
# Modélisation trop longue à débugger
Posté par Yth (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 :
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 :
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.
[^] # Re: Plus cool que les jours précédents
Posté par Yth (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 lesproperty
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.
Et voilà, à demain !
[^] # Re: Linuxfr ?
Posté par Yth (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.
[^] # Re: Peu d'obstacle?
Posté par Yth (Mastodon) . En réponse à la dépêche Le poste de travail Linux : un objectif gouvernemental ?. Évalué à 7.
C'est pareil, non ?
[^] # Re: Le Jour du Tetris
Posté par Yth (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.
PS : Je nettoie un peu le code et je poste ça…
# Le Jour du Tetris
Posté par Yth (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 :
(10**12-base)//cycle
;(10**12-base)%cycle
;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 :
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 !
[^] # Re: Tetris style
Posté par Yth (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…
[^] # Re: Tetris style
Posté par Yth (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.