J'aime bien ça !
Déjà j'ai ajouté un certain nombre de paquet qu'on m'ont parut intéressants, et que parfois j'utilise au quotidien.
Et puis j'en récupère d'autres quand les mainteneurs tournent.
Et j'aime bien soutenir les gens qui viennent sur LinuxFR présenter leurs projets, je maintiens Glewlwyd, un système assez efficace de gestion d'authentification (Oauth2 etc.) présenté ici par son auteur Babelouest.
Certes, c'est pour Slackware, pas la distrib la plus répandue, mais les scripts sont parfaitement compréhensibles par n'importe quel mainteneur de n'importe quelle distrib : c'est du shell très standard, et basé sur un seul outil externe : makepkg qui prend un répertoire et en fait un paquet Slackware.
Donc c'est très facile de s'en inspirer pour faire un paquet sur une autre distribution. Je ne sais pas si ça se fait en pratique, mais ça m'arrive de regarder ce qu'il se passe chez ArchLinux quand j'ai un soucis, pour voir s'ils l'ont résolu ou comment.
Donc ajouter un jeu que je peux faire découvrir à mes enfants, en leur disant que c'est moi qui l'ai rendu disponible (oui, ils ont pas le choix pour le moment, ils sont sous Slackware, voilà), ça me fait plaisir :)
Ah, donc le cas inverse d'un Bangladais qui viendrait toucher un SMIC en France, et comme là-bas ça correspondrait à un salaire de ministre, il serait taxé à 45%, ce qui est ingérable ici.
Pour ta dernière question, c'est facile : si une telle loi passe, je pense surtout que le pays de destination va juste faire évoluer ses taxes pour prendre la part entière des 15%, et ne rien laisser au pays d'origine, rien à perdre, tout à gagner, et pour l'employé c'est pareil, voire plus simple puisque taxé à un seul endroit.
Dilemme moral résolu…
Et le salaire il ne dépend pas du niveau de vie du pays où tu travailles ?
Quand je lis 15%, je lis 15% moi.
Donc mettons un français part vivre par exemple au Bangladesh. Cette personne bosse localement, pour un salaire normal là-bas, donc absolument minuscule en France, bah sa taxe de 15% de son salaire ridicule, soit peu de choses, mais tout de même 15% rapport au niveau de vie local.
Que veux-tu faire de plus ou de différent ?
Quel cas poserait problème ?
La façon dont c'est utilisé. Pour faire du code sans code, construire des algorithmes complexes à base de modules maison, et de templating Jinja.
C'est devenu extraordinairement difficile de savoir comment fonctionne un playbook.
En plus certains rôles, certaines tasks, utilisent des variables d'environnement, définies très loin de là.
C'est du bricolage très éloigné de l'utilité normale d'ansible…
Je suis plus traumatisé par l'utilisation qui est faite que par ansible lui-même, mais j'en viens à haïr le yaml+jinja…
Je n'avais pas eu le temps de m'y mettre plus tôt, mais c'est chose faite, le slackbuild de Blupimania est prêt, et sera disponible dans le dépôt dès demain probablement.
Il a fallut taper un peu dessus, parce que la Slackware 15.0 a une version un poil trop ancienne de SDL2_image et SDL2_mixer.
Comme pour la dernière version de Planetblupi avec SDL2_ttf.
J'embarque les versions à jour dans le répertoire du jeu, recompilés pour l'occasion, et youplà.
C'est rigolo comme jeu, j'étais complètement passé à côté des blupis dans les années 90.
Flûte, mon beau-père est décédé d'Alzheimer et de son diabète alors qu'il venait de chopper le Covid qui n'a fait que l'achever.
Ma grand-mère court toujours à 96 ans.
Et le taux de mortalité dans ma commune, pourtant si caractéristique et si généralisable à l'ensemble du village planétaire, est resté stable.
Mes propres doses de vaccin n'ont pas été fichues de m'achever, malgré tous mes efforts !
Et je n'ai absolument aucune connaissance qui soit décédée depuis le Covid19 alors qu'elle était vaccinée, excepté mon beau-père sus-cité, alors que leur taux de vaccination reflète la moyenne nationale.
Je me vois dans l'extrême obligation de décorréler le vaccin de tous ces évènements perturbants, selon mon étude scientifiquement empirique, et je sais de quoi je parle, j'ai plusieurs diplômes post-bac, j'ai travaillé dans des labos de recherche, ma tante est médecin, mes parents ingénieurs, et mes frères et sœurs sont tous docteurs, et j'ai déjà gagné plusieurs fois à Pandémie, et ma fille fait du Triathlon, et je bois du thé.
Oui, ça fonctionne parce que le nombre de coupe est faible dans un problème plutôt grand (1 coupe pour 1000 arêtes), et que les coupes sont assez éloignées.
J'ai supposé que ça pouvait être le cas, et j'ai gagné.
Après j'ai eu la chance de prendre un sommet initial assez éloigné de mes coupes. Par hasard en fait parce que si on regarde l'algo, je prend le dernier sommet source défini dans les données.
Et j'ai pris celui là parce que je l'avais sous la main à la fin de l'analyse des données, donc c'était vraiment sans arrière pensée : lui ou un autre, qu'importe ?
Et en fait, ça m'aurait été très difficile de comprendre pourquoi l'algo bloque à un moment, quelle est la topologie du graphe, et pourquoi je ne peux plus avancer, et comment savoir comment avancer.
Parce que sur téléphone c'est pénible, difficile à lire, prise de tête. Si ça avait raté, j'aurais probablement dû partir sur une toute autre idée (une exploration en largeur, en notant la taille des liens possibles ? du brute force trop long probablement. D'autres simplifications, trouver des zones fermées et les réduire ? Récursivement ?), voire attendre d'enfin récupérer un ordinateur.
Après vérification, mon hack, au lieu de tout ajouter, pourrait ajouter 1 seul sommet au hasard parmi les sommets possibles.
Je tombe sur la solution, mais pas toujours pour le coup, en y allant au pif, je tombe parfois sur un mauvais chemin.
Je sais déjà que ça peut fonctionner, parce que ça fonctionne en les ajoutant tous, mais ça veut surtout dire qu'on peut brancher sur une exploration 1 par 1 de tous les sommets possibles, quand on coince avec l'algo de base, et faire une exploration.
On doit pouvoir avoir un algo capable de nous assurer qu'on trouve une solution.
Encore une fois, tout ça fonctionne parce qu'on sait qu'on a trois sommets à couper hein.
C'est un brin moche mais voilà, on peut retomber sur nos pieds.
Ah, et côté perfs, on est sous la seconde pour l'exécution en python.
Je ne suis pas sûr que ça aurait été beaucoup plus long si j'avais codé à l'arrache ma propre fonction pour les diviseurs, plutôt que d'utiliser sympy : on n'en calcule pas tant que ça, et au bout du compte les nombres ne sont pas si grands, avec de l'ordre de 200 diviseurs, et une racine carrée autour de 10 millions, ça se réduit assez vite, c'est pas vraiment là qu'on va perdre du temps.
Avec sympy c'est immédiat.
On perd probablement plus de temps à charger le module, from sympy import divisors prend un temps visible dans un shell python, ça doit être la majeure partie de la seconde qui part là-dedans !
Bien sûr, ici, je sais que j'ai un dx, dy et dz, et l'algorithme ne s'adapte pas à une éventuelle situation où on n'en n'aurait que deux sur trois, mais à part de forcer à faire du code plus propre, ça ne changerait pas grand chose à l'algorithme final qui n'utilise que dz et dx et valide le dy recalculé.
Et comme dit plus haut, je calcule un paquet de fois la solution à partir de toutes les parallèles en z, alors qu'une seule suffit.
Bref, un algo plus générique ne serait pas beaucoup plus complexe, il faudrait formaliser mieux.
Par contre si on n'a de parallèles que sur un seul axe, je coince a priori. Il faudrait essayer des valeurs possibles sur un autre axe, en supposant qu'elles ne soient pas trop grandes, ce qui est le cas puisque dx=-242, dy=-49, dz=209, donc en explorant depuis 0 en positif et négatif, on va mettre quelques centaines de tests pour trouver la solution.
Et c'est nettement pire si on n'a aucune parallèle sur aucun axe…
La force brute en essayant au pif des dx, dy et dz sans en connaître aucun, devrait permettre de tomber sur la solution en quelques dizaines de millions de tests, ce qui reste faisable, et probablement assez rapide (quelques minutes ? une heure max ?) sur un ordinateur moderne.
Ma solution est beaucoup plus rapide : 0,07s, donc assez négligeable devant le temps de démarrage de python.
Mais…
Je ne sais pas qu'elle fonctionne, je le constate.
Et ça exploite très fortement le fait qu'on ait trois liens à couper, sans cette information je ne sais pas quand m'arrêter, l'algo n'est plus du tout le même.
En gros je fais l'hypothèse que deux liens à couper ne sont pas proches (partageant un même sommet), et que je vais avoir un peu de chance.
Je pars d'un sommet, au pif, mais ça rate s'il s'agit d'un sommet d'une des arêtes à supprimer. Là je me dis que si je ne trouve pas de solution, je peux prendre un autre sommet au pif, normalement, au bout du 7è je suis certain d'avoir au moins essayé avec un sommet qui n'est pas dans une des arêtes à supprimer.
Là ça a fonctionné directement.
Je considère comme « exploré » toutes ses arêtes, et les sommets directement connectés.
Et j'itère :
* Je considère l'ensemble des arêtes liées à tous mes sommets, et pas déjà explorées.
* Je considère l'ensemble des nouveaux sommets accessibles via ces arêtes.
* Pour chacun de ces nouveaux sommets, si il est accédé par au moins deux des nouvelles arêtes, je l'ajoute.
* Et je reconstruit l'ensemble des arêtes explorées à partir des liens possibles entre mes sommets explorés.
* Il me reste un ensemble d'arêtes considérées, mais rejetées, et qui seront à nouveau considérées le coup d'après.
* Si je n'ajoute aucun nouveau sommet, j'ai a priori fini.
Normalement, si il n'y a pas deux arêtes à couper qui partagent un même sommet, je ne peux pas « traverser » ces arêtes avec mon algorithme.
Il se trouve que ça s'arrête très très vite sans donner de résultat, donc j'ai juste essayé un truc :
* Si l'ensemble des arêtes que je peux atteindre mais que je n'ai pas considérées n'est pas de taille 3, alors j'ajoute unilatéralement toutes les arêtes possibles : je ne suis pas allé assez loin, il faut que j'avance, et c'est la méthode la plus naïve pour avancer.
À noter que ça peut foirer si l'un de ces nouvelles arêtes et une des arêtes à couper.
Je n'ai pas regardé dans le détail, mais je pense que ce problème n'existe qu'au démarrage, il faudrait peut-être partir directement à deux arêtes de distance de mon sommet d'origine (la suite me prouvera que j'ai raison pour le démarrage, mais tort globalement).
Bref, ça a fonctionné puisqu'après mon algorithme s'est arrêté à trois arêtes accessibles mais mises de côté, et là on sait que c'est le bon résultat, pif paf, terminé.
L'algorithme mériterait bien plus de vérifications, et éventuellement une boucle sur un sommet de démarrage différent, jusqu'à tomber sur une solution.
Il faudrait au minimum identifier quand est-ce que j'ai besoin de mon hack pour avancer un peu plus loin dans le noir, peut-être faire une exploration en branches pour ajouter un sous-ensemble et tester, histoire de s'assurer qu'on va trouver un truc viable, ou tout explorer sans trouver.
Mais ça a fonctionné du premier coup.
On peut noter qu'il y a 1502 sommets et 3363 arêtes dans mes données, donc au final démarrer depuis un des sommets à éviter, ça serait surtout beaucoup de malchance, c'est la taille du problème qui m'a incité à tester cette approche, en me disant que j'avais plus de chance de tomber dans le « gras » du problème que pile là où il ne fallait pas.
J'ai cherché des simplifications, un peu, avant, comme de simplifier les triangles (A<->B<->C<->A), mais autant ça donne un peu quelque chose sur les données de test (on peut brute-forcer la recherche sans soucis : prendre trois arêtes et voir si on a coupé en deux), c'est inutile sur les données réelles, on simplifie de 42 arêtes, sur 3363 ça change rien.
Par contre, en nettoyant mon code, je vois que le « hack » sert trois fois : à 15 sommets à explorer (1ère itération, donc dès le début), à 54 sommets à explorer (3ème itération), puis à 217 sommets à explorer (345 déjà validés, 13ème itération !), et là on est quand même assez loin, on aurait très facilement pu mal tomber, sachant que le résultat arrive à 18 itérations.
Bilan, je dirais que j'ai plutôt eu de la chance avec mon sommet de départ…
Voilà le code nettoyé :
fromsysimportstdintest=stdin.isatty()r1,r2=(54,0)iftestelse(562912,0)t1,t2="Étape 1","Étape 2"ok,nok="\033[38;5;118m✓\033[0m","\033[38;5;196m✗\033[0m"data=(__doc__iftestelsestdin.read()).strip().splitlines()ex1=ex2=0nodes=set()flinks=set()fordindata:a=d.replace(":","").split(" ")nodes.update(a)s=a.pop(0)forbina:flinks.add(frozenset((s,b)))S=s# Soit S un sommet quelconquedefexplore(s,links):explinks={iforiinlinksifsini}expnodes={aforiinexplinksforaini}newnodes=expnodes.difference([s])print(expnodes,explinks,newnodes)i=0whilenewnodes:i+=1newlinks={iforiinlinksifi.intersection(expnodes)}.difference(explinks)exploring=[_foriinnewlinksfor_iniif_notinexpnodes]newnodes={iforiinexploringifexploring.count(i)>1}expnodes.update(newnodes)explinks.update(iforiinlinksifi.issubset(expnodes))# Hack when stopping too early: adding everything linkedifnotnewnodesandlen(newlinks.difference(explinks))>3:newnodes=set(exploring).difference(expnodes)expnodes.update(newnodes)print(f"{i}# newlinks[{len(newlinks)}], exploring[{len(exploring)}], newnodes[{len(newnodes)}], expnodes[{len(expnodes)}], explinks[{len(explinks)}]")print(f"{i}# newlinks[{len(newlinks)}], exploring[{len(exploring)}], newnodes[{len(newnodes)}], expnodes[{len(expnodes)}], explinks[{len(explinks)}]")returnexpnodes,newlinks.difference(explinks)a,b=explore(S,flinks)iflen(b)!=3:print("ERROR, wrong result ahead")ex1=len(a)*(len(nodes)-len(a))
Pour une fois, mes expérimentations téléphoniques pour coder moins et avoir de la chance rapidement, ont portées leurs fruits, j'étais le premier surpris :)
Mais c'est rude de faire du code aussi approximatif, et de s'en contenter au bout du compte, ça heurte vraiment ma façon de penser.
Enfin, c'est pour ça que j'ai validé cette étoile avant la seconde du jour précédent.
C'est celui qui m'a le plus gonflé sur téléphone.
Pas la partie 1 bien sûr, encore expédiée assez vite dès que je m'y suis mis (c'est à dire une fois le jour précédent terminé).
La partie 2.
Où les données de test laissent entrevoir plein de simplifications qui ne fonctionnent pas avec le vrai problème.
Et une résolution finale qui ne fonctionne pas sur les données de test !
J'ai assez modélisé mes trajectoires de grêlon, pour faire des opérations en masse, je cherchais des simplifications, des translations, pivots, etc, mais je n'ai jamais réussi à résoudre autre chose que les données de test comme ça : à chaque fois il fallait tester au moins un paramètre final, et le plus complexe à tester a au final une valeur de 57 milliard et quelques au minimum, donc on ne va pas l'atteindre comme ça, en cherchant…
C'est le temps nécessaire à notre caillou pour atteindre un élément.
On tombe pas dessus par hasard.
Dans les données de test, c'est 1, ça simplifie grandement le problème.
En fait, il faut comprendre le problème.
On choisit un point d'origine et une trajectoire : Traj(x=393358484426865.0, y=319768494554521.0, z=158856878271783.0, dx=-242, dy=-49, dz=209)
À partir de là on choisit des entiers, grands, ça va de quelques dizaines de milliards à probablement mille milliards (j'ai un 943 538 374 225 pour un grêlon), ça définit des points de départ sur notre trajectoire.
De chacun de ces points on choisit une direction, et on fait reculer notre grêlon du temps nécessaire à atteindre le point en question.
Voilà, on a notre problème posé, on oublie la trajectoire initiale, il faut la retrouver.
Facile à construire, pas simple à démêler…
Et franchement, il faut trouver des simplifications.
Et là on les trouve avec une première constatation : ce qui se passe en x, y et z est presque entièrement décorrélé, pour trouver dx, dy ou dz, on n'a besoin de se concentrer que sur la coordonnée en question. Après on fera une corrélation sur l'écart en temps entre deux grêlons, qu'on peut connaître pour dx, dy ou dz, et qui sera donc égale pour les autres, et permet de faire une triangulation.
Et une seconde constatation, sur un axe on a des grêlons parallèles, c'est à dire qui ont le même dx, le même dy ou le même dz.
Et ça va nous aider.
C'est même la seule simplification que j'ai trouvé pour réussir à résoudre ce problème.
Parce que si entre deux grêlons on a un dx identique, ça veut dire que l'écart en x entre ces deux grêlon est une constante.
Et donc qu'on parcourt cette écart avec un nombre entier d'étapes, chacune d'un nombre entier de décalages.
Donc pour deux grêlons a et b parallèles en x, donc a.dx==b.dx, on a que l'écart en x (a.x - b.x) est divisible par r.dx-a.dx ou r est notre trajectoire résultat à trouver. On cherche r.dx.
Et ben on va chercher les diviseurs de a.x - b.x, sans connaître le sens on va tous les prendre en positif ou négatif, on ajoute a.dx, et on a des valeurs possibles de r.dx.
Et on cherche les valeurs communes entre tous les éléments parallèles en x, on aura réduit drastiquement nos possibilités de r.dx.
En pratique, si on n'oublie pas de considérer les diviseurs en négatif ou positif (parce qu'on ne sait pas dans quel sens on va, on a juste deux grêlons au pif), on va trouver une seul valeur pour dx, dy et dz.
On a la direction parfaite de notre caillou !
Ça aurait pu rater, on aurait pu avoir des choix et devoir tester parmi ces choix lesquels seraient les bons, mais on sent que même si on en avait eu plusieurs, ça n'aurait pas été trop explosif, et si l'algo pour finir le boulot est pas trop pourri on pouvait tout tester.
Là, suite à une erreur de ma part, j'ai aussi pondu un algorithme capable de calculer dy si on connaît dx et dz !
Sauf que ça foirait, à cause de mon erreur, mais j'ai corrigé et poursuivi, en pratique je calcule la solution pour tous les grêlons parallèles deux à deux en x, et je valide cette solution en montrant qu'ils donnent tous le même résultat. Ça m'a permis de débugger et d'être absolument certain d'avoir le bon résultat au bout du compte.
En pratique, quand on a dx, dy, et dz, il suffit de prendre deux grêlons parallèles selon n'importe quel axe, et on va avoir la solution.
On calcule le nombre d'étapes (microsecondes) pour que notre caillou passe de l'un à l'autre, ce qui est facile si on a compris l'algorithme qui a permit de trouver les dx, dy et dz : on divise l'écart en x a.x-b.x par r.dx-a.dx qui sont connus.
Sachant le temps séparant ces deux chocs, on peut calculer l'écart en y ou en z, constaté parce que nos grêlons ne sont pas parallèles en y ou z, et ça va nous permettre de savoir de combien d'étapes dans le temps il faut remonter pour combler cet écart, et faire en sorte de bien percuter les deux grêlons, en x, y et z.
En pratique mon algorithme, que je n'ai pas simplifié, calcule dy à partir de la connaissance de dx et dz sur des grêlons parallèles en z, c'est pas trop compliqué une fois qu'on a le nombre d'étapes à remonter dans le temps, et on valide déjà qu'on trouve pour tous la bonne valeur de dy. Puis on fait remonter effectivement dans le temps notre caillou depuis sa percussion avec a pour trouver un point de départ.
J'ai juste validé que r.x était identique pour tous, mais tant que ce n'était pas le cas c'était que j'avais une erreur dans mes formules.
Les maths sont simples, mais prise de tête et il faut bien se torturer les neurones.
Au final je fais bien trop de calculs, qui me donnent tous le même résultat, heureusement, et ça prend moins d'une seconde malgré tout.
Voici donc le code, avec trop de méthodes inutilisées dans mes Trajectoires, et des noms de variable bien trop peu lisibles.
Heureusement le code n'est pas trop complexe, et reste a peu près lisible.
Il y a un hack au milieu pour les données de test, puisqu'on n'a pas assez de parallèles pour trouver dx, dy et dz, je force les valeurs, connues, pour valider la seconde partie de l'algorithme.
Mais ça aurait pu faire l'objet d'un développement intéressant pour valider sur un ensemble de valeurs possible, si on n'avait pas eu un dx, dy et dz unique à l'issue de la première partie.
Rendant nécessaire de tester plusieurs cas et de vérifier qu'on ait bien un même résultat. Ça aurait été immonde à débugger par contre…
J'ai tout de même utilisé sympy pour les diviseurs, pour le coup c'était quand même plus simple que de coder une fonction moi-même.
fromsysimportstdinfromdataclassesimportdataclassfromfunctoolsimporttotal_orderingfromsympyimportdivisorstest=Falsedata=stdin.read().strip().splitlines()ex1=ex2=0m0,m1=(7,27)iftestelse(200000000000000,400000000000000)@total_ordering@dataclass(frozen=True)classTraj:x:int=0y:int=0z:int=0dx:int=0dy:int=0dz:int=0@propertydefa(self):returnself.dy/self.dx@propertydefb(self):returnself.y-self.x*self.dy/self.dxdef__mul__(self,other):# t = (x-x0)/dx# y = y0+dy*(x-x0)/dx = a*x+b# b = y0-x0*dy/dx# a = dy/dx# x = (B-b)/(a-A)ifself.a==other.a:return0,0,-1,-1x=(other.b-self.b)/(self.a-other.a)y=self.a*x+self.breturnx,y,(x-self.x)/self.dx,(x-other.x)/other.dxdef__lt__(self,other):returnself.tzero<other.tzerodef__add__(self,n):returnTraj(self.x+self.dx*n,self.y+self.dy*n,self.z+self.dz*n,self.dx,self.dy,self.dz)def__sub__(self,other):returnTraj(self.x-other.x,self.y-other.y,self.z-other.z,self.dx,self.dy,self.dz)def__truediv__(self,other):returnTraj(self.x,self.y,self.z,self.dx-other.dx,self.dy-other.dy,self.dz-other.dz)def__neg__(self):returnTraj(-self.x,-self.y,-self.z,-self.dx,-self.dy,-self.dz)@propertydeftzero(self):return-self.z/self.dzifself.dzelse0# dataD=[Traj(*(int(x)forxinline.replace(" ","").replace("@",",").split(",")))forlineindata]# ex1fori,dinenumerate(D):forfinD[i+1:]:x,y,t,tt=d*fifx>=m0andx<=m1andy>=m0andy<=m1andt>0andtt>0:ex1+=1# ex2defcorrelate(trucs):dds=[d[0]fordintrucs]dds={dfordinddsifdds.count(d)>1}X={d:sorted(xfordx,xintrucsifd==dx)fordindds}Z={dx:{s*di+dxforx1inxfordiindivisors(x0-x1)forsin[1,-1]}fordx,(*x,x0)inX.items()}returnset.intersection(*Z.values())defrecorrelate(trucs,dx,dy,dz):dds=[d.dzfordintrucs]dds={dfordinddsifdds.count(d)>1}X={d:sorted((_for_intrucsif_.dz==d),key=lambdaf:f.z)fordindds}Y=[{"dy":(x0.y-x1.y-step0*(x0.dy-x1.dy))/step+x0.dy,"x0":x0,"x1":x1,"step":step,"xp":xp,"step0":step0,"src":Traj(x1.x-x1.dx*step0,x1.y-x1.dy*step0,x1.z-x1.dz*step0,dx,dy,dz)+step0,}for_,(*x,x0)inX.items()forx1inxforstepin[(x0.z-x1.z)/(dz-x0.dz)]ifstepforxpin[(x0.x-x1.x)-(dx-x0.dx)*step]forstep0in[xp/(x0.dx-x1.dx)]]returnY,{h["dy"]forhinY},{h["src"].xforhinY}PDX=correlate([(d.dx,d.x)fordinD])PDY=correlate([(d.dy,d.y)fordinD])PDZ=correlate([(d.dz,d.z)fordinD])print(PDX,PDY,PDZ)PDX,PDY,PDZ=(-3,1,2)iftestelse(PDX.pop(),PDY.pop(),PDZ.pop())Y,dys,xs=recorrelate(D,PDX,PDY,PDZ)print(Y)print(dys)print(xs)print(sorted(-h["step0"]forhinY))# This searches for a hailstone going parallel to our rock in one axis.# Turns out that won't be useful, but it could lead to an easy way for initial position# for d in D:# if d.dx == PDX or d.dy == PDY or d.dz == PDZ:# print(d)T=Y[0]["x1"]R=Y[0]["src"]print(R)ex2=R.x+R.y+R.zr1,r2=(2,47)iftestelse(16779,871983857253169)print(f"{'ok' if ex1 == r1 else 'nok'}: {ex1}")print(f"{'ok' if ex2 == r2 else 'nok'}: {ex2}")
J'ai pas trop nettoyé le code hein.
Et dans la version téléphone, j'utilise s et o au lieu de self et other dans la classe Traj (qui ne va quand même pas s'appeler Trajectory non plus, trop long…), tout pour écrire le moins possible !
Pour moi, les ennuis ont commencés : pas d'ordinateur, pas de clavier, juste mon petit téléphone qui ne permet pas vraiment de voir les données avec du recul, et l'extrême pénibilité de coder avec un clavier tactile, toujours à basculer pour chercher les chiffres, les opérations, les =, :, les (), [] et {}.
Bref, pénible, donc on code avec des variables à une ou deux lettres, on fait les algos les plus courts à écrire, et on tâtonne.
La première partie reste assez simple, je n'ai pas mis bien longtemps et le temps de calcul sur téléphone est assez ridicule.
Pour la seconde j'ai tenté de laisser tourner des heures avec l'algo brute-force bête et méchant, mais à part flinguer la batterie on n'arrive pas à grand chose, soyons honnêtes.
Donc être malins.
Et là je l'ai pas été, j'ai tout de suite tenté de réduire le problème aux nœuds d'exploration : les cases où il y a 3 ou 4 directions possibles, et je note les distances entre ces nœuds, puis j'explore le graphe réduit des nœuds.
Sauf que j'ai cru ce problème trop complexe pour mon téléphone, et cherché à simplifier : trouver des nœuds qui sont des passages obligés.
J'étais encouragé par le fait qu'il y en a dans les données de test.
Ça veut dire qu'on peut découper le graphe simplifié en plusieurs graphes qui s'enchaînent.
Donc je code, je débugge, ça marche, je lance sur les données réelles, il me laisse avec comme seul noeud intermédiaire le noeud d'arrivée, et tout ça n'a servi à rien.
Sauf que la réponse tombe malgré tout sans trop d'attente, le problème réduit est suffisamment simple pour que la force brute s'en empare.
Ça met ~10s sur mon PC (avec pypy bien sûr, pour le coup), pas loin de 2 minutes sur le téléphone.
Je n'ai pas cherché plus loin, et j'ai juste remis le code au propre, en virant l'exploration inutile des nœuds intermédiaires, avant de le poster.
La première passe, sur la carte complète, permet aussi de lister les nœuds et la distance les séparant. Techniquement, il pourrait en manquer, puisque l'exploration se fait avec les contraintes de glissement, ça n'est pas le cas, j'ai misé sur cette simplification parce que la denrée qui me manquait vraiment c'était du temps pour coder correctement les choses.
Je me rappelle cependant avoir tenté plein de trucs et finalement avoir été déçu de la simplicité du bidule qui fournit finalement la solution, bref.
Au passage, j'utilise une pile de chemins en cours d'exploration, un deque() bien utile pour ça, plutôt qu'une fonction récursive, on fait exploser la limite de récursivité bien trop vite sur le téléphone. Donc j'ai une boucle et une FIFO d'états à faire avancer, c'est pas trop violent sur la RAM, et on n'atteint pas les limites.
Donc je commence, et j'ai pas fini, les codes dont je n'ai aucune réelle certitude de l'exactitude en toutes circonstances, ça sera pire dans les jours qui viennent.
fromsysimportstdinfromcollectionsimportdequedata=stdin.read().strip().splitlines()W=len(data[0])H=len(data)MAX=W*HM="".join(data)+"#"*WS=M.index(".")F=data[-1].index(".")+MAX-WD={"<":(-1,),">":(1,),"v":(W,),"^":(-W,),".":(1,-1,W,-W)}NODES={}defrexplore(start,end,nodes):"""Exploring full problem, storing path length between nodes A node is a crossroad in the maze : where 3 or 4 destinations are possible. Start and End are also nodes. """defnextpos(pos,previous):fordinD.get(M[pos],0):y=pos+dify>=0andynotinpreviousandM[y]!="#":yieldpos+dnodes[start]={}nodes[end]={}stack=deque()# Current exploring position, [previous positions leading there], last node visitedstack.append((start+W,[start],start))whilestack:x,path,last=stack.pop()yy=list(nextpos(x,path+[x]))ifx==endorlen(yy)>1:# We are on a nodeifxnotinnodes:nodes[x]={}nodes[last][x]=max(nodes[last].get(x,0),len(path)-path.index(last))nodes[x][last]=nodes[last][x]last=xifx==end:# End of the path, yielding ityieldpathcontinueforyinyy:# following all available pathsstack.append((y,path+[x],last))ex1=max(len(q)forqinrexplore(S,F,NODES))defexplore2(start,end):"""Dumb exploration of node graph Small enough that brute-force wins the day fast enough (~10s) """stack=deque([(start,[],0)])whilestack:pos,path,score=stack.pop()ifpos==end:yield(score,path)continuefornode,valin[_for_inNODES[pos].items()if_[0]notinpath]:stack.append((node,path+[pos],score+val))ex2,P=max(explore2(S,F))
Quand je code en Python, ya pas photo, c'est emacs le meilleur IDE.
Quand je code en C, les IDE sont majoritairement équivalents, man est mon principal ami, donc c'est mon shell le plus utile.
Quand je code en ansible, de toute façon, quel que soit l'IDE, je souffre, et mon principal allié est de ne pas avoir internet, ni de jeu vidéo installé sur ma machine, histoire de bien me contraindre à avancer, faut aussi que je décharge complètement mon téléphone, et que j'oublie le câble USB ailleurs, sinon ça avance pas.
Quand je code en JS… Ah, non, j'ai arrêté ça, le PHP aussi.
Bref, je suis pas prêt de lâcher mon emacs, en vrai.
C'est le dernier jour où je vais avoir le temps de la faire, la suite ça sera peut-être dans une semaine…
J'ai inventé un algo un peu tordu, assez efficace, rude à piger, donc à débugger.
Déjà les coordonnées sont en 1 dimension : x+y*10+z*100, on va simplifier, surtout qu'on ne fait que des mouvements vers le bas, aucun test aux bornes à faire.
J'ajoute un bloc de 10x10 en 0 pour poser le bazar.
Une structure de Blocs assez modélisée, une autre pour l'Univers bien plus simple et à la fin un algo tordu.
fromsysimportstdinfromfunctoolsimporttotal_orderingfromcollectionsimportdequefromitertoolsimportchaindata=deque(stdin.read().strip().splitlines())@total_orderingclassBloc:def__init__(self,blocdef=None,blocname=None,cubes=None):self.name=blocnameifcubes:self.cubes=cubesself.alt=min(cubes)//100returnx,y,z=zip(*((int(__)for__in_.split(","))for_inblocdef.split("~")))self.cubes={a+b*10+c*100forainrange(min(x),max(x)+1)forbinrange(min(y),max(y)+1)forcinrange(min(z),max(z)+1)}self.alt=min(z)def__iter__(self):forpinself.cubes:yieldpdef__eq__(self,o):returnself.alt==o.altdef__lt__(self,o):returnself.alt<o.altdef__contains__(self,_):return_inself.cubesdef__repr__(self):returnf"Bloc#{self.name}({self.cubes})"def__neg__(self):alt=min(_//100for_inself.cubes)*100-100returnBloc(blocname=self.name,cubes={alt+_%100for_inself.cubes})def__pos__(self):alt=max(_//100for_inself.cubes)*100+100returnBloc(blocname=self.name,cubes={alt+_%100for_inself.cubes})def__sub__(self,x):self.cubes={_-100*xfor_inself.cubes}classUniverse:def__init__(self):self.zone=set(range(100))self.blocs={}def__contains__(self,_):# True if bloc can be placed in universereturnnotself.zone.intersection(_.cubes)defadd(self,_):self.zone.update(_)forpin_:self.blocs[p]=_.namedata.extendleft(["0,0,0~9,9,0"])blocs=sorted(Bloc(line,i)fori,lineinenumerate(data))ground=blocs.pop(0)universe=Universe()universe.add(ground)forblocinblocs:while-blocinuniverse:bloc-1universe.add(bloc)# Blocs under each blocdown={bloc.name:{universe.blocs[p]forpin-blocifpinuniverse.blocs}forblocinblocs}cannot={blocfor_indown.values()iflen(_)==1forblocin_}.difference({0})ex1=len(blocs)-len(cannot)
Et l'exercice 2, prenez peur !
topof={}partial={}forblocinsorted(blocs,reverse=True):name=bloc.nameifnamenotintopof:topof[name]=set()# Handling partially supported blocksmypartial=partial.pop(name,set())ifmypartial:replay=Truewhilereplay:replay=Falsenewpart=set()# All blocs partially supported elsewhereotherpart=set(chain.from_iterable(vfork,vinpartial.items()ifknotintopof[name]))for_inmypartial:if_notinotherpart:# That bloc isn't supported by someone else elsewhere, it is mine!topof[name].add(_)topof[name].update(topof.get(_,[]))replay=True# We'll have to restart the search here, because the world changed.else:newpart.add(_)mypartial=newpartifmypartial:partial[name]=mypartial# Sending down my informationsup=topof.get(name,set()).union({name})downward=list(down.get(name,[]))iflen(downward)==1:# Supported by only one other bloc, sending what I'm actively supportingtopof[downward[0]]=topof.get(downward[0],set()).union(up)# Sending known partial information downforblocindownward:partial[bloc]=partial.get(bloc,set()).union({name}).union(partial.get(name,{}))partial.pop(name,None)ex2=sum(len(topof[bloc])forblocincannot)
J'ai pas vraiment le temps de remettre au propre, en gros je pars du haut, et je « pose » les blocs les uns sur les autres, en notant ceux qui sont partiellement posés, et où.
Et puis à chaque bloc, j'essaie de simplifier par ceux qui ne sont partiellement posés plus que sur lui.
Et… bah ça marche, en tapant bien sur le code.
Ah non, on manipule des chiffres ou des lettres, réunis en ensembles, en listes, en dictionnaires.
Parfois on peut représenter ce qu'il se passe, parfois pas trop.
Et on doit faire gaffe à pas trop demander de calculs à la machine, sinon ça peut prendre des mois.
On va dire qu'un « low pulse » est un 1, et un « high pulse » un 0.
C'est plus simple pour comprendre.
Le button envoie un 1 quand on appuie dessus.
Le broadcaster transmet ce qu'il a reçu à toutes ses destinations.
Les noms simples, en deux lettres, sans cadre, sont des alternateurs, s'ils reçoivent un 1, ils envoient une fois un 1, et une fois un 0. Mais s'ils reçoivent 0 ils bougent pas.
À l'état initial ils enverront un 0 au premier 1 reçu.
Donc notre broadcaster étant relié à des alternateurs, au repos il ne se passe rien, mais quand on appuie sur le gros bouton rouge, il active les quatre alternateurs devant lui.
Les noms dans les cadres sont des boîtes de remise à zéro, en gros.
Au début elles sont configurées sur 1 à toutes leurs entrées, mais c'est mis à jour dès qu'elles reçoivent un truc.
Si toutes leurs entrées sont à 0, alors elles envoient un 1 à toutes leurs sorties ! Sinon, c'est un 0, qui sera ignoré par tous les alternateurs connectés. D'où le nom de boîte de remise à zéro, ça ne va envoyer 1 aux alternateurs que quand ça reçoit du 0 de partout à la fois !
Quand ça arrive, les boîtes à droites reçoivent un 1 et donc envoient un 0, sinon elles reçoivent un 0 et envoie un 1.
Avec une seule entrée, ce sont des inverseurs.
Donc quand nos grosses boîtes s'activent et réussissent à envoyer un 1, le signal est inversé en 0 vers la boîte finale.
Si toutes les quatre grosses boîtes envoient un 1 en même temps, alors la boîte finale reçoit quatre 0.
À ce moment là elle va envoyer un 1 vers rx, qui est notre module de sortie et qui n'attends que ça !
Franchement, une fois représenté comme ça, le problème il est hyper clair hein ?
Faut trouver le moment où chacune des grosses boîte s'active.
Là, on a grosso-modo tous fait une simulation : on part de l'état initial, chaque alternateur va envoyer un 0, et les grosses boîtes sont sur 1 dans toutes leurs entrées, et on appuie sur le gros bouton rouge, jusqu'à ce que les boîtes s'activent.
Là on note quand c'est arrivé.
Typiquement on va continuer pour voir quand ça va se produire à nouveau, pour chaque boîte, et essayer de déduire un schéma.
Ici c'est facile, en fait, dès la première fois que ça s'active, on a fait un cycle et c'est retour à l'état initial, en fait pas tout à fait, mais au moins ça boucle sur la même durée.
On a donc 4 cycles, il ne reste plus qu'à les coordonner, savoir quand est-ce qu'ils vont s'activer tous ensemble.
Et le plus petit multiple commun aux quatre valeurs mesurées est notre réponse.
Maintenant en poussant l'analyse.
Notre série par exemple de la première boîte, consiste en 12 alternateurs, tous éteints donc prêts à envoyer 0.
On va noter ça 000000000000.
La boîte n'enverra absolument rien tant qu'on ne l'aura pas activée (enfin, elle envoie des 0 qui sont ignorés par les alternateurs).
Si on appuie, le premier va s'allumer, et envoyer 0, qui va être ignoré, on est donc dans cette situation : 100000000000.
Au second coup, notre premier alternateur va s'éteindre, repasser à 0, mais aura envoyé un 1 à droite, sur le second, qui va s'allumer et envoyer 0 qui sera ignoré. 01000000000
Au 3ème coup, on rallume le premier, rien d'autre ne bouge : 110000000000.
4 : 0010000000
5 : 1010000000
6 : 0110000000
7 : 1110000000
Ok peut continuer la simulation, mais il apparaît comme évident qu'on est en train de compter. On a exactement la représentation binaire, mais de gauche à droite, des numéros des étapes.
Là on va regarder notre boîte nl, et constater qu'elle va s'activer dès qu'elle reçoit 0 en même temps de la part de hd, rh, tg, qz, rl, pf et pr, ce qui va arriver quand il vont tous s'être allumés (passer de 0 à 1) comme dernière action.
Ça arrive dès qu'on a 1 sur chacun d'entre eux, et 0 sur les autres, c'est la première fois où ça va se produire et c'est cette configuration : 101001001111 qu'on retourne en 111100100101 pour avoir le chiffre binaire 3877, qu'on retrouve bien dans mes résultats plus haut.
Pour les autres, on va simplement lire 111000001111 soit 3847, 110010111111 soit 4051, et enfin 101010110111 soit 3797.
Diantre c'est juste.
Là nos nombres sont premiers entre eux, donc le PPCM vaut la multiplication des 4 soit… beaucoup.
Mais bref, voilà le problème entièrement décortiqué, et finalement une lecture directe des chiffre à trouver, sans aucun calcul, sans besoin d'ordinateur, sauf pour le PPCM (c'est un peu misérable à la main avec des chiffres aussi gros quand même).
Merci de ta question Ysabeau, je n'aurais pas poussé autant sinon :)
Pour continuer un petit peu, sur notre exemple 1.
On active sur 101001001111 mais à ce moment là notre boîte ne se contente pas d'envoyer un 1 vers la sortie, elle envoie aussi un 1 vers tous nos 0 !
En effet, tous les alternateurs qui n'envoient pas vers la boîte, reçoivent de la boîte.
Ils sont éteints, ils vont donc s'allumer, envoyer des 0 qui seront ignorés et passer tous à 1 : 111111111111 = 4095.
Sauf que le tout premier reçoit lui aussi un 1, exactement comme si on avait appuyé sur le bouton une fois tout passé à 1 !
C'est hd, et il est bien en dernier de la liste des alternateurs activés par nl. On lui envoie un 1 qui va faire s'éteindre tous les alternateurs en chaîne, puisqu'ils envoient un 1 en s'éteignant. Ils vont donc tous avoir envoyé un 1 vers la boîte (ceux qui sont connectés) qui verra bien son état retourner à celui d'origine.
D'où la boucle et le cycle qui recommence exactement à zéro, on est effectivement retourné précisément à l'état initial.
On a compté de 0 à 3877, et au moment d'arriver à 3877, on a une remise à 0 avec un signal envoyé vers la sortie.
Alors j'ai rien compris à ton explication, mais je crois que je suis en train de tomber malade.
J'ai hyper galéré à débugger mon code, bourré de mauvaises bornes, jusqu'au bout du bout…
Bon, d'une façon ou d'une autre je n'ai pas fait comme toi.
Cf plus bas :)
Un problème bien bien pénible aujourd'hui, où il faut être très précis pour éviter les effets de bords.
encore une fois on « voit » des trucs dans les données, qui sont indispensables à la résolution…
On explore en damier, soit les cases noires (x+y pairs) soit les cases blanches (x+y impairs).
Une exploration type celle de l'exercice 1 que tout le monde a dû réussir, nous permet facilement de trouver le nombre de cases blanches et noires, chez moi c'est 7509 et 7566, ce qui additionné avec les rochers ne fait pas la taille du terrain, car il y a 4 cases inaccessibles (chez moi). Jusqu'ici tout va bien.
Comme tu l'as fait remarquer, on peut aller en ligne droite vers les répétitions du terrain, donc l'exploration d'une zone répétée autour de la zone de départ se fait le plus efficacement à partir du point d'entrée : le milieu du côté.
Pour les zones en diagonale, on va rentrer par la case au coin.
Ya pas plus rapide.
Le terrain fait 131x131, et le départ au centre en 65x65.
Donc on peut explorer indépendamment les différentes zones, en notant simplement le temps nécessaire à les atteindre. 65 + 1 + 131 * (distance - 1) quand on va en ligne droite nord, sud, est ou ouest.
Et 65 + 1 + 65 + 1 + 131 * (distance de Manhattan - 2) pour les cases qui sont au moins un peu en diagonale.
Bon, ya des +1, des +2, des -1, des -2, c'est les effets de bords ça.
On rentre au nord en 66 mouvements, et deux fois au nord en 66+131 mouvements, etc.
On rentre au nord-ouest en 65+1+65+1 = 132 mouvements, et de là on se décale horizontalement ou verticalement par paquets de 131.
On sait donc rapidement combien d'étapes il nous reste quand on entre dans une zone. Ça va être plein tout du long, et on va soit valider les cases noires, soit les cases blanches, en alternance.
Ben oui, si on entre dans une zone mettons via (0, 0), la case (0, 0) d'une zone adjacente est à 131 mouvements, qui est un nombre impair, donc on ne l'atteint pas.
On a en fait un damier de damiers, yay !
Là on va donc simplement regarder combien d'étape il reste à parcourir, ou combien on en a parcouru, et choisir sans se tromper la bonne valeur entre noir et blanc.
On additionne.
En pratique, une exploration en distance de zone par rapport à celle du départ est assez simple : on a 4 zones directement en face de la zone de départ, et (distance -1) * 4 zones qui forment une diagonale, on a un joli losange.
...●.....●○●...●○●○●.●○●○●○●.●○●○●...●○●.....●...
En distance 0 on a la zone de départ.
En distance 1 on a 4 zones directement liées.
En distance 2 on a 4 zones directes, et 4 zones diagonales.
En distance 3 c'est 4 et 8.
En distance n, c'est 4 et (n-1)*4.
Il se trouve que tout le monde à une distance donnée est soit blanc, soit noir (blanc = on considère les cases blanches à l'intérieur de la zone, noir = on considère les cases noires).
Comme le nombre d'étape final est impair, on ne considère pas la case de départ, donc la case de départ sur mon schéma, dans une zone blanche, doit être noire.
Ceci nous amène presque au bout, parce que là on va commencer à avoir des zones qu'on n'explorera plus entièrement, à cause des pas restants, trop courts.
Dans mon code, je prends une marge suffisante, et je calcule les cases à partir des déplacements restants.
Mais c'est assez facile, j'ai 8 zones : nord, sud, est, ouest et nord-est, nord-ouest, sud-est, sud-ouest, chacune explorée à partir d'un point de départ spécifique.
Lors de l'exploration, je note pour chaque pas effectué les cases atteintes.
Donc il me suffit de regarder quelle distance je peux parcourir dans mon exploration, avec les déplacements restants, et je sais quelles cases sont atteintes.
Je dénombre, j'additionne.
Et comme pour le reste du problème, on a les 4 directions cardinales uniques, et les 4 directions diagonales répétées (distance - 1) fois, donc on calcule 8 valeurs, on multiplie 4 d'entre elles, on additionne et c'est ok.
On passe à la distance suivante.
On s'arrête avec une petite marge où on va additionner des zéros.
J'ai pas mal fait ça pour éviter d'être sûr de moi, vu que j'ai eu des quantités invraisemblables d'erreurs aux bornes…
Et puis, voilà, résultat :)
Ça permet aussi de résoudre l'exercice 1 avec le problème central, vu que pour chacune de mes zones, je ne regarde que ce qu'il se passe dedans, j'ai les infos pour le premier problème.
fromsysimportstdinfromdataclassesimportdataclassfromfunctoolsimportcached_propertydata=stdin.read().strip().splitlines()LARGEUR=len(data[0])# 131HAUTEUR=len(data)# 131XMAX=LARGEUR-1YMAX=HAUTEUR-1MIDDLE=XMAX//2# 65ROCKS=frozenset((x,y)fory,_inenumerate(data)forx,tinenumerate(_)ift=='#')START="".join(data).index("S")START=(START%LARGEUR,START//LARGEUR)# 65x65STEPS1,STEPS2=(64,26501365)@dataclassclassexploration:sx:int=0sy:int=0defrun(self):defdest(x,y):yield(x-1),yyield(x+1),yyieldx,(y-1)yieldx,(y+1)explored={(self.sx,self.sy)}exploring={(self.sx,self.sy)}steps=[{(self.sx,self.sy)}]overexplored=set()s=0whileexploring:s=s+1exploring={dforx,yinexploringfordindest(x,y)ifdnotinROCKS}.difference(explored).difference(overexplored)forx,yinexploring:if(x<0orx>=LARGEURory<0ory>=LARGEUR)and(x,y)notinoverexplored:overexplored.add((x,y))exploring.difference_update(overexplored)steps.append(exploring)# adds an empty set() at the endexplored.update(exploring)self._exploration=stepsself.even=self.explored(0,len(steps))self.odd=self.explored(1,len(steps))@cached_propertydefexploration(self):ifnothasattr(self,'_exploration'):self.run()returnself._explorationdefexplored(self,start=0,steps=None):steps=min(steps+1,len(self.exploration))returnsum(len(self.exploration[i])foriinrange(start,steps,2))exp1=exploration(*START)ex1=exp1.explored(STEPS1%2,STEPS1)
Voilà notre explorateur de zone, et la fonction explored qui retourne les cases explorées selon le parité (zone noire ou blanche), et le nombre de pas restant.
Pour le premier problème, on démarre en START = (65, 65) et on fait 64 pas, on a un damier pair puisque 64 est pair, donc en particulier la case de départ est prise en compte.
Pour le second problème on a une seconde exploration à faire. D'abord le paramétrage.
N=exploration(MIDDLE,0)S=exploration(MIDDLE,YMAX)E=exploration(XMAX,MIDDLE)W=exploration(0,MIDDLE)NE=exploration(XMAX,0)NW=exploration(0,0)SE=exploration(XMAX,YMAX)SW=exploration(0,YMAX)# nombre minimum de pas pour explorer entièrement n'importe quelle zone.MAXEXPLORATION=max(len(x.exploration)-1forxin[N,S,E,W,NE,NW,SE,SW])defbigexploration(x,y):bx=MIDDLE+1+LARGEUR*(abs(x)-1)by=MIDDLE+1+HAUTEUR*(abs(y)-1)bd=bx+byify==0:ifx>0:returnE,bxifx<0:returnW,bxreturnexp1,0elifx==0:ify>0:returnS,byreturnN,byifx>0andy>0:returnSE,bdifx>0andy<0:returnSW,bdifx<0andy>0:returnNE,bdreturnNW,bdFINESTEPS=STEPS2-MAXEXPLORATION*2odd=STEPS2%2score=exp1.oddifoddelseexp1.even
La fonction bigexploration retourne le type de zone, et le nombre de pas effectués, pour entrer dans la zone en (x, y) par rapport à celle de départ.
FINESTEPS c'est la distance à partir de laquelle on va vraiment compter les pas dans chaque zone. J'ai mis * 2 pour avoir de la marge et ne pas avoir à réfléchir aux effets de bords, mais je peux valider que simplement STEPS2 - MAXEXPLORATION fonctionne.
Après ça le code est moche et répétitif, dans l'esprit de bigexploration.
Et bigre, même le range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2) m'a causé 2h de prise de tête, j'avais oublié de ne pas commencer à 0, mais bien à 1, donc je comptais 5 fois la zone de départ, comme j'ai lutté pour trouver ça, rhaaa !
On vérifie l'intérêt de nos FINESTEPS avec les sorties :
On voit bien qu'on a les 4 sommets qui sont incomplets, et pour les diagonales on a deux couches de diagonales à considérer. Et à chaque fois, le résultat pratique dépend de la direction qu'on considère, parce que la distribution des rochers met le bazar.
C'est officiellement celui qui m'a le plus résisté jusqu'à présent, mais au final, l'algo était là assez rapidement, il était juste buggé de partout :(
Ah oui, le deque() permet de faire une FIFO de messages, on les empile à droite, on les dépile à gauche, on a fini quand c'est vide, d'où un code d'itération assez simple dans la fonction push().
C'était la minute structure de données pas encore vue cette année. Le deque() c'est une list() optimisée pour faire des ajouts/suppressions aux bouts, donc idéal pour des FIFO, LIFO et trucs du genre.
Ah, oui, c'est vrai ça, le résultat c'est le PPCM des 4 cycles, sauf qu'en l'occurrence ils sont premiers entre eux (enfin, chez moi en tout cas…), encore une propriété cachée dans les données, d'où la multiplication annoncée dans mon message !
J'ai testé vite fait la multiplication sur le site avant de lancer le PPCM, et ça a fonctionné, donc j'ai complètement oublié qu'il fallait faire ça pour être corrects.
[^] # Re: Illisible
Posté par Yth (Mastodon) . En réponse au lien L’impôt minimum mondial de 15 % est lancé. Évalué à 3.
Mais si l'impôt minimal mondial est de 15%, ça n'est pas aussi valable pour les gens qui travaillent et paient leurs impôts dans leur propre pays ?
[^] # Re: Slackbuild dans les tuyaux !
Posté par Yth (Mastodon) . En réponse à la dépêche Libération du jeu Blupimania. Évalué à 3.
J'aime bien ça !
Déjà j'ai ajouté un certain nombre de paquet qu'on m'ont parut intéressants, et que parfois j'utilise au quotidien.
Et puis j'en récupère d'autres quand les mainteneurs tournent.
Et j'aime bien soutenir les gens qui viennent sur LinuxFR présenter leurs projets, je maintiens Glewlwyd, un système assez efficace de gestion d'authentification (Oauth2 etc.) présenté ici par son auteur Babelouest.
Certes, c'est pour Slackware, pas la distrib la plus répandue, mais les scripts sont parfaitement compréhensibles par n'importe quel mainteneur de n'importe quelle distrib : c'est du shell très standard, et basé sur un seul outil externe : makepkg qui prend un répertoire et en fait un paquet Slackware.
Donc c'est très facile de s'en inspirer pour faire un paquet sur une autre distribution. Je ne sais pas si ça se fait en pratique, mais ça m'arrive de regarder ce qu'il se passe chez ArchLinux quand j'ai un soucis, pour voir s'ils l'ont résolu ou comment.
Donc ajouter un jeu que je peux faire découvrir à mes enfants, en leur disant que c'est moi qui l'ai rendu disponible (oui, ils ont pas le choix pour le moment, ils sont sous Slackware, voilà), ça me fait plaisir :)
[^] # Re: Illisible
Posté par Yth (Mastodon) . En réponse au lien L’impôt minimum mondial de 15 % est lancé. Évalué à 3.
Ah, donc le cas inverse d'un Bangladais qui viendrait toucher un SMIC en France, et comme là-bas ça correspondrait à un salaire de ministre, il serait taxé à 45%, ce qui est ingérable ici.
Pour ta dernière question, c'est facile : si une telle loi passe, je pense surtout que le pays de destination va juste faire évoluer ses taxes pour prendre la part entière des 15%, et ne rien laisser au pays d'origine, rien à perdre, tout à gagner, et pour l'employé c'est pareil, voire plus simple puisque taxé à un seul endroit.
Dilemme moral résolu…
[^] # Re: Illisible
Posté par Yth (Mastodon) . En réponse au lien L’impôt minimum mondial de 15 % est lancé. Évalué à 3.
Et le salaire il ne dépend pas du niveau de vie du pays où tu travailles ?
Quand je lis 15%, je lis 15% moi.
Donc mettons un français part vivre par exemple au Bangladesh. Cette personne bosse localement, pour un salaire normal là-bas, donc absolument minuscule en France, bah sa taxe de 15% de son salaire ridicule, soit peu de choses, mais tout de même 15% rapport au niveau de vie local.
Que veux-tu faire de plus ou de différent ?
Quel cas poserait problème ?
[^] # Re: le bit de poids faible
Posté par Yth (Mastodon) . En réponse au lien la manière la plus efficace de déterminer si un nombre est pair. Évalué à 3.
La façon dont c'est utilisé. Pour faire du code sans code, construire des algorithmes complexes à base de modules maison, et de templating Jinja.
C'est devenu extraordinairement difficile de savoir comment fonctionne un playbook.
En plus certains rôles, certaines tasks, utilisent des variables d'environnement, définies très loin de là.
C'est du bricolage très éloigné de l'utilité normale d'ansible…
Je suis plus traumatisé par l'utilisation qui est faite que par ansible lui-même, mais j'en viens à haïr le yaml+jinja…
[^] # Re: Journal franchement malhonnête !
Posté par Yth (Mastodon) . En réponse au journal J’ai tenté de libérer une habitation, mais l’ayant-droit nous a mis des bâtons dans les roues. Évalué à 4.
C'est pas vendu avec les frigos ça ?
De série ?
# Slackbuild dans les tuyaux !
Posté par Yth (Mastodon) . En réponse à la dépêche Libération du jeu Blupimania. Évalué à 5.
Merci pour ton nouveau portage Mathieu !
Je n'avais pas eu le temps de m'y mettre plus tôt, mais c'est chose faite, le slackbuild de Blupimania est prêt, et sera disponible dans le dépôt dès demain probablement.
Il a fallut taper un peu dessus, parce que la Slackware 15.0 a une version un poil trop ancienne de SDL2_image et SDL2_mixer.
Comme pour la dernière version de Planetblupi avec SDL2_ttf.
J'embarque les versions à jour dans le répertoire du jeu, recompilés pour l'occasion, et youplà.
C'est rigolo comme jeu, j'étais complètement passé à côté des blupis dans les années 90.
[^] # Re: Journal franchement malhonnête !
Posté par Yth (Mastodon) . En réponse au journal J’ai tenté de libérer une habitation, mais l’ayant-droit nous a mis des bâtons dans les roues. Évalué à 6.
Ouhlà, tu veux pas savoir comment elle les a tricotées ses sources !
[^] # Re: Ont-ils bien modélisé les milliers de morts dus à l'Hydroxychloroquine ?
Posté par Yth (Mastodon) . En réponse au journal jeu libre Covid-25 !. Évalué à 8.
Flûte, mon beau-père est décédé d'Alzheimer et de son diabète alors qu'il venait de chopper le Covid qui n'a fait que l'achever.
Ma grand-mère court toujours à 96 ans.
Et le taux de mortalité dans ma commune, pourtant si caractéristique et si généralisable à l'ensemble du village planétaire, est resté stable.
Mes propres doses de vaccin n'ont pas été fichues de m'achever, malgré tous mes efforts !
Et je n'ai absolument aucune connaissance qui soit décédée depuis le Covid19 alors qu'elle était vaccinée, excepté mon beau-père sus-cité, alors que leur taux de vaccination reflète la moyenne nationale.
Je me vois dans l'extrême obligation de décorréler le vaccin de tous ces évènements perturbants, selon mon étude scientifiquement empirique, et je sais de quoi je parle, j'ai plusieurs diplômes post-bac, j'ai travaillé dans des labos de recherche, ma tante est médecin, mes parents ingénieurs, et mes frères et sœurs sont tous docteurs, et j'ai déjà gagné plusieurs fois à Pandémie, et ma fille fait du Triathlon, et je bois du thé.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 25. Évalué à 2.
Oui, ça fonctionne parce que le nombre de coupe est faible dans un problème plutôt grand (1 coupe pour 1000 arêtes), et que les coupes sont assez éloignées.
J'ai supposé que ça pouvait être le cas, et j'ai gagné.
Après j'ai eu la chance de prendre un sommet initial assez éloigné de mes coupes. Par hasard en fait parce que si on regarde l'algo, je prend le dernier sommet source défini dans les données.
Et j'ai pris celui là parce que je l'avais sous la main à la fin de l'analyse des données, donc c'était vraiment sans arrière pensée : lui ou un autre, qu'importe ?
Et en fait, ça m'aurait été très difficile de comprendre pourquoi l'algo bloque à un moment, quelle est la topologie du graphe, et pourquoi je ne peux plus avancer, et comment savoir comment avancer.
Parce que sur téléphone c'est pénible, difficile à lire, prise de tête. Si ça avait raté, j'aurais probablement dû partir sur une toute autre idée (une exploration en largeur, en notant la taille des liens possibles ? du brute force trop long probablement. D'autres simplifications, trouver des zones fermées et les réduire ? Récursivement ?), voire attendre d'enfin récupérer un ordinateur.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 25. Évalué à 2.
Après vérification, mon hack, au lieu de tout ajouter, pourrait ajouter 1 seul sommet au hasard parmi les sommets possibles.
Je tombe sur la solution, mais pas toujours pour le coup, en y allant au pif, je tombe parfois sur un mauvais chemin.
Je sais déjà que ça peut fonctionner, parce que ça fonctionne en les ajoutant tous, mais ça veut surtout dire qu'on peut brancher sur une exploration 1 par 1 de tous les sommets possibles, quand on coince avec l'algo de base, et faire une exploration.
On doit pouvoir avoir un algo capable de nous assurer qu'on trouve une solution.
Encore une fois, tout ça fonctionne parce qu'on sait qu'on a trois sommets à couper hein.
C'est un brin moche mais voilà, on peut retomber sur nos pieds.
[^] # Re: Pas de Z3, mais au moins Z^3 neurones grillés
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 24. Évalué à 2. Dernière modification le 03 janvier 2024 à 10:46.
Ah, et côté perfs, on est sous la seconde pour l'exécution en python.
Je ne suis pas sûr que ça aurait été beaucoup plus long si j'avais codé à l'arrache ma propre fonction pour les diviseurs, plutôt que d'utiliser sympy : on n'en calcule pas tant que ça, et au bout du compte les nombres ne sont pas si grands, avec de l'ordre de 200 diviseurs, et une racine carrée autour de 10 millions, ça se réduit assez vite, c'est pas vraiment là qu'on va perdre du temps.
Avec sympy c'est immédiat.
On perd probablement plus de temps à charger le module,
from sympy import divisorsprend un temps visible dans un shell python, ça doit être la majeure partie de la seconde qui part là-dedans !Bien sûr, ici, je sais que j'ai un dx, dy et dz, et l'algorithme ne s'adapte pas à une éventuelle situation où on n'en n'aurait que deux sur trois, mais à part de forcer à faire du code plus propre, ça ne changerait pas grand chose à l'algorithme final qui n'utilise que dz et dx et valide le dy recalculé.
Et comme dit plus haut, je calcule un paquet de fois la solution à partir de toutes les parallèles en z, alors qu'une seule suffit.
Bref, un algo plus générique ne serait pas beaucoup plus complexe, il faudrait formaliser mieux.
Par contre si on n'a de parallèles que sur un seul axe, je coince a priori. Il faudrait essayer des valeurs possibles sur un autre axe, en supposant qu'elles ne soient pas trop grandes, ce qui est le cas puisque
dx=-242, dy=-49, dz=209, donc en explorant depuis 0 en positif et négatif, on va mettre quelques centaines de tests pour trouver la solution.Et c'est nettement pire si on n'a aucune parallèle sur aucun axe…
La force brute en essayant au pif des dx, dy et dz sans en connaître aucun, devrait permettre de tomber sur la solution en quelques dizaines de millions de tests, ce qui reste faisable, et probablement assez rapide (quelques minutes ? une heure max ?) sur un ordinateur moderne.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 25. Évalué à 2.
Ma solution est beaucoup plus rapide : 0,07s, donc assez négligeable devant le temps de démarrage de python.
Mais…
Je ne sais pas qu'elle fonctionne, je le constate.
Et ça exploite très fortement le fait qu'on ait trois liens à couper, sans cette information je ne sais pas quand m'arrêter, l'algo n'est plus du tout le même.
En gros je fais l'hypothèse que deux liens à couper ne sont pas proches (partageant un même sommet), et que je vais avoir un peu de chance.
Je pars d'un sommet, au pif, mais ça rate s'il s'agit d'un sommet d'une des arêtes à supprimer. Là je me dis que si je ne trouve pas de solution, je peux prendre un autre sommet au pif, normalement, au bout du 7è je suis certain d'avoir au moins essayé avec un sommet qui n'est pas dans une des arêtes à supprimer.
Là ça a fonctionné directement.
Je considère comme « exploré » toutes ses arêtes, et les sommets directement connectés.
Et j'itère :
* Je considère l'ensemble des arêtes liées à tous mes sommets, et pas déjà explorées.
* Je considère l'ensemble des nouveaux sommets accessibles via ces arêtes.
* Pour chacun de ces nouveaux sommets, si il est accédé par au moins deux des nouvelles arêtes, je l'ajoute.
* Et je reconstruit l'ensemble des arêtes explorées à partir des liens possibles entre mes sommets explorés.
* Il me reste un ensemble d'arêtes considérées, mais rejetées, et qui seront à nouveau considérées le coup d'après.
* Si je n'ajoute aucun nouveau sommet, j'ai a priori fini.
Normalement, si il n'y a pas deux arêtes à couper qui partagent un même sommet, je ne peux pas « traverser » ces arêtes avec mon algorithme.
Il se trouve que ça s'arrête très très vite sans donner de résultat, donc j'ai juste essayé un truc :
* Si l'ensemble des arêtes que je peux atteindre mais que je n'ai pas considérées n'est pas de taille 3, alors j'ajoute unilatéralement toutes les arêtes possibles : je ne suis pas allé assez loin, il faut que j'avance, et c'est la méthode la plus naïve pour avancer.
À noter que ça peut foirer si l'un de ces nouvelles arêtes et une des arêtes à couper.
Je n'ai pas regardé dans le détail, mais je pense que ce problème n'existe qu'au démarrage, il faudrait peut-être partir directement à deux arêtes de distance de mon sommet d'origine (la suite me prouvera que j'ai raison pour le démarrage, mais tort globalement).
Bref, ça a fonctionné puisqu'après mon algorithme s'est arrêté à trois arêtes accessibles mais mises de côté, et là on sait que c'est le bon résultat, pif paf, terminé.
L'algorithme mériterait bien plus de vérifications, et éventuellement une boucle sur un sommet de démarrage différent, jusqu'à tomber sur une solution.
Il faudrait au minimum identifier quand est-ce que j'ai besoin de mon hack pour avancer un peu plus loin dans le noir, peut-être faire une exploration en branches pour ajouter un sous-ensemble et tester, histoire de s'assurer qu'on va trouver un truc viable, ou tout explorer sans trouver.
Mais ça a fonctionné du premier coup.
On peut noter qu'il y a 1502 sommets et 3363 arêtes dans mes données, donc au final démarrer depuis un des sommets à éviter, ça serait surtout beaucoup de malchance, c'est la taille du problème qui m'a incité à tester cette approche, en me disant que j'avais plus de chance de tomber dans le « gras » du problème que pile là où il ne fallait pas.
J'ai cherché des simplifications, un peu, avant, comme de simplifier les triangles (
A<->B<->C<->A), mais autant ça donne un peu quelque chose sur les données de test (on peut brute-forcer la recherche sans soucis : prendre trois arêtes et voir si on a coupé en deux), c'est inutile sur les données réelles, on simplifie de 42 arêtes, sur 3363 ça change rien.Par contre, en nettoyant mon code, je vois que le « hack » sert trois fois : à 15 sommets à explorer (1ère itération, donc dès le début), à 54 sommets à explorer (3ème itération), puis à 217 sommets à explorer (345 déjà validés, 13ème itération !), et là on est quand même assez loin, on aurait très facilement pu mal tomber, sachant que le résultat arrive à 18 itérations.
Bilan, je dirais que j'ai plutôt eu de la chance avec mon sommet de départ…
Voilà le code nettoyé :
Pour une fois, mes expérimentations téléphoniques pour coder moins et avoir de la chance rapidement, ont portées leurs fruits, j'étais le premier surpris :)
Mais c'est rude de faire du code aussi approximatif, et de s'en contenter au bout du compte, ça heurte vraiment ma façon de penser.
Enfin, c'est pour ça que j'ai validé cette étoile avant la seconde du jour précédent.
# Pas de Z3, mais au moins Z^3 neurones grillés
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 24. Évalué à 2.
C'est celui qui m'a le plus gonflé sur téléphone.
Pas la partie 1 bien sûr, encore expédiée assez vite dès que je m'y suis mis (c'est à dire une fois le jour précédent terminé).
La partie 2.
Où les données de test laissent entrevoir plein de simplifications qui ne fonctionnent pas avec le vrai problème.
Et une résolution finale qui ne fonctionne pas sur les données de test !
J'ai assez modélisé mes trajectoires de grêlon, pour faire des opérations en masse, je cherchais des simplifications, des translations, pivots, etc, mais je n'ai jamais réussi à résoudre autre chose que les données de test comme ça : à chaque fois il fallait tester au moins un paramètre final, et le plus complexe à tester a au final une valeur de 57 milliard et quelques au minimum, donc on ne va pas l'atteindre comme ça, en cherchant…
C'est le temps nécessaire à notre caillou pour atteindre un élément.
On tombe pas dessus par hasard.
Dans les données de test, c'est 1, ça simplifie grandement le problème.
En fait, il faut comprendre le problème.
On choisit un point d'origine et une trajectoire :
Traj(x=393358484426865.0, y=319768494554521.0, z=158856878271783.0, dx=-242, dy=-49, dz=209)À partir de là on choisit des entiers, grands, ça va de quelques dizaines de milliards à probablement mille milliards (j'ai un 943 538 374 225 pour un grêlon), ça définit des points de départ sur notre trajectoire.
De chacun de ces points on choisit une direction, et on fait reculer notre grêlon du temps nécessaire à atteindre le point en question.
Voilà, on a notre problème posé, on oublie la trajectoire initiale, il faut la retrouver.
Facile à construire, pas simple à démêler…
Et franchement, il faut trouver des simplifications.
Et là on les trouve avec une première constatation : ce qui se passe en x, y et z est presque entièrement décorrélé, pour trouver dx, dy ou dz, on n'a besoin de se concentrer que sur la coordonnée en question. Après on fera une corrélation sur l'écart en temps entre deux grêlons, qu'on peut connaître pour dx, dy ou dz, et qui sera donc égale pour les autres, et permet de faire une triangulation.
Et une seconde constatation, sur un axe on a des grêlons parallèles, c'est à dire qui ont le même dx, le même dy ou le même dz.
Et ça va nous aider.
C'est même la seule simplification que j'ai trouvé pour réussir à résoudre ce problème.
Parce que si entre deux grêlons on a un dx identique, ça veut dire que l'écart en x entre ces deux grêlon est une constante.
Et donc qu'on parcourt cette écart avec un nombre entier d'étapes, chacune d'un nombre entier de décalages.
Donc pour deux grêlons a et b parallèles en x, donc a.dx==b.dx, on a que l'écart en x (a.x - b.x) est divisible par
r.dx-a.dxou r est notre trajectoire résultat à trouver. On cherche r.dx.Et ben on va chercher les diviseurs de
a.x - b.x, sans connaître le sens on va tous les prendre en positif ou négatif, on ajoute a.dx, et on a des valeurs possibles de r.dx.Et on cherche les valeurs communes entre tous les éléments parallèles en x, on aura réduit drastiquement nos possibilités de r.dx.
En pratique, si on n'oublie pas de considérer les diviseurs en négatif ou positif (parce qu'on ne sait pas dans quel sens on va, on a juste deux grêlons au pif), on va trouver une seul valeur pour dx, dy et dz.
On a la direction parfaite de notre caillou !
Ça aurait pu rater, on aurait pu avoir des choix et devoir tester parmi ces choix lesquels seraient les bons, mais on sent que même si on en avait eu plusieurs, ça n'aurait pas été trop explosif, et si l'algo pour finir le boulot est pas trop pourri on pouvait tout tester.
Là, suite à une erreur de ma part, j'ai aussi pondu un algorithme capable de calculer dy si on connaît dx et dz !
Sauf que ça foirait, à cause de mon erreur, mais j'ai corrigé et poursuivi, en pratique je calcule la solution pour tous les grêlons parallèles deux à deux en x, et je valide cette solution en montrant qu'ils donnent tous le même résultat. Ça m'a permis de débugger et d'être absolument certain d'avoir le bon résultat au bout du compte.
En pratique, quand on a dx, dy, et dz, il suffit de prendre deux grêlons parallèles selon n'importe quel axe, et on va avoir la solution.
On calcule le nombre d'étapes (microsecondes) pour que notre caillou passe de l'un à l'autre, ce qui est facile si on a compris l'algorithme qui a permit de trouver les dx, dy et dz : on divise l'écart en x
a.x-b.xparr.dx-a.dxqui sont connus.Sachant le temps séparant ces deux chocs, on peut calculer l'écart en y ou en z, constaté parce que nos grêlons ne sont pas parallèles en y ou z, et ça va nous permettre de savoir de combien d'étapes dans le temps il faut remonter pour combler cet écart, et faire en sorte de bien percuter les deux grêlons, en x, y et z.
En pratique mon algorithme, que je n'ai pas simplifié, calcule dy à partir de la connaissance de dx et dz sur des grêlons parallèles en z, c'est pas trop compliqué une fois qu'on a le nombre d'étapes à remonter dans le temps, et on valide déjà qu'on trouve pour tous la bonne valeur de dy. Puis on fait remonter effectivement dans le temps notre caillou depuis sa percussion avec a pour trouver un point de départ.
J'ai juste validé que r.x était identique pour tous, mais tant que ce n'était pas le cas c'était que j'avais une erreur dans mes formules.
Les maths sont simples, mais prise de tête et il faut bien se torturer les neurones.
Au final je fais bien trop de calculs, qui me donnent tous le même résultat, heureusement, et ça prend moins d'une seconde malgré tout.
Voici donc le code, avec trop de méthodes inutilisées dans mes Trajectoires, et des noms de variable bien trop peu lisibles.
Heureusement le code n'est pas trop complexe, et reste a peu près lisible.
Il y a un hack au milieu pour les données de test, puisqu'on n'a pas assez de parallèles pour trouver dx, dy et dz, je force les valeurs, connues, pour valider la seconde partie de l'algorithme.
Mais ça aurait pu faire l'objet d'un développement intéressant pour valider sur un ensemble de valeurs possible, si on n'avait pas eu un dx, dy et dz unique à l'issue de la première partie.
Rendant nécessaire de tester plusieurs cas et de vérifier qu'on ait bien un même résultat. Ça aurait été immonde à débugger par contre…
J'ai tout de même utilisé sympy pour les diviseurs, pour le coup c'était quand même plus simple que de coder une fonction moi-même.
J'ai pas trop nettoyé le code hein.
Et dans la version téléphone, j'utilise s et o au lieu de self et other dans la classe Traj (qui ne va quand même pas s'appeler Trajectory non plus, trop long…), tout pour écrire le moins possible !
# Les ennuis commencent...
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 23. Évalué à 2.
Pour moi, les ennuis ont commencés : pas d'ordinateur, pas de clavier, juste mon petit téléphone qui ne permet pas vraiment de voir les données avec du recul, et l'extrême pénibilité de coder avec un clavier tactile, toujours à basculer pour chercher les chiffres, les opérations, les =, :, les (), [] et {}.
Bref, pénible, donc on code avec des variables à une ou deux lettres, on fait les algos les plus courts à écrire, et on tâtonne.
La première partie reste assez simple, je n'ai pas mis bien longtemps et le temps de calcul sur téléphone est assez ridicule.
Pour la seconde j'ai tenté de laisser tourner des heures avec l'algo brute-force bête et méchant, mais à part flinguer la batterie on n'arrive pas à grand chose, soyons honnêtes.
Donc être malins.
Et là je l'ai pas été, j'ai tout de suite tenté de réduire le problème aux nœuds d'exploration : les cases où il y a 3 ou 4 directions possibles, et je note les distances entre ces nœuds, puis j'explore le graphe réduit des nœuds.
Sauf que j'ai cru ce problème trop complexe pour mon téléphone, et cherché à simplifier : trouver des nœuds qui sont des passages obligés.
J'étais encouragé par le fait qu'il y en a dans les données de test.
Ça veut dire qu'on peut découper le graphe simplifié en plusieurs graphes qui s'enchaînent.
Donc je code, je débugge, ça marche, je lance sur les données réelles, il me laisse avec comme seul noeud intermédiaire le noeud d'arrivée, et tout ça n'a servi à rien.
Sauf que la réponse tombe malgré tout sans trop d'attente, le problème réduit est suffisamment simple pour que la force brute s'en empare.
Ça met ~10s sur mon PC (avec pypy bien sûr, pour le coup), pas loin de 2 minutes sur le téléphone.
Je n'ai pas cherché plus loin, et j'ai juste remis le code au propre, en virant l'exploration inutile des nœuds intermédiaires, avant de le poster.
La première passe, sur la carte complète, permet aussi de lister les nœuds et la distance les séparant. Techniquement, il pourrait en manquer, puisque l'exploration se fait avec les contraintes de glissement, ça n'est pas le cas, j'ai misé sur cette simplification parce que la denrée qui me manquait vraiment c'était du temps pour coder correctement les choses.
Je me rappelle cependant avoir tenté plein de trucs et finalement avoir été déçu de la simplicité du bidule qui fournit finalement la solution, bref.
Au passage, j'utilise une pile de chemins en cours d'exploration, un deque() bien utile pour ça, plutôt qu'une fonction récursive, on fait exploser la limite de récursivité bien trop vite sur le téléphone. Donc j'ai une boucle et une FIFO d'états à faire avancer, c'est pas trop violent sur la RAM, et on n'atteint pas les limites.
Donc je commence, et j'ai pas fini, les codes dont je n'ai aucune réelle certitude de l'exactitude en toutes circonstances, ça sera pire dans les jours qui viennent.
[^] # Re: le bit de poids faible
Posté par Yth (Mastodon) . En réponse au lien la manière la plus efficace de déterminer si un nombre est pair. Évalué à 3.
Quand je code en Python, ya pas photo, c'est emacs le meilleur IDE.
Quand je code en C, les IDE sont majoritairement équivalents, man est mon principal ami, donc c'est mon shell le plus utile.
Quand je code en ansible, de toute façon, quel que soit l'IDE, je souffre, et mon principal allié est de ne pas avoir internet, ni de jeu vidéo installé sur ma machine, histoire de bien me contraindre à avancer, faut aussi que je décharge complètement mon téléphone, et que j'oublie le câble USB ailleurs, sinon ça avance pas.
Quand je code en JS… Ah, non, j'ai arrêté ça, le PHP aussi.
Bref, je suis pas prêt de lâcher mon emacs, en vrai.
[^] # Re: En binaire et en puissances de 2
Posté par Yth (Mastodon) . En réponse au message Advent of Code, jour 13. Évalué à 2.
Pertinent, je n'ai pas révisé mon opération logiques depuis un moment, je n'ai plus les réflexes…
Je vais me rafraîchir ça.
# On fait tomber des trucs, mais on fait pas de Tetris.
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 22. Évalué à 2.
C'est le dernier jour où je vais avoir le temps de la faire, la suite ça sera peut-être dans une semaine…
J'ai inventé un algo un peu tordu, assez efficace, rude à piger, donc à débugger.
Déjà les coordonnées sont en 1 dimension :
x+y*10+z*100, on va simplifier, surtout qu'on ne fait que des mouvements vers le bas, aucun test aux bornes à faire.J'ajoute un bloc de 10x10 en 0 pour poser le bazar.
Une structure de Blocs assez modélisée, une autre pour l'Univers bien plus simple et à la fin un algo tordu.
Et l'exercice 2, prenez peur !
J'ai pas vraiment le temps de remettre au propre, en gros je pars du haut, et je « pose » les blocs les uns sur les autres, en notant ceux qui sont partiellement posés, et où.
Et puis à chaque bloc, j'essaie de simplifier par ceux qui ne sont partiellement posés plus que sur lui.
Et… bah ça marche, en tapant bien sur le code.
[^] # Re: Pas d'exemple
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 20. Évalué à 2.
Ah non, on manipule des chiffres ou des lettres, réunis en ensembles, en listes, en dictionnaires.
Parfois on peut représenter ce qu'il se passe, parfois pas trop.
Et on doit faire gaffe à pas trop demander de calculs à la machine, sinon ça peut prendre des mois.
[^] # Re: Pas d'exemple
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 20. Évalué à 3.
C'est pas hyper simple à représenter, mais je vais essayer.
On va dire qu'un « low pulse » est un 1, et un « high pulse » un 0.
C'est plus simple pour comprendre.
Le button envoie un 1 quand on appuie dessus.
Le broadcaster transmet ce qu'il a reçu à toutes ses destinations.
Les noms simples, en deux lettres, sans cadre, sont des alternateurs, s'ils reçoivent un 1, ils envoient une fois un 1, et une fois un 0. Mais s'ils reçoivent 0 ils bougent pas.
À l'état initial ils enverront un 0 au premier 1 reçu.
Donc notre broadcaster étant relié à des alternateurs, au repos il ne se passe rien, mais quand on appuie sur le gros bouton rouge, il active les quatre alternateurs devant lui.
Les noms dans les cadres sont des boîtes de remise à zéro, en gros.
Au début elles sont configurées sur 1 à toutes leurs entrées, mais c'est mis à jour dès qu'elles reçoivent un truc.
Si toutes leurs entrées sont à 0, alors elles envoient un 1 à toutes leurs sorties ! Sinon, c'est un 0, qui sera ignoré par tous les alternateurs connectés. D'où le nom de boîte de remise à zéro, ça ne va envoyer 1 aux alternateurs que quand ça reçoit du 0 de partout à la fois !
Quand ça arrive, les boîtes à droites reçoivent un 1 et donc envoient un 0, sinon elles reçoivent un 0 et envoie un 1.
Avec une seule entrée, ce sont des inverseurs.
Donc quand nos grosses boîtes s'activent et réussissent à envoyer un 1, le signal est inversé en 0 vers la boîte finale.
Si toutes les quatre grosses boîtes envoient un 1 en même temps, alors la boîte finale reçoit quatre 0.
À ce moment là elle va envoyer un 1 vers rx, qui est notre module de sortie et qui n'attends que ça !
Franchement, une fois représenté comme ça, le problème il est hyper clair hein ?
Faut trouver le moment où chacune des grosses boîte s'active.
Là, on a grosso-modo tous fait une simulation : on part de l'état initial, chaque alternateur va envoyer un 0, et les grosses boîtes sont sur 1 dans toutes leurs entrées, et on appuie sur le gros bouton rouge, jusqu'à ce que les boîtes s'activent.
Là on note quand c'est arrivé.
Typiquement on va continuer pour voir quand ça va se produire à nouveau, pour chaque boîte, et essayer de déduire un schéma.
Ici c'est facile, en fait, dès la première fois que ça s'active, on a fait un cycle et c'est retour à l'état initial, en fait pas tout à fait, mais au moins ça boucle sur la même durée.
On a donc 4 cycles, il ne reste plus qu'à les coordonner, savoir quand est-ce qu'ils vont s'activer tous ensemble.
Et le plus petit multiple commun aux quatre valeurs mesurées est notre réponse.
Maintenant en poussant l'analyse.
Notre série par exemple de la première boîte, consiste en 12 alternateurs, tous éteints donc prêts à envoyer 0.
On va noter ça
000000000000.La boîte n'enverra absolument rien tant qu'on ne l'aura pas activée (enfin, elle envoie des 0 qui sont ignorés par les alternateurs).
Si on appuie, le premier va s'allumer, et envoyer 0, qui va être ignoré, on est donc dans cette situation :
100000000000.Au second coup, notre premier alternateur va s'éteindre, repasser à 0, mais aura envoyé un 1 à droite, sur le second, qui va s'allumer et envoyer 0 qui sera ignoré.
01000000000Au 3ème coup, on rallume le premier, rien d'autre ne bouge :
110000000000.4 :
00100000005 :
10100000006 :
01100000007 :
1110000000Ok peut continuer la simulation, mais il apparaît comme évident qu'on est en train de compter. On a exactement la représentation binaire, mais de gauche à droite, des numéros des étapes.
Là on va regarder notre boîte nl, et constater qu'elle va s'activer dès qu'elle reçoit 0 en même temps de la part de hd, rh, tg, qz, rl, pf et pr, ce qui va arriver quand il vont tous s'être allumés (passer de 0 à 1) comme dernière action.
Ça arrive dès qu'on a 1 sur chacun d'entre eux, et 0 sur les autres, c'est la première fois où ça va se produire et c'est cette configuration :
101001001111qu'on retourne en111100100101pour avoir le chiffre binaire 3877, qu'on retrouve bien dans mes résultats plus haut.Pour les autres, on va simplement lire
111000001111soit 3847,110010111111soit 4051, et enfin101010110111soit 3797.Diantre c'est juste.
Là nos nombres sont premiers entre eux, donc le PPCM vaut la multiplication des 4 soit… beaucoup.
Mais bref, voilà le problème entièrement décortiqué, et finalement une lecture directe des chiffre à trouver, sans aucun calcul, sans besoin d'ordinateur, sauf pour le PPCM (c'est un peu misérable à la main avec des chiffres aussi gros quand même).
Merci de ta question Ysabeau, je n'aurais pas poussé autant sinon :)
Pour continuer un petit peu, sur notre exemple 1.
On active sur
101001001111mais à ce moment là notre boîte ne se contente pas d'envoyer un 1 vers la sortie, elle envoie aussi un 1 vers tous nos 0 !En effet, tous les alternateurs qui n'envoient pas vers la boîte, reçoivent de la boîte.
Ils sont éteints, ils vont donc s'allumer, envoyer des 0 qui seront ignorés et passer tous à 1 :
111111111111= 4095.Sauf que le tout premier reçoit lui aussi un 1, exactement comme si on avait appuyé sur le bouton une fois tout passé à 1 !
C'est
hd, et il est bien en dernier de la liste des alternateurs activés parnl. On lui envoie un 1 qui va faire s'éteindre tous les alternateurs en chaîne, puisqu'ils envoient un 1 en s'éteignant. Ils vont donc tous avoir envoyé un 1 vers la boîte (ceux qui sont connectés) qui verra bien son état retourner à celui d'origine.D'où la boucle et le cycle qui recommence exactement à zéro, on est effectivement retourné précisément à l'état initial.
On a compté de 0 à 3877, et au moment d'arriver à 3877, on a une remise à 0 avec un signal envoyé vers la sortie.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 21. Évalué à 2.
Ça y est, j'ai, compris ton explication, bien vu !
Yth.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 21. Évalué à 2.
Alors j'ai rien compris à ton explication, mais je crois que je suis en train de tomber malade.
J'ai hyper galéré à débugger mon code, bourré de mauvaises bornes, jusqu'au bout du bout…
Bon, d'une façon ou d'une autre je n'ai pas fait comme toi.
Cf plus bas :)
# Rhaaaaaa !!!
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 21. Évalué à 3.
Un problème bien bien pénible aujourd'hui, où il faut être très précis pour éviter les effets de bords.
encore une fois on « voit » des trucs dans les données, qui sont indispensables à la résolution…
On explore en damier, soit les cases noires (x+y pairs) soit les cases blanches (x+y impairs).
Une exploration type celle de l'exercice 1 que tout le monde a dû réussir, nous permet facilement de trouver le nombre de cases blanches et noires, chez moi c'est 7509 et 7566, ce qui additionné avec les rochers ne fait pas la taille du terrain, car il y a 4 cases inaccessibles (chez moi). Jusqu'ici tout va bien.
Comme tu l'as fait remarquer, on peut aller en ligne droite vers les répétitions du terrain, donc l'exploration d'une zone répétée autour de la zone de départ se fait le plus efficacement à partir du point d'entrée : le milieu du côté.
Pour les zones en diagonale, on va rentrer par la case au coin.
Ya pas plus rapide.
Le terrain fait 131x131, et le départ au centre en 65x65.
Donc on peut explorer indépendamment les différentes zones, en notant simplement le temps nécessaire à les atteindre.
65 + 1 + 131 * (distance - 1)quand on va en ligne droite nord, sud, est ou ouest.Et
65 + 1 + 65 + 1 + 131 * (distance de Manhattan - 2)pour les cases qui sont au moins un peu en diagonale.Bon, ya des +1, des +2, des -1, des -2, c'est les effets de bords ça.
On rentre au nord en 66 mouvements, et deux fois au nord en 66+131 mouvements, etc.
On rentre au nord-ouest en 65+1+65+1 = 132 mouvements, et de là on se décale horizontalement ou verticalement par paquets de 131.
On sait donc rapidement combien d'étapes il nous reste quand on entre dans une zone. Ça va être
pleintout du long, et on va soit valider les cases noires, soit les cases blanches, en alternance.Ben oui, si on entre dans une zone mettons via
(0, 0), la case(0, 0)d'une zone adjacente est à 131 mouvements, qui est un nombre impair, donc on ne l'atteint pas.On a en fait un damier de damiers, yay !
Là on va donc simplement regarder combien d'étape il reste à parcourir, ou combien on en a parcouru, et choisir sans se tromper la bonne valeur entre noir et blanc.
On additionne.
En pratique, une exploration en distance de zone par rapport à celle du départ est assez simple : on a 4 zones directement en face de la zone de départ, et (distance -1) * 4 zones qui forment une diagonale, on a un joli losange.
En distance 0 on a la zone de départ.
En distance 1 on a 4 zones directement liées.
En distance 2 on a 4 zones directes, et 4 zones diagonales.
En distance 3 c'est 4 et 8.
En distance n, c'est 4 et (n-1)*4.
Il se trouve que tout le monde à une distance donnée est soit blanc, soit noir (blanc = on considère les cases blanches à l'intérieur de la zone, noir = on considère les cases noires).
Comme le nombre d'étape final est impair, on ne considère pas la case de départ, donc la case de départ sur mon schéma, dans une zone blanche, doit être noire.
Ceci nous amène presque au bout, parce que là on va commencer à avoir des zones qu'on n'explorera plus entièrement, à cause des pas restants, trop courts.
Dans mon code, je prends une marge suffisante, et je calcule les cases à partir des déplacements restants.
Mais c'est assez facile, j'ai 8 zones : nord, sud, est, ouest et nord-est, nord-ouest, sud-est, sud-ouest, chacune explorée à partir d'un point de départ spécifique.
Lors de l'exploration, je note pour chaque pas effectué les cases atteintes.
Donc il me suffit de regarder quelle distance je peux parcourir dans mon exploration, avec les déplacements restants, et je sais quelles cases sont atteintes.
Je dénombre, j'additionne.
Et comme pour le reste du problème, on a les 4 directions cardinales uniques, et les 4 directions diagonales répétées (distance - 1) fois, donc on calcule 8 valeurs, on multiplie 4 d'entre elles, on additionne et c'est ok.
On passe à la distance suivante.
On s'arrête avec une petite marge où on va additionner des zéros.
J'ai pas mal fait ça pour éviter d'être sûr de moi, vu que j'ai eu des quantités invraisemblables d'erreurs aux bornes…
Et puis, voilà, résultat :)
Ça permet aussi de résoudre l'exercice 1 avec le problème central, vu que pour chacune de mes zones, je ne regarde que ce qu'il se passe dedans, j'ai les infos pour le premier problème.
Voilà notre explorateur de zone, et la fonction explored qui retourne les cases explorées selon le parité (zone noire ou blanche), et le nombre de pas restant.
Pour le premier problème, on démarre en
START = (65, 65)et on fait 64 pas, on a un damier pair puisque 64 est pair, donc en particulier la case de départ est prise en compte.Pour le second problème on a une seconde exploration à faire. D'abord le paramétrage.
La fonction
bigexplorationretourne le type de zone, et le nombre de pas effectués, pour entrer dans la zone en(x, y)par rapport à celle de départ.FINESTEPS c'est la distance à partir de laquelle on va vraiment compter les pas dans chaque zone. J'ai mis
* 2pour avoir de la marge et ne pas avoir à réfléchir aux effets de bords, mais je peux valider que simplementSTEPS2 - MAXEXPLORATIONfonctionne.Après ça le code est moche et répétitif, dans l'esprit de bigexploration.
Et bigre, même le
range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2)m'a causé 2h de prise de tête, j'avais oublié de ne pas commencer à 0, mais bien à 1, donc je comptais 5 fois la zone de départ, comme j'ai lutté pour trouver ça, rhaaa !On vérifie l'intérêt de nos
FINESTEPSavec les sorties :On voit bien qu'on a les 4 sommets qui sont incomplets, et pour les diagonales on a deux couches de diagonales à considérer. Et à chaque fois, le résultat pratique dépend de la direction qu'on considère, parce que la distribution des rochers met le bazar.
C'est officiellement celui qui m'a le plus résisté jusqu'à présent, mais au final, l'algo était là assez rapidement, il était juste buggé de partout :(
[^] # Re: Les données imposent la méthode
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 20. Évalué à 2.
Ah oui, le
deque()permet de faire une FIFO de messages, on les empile à droite, on les dépile à gauche, on a fini quand c'est vide, d'où un code d'itération assez simple dans la fonctionpush().C'était la minute structure de données pas encore vue cette année. Le
deque()c'est unelist()optimisée pour faire des ajouts/suppressions aux bouts, donc idéal pour des FIFO, LIFO et trucs du genre.[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 20. Évalué à 2.
Ah, oui, c'est vrai ça, le résultat c'est le PPCM des 4 cycles, sauf qu'en l'occurrence ils sont premiers entre eux (enfin, chez moi en tout cas…), encore une propriété cachée dans les données, d'où la multiplication annoncée dans mon message !
J'ai testé vite fait la multiplication sur le site avant de lancer le PPCM, et ça a fonctionné, donc j'ai complètement oublié qu'il fallait faire ça pour être corrects.