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.
Posté par Yth (Mastodon) .
En réponse au message Avent du Code, jour 17.
Évalué à 2.
Dernière modification le 17 décembre 2022 à 19:23.
C'est plus compliqué que ça a priori.
Je n'ai pas de méthode de calcul du cycle, je le mesure en prenant des bornes assez grandes.
On a plusieurs problèmes :
Trouver en combien de blocs on cycle, c'est à dire qu'en partant de l'ajout du premier bloc avec la première instruction, on revient à l'ajout du premier bloc avec la première instruction. Dans mon cas c'est en 1705 blocs, dans les données de test c'est en 35 blocs.
Constater que le début de partie ne correspond pas du tout à un cycle répétitif, la situation est particulière, et le premier cycle commence… plus tard. Sur mes données il faut passer quelque chose entre 200 et 300 blocs pour démarrer le premier cycle.
mesurer la hauteur ajoutée par un cycle complet normal en milieu de tour (donc pas le début, pas la fin).
Et mesurer la fin, en haut, soit mille milliards modulo le cycle.
En pratique, il suffit de faire une tour de deux cycles plus la fin, on a un cycle normal et complet au milieu, donc on sait qu'on peut en rajouter autant qu'on veut, ça agrandira linéairement.
Le principe c'est ça, avec la fonction simulation() qui fait une simulation (ouais ouais ! Promis !), en paramètres les data, et le nombre de blocs à faire tomber. Elle retourne la hauteur finale. L'exercice 1 c'est l'appel avec 2022 blocs, et voilà.
Cas particulier, si je fournis un 3è paramètre, je laisse passer ce nombre de blocs, et je prend l'état (n° de bloc, n° d'instruction), et dès que je retrouve le même état, j'ai mon cycle, je sors la valeur !
Après on mesure, on calcule, ça marche.
data=sys.stdin.read().strip()h1=simulation(data,2022)print(f"Height of 2022 blocks: {h1}")# Finding cycle length, knowing this limits would be enoughcycle=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)+hrprint(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…
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.
classValve:def__init__(self,name,flow,links):self.name=nameself.flow=int(flow)self.locallinks=links.strip().split(", ")self.links=dict()# considering valve with no flow as already openedself.open=self.flow==0def__repr__(self):returnf"{self.name}@{self.flow}: {' '.join(f'{n.name}:{d}' for n, d in sorted(self.links.items()))}"def__lt__(self,other):returnself.name<other.namedeflinkvalves(self,valves):self.valves=valvesself.locallinks=[valves[link]forlinkinself.locallinks]# self.links = {link: 1 for link in self.locallinks}self.links[self]=0defgraph(self):explore={self,}distance=0whileexplore:distance+=1step=set(linkforvalveinexploreforlinkinvalve.locallinksiflinknotinself.links)forvalveinstep:self.links[valve]=distanceexplore=stepdefreducegraph(self):self.links={link:scoreforlink,scoreinself.links.items()iflink.flow}defgetscores(self,timeleft,currentscore,opened):self.scores=dict()forlink,distanceinself.links.items():timeafter=timeleft-distance-1# valve already opened or too far to be usefuliflinkinopenedortimeafter<=0:continueself.scores[link]=currentscore+timeafter*link.flow,timeafterreturnself.scoresregex=re.compile(r"Valve ([A-Z]+) has flow rate=(\d+); "r"tunnels? leads? to valves? ([A-Z, ]+)")valves={v.name:vforvin(Valve(*regex.match(line).groups())forlineinsys.stdin)}forvalveinvalves.values():valve.linkvalves(valves)forvalveinvalves.values():valve.graph()forvalveinvalves.values():valve.reducegraph()defnextscores(valve,currentscore,timeleft,opened,currentpath):path=valve.getscores(timeleft,currentscore,opened)ifnotpath:# end of the line !returncurrentscore,timeleft,currentpath,1explored=0r=(0,0,"",0)forlink,(score,time)inpath.items():x=nextscores(link,score,time,opened+[link],currentpath+"->"+link.name)explored+=x[-1]r=xifx>relserreturnr[0],r[1],r[2],exploredscore,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.
classexplorer:# pour se simplifier la viedef__init__(self,valve,timeleft,path=None):self.valve=valveself.timeleft=timeleftself.path=pathorvalve.namedef__call__(self,s):returnf"{self.path}->{s}"def__repr__(self):returnf"time remaining {self.timeleft}{self.path}"def__lt__(self,other):returnself.timeleft<other.timeleftdefdoublescores(e1,e2,currentscore,opened):ife1<e2:# look using the explorer with the most time remaininge2,e1=e1,e2path=e1.valve.getscores(e1.timeleft,currentscore,opened)ifnotpath:# end of the line !return(currentscore,e1,e2,1)explored=0r=(0,0,"",0)forlink,(score,time)inpath.items():x=doublescores(explorer(link,time,e1(link.name)),e2,score,opened+[link],)explored+=x[-1]r=xifx>relserreturnr[0],r[1],r[2],exploredscore,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.
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 !
Posté par Yth (Mastodon) .
En réponse au message Avent du Code jour 15.
Évalué à 2.
Dernière modification le 16 décembre 2022 à 11:27.
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.
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'exo2classRobotSensor:def__init__(self,*args):self.sx,self.sy,self.bx,self.by,*self.other=argsself.distance=manhattan(*args)def__contains__(self,line):returnabs(self.sy-line)<=self.distancedef__getitem__(self,line):deltax=self.distance-abs(self.sy-line)returnself.sx-deltax,self.sx+deltaxsensors=[RobotSensor(*(int(x)forxinline))forlineindata]r=sorted([sensor[line_to_check]forsensorinsensorsifline_to_checkinsensor])xmin,xmax,holes=r[0][0],0,0fors,einr:ifs>xmax:holes+=s-xmaxxmax=max(xmax,e)beacons=len(set(s.bxforsinsensorsifs.by==line_to_check))result1=xmax-xmin+1-holes-beaconsprint(f"No beacon on {result1} positions"f" [{xmin}->{xmax}, {holes} holes and {beacons} beacons]\n")
Voilà le code à rajouter, on refait la classe en ZoneSensor pour retourner les bornes de l'intervalle sur une ligne, et à l'intérieur de la zone [0, 4000000] :
classZoneSensor:def__init__(self,*args):self.sx,self.sy,self.bx,self.by,self.zone,*self.other=argsself.distance=manhattan(*args)def__contains__(self,line):returnabs(self.sy-line)<=self.distancedef__getitem__(self,line):deltax=self.distance-abs(self.sy-line)returnmax(0,self.sx-deltax),min(self.zone,self.sx+deltax)zone=line_to_check*2sensors=[ZoneSensor(*(int(x)forxinline),zone)forlineindata]try:forlineinrange(zone,-1,-1):r=sorted([sensor[line]forsensorinsensorsiflineinsensor])ifr[0][0]!=0:raiseBaseException(0,line)xmax=0fors,einr:ifs>xmax:raiseBaseException(s-1,line)xmax=max(xmax,e)ifxmax!=zone:raiseBaseException(zone,line)print("Nothing found, there is a bug")exceptBaseExceptionase:x,y=e.argsprint(f"Beacon on position {x}, {y}, value={x*4000000+y}")
Le sorted au début de la boucle va ordonner par le premier élément du tuple, donc le début des intervalles, puis en cas d'égalité par le second. A partir de là on sait que les intervalles vont de gauche à droite.
On note la fin de notre intervalle consolidé, et si l'intervalle suivant commence après, bingo, on a trouvé !
On teste vite fait au début ou à la fin, si notre case à trouver ne serait pas au début ou à la fin, et voilà.
Et bien sûr, on va pas se fouler, exception quand on a trouvé quelque chose : on arrête tout et on jubile !
À noter que je pars de la ligne du bas, mon nez m'a dit que l'auteur allait fourber et mettre la ligne à trouver vers la fin, j'avais raison, la mienne est la 3 391 794.
C'est peut-être là où je gagne le plus de temps en fait.
Sinon, pour essayer d'avoir de la chance, on peut parcourir la zone avec un index qui se balade en parcourant tout.
step = un nombre premier avec 4000000
i = 4000000 # parce que line % 4000000 ne vaudra jamais 4000000
i = (i + step) % 4000000
En moyenne on va mettre pareil que si on ne sait pas où est la ligne, mais on tape au milieu dès le début et comme la probabilité que l'auteur n'ait pas mis sa ligne proche du bord, pour empêcher la force brute, est assez élevée, on a plus de chance d'avoir de la chance.
De l'autre côté (lignes croissantes de 0 à 4000000) ça prend 1min11s, et bien sûr on a le même résultat.
Avec un step de 747319 (nombre premier, donc premier avec 4000000, choisi au pif), je trouve le résultat en 49 secondes, assez proche de la moitié de la recherche totale ((1m11s+19s)/2=45s).
Posté par Yth (Mastodon) .
En réponse au message Avent du Code jour 15.
Évalué à 2.
Dernière modification le 15 décembre 2022 à 10:37.
Soyons honnêtes, le premier exercice, je l'ai bourriné en force brute.
Objectif : soit une ligne donnée, trouver le nombre de cases qui ne contiennent pas de balises.
Donc les cases visibles par une robot-senseur quelconque, moins les balises sur la ligne (piège, haha !).
Je suis tombé dans un autre piège : il faut scanner la ligne 2 000 000, mais pour l'exemple (pour valider le code) il faut scanner la ligne 10. Mais bon, la réponse pour la ligne 10 du problème complet, c'pas la réponse attendue, bref…
La méthode bourrine :
* pour chaque robot-senseur qui voit la ligne donnée :
* faire un set() des cases vues set(range(début, fin)) ;
* union des sets() ;
* compter sa taille ;
* lister pour chaque robot-senseur sa balise, si elle est sur la bonne ligne ;
* supprimer les balises trouvées.
Ça marche en 1,25 secondes sur les données réelles, le résultat étant de 5838453 on a quand même fait un set-comprehension en double boucle d'une taille non négligeable.
La rumeur comme quoi Python c'est lent, c'pas toujours vrai hein, ya aucune optimisation dans mon code.
importsysimportredefmanhattan(x1,y1,x2,y2,*args):returnabs(x1-x2)+abs(y1-y2)classSensor:def__init__(self,*args):self.sx,self.sy,self.bx,self.by,*self.other=argsself.distance=manhattan(*args)def__contains__(self,line):returnabs(self.sy-line)<=self.distancedef__getitem__(self,line):deltax=self.distance-abs(self.sy-line)returnrange(self.sx-deltax,self.sx+deltax+1)# inputsline_to_check=2000000iflen(sys.argv)<=1elseint(sys.argv[1])zone=line_to_check*2regex=re.compile(r"Sensor at x=(-?\d+), y=(-?\d+): "r"closest beacon is at x=(-?\d+), y=(-?\d+)")data=[regex.match(line).groups()forlineinsys.stdin]sensors=[Sensor(*(int(x)forxinline),zone)forlineindata]result1=len(set(posforsensorinsensorsifline_to_checkinsensorforposinsensor[line_to_check]))-len(set(s.bxforsinsensorsifs.by==line_to_check))print(f"No beacon on {result1} positions\n")
Pour l'exercice 2, la méthode bourrine est hors de question.
Parce que sinon, mon PC serait toujours en train de calculer là.
Et l'énergie coûte plus cher que mon temps de cerveau disponible.
Optimisé, ça prend quand même 19 secondes, le ventilo a le temps de décoller.
Posté par Yth (Mastodon) .
En réponse au message Avent du Code, jour 14.
Évalué à 2.
Dernière modification le 14 décembre 2022 à 16:01.
Et maintenant, on allume le cerveau :
Pour l'exercice 2, la base se calcule trivialement : le sable formant une pyramide, on sait qu'il va de 500-hauteur à 500+hauteur, vu qu'on a 174 de haut (de 0 à 173), la coursive est en 174, et le sol en 175, le sable s'entasse donc de 326 à 674, et le sol doit s'étendre une case plus loin : de 325 à 675, comme « triché » dans mon code, sauf que ça se calcule de façon sûre avec d'autres données en entrée.
Pour l'exercice 2 encore, et suivant la remarque de Tanguy sur les zones protégées par les rochers pour calculer des surfaces :
On va créer des cases « dark » sous les lignes.
Une ligne de (x1, y1) à (x2, y2) avec x1<=x2 va générer une ligne protégée de gauche à droite de (x1+1, max(y1, y2)) à (x2-1, max(y1, y2)), donc si x1+1>x2-1 (ça arrive quand x1==x2, ligne verticale, ou quand la ligne horizontale fait 2 de large : x2=x1+1) on ne met rien.
Après on peut filtrer les cases bouchées (dark et rocher) sur la zone de pyramide de sable, c'est à dire quand 500-y <= x <= 500+y pour chaque élément. Ici on ne supprime rien, donc on n'a pas à gérer d'éventuels effets de bord, avec une plateforme qui dépasse de la pyramide de sable et peut protéger une zone qui serait ensevelie si la source du sable était plus haute.
La taille de la pyramide est, en prenant le triangle de droite et en le posant retourné au dessus du triangle de gauche, un carré de la hauteur totale, soit 175^2 = 30625 grains potentiels.
Ici ça ne suffit pas : un mur vertical sous une plate-forme va protéger une zone. Donc il faut ne pas réduire la ligne sur un côté si on a un rocher juste là.
Les données en entrée ne sont pas collaboratives, donc en fait on essaie toujours d'élargir la plate-forme qu'on considère pour la zone protégée du dessous, sur la gauche et la droite, puis on protège la ligne en dessous en retirant un élément à gauche et un à droite.
-> Ça fonctionne, il faut juste faire très attention à protéger une ligne en dessous des derniers rochers, le niveau de la coursive, mais pas plus bas au niveau du sol et en dessous, en traitant les données en flux on n'a pas la taille de la zone, donc la position du sol, donc on doit élaguer après coup pour le décompte : tout ce qui est en y < 175.
Voici l'image générée avec les rochers et les zones protégées en dessous :
Pour mon exemple, j'ai en zones protégées (rochers et dark) 1804 cases, donc 30625-1804 = 28821, c'est mon résultat !
Pour les deux exercices :
Quand le sable n'est pas en chute libre, il va s'empiler sur toutes les cases visiter, à terme, sauf à sortir du terrain de jeu pour l'exercice 1.
Donc on n'est pas obligé de faire tomber le sable grain par grain, mais on peut poser des couches, avec un algo récursif.
Il suffit de le faire prendre en remontant la récursion quand on a trouver où se poser en bas. Parce que si on ne trouve pas où se poser (exercice 1 uniquement), alors aucun grain suivant ne pourra se poser.
C'est beaucoup plus simple à mettre en œuvre pour l'exo 2 puisqu'un fil de sable trouvera toujours un endroit où s'arrêter, donc on peut remplir en descendant, et explorer à la fois à gauche et à droite en bas de chaque chute libre.
Pour l'exo 1, si on parcours normalement, qu'on pose les grains en remontant de la récursion et pas avant de descendre, et qu'on sort brutalement (exception python en haut de l'exploration) dès qu'on est au bout, on devrait avoir le résultat.
Je ne l'ai pas encore fait, il est tard, je devrais commencer ma journée de taf quand même :D
Parce que un truc de 351 * 175 dans le terminal c'est galère quand même…
Bref, j'ai perdu plein de temps à faire une animation pas trop lente (j'ai fini par exponentiellement sauter des images : j'affiche l'image 2n), et réussir à faire entrer ça proprement dans le terminal. Après coup j'ai réalisé qu'il suffisait d'afficher chaque grain de sable une fois calculé, au lieu de tout retracer… Dans un terminal… Diantre…
J'avais un bug débile aussi pour l'exo 2, comme je voulais un sol pas trop large pour l'affichage, j'ai essayé d'être intelligent, et ça n'a pas marché, j'ai fini par faire un affichage avec un sol pas très large, puis rajouter un sol très très large.
Après j'ai triché et j'ai juste mis le sol en dur aux bonnes dimensions pour tout afficher, une fois le résultat obtenu.
Deux belles images :
Et un code probablement trop complexe.
L'affichage déjà
classdisplay:sand=" "# "▒"sandcolor=220void=" "rock=" "# "█"rockcolor=94start="+"def__init__(self,x0,x1,y0,y1,*rocks):self.x0,self.x1,self.y0,self.y1=x0,x1,y0,y1self.bg=[[f"{self.color(bg=0)}{self.void}"forxinrange(x0,x1+1)]foryinrange(y0,y1+1)]forxinrocks:self.bg[x[1]-y0][x[0]-x0]=f"{self.color(bg=self.rockcolor)}{self.rock}"self.bg[0][500-x0]=self.startself.background="\n".join("".join(self.bg[y][x]forxinrange(len(self.bg[0])))foryinrange(len(self.bg)))self.width=len(self.bg[0])self.height=len(self.bg)defcolor(self,bg=None,fg=None,rgb=None):bg=f"\033[48;5;{bg}m"ifbgelse""fg=f"\033[38;5;{fg}m"iffgelse""fg=f"\033[38;2;{rgb[0]};{rgb[1]};{rgb[2]}m"ifrgbelsefgifnotbgandnotfg:return"\033[0m"returnf"{bg}{fg}"defcursor(self,row=0,col=0):ifrow<0:row=self.height-rowreturnf"\033[{row+1};{col+1}H"def__call__(self,*items,wait=0):print(self.str(items))ifwait:time.sleep(wait)defitem(self,item):return(f"{self.cursor(col=item[0]-self.x0, row=item[1]-self.y0)}"f"{self.color(bg=self.sandcolor)}"f"{self.sand}")if(item[0]>=self.x0anditem[0]<=self.x1anditem[1]>=self.y0anditem[1]<=self.y1)else""defstr(self,items):return(f"{self.cursor()}"f"{self.color()}"f"{self.background}"f"{''.join(self.item(item) for item in items)}")
Et le code en lui-même :
definput():forlineinsys.stdin:x=list(tuple(map(int,r.split(',')))forrinline.split(' -> '))for_inzip(x[:-1],x[1:]):yield_classRockFormation:def__init__(self,input):self.finished=Falseself.source=(500,0)self.carte=set()self.sand=set()for_ininput():self._add_rocks(*_)self.dim=self.calcdim(self.carte)self.rock=self.carte.copy()self.sand=set()def_add_rocks(self,r1,r2):x1=min(r1[0],r2[0])x2=max(r1[0],r2[0])y1=min(r1[1],r2[1])y2=max(r1[1],r2[1])self.carte.update((x,y)forxinrange(x1,x2+1)foryinrange(y1,y2+1))defadd_rocks(self,r1,r2):self._add_rocks(r1,r2)self.dim=self.calcdim(self.carte)self.rock=self.carte.copy()defcalcdim(self,carte):return(min(x[0]forxincarte),max(x[0]forxincarte),0,max(x[1]forxincarte),)def__call__(self):s=self._sand(*self.source)ifnotself.finished:ifsinself.carte:print(f"Re-adding {s} !")raiseIndexErrorself.carte.add(s)self.sand.add(s)ifs==self.source:self.finished=Truereturnsdef_sand(self,x,y):ifx<self.dim[0]orx>self.dim[1]ory==self.dim[3]:self.finished=Truereturnx,ywhile(x,y+1)notinself.carte:y+=1if(x-1,y+1)notinself.carte:x,y=self._sand(x-1,y+1)elif(x+1,y+1)notinself.carte:x,y=self._sand(x+1,y+1)returnx,ydefsimulation(rocks):d()whilerocks.finishedisFalse:print(d.item(rocks()))# Inputsrocks=RockFormation(input)# First simulationd=display(*rocks.dim,*rocks.rock)simulation(rocks)result1=len(rocks.sand)print(f"{d.cursor(row=-4)}{d.color()}Resting sand : {len(rocks.sand)}")# Second simulation preparationrocks.finished=False# Limited floor for display# rocks.add_rocks(# (rocks.dim[0]-1, rocks.dim[3]+2),# (rocks.dim[1]+1, rocks.dim[3]+2)# )# d = display(*rocks.dim, *rocks.rock)# # Big (not too huge) floor for simulation# rocks.add_rocks(# (rocks.dim[0]-1000, rocks.dim[3]),# (rocks.dim[1]+1000, rocks.dim[3])# )# Enough floor knowing the solutionrocks.add_rocks((325,174),(675,174))d=display(*rocks.dim,*rocks.rock)simulation(rocks)print(f"{d.cursor(row=-3)}{d.color()}",end='')print(f"Resting sand : {result1}")print(f"Filling sand : {len(rocks.sand)}")print(f"Dimensions 1 : {dim1}")print(f"Dimensions 2 : {rocks.dim}")display2=d.str(rocks.sand)# Et enfin afficher le résultat pour les screenshotsw,h=tuple(os.get_terminal_size())print("\n"*h)print(display1)print("\n"*h)print(display2)print(f"{d.cursor(row=-2)}{d.color()}",end='')
Il faut vachement zoomer arrière dans le terminal, après c'est écrit trop petit pour lire, mais on a une belle animation :)
Ouais, j'ai essayé de faire un hack pour remplacer les chiffres seuls par des listes de chiffres, et après faire un json.loads() et juste comparer, en bricolant quelques trucs du genre on arrive à faire tourner les données de démo.
Pour faire court, c'est le premier exercice du calendrier où je n'ai pas fourni la bonne réponse du premier coup…
On peut faire un truc rigolo sur la partie travail, on garde packet et input() identiques, et on reste sur du générateur/itérateur jusqu'à la fin avec le sort :
defanalyse(decoder):score=0forid,(a,b)inenumerate(input()):yieldayieldbifa<=b:score+=id+1print(f"Pairs in the right order : {score}")fordindecoder:yieldddecoder=[packet([[2]]),packet([[6]])]s=sorted(analyse(decoder))print(f"Decoder Key = {(s.index(decoder[0])+1) * (s.index(decoder[1])+1)}")
J'ai un code équivalent, avec un peu plus de modélisation, mais sinon, c'est algorithmiquement identique :
importsysimportjsonfromfunctoolsimporttotal_ordering@total_orderingclasspacket:def__init__(self,data):self.data=datadefcompare(self,a,b):iftype(a)==type(b)==int:ifa==b:returnNonereturna<biftype(a)==int:a=[a]iftype(b)==int:b=[b]fori,jinzip(a,b):c=self.compare(i,j)ifcisnotNone:returncelse:returnself.compare(len(a),len(b))returnNonedef__lt__(self,other):returnself.compare(self.data,other.data)isTruedef__eq__(self,other):returnself.compare(self.data,other.data)isNonedefinput():x=Noneforlineinsys.stdin:ifline=="\n":x=NoneelifxisnotNone:yieldx,packet(json.loads(line))else:x=packet(json.loads(line))score=0all_packets=[]forid,(a,b)inenumerate(input()):all_packets+=[a,b]ifa<=b:score+=id+1print(f"Pairs in the right order : {score}")decoder=[packet([[2]]),packet([[6]])]s=sorted(all_packets+decoder)print(f"Decoder Key = {(s.index(decoder[0])+1) * (s.index(decoder[1])+1)}")
Je n'ai pas songé à split("\n\n"), ça fait que j'ai une première partie qui bosse en flux, mais comme pour la seconde il faut trier, on est obligé d'avoir toutes les données chargées, change rien.
Et ma fonction de comparaison est très centrée sur l'exercice : a < b c'est True, a > b c'est False et a == b c'est None, ergo on poursuit. C'est plus propre de faire -1/0/1.
classdisplay:def__init__(self,input,width,heights):self.heights=heightsself.bgcolors=[[min(255,max(232,heights[c]+231))forcinline]forlineininput]self.background="\n".join("".join(f"{self.color(c)} "forcinline)forlineinself.bgcolors)self.bgcolors=sum(self.bgcolors,[])self.width=widthdefcolor(self,bg=None,fg=None,rgb=None):bg=f"\033[48;5;{bg}m"ifbgelse""fg=f"\033[38;5;{fg}m"iffgelse""fg=f"\033[38;2;{rgb[0]};{rgb[1]};{rgb[2]}m"ifrgbelsefgreturnf"{bg}{fg}"defcursor(self,row=0,col=0):returnf"\033[{row};{col}H"def__call__(self,*visited):print(self.cursor(),end='')print(self.background)forvinvisited:print(f"{self.cursor(*divmod(v, self.width))}{self.color(bg=self.bgcolors[v], fg=160)}o")time.sleep(.1)# On ajoute ces deux lignes juste avant la troisième :d=display(input,w,heights)d()input="".join(input)# Et enfin en dernière ligne de main():d(*v1,*v2)# Et pour éviter d'avoir les résultats en tout moche au milieu :s1=main([start],[end])s2=main([posforpos,heightinenumerate(map)ifheight==1],[end])print(d.cursor(row=h+1),end='')print("\033[0m",end='')print(f"Path found in {s1} moves !")print(f"Path found in {s2} moves !")
Et il faut mettre le terminal en grand, parce que sinon ça va faire très très moche et buggé !
On a une animation des cases en cours de visite, sur fond de montagne enneigée (dégradé noir en bas, et blanc en haut).
Ah, classe :)
J'ai rien de joli à montrer ce coup-ci.
Mais bon, journée présentiel au taf hier, trois heures dans la voiture, 4h en réunions, j'ai à peine eu le temps de bricoler une solution, en ayant réfléchi sur le trajet…
J'ai fait un parcours de graphe inventé à la volée : je n'ai jamais été fichu de retenir le moindre des algos de parcours que j'ai pu apprendre, alors je suis condamné à réinventer la roue !
J'ai des cases en entrée, je regarde pour chacune d'elles où elles peuvent aller (haut, bas, gauche, droite, si la différence de hauteur est bonne), et si je n'ai pas déjà été là (donc matrice des cases visitées avec distance au départ dedans).
Je note l'ensemble des cases nouvellement visitées, et j'itère sur cet ensemble.
Donc a priori inutile de stocker le score pour le retrouver et calculer la suite comme dans mon code plus bas : il suffit de compter les étapes.
Instinctivement, je me suis dis que ça pouvait grossir, et donc j'ai décidé de manger le problème par les deux bouts, donc j'explore en montant depuis "S" et en descendant depuis "E".
Je stocke des scores positifs en montant, et négatifs en descendant.
Si je rencontre une case visitée depuis l'autre bout (case négative si je monte ou positive si je descends), j'ai fait la liaison.
En pratique je peux m'arrêter là : si je suis en train de monter c'est étape*2+1, si je suis en train de descendre c'est étape*2+2.
Dans mon code j'additionne les valeurs absolues : la valeur que j'aurais dû mettre dans la case, et celle déjà présente, et j'ai mon résultat.
Pour l'exercice 2, comme je fournis déjà une liste de case par itération, il suffit de mettre comme liste de démarrage tout les "a" et le "S", vraiment rien à coder, la dernière ligne du programme et basta.
Ah, et j'ai aligné, je bosse sur un tableau à une dimension, au lieu d'une matrice.
Et les mouvements possibles ne sont pas (haut, bas, gauche droite) mais (-1, +1, -largeur, +largeur) et un mouvement doit être dans [0, taille[
Allez, trêve de blabla, code !
heights={v:(26ifk==27elsek)or1fork,vinenumerate("SabcdefghijklmnopqrstuvwxyzE")}input=[lineforlineinsys.stdin.read().strip().splitlines()]w,h=len(input[0]),len(input)size=w*hmoves=[1,-1,w,-w]input="".join(input)map=[heights[c]forcininput]start=input.index("S")end=input.index("E")deftest(score,newpos,height,sign):""" False : mouvement impossible True : mouvement possible vers case non visitée int : mouvement possible vers case visitée, retourne le score de cette case """ifnewpos<0ornewpos>=size:returnFalseif(sign>0andmap[newpos]>height+1)\
or(sign<0andmap[newpos]<height-1):returnFalseifscore[newpos]isNone:returnTruereturnscore[newpos]defmove(score,pos,sign=1):height=map[pos]visited=[]solution=Falseforminmoves:newpos=pos+mt=test(score,newpos,height,sign)ifnott:# Movement not allowedcontinueiftisTrue:# New tile visitedscore[newpos]=score[pos]+signvisited.append(newpos)continueift*sign>0:# Already visitedcontinue# Visited from the other side : solution found !visited.append(newpos)solution=min(solutionorsize,1+sign*score[pos]-sign*score[newpos])returnvisited,solutiondefmain(s1,s2):score=[0if(posins1orposins2)elseNoneforposinrange(size)]unfinished=Truewhileunfinished:v1,v2=[],[]forposins1:v,solution=move(score,pos,1)v1+=vifsolution:print(score)print(f"Path found in {solution} moves !")unfinished=Falseforposins2:v,solution=move(score,pos,-1)v2+=vifsolution:print(score)print(f"Path found in {solution} moves !")unfinished=Falses1,s2=v1,v2main([start],[end])main([posforpos,heightinenumerate(map)ifheight==1],[end])
[^] # 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.
[^] # Re: Tetris style
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 17. Évalué à 2. Dernière modification le 17 décembre 2022 à 19:23.
C'est plus compliqué que ça a priori.
Je n'ai pas de méthode de calcul du cycle, je le mesure en prenant des bornes assez grandes.
On a plusieurs problèmes :
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 lesdata
, 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.
[^] # Re: Ça chauffe, ça chauffe !
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 16. Évalué à 2. Dernière modification le 16 décembre 2022 à 23:09.
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 !!!
[^] # Re: Une solution brillante
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 15. Évalué à 2. Dernière modification le 16 décembre 2022 à 15:29.
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…
[^] # Re: Ça chauffe, ça chauffe !
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 16. Évalué à 4.
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.
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.
Et voilà, on a bien perdu du temps et fait chauffer la machine.
[^] # Re: C'est trop pour moi
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 16. Évalué à 3.
Ç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.
# Ça chauffe, ça chauffe !
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 16. Évalué à 3.
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 :)
[^] # Re: Force Brute.
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 15. Évalué à 2. Dernière modification le 16 décembre 2022 à 11:27.
Alors j'ai un bug : il faut écrire
if s > xmax + 1:
à la place deif 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.
[^] # Re: Force Brute.
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 15. Évalué à 2.
D'ailleurs, en utilisant la technique de l'exercice 2 on peut refaire l'exercice 1 en immédiat :
Le calcul est immédiat.
[^] # Re: Une solution brillante
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 15. Évalué à 2.
Ah, c'est joli ça, oui !
Comme quoi on ferait mieux de réfléchir avant d'agir hein…
[^] # Re: Force Brute.
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 15. Évalué à 2. Dernière modification le 15 décembre 2022 à 13:05.
En très pythonesque, l'itération par nombre premier se fait comme ça :
[^] # Re: Force Brute.
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 15. Évalué à 2.
Voilà le code à rajouter, on refait la classe en ZoneSensor pour retourner les bornes de l'intervalle sur une ligne, et à l'intérieur de la zone [0, 4000000] :
Le sorted au début de la boucle va ordonner par le premier élément du tuple, donc le début des intervalles, puis en cas d'égalité par le second. A partir de là on sait que les intervalles vont de gauche à droite.
On note la fin de notre intervalle consolidé, et si l'intervalle suivant commence après, bingo, on a trouvé !
On teste vite fait au début ou à la fin, si notre case à trouver ne serait pas au début ou à la fin, et voilà.
Et bien sûr, on va pas se fouler, exception quand on a trouvé quelque chose : on arrête tout et on jubile !
À noter que je pars de la ligne du bas, mon nez m'a dit que l'auteur allait fourber et mettre la ligne à trouver vers la fin, j'avais raison, la mienne est la
3 391 794
.C'est peut-être là où je gagne le plus de temps en fait.
Sinon, pour essayer d'avoir de la chance, on peut parcourir la zone avec un index qui se balade en parcourant tout.
i = (i + step) % 4000000
En moyenne on va mettre pareil que si on ne sait pas où est la ligne, mais on tape au milieu dès le début et comme la probabilité que l'auteur n'ait pas mis sa ligne proche du bord, pour empêcher la force brute, est assez élevée, on a plus de chance d'avoir de la chance.
De l'autre côté (lignes croissantes de 0 à 4000000) ça prend 1min11s, et bien sûr on a le même résultat.
Avec un step de 747319 (nombre premier, donc premier avec 4000000, choisi au pif), je trouve le résultat en 49 secondes, assez proche de la moitié de la recherche totale (
(1m11s+19s)/2=45s
).# Force Brute.
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 15. Évalué à 2. Dernière modification le 15 décembre 2022 à 10:37.
Soyons honnêtes, le premier exercice, je l'ai bourriné en force brute.
Objectif : soit une ligne donnée, trouver le nombre de cases qui ne contiennent pas de balises.
Donc les cases visibles par une robot-senseur quelconque, moins les balises sur la ligne (piège, haha !).
Je suis tombé dans un autre piège : il faut scanner la ligne 2 000 000, mais pour l'exemple (pour valider le code) il faut scanner la ligne 10. Mais bon, la réponse pour la ligne 10 du problème complet, c'pas la réponse attendue, bref…
La méthode bourrine :
* pour chaque robot-senseur qui voit la ligne donnée :
* faire un set() des cases vues
set(range(début, fin))
;* union des sets() ;
* compter sa taille ;
* lister pour chaque robot-senseur sa balise, si elle est sur la bonne ligne ;
* supprimer les balises trouvées.
Ça marche en 1,25 secondes sur les données réelles, le résultat étant de 5838453 on a quand même fait un set-comprehension en double boucle d'une taille non négligeable.
La rumeur comme quoi Python c'est lent, c'pas toujours vrai hein, ya aucune optimisation dans mon code.
Pour l'exercice 2, la méthode bourrine est hors de question.
Parce que sinon, mon PC serait toujours en train de calculer là.
Et l'énergie coûte plus cher que mon temps de cerveau disponible.
Optimisé, ça prend quand même 19 secondes, le ventilo a le temps de décoller.
[^] # Re: Beaucoup de temps pour animer et afficher joli
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 14. Évalué à 2.
[^] # Re: Beaucoup de temps pour animer et afficher joli
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 14. Évalué à 2.
Au passage, les images sont générées comme un bourrin :
Yth.
[^] # Re: Beaucoup de temps pour animer et afficher joli
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 14. Évalué à 2. Dernière modification le 14 décembre 2022 à 16:01.
Et maintenant, on allume le cerveau :
Pour l'exercice 2, la base se calcule trivialement : le sable formant une pyramide, on sait qu'il va de 500-hauteur à 500+hauteur, vu qu'on a 174 de haut (de 0 à 173), la coursive est en 174, et le sol en 175, le sable s'entasse donc de 326 à 674, et le sol doit s'étendre une case plus loin : de 325 à 675, comme « triché » dans mon code, sauf que ça se calcule de façon sûre avec d'autres données en entrée.
Pour l'exercice 2 encore, et suivant la remarque de Tanguy sur les zones protégées par les rochers pour calculer des surfaces :
On va créer des cases « dark » sous les lignes.
Une ligne de
(x1, y1)
à(x2, y2)
avecx1<=x2
va générer une ligne protégée de gauche à droite de(x1+1, max(y1, y2))
à(x2-1, max(y1, y2))
, donc six1+1>x2-1
(ça arrive quandx1==x2
, ligne verticale, ou quand la ligne horizontale fait 2 de large :x2=x1+1
) on ne met rien.Après on peut filtrer les cases bouchées (dark et rocher) sur la zone de pyramide de sable, c'est à dire quand
500-y <= x <= 500+y
pour chaque élément. Ici on ne supprime rien, donc on n'a pas à gérer d'éventuels effets de bord, avec une plateforme qui dépasse de la pyramide de sable et peut protéger une zone qui serait ensevelie si la source du sable était plus haute.La taille de la pyramide est, en prenant le triangle de droite et en le posant retourné au dessus du triangle de gauche, un carré de la hauteur totale, soit
175^2 = 30625
grains potentiels.Ici ça ne suffit pas : un mur vertical sous une plate-forme va protéger une zone. Donc il faut ne pas réduire la ligne sur un côté si on a un rocher juste là.
Les données en entrée ne sont pas collaboratives, donc en fait on essaie toujours d'élargir la plate-forme qu'on considère pour la zone protégée du dessous, sur la gauche et la droite, puis on protège la ligne en dessous en retirant un élément à gauche et un à droite.
-> Ça fonctionne, il faut juste faire très attention à protéger une ligne en dessous des derniers rochers, le niveau de la coursive, mais pas plus bas au niveau du sol et en dessous, en traitant les données en flux on n'a pas la taille de la zone, donc la position du sol, donc on doit élaguer après coup pour le décompte : tout ce qui est en
y < 175
.Voici l'image générée avec les rochers et les zones protégées en dessous :
Pour mon exemple, j'ai en zones protégées (rochers et dark) 1804 cases, donc 30625-1804 = 28821, c'est mon résultat !
Pour les deux exercices :
Quand le sable n'est pas en chute libre, il va s'empiler sur toutes les cases visiter, à terme, sauf à sortir du terrain de jeu pour l'exercice 1.
Donc on n'est pas obligé de faire tomber le sable grain par grain, mais on peut poser des couches, avec un algo récursif.
Il suffit de le faire prendre en remontant la récursion quand on a trouver où se poser en bas. Parce que si on ne trouve pas où se poser (exercice 1 uniquement), alors aucun grain suivant ne pourra se poser.
C'est beaucoup plus simple à mettre en œuvre pour l'exo 2 puisqu'un fil de sable trouvera toujours un endroit où s'arrêter, donc on peut remplir en descendant, et explorer à la fois à gauche et à droite en bas de chaque chute libre.
Pour l'exo 1, si on parcours normalement, qu'on pose les grains en remontant de la récursion et pas avant de descendre, et qu'on sort brutalement (exception python en haut de l'exploration) dès qu'on est au bout, on devrait avoir le résultat.
Je ne l'ai pas encore fait, il est tard, je devrais commencer ma journée de taf quand même :D
# Beaucoup de temps pour animer et afficher joli
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 14. Évalué à 4.
Parce que un truc de 351 * 175 dans le terminal c'est galère quand même…
Bref, j'ai perdu plein de temps à faire une animation pas trop lente (j'ai fini par exponentiellement sauter des images : j'affiche l'image 2n), et réussir à faire entrer ça proprement dans le terminal. Après coup j'ai réalisé qu'il suffisait d'afficher chaque grain de sable une fois calculé, au lieu de tout retracer… Dans un terminal… Diantre…
J'avais un bug débile aussi pour l'exo 2, comme je voulais un sol pas trop large pour l'affichage, j'ai essayé d'être intelligent, et ça n'a pas marché, j'ai fini par faire un affichage avec un sol pas très large, puis rajouter un sol très très large.
Après j'ai triché et j'ai juste mis le sol en dur aux bonnes dimensions pour tout afficher, une fois le résultat obtenu.
Deux belles images :
![Source : https://ythogtha.org/advent_of_code/aoc-2022-14-01.png Premier exercice](//img.linuxfr.org/img/68747470733a2f2f7974686f677468612e6f72672f616476656e745f6f665f636f64652f616f632d323032322d31342d30312e706e67/aoc-2022-14-01.png)
![Source : https://ythogtha.org/advent_of_code/aoc-2022-14-02.png Deuxième exercice](//img.linuxfr.org/img/68747470733a2f2f7974686f677468612e6f72672f616476656e745f6f665f636f64652f616f632d323032322d31342d30322e706e67/aoc-2022-14-02.png)
Et un code probablement trop complexe.
L'affichage déjà
Et le code en lui-même :
Il faut vachement zoomer arrière dans le terminal, après c'est écrit trop petit pour lire, mais on a une belle animation :)
[^] # Re: python, en trichant
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 13. Évalué à 3.
Ouais, j'ai essayé de faire un hack pour remplacer les chiffres seuls par des listes de chiffres, et après faire un json.loads() et juste comparer, en bricolant quelques trucs du genre on arrive à faire tourner les données de démo.
Pour faire court, c'est le premier exercice du calendrier où je n'ai pas fourni la bonne réponse du premier coup…
Après j'ai été moins « malin », et j'ai réussi…
[^] # Re: python, en trichant
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 13. Évalué à 2.
On peut faire un truc rigolo sur la partie travail, on garde packet et input() identiques, et on reste sur du générateur/itérateur jusqu'à la fin avec le sort :
[^] # Re: En Pypthon
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 13. Évalué à 2.
Ah, j'avoue, j'ai même pas imaginé deux secondes faire un vrai parsing des données :)
[^] # Re: python, en trichant
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 13. Évalué à 2.
J'ai un code équivalent, avec un peu plus de modélisation, mais sinon, c'est algorithmiquement identique :
Je n'ai pas songé à split("\n\n"), ça fait que j'ai une première partie qui bosse en flux, mais comme pour la seconde il faut trier, on est obligé d'avoir toutes les données chargées, change rien.
Et ma fonction de comparaison est très centrée sur l'exercice : a < b c'est True, a > b c'est False et a == b c'est None, ergo on poursuit. C'est plus propre de faire -1/0/1.
[^] # Re: Étoile
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 12. Évalué à 3.
Le rendu de mon paysage, en doublant la largeur pour faire moins écrasé.
Complètement Numénor oui.
[^] # Re: python et lib de graph
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 12. Évalué à 3.
Pour faire du joli on fait ça :
Et il faut mettre le terminal en grand, parce que sinon ça va faire très très moche et buggé !
On a une animation des cases en cours de visite, sur fond de montagne enneigée (dégradé noir en bas, et blanc en haut).
[^] # Re: python et lib de graph
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 12. Évalué à 2.
Ah, classe :)
J'ai rien de joli à montrer ce coup-ci.
Mais bon, journée présentiel au taf hier, trois heures dans la voiture, 4h en réunions, j'ai à peine eu le temps de bricoler une solution, en ayant réfléchi sur le trajet…
J'ai fait un parcours de graphe inventé à la volée : je n'ai jamais été fichu de retenir le moindre des algos de parcours que j'ai pu apprendre, alors je suis condamné à réinventer la roue !
J'ai des cases en entrée, je regarde pour chacune d'elles où elles peuvent aller (haut, bas, gauche, droite, si la différence de hauteur est bonne), et si je n'ai pas déjà été là (donc matrice des cases visitées avec distance au départ dedans).
Je note l'ensemble des cases nouvellement visitées, et j'itère sur cet ensemble.
Donc a priori inutile de stocker le score pour le retrouver et calculer la suite comme dans mon code plus bas : il suffit de compter les étapes.
Instinctivement, je me suis dis que ça pouvait grossir, et donc j'ai décidé de manger le problème par les deux bouts, donc j'explore en montant depuis "S" et en descendant depuis "E".
Je stocke des scores positifs en montant, et négatifs en descendant.
Si je rencontre une case visitée depuis l'autre bout (case négative si je monte ou positive si je descends), j'ai fait la liaison.
En pratique je peux m'arrêter là : si je suis en train de monter c'est étape*2+1, si je suis en train de descendre c'est étape*2+2.
Dans mon code j'additionne les valeurs absolues : la valeur que j'aurais dû mettre dans la case, et celle déjà présente, et j'ai mon résultat.
Pour l'exercice 2, comme je fournis déjà une liste de case par itération, il suffit de mettre comme liste de démarrage tout les "a" et le "S", vraiment rien à coder, la dernière ligne du programme et basta.
Ah, et j'ai aligné, je bosse sur un tableau à une dimension, au lieu d'une matrice.
Et les mouvements possibles ne sont pas (haut, bas, gauche droite) mais (-1, +1, -largeur, +largeur) et un mouvement doit être dans [0, taille[
Allez, trêve de blabla, code !