Mon premier algo a fait fondre deux CPU en même temps, sur deux machines différentes, avec partage du travail à faire, pour pondre le résultat en pas loin de 40 minutes, avec PyPy.
Voici le second, celui qui fonctionne, qui prends moins d'un dixième de seconde pour résoudre tout le problème, et de façon assez élégante en plus, juste en exploitant le range() de Python.
C'est pour ça que dans l'algo présenté, j'utilise la même méthode pour les deux exercices, avec des range de un élément pour l'exercice 1, je n'ai pas codé ça dès le début.
Et non, je ne posterai pas mon premier algo, très bien pour l'exo 1, mais très crado pour le 2 ^
Les données d'abord, je distingue les graines et le reste :
Ensuite les transformations pour trouver les correspondances, on va avoir une classe avec deux listes : les range() source, et les opérations à appliquer sur chaque range, qui sont simplement un entier relatif à ajouter. Et puis les noms des éléments depuis et vers lesquels on transforme :
Pour les calculs en eux-même, la méthode qui fait le travail est ajoutée à Map(), et la résolution est assez simple au bout du compte.
On calcule tout simplement les superpositions de deux range() : on va avoir un range d'éléments non traité avant un range de transformation, un range d'éléments non traités après un range de transformation, et enfin un range transformé. On boucle sur toutes les opérations disponibles, en remettant dans le pot les range non traités (avant et après) et en retournant (yield est ton ami) les range traités.
On n'oublie pas à la fin de retourner tous les range ayant échappés aux transformations, car ils restent identiques selon l'énoncé.
Le code est vraiment simple grâce aux itérateurs, avec yield, on ne se fatigue pas à construire une liste, à tester des trucs : on a une donnée finale ? yield, et on continue, elle est envoyée, et on ne s'en occupe plus.
Et on utilise les propriétés des range(), au début je voulais faire des if élément in range_operation qui est immédiat, mais en fait on n'en a pas besoin. La seule subtilité c'est qu'un range est Vrai s'il contient en pratique des éléments, et Faux sinon, donc range(20, 10) c'est faux. if before signifie donc simplement : si on a des éléments non traités avant.
Enfin le résolution se fait à l'identique pour les deux parties, avec la bonne valeur initiale pour values :
whilesrcinconverters:dst,converter=converters[src]# print(f"Converting from {src} to {dst}")values=list(converter(values))src=dstprint("Closest location is {}".format(min(v.startforvinvalues)))
Pour info, faire les 7 moulinettes sur une liste de 850 millions d'éléments, même avec PyPy, ça prend dans les dix/quinze minutes, et je parle pas de la RAM.
Comme quoi ça peut valoir le coup de regarder les données à traiter pour savoir où on va se planter, avant de coder…
Cela dit, un algo non optimisé, même à 45 minutes de calcul réparti sur deux machines (j'aurais pu aller plus vite en parallélélisant sur les multiples proc des machines, un range initial par exécution, en moins de 15 minutes c'était plié), c'est plus rapide que de réinventer un algorithme, le coder, le valider.
"zero" n'est pas dans les données, mais l'ajouter chez moi permet d'avoir la correspondance entre les textes et les index de la liste Python qui commence à 0.
C'est une optimisation facile de lisibilité on va dire.
Par ailleurs, j'ai codé sans regarder les données justement, donc en fait je ne savais pas que le zéro était inutilisé.
Dans l'idée, il aurait pu l'être.
Une classe pour représenter un sac, avec des cubes rouges, verts et bleus dedans. La dataclass c'est bien pratique, ça s'initialise automatiquement avec les paramètres fournis aux noms des variables, ou alors aux valeurs par défaut.
Par exemple Bag() c'est 0 de chaque, Bag(red=12, green=5), ça fait ce qui est écrit en laissant blue à 0.
Il est frozen ce qui signifie qu'on ne peut pas le modifier, donc les opérations retournent une nouvelle instance de Bag, c'est utile en optimisation parce que ça va plus vite. Ici c'est sans importance.
On définit trois opérations dessus : __le__ permet de comparer bag1 <= bag2, c'est True ssi tous les éléments de bag1 sont inférieurs ou égaux à ceux de bag2. __add__ c'est un peu un hack, et ça retourne un Bag avec le maximum pour chaque valeur dans les deux Bag additionnés, ça permet d'utiliser la fonction sum() pour calculer un maximum, parce que la fonction max() fait des comparaisons, et retourne le Bag en entrée le plus grand, ce qui n'a rien à voir avec ce dont on a besoin.
Et finalement power est un attribut qui sert au calcul du score du second exercice.
Avec cette classe on va analyser les données, en exploitant les passages d'arguments python par dictionnaire, et les valeurs par défaut de Bag, c'est pas trop abscons à lire, si on n'est pas débutant en Python (et qu'on aime les struct-comprehension) :
En réalité on n'a jamais besoin des divers sacs possible, la seule chose qui nous intéresse c'est le maximum pour chaque valeur rouge, vert et bleu, d'où le sum(), et une fois cette optimisation faite, on réalise qu'on s'est furieusement compliqué la vie et qu'au final on avait juste besoin, depuis le tout début de l'exercice, de trouver ce maximum, et de ne s'intéresser qu'à lui.
Les exercices ensuite sont triviaux, surtout le second, il n'y a vraiment plus rien à faire :
datas=[xforxininput()]constraint=Bag(red=12,green=13,blue=14)r=sum(gameforgame,biggestbagindatasifbiggestbag<=constraint)print(f"Possible games : {r}")power=sum(biggestbag.powerforgame,biggestbagindatas)print(f"Sum of Power of games : {power}")
Yth, qui vient de faire brûler un CPU sur l'exercice 5, parce que parfois c'est plus « rapide » de laisser turbiner que de trouver un meilleur algorithme, mais on en parle jour 5…
Le weekend, j'ai moins de cerveau, moins de temps, et je n'ai pas encore trop cherché les bonnes optimisations, mais je devrais commencer, pour reprendre les bonnes habitudes.
Et me remettre en tête les structures de données moins utilisées, et pourtant tellement utiles.
J'aurais aussi pu faire une classe cubes avec trois éléments red, green et blue, qui permet des comparaisons immédiates avec <, >, des min, max, sum, multiplications, etc.
Après les opérations deviennent très simples. Je vais peut-être poster ça demain :)
Ce calcul fait à l'avance m'aurait permis de voir que 9691964 comme résultat, c'était ouvertement faux…
Bref, j'ai commencé à chercher certaines optimisations, en utilisant des comparaisons de set() en python, qui sont plutôt efficaces. Et j'aurais probablement dû utiliser des frozenset, car c'est plus rapide, quand on n'a pas besoin de les modifier.
Il reste aussi des optimisations faisables, mais la taille des données ne les justifient pas encore.
Zéro structures de données, un traitement très linéaire, ça reste simple, on ne fait pas encore de réelles abstractions.
importsysdirections=((-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1))defenvelope(positions):returnset(tuple(sum(x)forxinzip(a,p))forpinpositionsforaindirections)numbers=list()symbols=set()gears=set()nl=0forlineinsys.stdin:number=[]positions=set()nc=0forcinline.strip():ifcin"0123456789":number.append(c)positions.add((nl,nc))else:ifc!=".":print(f"Symbol {c} at {nl}, {nc}")symbols.add((nl,nc))ifc=="*":gears.add((nl,nc))ifnumber:numbers.append((int("".join(number)),envelope(positions)))number=[]positions=set()nc+=1ifnumber:numbers.append((int("".join(number)),envelope(positions)))number=[]positions=set()nl+=1
numbers est la liste des nombres et de leur « enveloppe » c'est à dire des coordonnées de toutes les cases composant ce nombre et adjacentes à lui.
C'est un set() de doublets. symbols contient la liste des coordonnées (doublets) de tous les symboles du plan. gears contient la liste des coordonnées des symboles * uniquement, et ne servira que pour la seconde partie.
Je trouve le code un poil moche, et un meilleur travail sur les entrées, et les conditions boucles, pourrait alléger, mais il faut absolument ne pas se planter dans les cas limites : un nombre en fin de ligne, deux nombres séparés par un symbole (celui-là m'a mis dedans), etc.
Être carré, clairs, précis, sinon c'est l'écran bleu… Euh, enfin, la mauvaise réponse quoi…
La résolution des problèmes est assez simple après ça.
Problème n°1 :
result=list()nope=0fornumber,posinnumbers:ifsymbols.intersection(pos):result.append(number)else:nope+=numberprint(result)print(f"Sum of Numbers : {sum(result)} ({nope})")
nope me sert à la validation, vu que j'ai la somme de tous ems chiffres qui vaut 598313, je dois avoir result + nope = 598313, et j'aurais pu aussi juste calculer nope et obtenir mon résultat comme ça, par soustraction.
Ça pourra servir comme façon de faire plus tard, je me rappelle d'un exercice avec du sable qui s'écoule, qui peut se résoudre très facilement en regardant uniquement là où il ne s'écoule pas et en faisant une soustraction…
Et le second challenge :
gear_value=0forgearingears:parts=[numberfornumber,posinnumbersifgearinpos]iflen(parts)==2:gear_value+=parts[0]*parts[1]print(f"Sum of NumbersGear Value : {gear_value})")
Rien à recalculer, on va analyser dans l'autre sens : pour chaque « gear » on regarde dans combien de « number » il se trouve, si c'est 2, bingo, on l'ajoute.
C'est tout.
Ce coup-ci, avec une analyse des données, placées dans les bonnes structures, la seconde partie de l'exercice va se faire immédiatement après la première.
Ici on a encore un truc assez simple, et on va faire un dictionnaire avec en clé le numéro de la partie et en valeur une liste de triplets (rouge, vert, bleu), avec des zéros là où on n'a pas d'infos en entrée.
-> Normaliser les entrées, avoir une structure assez facile à analyser ensuite.
Déjà, j'abuse des yields et des générateurs, c'est pas encore utile, mais ça va venir.
Pour la partie 1 on va avoir une fonction de validation, et après on fait une somme :
deftest_elements(elements,constraint):forelinelements:foriinrange(3):ifel[i]>constraint[i]:returnFalsereturnTrueconstraint=[12,13,14]r=sum(gameforgame,elementsindatasiftest_elements(elements,constraint))print(f"Possible games : {r}")
Et là, pour la seconde partie on n'a même plus besoin de fonction de validation, le calcul est immédiat, même si le code est moche. Y'aurait moyen avec des structures de données de numpy de se passer de certaines méthodes peu explicites avec directement des comparaisons de vecteurs, ou un produit vectoriel. Bah, pas encore, on reste en python chocolat, poire… Vanille !
power=sum(reduce(lambdax,y:x*y,[max(i)foriinzip(*elements)])forgame,elementsindatas)print(f"Sum of Power of games : {power}")
Le reduce sert à multiplier entre eux tous les éléments de la liste, et le zip va transformer une liste de triplets (r, v, b) en triplet de listes ([r, r, r…], [v, v, v…], [b, b, b…]).
Jusqu'ici, ya pas grand chose à déclarer, on manipule des données, on n'a même pas vraiment besoin de trop se compliquer à trouver les bonnes structures de données.
La fonction analyze prend une ligne, la parcours charactère par charactère, et regarde si c'est un chiffre, ou l'écriture d'un chiffre, et envoie dans l'itérateur.
Zéro intelligence, zéro optimisation, zéro plantage.
Bientôt on pourra plus faire comme ça !
Mais bon, jour 1, on se dérouille les neurones, on reprend le pli des traitements de flux, on essaie déjà de mettre des itérateurs plutôt que de tout traiter en mémoire, juste pour reprendre les futurs bonnes habitudes…
L'histoire, la géographie, les maths, la physique, la chimie, la biologie, etc.
Tout ça non plus n'est pas « normé ».
Par contre, comme pour la langue française, il y a un programme, assez précis, des manuels qui explicitent ce programme et sont validés par le ministère, et les élèves sont évalués sur ce programme.
Il n'est nulle part question de droit, et aucune loi n'impose que la note d'une dictée soit faite sur une base équitable, normée ou quoi que ce soit.
Je suis assez perturbé, toujours, par l'académie française.
Défendre la langue oui, mais essayer de la normer, ou plutôt de normer ses évolutions, ben nettement moins.
Défendre des constructions et des orthographes qui portent du sens et évitent des confusions, c'est important.
Quand les gens confondent à l'écrit « serez » et « saurez », ça m'affole un poil.
Mais lire « T ou 2m1? » me dérange beaucoup moins.
Moi aussi j'essaie d'avoir une bonne orthographe et une bonne grammaire, de manière générale une bonne maîtrise de la langue, parce que je considère que connaître le cadre, forcément un peu rigide, est la première étape pour le transcender, et apporter du sens par les transgressions qu'on y apporte.
Sous forme de néologismes, barbarismes, jeux de mots, fautes assumées, etc., si on connaît la « bonne façon » d'écrire, le fait d'écrire mal exprès fait aussi passer des messages.
Et évidemment, ce que j'accepte chez moi, je l'accepte chez les autres.
Alors oui, je tique quand je voit écrit ça, et je pourrais même faire la remarque dans certains cas. Mais les évolutions et les nouveautés, j'adore, c'est ce qu'il y a de plus excitant dans la langue, jouer avec, la faire vivre :)
Yth, j'ai un défaut contre les anglicismes aussi, je cherche toujours le bon mot français à la place, et je trouve qu'en général on y gagne.
Chais pas trop, en France, sur l'intégralité de la 5è république, on a eu 70% de présidences de droite (45 ans) et 30% de présidences de gauche (19 ans).
Vers où cet échiquier politique penchait-il donc par le passé ?
En tout cas, il y a eu des écologistes aux présidentielles depuis 1974, soit plus des trois quarts de l'existence de la Vè, mais l'échiquier n'a jamais penché de ce côté là.
Posté par Yth (Mastodon) .
En réponse au journal Advent of code 2023.
Évalué à 10.
Dernière modification le 01 décembre 2023 à 12:36.
Aussi, nous sommes 4 à avoir eu 50 étoiles, et 4 de plus à en avoir eu plus de 40.
Sachant que la fin est relativement fastidieuse, avec des algos qui peuvent prendre du temps, et donc un débuggage allongé d'autant, jusqu'à la veille de Noël où on peut avoir franchement autre chose à faire : ne pas chercher à finir est entièrement compréhensible.
Quand ça cesse d'être fun, ça cesse d'être fun.
Mais vivement dans quelques jours quand ça commencera à devenir fun, et qu'il faudra avoir de vraies idées d'algorithmie pour affronter les épreuves :)
Bon courage à toutes celles et tout ceux qui vont participer !
Premier conseil pour ceux qui s'y mettent : testez vos programme avec les données de démo avant d'envoyer un résultat.
Les cas particuliers ne sont pas décrits dans les énoncés, mais sont souvent présents dans les données de test.
Par exemple, premier jour de 2023, second challenge ligne 2 : "eightwothree".
L'approche « facile » consiste à faire des remplacement de chaînes : "one" par "1", "two" par "2", etc.
Si on fait ça sans réfléchir et dans l'ordre, notre chaîne devient alors : "eigh23", et on a comme valeur 23.
Mais on devrait remplacer le début de la chaîne, "eight" par 8, et obtenir 83 comme résultat.
Une simple validation avec les données de test montre qu'on s'est planté…
Si ça sent le vécu, c'est parce que ça sent le vécu.
Second conseil, en Python, mais surtout utile à partir de la moitié en général : utilisez PyPy quand les algos commencent à boucler à mort et traiter des millions de cas, ça peut aller de 20 à 50 fois plus vite, sans rien changer au code.
Et abusez des générateurs, pour éviter les explosions de mémoire.
Mon prompt est assez basique, il fait : user@machine:dir$
Mais le nom d'utilisateur est en rouge quand c'est root et en vert sinon.
Et le nom de la machine est d'une couleur différente selon la machine.
Et le répertoire est toujours complet, je déteste les répertoires réduits, juste le dernier chemin, ou des pointillés.
Parfois c'est moche et ça fait un prompt de 12 kilomètres.
Parfois.
Et ben ça me fait gagner un temps fou de juste voir le rouge, là, à l'endroit où j'écris ma commande, mais sans être trop intrusif non plus. D'avoir toujours conscience de si l'utilisateur du shell à l'écran peut faire des conneries ou pas.
C'est aussi utile pour se dépatouiller des SSH, le nom de la machine n'est pas toujours évident sans avoir besoin d'être lu, alors qu'une couleur différente, ça va sauter aux yeux qu'on est en SSH sur une autre machine.
En fait t'as besoin de deux couleurs : une pour la machine locale, une pour les machines accessibles uniquement à distance, après je lis le nom de la machine pour bien vérifier où je suis.
Et s'il n'y a aucune couleur, je sais que je suis sur une autre machine, que je ne gère pas, et donc que j'y suis pour une raison précise, et ça saute encore plus aux yeux !
Bah voilà, ça va pas très loin, c'est de la conf statique (la couleur est paramétrée dans le .bashrc), et pif je gagne du temps, et je perds des chances de faire des boulettes.
Pour un effort somme toute assez minimal de paramétrage.
C'est bon, j'ai relevé ton défi, j'ai gagné quoi ?
Et donc la façon naturelle de régler les choses c'est de laisser l'environnement se dégrader jusqu'à perte brutale de la population humaine, sans obligatoirement une extinction.
Alors contrairement à ce que cette phrase laisse entendre, un cancer ce n'est pas une croissance dérégulée, mais une absence de décroissance.
En fait nos cellules ont déjà un rythme de reproduction effréné, mais elles sont recyclées à peu près au même rythme.
Dans un cancer il y a défaut de recyclage, les cellules restent, la tumeur grossit, mais pas plus vite que la croissance classique des cellules.
De fait j'ai un peu de mal à faire une analogie avec notre société… Je suppose qu'on a en effet un grave déficit de recyclage, et qu'on aurait bien besoin de ne pas simplement jeter, mais de reconstruire.
C'est le principe de l'économie circulaire : tu produits de la valeur en fabricant un bidule.
Puis tu le récupère et en extrait la matière utile, produisant à nouveau de la valeur.
Cette matière utile sert à reconstruire un autre bidule, en créant donc de la valeur.
On arrive à une création de valeur à chaque étape, sans extraction de matière première après le lancement du cycle.
Toute la subtilité est dans l'énergie employée à chaque étape. Et la quantité de pertes aussi.
La France : 2% des émissions pour 0,8% de la population.
Et ce très mauvais résultat est atteint avec une électricité presque entièrement décarbonée (j'ai pas dis non-polluante).
Ça fout un peu la honte cet argument de dernier de la classe…
Est-ce que tu dis « D point bidule » à l'oral ?
Non, tu dis Docteur bidule.
C'est pas oralisable, c'est un défaut de cette façon de faire.
Ça ne la rend pas du tout inadaptée pour la plaque en bas de l'immeuble.
Et en plus c'est assez aisé à dérouler : ça remplace un mot unique, donc ça se ré-oralise facilement, ce qui n'est pas le cas de la notation avec le point médian.
Voilà, je pointe un défaut, qui freine son adoption, parce que l'objectif ici c'est d'inclure plus de gens dans les discours, à la fois à l'oral et à l'écrit.
On a une solution qui passe mal de l'un à l'autre.
Jamais je n'ai dis qu'il fallait la jeter, j'ai simplement pointé un défaut.
C'est possible de discuter des qualités et défauts d'un truc quelconque sans que le fait de pointer un défaut ne fasse de nous un fanatique anti-truc-quelconque ?
Je sais que la mode est est au tout noir/tout blanc, si t'es pas avec moi t'es contre moi, blabla, mais je dois être un vieux con, parce que c'est pas ma façon de faire, merci.
# Le code que j'aurais aimé faire du premier coup.
Posté par Yth (Mastodon) . En réponse au message [Doublon] Advent of Code 2023 : Day 5. Évalué à 2.
Mon premier algo a fait fondre deux CPU en même temps, sur deux machines différentes, avec partage du travail à faire, pour pondre le résultat en pas loin de 40 minutes, avec PyPy.
Voici le second, celui qui fonctionne, qui prends moins d'un dixième de seconde pour résoudre tout le problème, et de façon assez élégante en plus, juste en exploitant le
range()de Python.C'est pour ça que dans l'algo présenté, j'utilise la même méthode pour les deux exercices, avec des range de un élément pour l'exercice 1, je n'ai pas codé ça dès le début.
Et non, je ne posterai pas mon premier algo, très bien pour l'exo 1, mais très crado pour le 2 ^
Les données d'abord, je distingue les graines et le reste :
Les graines sont donc une liste de range().
Ensuite les transformations pour trouver les correspondances, on va avoir une classe avec deux listes : les range() source, et les opérations à appliquer sur chaque range, qui sont simplement un entier relatif à ajouter. Et puis les noms des éléments depuis et vers lesquels on transforme :
Pour les calculs en eux-même, la méthode qui fait le travail est ajoutée à Map(), et la résolution est assez simple au bout du compte.
On calcule tout simplement les superpositions de deux range() : on va avoir un range d'éléments non traité avant un range de transformation, un range d'éléments non traités après un range de transformation, et enfin un range transformé. On boucle sur toutes les opérations disponibles, en remettant dans le pot les range non traités (avant et après) et en retournant (yield est ton ami) les range traités.
On n'oublie pas à la fin de retourner tous les range ayant échappés aux transformations, car ils restent identiques selon l'énoncé.
Le code est vraiment simple grâce aux itérateurs, avec yield, on ne se fatigue pas à construire une liste, à tester des trucs : on a une donnée finale ? yield, et on continue, elle est envoyée, et on ne s'en occupe plus.
Et on utilise les propriétés des
range(), au début je voulais faire desif élément in range_operationqui est immédiat, mais en fait on n'en a pas besoin. La seule subtilité c'est qu'un range est Vrai s'il contient en pratique des éléments, et Faux sinon, donc range(20, 10) c'est faux.if beforesignifie donc simplement : si on a des éléments non traités avant.Enfin le résolution se fait à l'identique pour les deux parties, avec la bonne valeur initiale pour
values:Pour info, faire les 7 moulinettes sur une liste de 850 millions d'éléments, même avec PyPy, ça prend dans les dix/quinze minutes, et je parle pas de la RAM.
Comme quoi ça peut valoir le coup de regarder les données à traiter pour savoir où on va se planter, avant de coder…
Cela dit, un algo non optimisé, même à 45 minutes de calcul réparti sur deux machines (j'aurais pu aller plus vite en parallélélisant sur les multiples proc des machines, un range initial par exécution, en moins de 15 minutes c'était plié), c'est plus rapide que de réinventer un algorithme, le coder, le valider.
[^] # Re: Python
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023 : Day 1. Évalué à 2.
"zero" n'est pas dans les données, mais l'ajouter chez moi permet d'avoir la correspondance entre les textes et les index de la liste Python qui commence à 0.
C'est une optimisation facile de lisibilité on va dire.
Par ailleurs, j'ai codé sans regarder les données justement, donc en fait je ne savais pas que le zéro était inutilisé.
Dans l'idée, il aurait pu l'être.
[^] # Re: En Python
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023 : Day 4. Évalué à 2.
J'aime bien, c'est assez propre et concis !
Je suis sur quelque chose de nettement moins abstrait, mais l'exercice du jour est assez simple je trouve.
Et le calcul est immédiat aussi.
[^] # Re: C'était trop simple... je suspecte un piège !
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023 : Day 2. Évalué à 2.
Jour 2, c'est simple, on ne se fait pas déjà des noeuds dans le cerveau, c'est normal…
[^] # Re: Commencer à représenter le problème pas trop bêtement.
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023 : Day 2. Évalué à 2.
Alors avec plus d'abstraction, j'ai ça :
Une classe pour représenter un sac, avec des cubes rouges, verts et bleus dedans. La dataclass c'est bien pratique, ça s'initialise automatiquement avec les paramètres fournis aux noms des variables, ou alors aux valeurs par défaut.
Par exemple
Bag()c'est 0 de chaque,Bag(red=12, green=5), ça fait ce qui est écrit en laissant blue à 0.Il est
frozence qui signifie qu'on ne peut pas le modifier, donc les opérations retournent une nouvelle instance deBag, c'est utile en optimisation parce que ça va plus vite. Ici c'est sans importance.On définit trois opérations dessus :
__le__permet de comparerbag1 <= bag2, c'estTruessi tous les éléments de bag1 sont inférieurs ou égaux à ceux de bag2.__add__c'est un peu un hack, et ça retourne un Bag avec le maximum pour chaque valeur dans les deux Bag additionnés, ça permet d'utiliser la fonctionsum()pour calculer un maximum, parce que la fonctionmax()fait des comparaisons, et retourne le Bag en entrée le plus grand, ce qui n'a rien à voir avec ce dont on a besoin.Et finalement
powerest un attribut qui sert au calcul du score du second exercice.Avec cette classe on va analyser les données, en exploitant les passages d'arguments python par dictionnaire, et les valeurs par défaut de Bag, c'est pas trop abscons à lire, si on n'est pas débutant en Python (et qu'on aime les struct-comprehension) :
En réalité on n'a jamais besoin des divers sacs possible, la seule chose qui nous intéresse c'est le maximum pour chaque valeur rouge, vert et bleu, d'où le sum(), et une fois cette optimisation faite, on réalise qu'on s'est furieusement compliqué la vie et qu'au final on avait juste besoin, depuis le tout début de l'exercice, de trouver ce maximum, et de ne s'intéresser qu'à lui.
Les exercices ensuite sont triviaux, surtout le second, il n'y a vraiment plus rien à faire :
[^] # Re: Commencer à représenter le problème pas trop bêtement.
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023 : Day 2. Évalué à 2. Dernière modification le 04 décembre 2023 à 17:30.
Le weekend, j'ai moins de cerveau, moins de temps, et je n'ai pas encore trop cherché les bonnes optimisations, mais je devrais commencer, pour reprendre les bonnes habitudes.
Et me remettre en tête les structures de données moins utilisées, et pourtant tellement utiles.
J'aurais aussi pu faire une classe cubes avec trois éléments red, green et blue, qui permet des comparaisons immédiates avec <, >, des min, max, sum, multiplications, etc.
Après les opérations deviennent très simples. Je vais peut-être poster ça demain :)
# On bourrine, on bourrine et on fait des bêtises...
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023 : Day 3. Évalué à 2.
Faut dire, j'ai pu m'y mettre vers 23h30 hier soir…
Et ma bêtise a été de transformer "927*741" en 927741 au lieu de 927 et 741 séparés.
Déjà, la somme totale de tous les nombre du jeu se calcule ainsi :
Ce calcul fait à l'avance m'aurait permis de voir que 9691964 comme résultat, c'était ouvertement faux…
Bref, j'ai commencé à chercher certaines optimisations, en utilisant des comparaisons de set() en python, qui sont plutôt efficaces. Et j'aurais probablement dû utiliser des frozenset, car c'est plus rapide, quand on n'a pas besoin de les modifier.
Il reste aussi des optimisations faisables, mais la taille des données ne les justifient pas encore.
Zéro structures de données, un traitement très linéaire, ça reste simple, on ne fait pas encore de réelles abstractions.
numbersest la liste des nombres et de leur « enveloppe » c'est à dire des coordonnées de toutes les cases composant ce nombre et adjacentes à lui.C'est un
set()de doublets.symbolscontient la liste des coordonnées (doublets) de tous les symboles du plan.gearscontient la liste des coordonnées des symboles*uniquement, et ne servira que pour la seconde partie.Je trouve le code un poil moche, et un meilleur travail sur les entrées, et les conditions boucles, pourrait alléger, mais il faut absolument ne pas se planter dans les cas limites : un nombre en fin de ligne, deux nombres séparés par un symbole (celui-là m'a mis dedans), etc.
Être carré, clairs, précis, sinon c'est l'écran bleu… Euh, enfin, la mauvaise réponse quoi…
La résolution des problèmes est assez simple après ça.
Problème n°1 :
nopeme sert à la validation, vu que j'ai la somme de tous ems chiffres qui vaut 598313, je dois avoirresult + nope = 598313, et j'aurais pu aussi juste calculer nope et obtenir mon résultat comme ça, par soustraction.Ça pourra servir comme façon de faire plus tard, je me rappelle d'un exercice avec du sable qui s'écoule, qui peut se résoudre très facilement en regardant uniquement là où il ne s'écoule pas et en faisant une soustraction…
Et le second challenge :
Rien à recalculer, on va analyser dans l'autre sens : pour chaque « gear » on regarde dans combien de « number » il se trouve, si c'est 2, bingo, on l'ajoute.
C'est tout.
# Commencer à représenter le problème pas trop bêtement.
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023 : Day 2. Évalué à 2.
Ce coup-ci, avec une analyse des données, placées dans les bonnes structures, la seconde partie de l'exercice va se faire immédiatement après la première.
Ici on a encore un truc assez simple, et on va faire un dictionnaire avec en clé le numéro de la partie et en valeur une liste de triplets (rouge, vert, bleu), avec des zéros là où on n'a pas d'infos en entrée.
-> Normaliser les entrées, avoir une structure assez facile à analyser ensuite.
Déjà, j'abuse des yields et des générateurs, c'est pas encore utile, mais ça va venir.
Pour la partie 1 on va avoir une fonction de validation, et après on fait une somme :
Et là, pour la seconde partie on n'a même plus besoin de fonction de validation, le calcul est immédiat, même si le code est moche. Y'aurait moyen avec des structures de données de numpy de se passer de certaines méthodes peu explicites avec directement des comparaisons de vecteurs, ou un produit vectoriel. Bah, pas encore, on reste en python chocolat, poire… Vanille !
Le reduce sert à multiplier entre eux tous les éléments de la liste, et le zip va transformer une liste de triplets (r, v, b) en triplet de listes ([r, r, r…], [v, v, v…], [b, b, b…]).
Jusqu'ici, ya pas grand chose à déclarer, on manipule des données, on n'a même pas vraiment besoin de trop se compliquer à trouver les bonnes structures de données.
# Premier jour : on n'optimise pas, on fonce dans l'tas !
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023 : Day 1. Évalué à 2.
Le premier exercice est trivial :
On fait
python3 01.py < 01.inputou01.demopour les données de test, et hop, résultat en une commande.Le second exercice sans optimisation consiste à rechercher les chiffres et les chiffres écrits, ajouter ça dans une liste, et faire pareil :
La fonction analyze prend une ligne, la parcours charactère par charactère, et regarde si c'est un chiffre, ou l'écriture d'un chiffre, et envoie dans l'itérateur.
Zéro intelligence, zéro optimisation, zéro plantage.
Bientôt on pourra plus faire comme ça !
Mais bon, jour 1, on se dérouille les neurones, on reprend le pli des traitements de flux, on essaie déjà de mettre des itérateurs plutôt que de tout traiter en mémoire, juste pour reprendre les futurs bonnes habitudes…
[^] # Re: y'a un forum dédié
Posté par Yth (Mastodon) . En réponse au journal Advent of code 2023. Évalué à 2.
Poste ton code ?
[^] # Re: J'y retourne !
Posté par Yth (Mastodon) . En réponse au journal Advent of code 2023. Évalué à 3.
C'était dans Programmation.Autre, j'ai pas trop le temps ce week-end, mais si quelqu'un veut démarrer.
[^] # Re: Plusieurs leaderboards privés ?
Posté par Yth (Mastodon) . En réponse au journal Advent of code 2023. Évalué à 3.
A priori oui, on peut.
[^] # Re: Je veux pas être méchant mais...
Posté par Yth (Mastodon) . En réponse au lien COP28 à Dubaï : des scientifiques organisent leur propre sommet en protestation . Évalué à 10.
Je m'inscris complètement en faux par rapport à l'infox comme quoi Macron serait centriste.
[^] # Re: Normalisation
Posté par Yth (Mastodon) . En réponse au lien Avec la langue — Sur l'échelle du purisme, vous vous situez où? (Une tentation très française). Évalué à 4.
L'histoire, la géographie, les maths, la physique, la chimie, la biologie, etc.
Tout ça non plus n'est pas « normé ».
Par contre, comme pour la langue française, il y a un programme, assez précis, des manuels qui explicitent ce programme et sont validés par le ministère, et les élèves sont évalués sur ce programme.
Il n'est nulle part question de droit, et aucune loi n'impose que la note d'une dictée soit faite sur une base équitable, normée ou quoi que ce soit.
[^] # Re: wesh
Posté par Yth (Mastodon) . En réponse au lien Avec la langue — Sur l'échelle du purisme, vous vous situez où? (Une tentation très française). Évalué à 7.
Un parent ?
[^] # Re: Rimes de mauvaise foi
Posté par Yth (Mastodon) . En réponse au lien Avec la langue — Sur l'échelle du purisme, vous vous situez où? (Une tentation très française). Évalué à 5.
Je suis assez perturbé, toujours, par l'académie française.
Défendre la langue oui, mais essayer de la normer, ou plutôt de normer ses évolutions, ben nettement moins.
Défendre des constructions et des orthographes qui portent du sens et évitent des confusions, c'est important.
Quand les gens confondent à l'écrit « serez » et « saurez », ça m'affole un poil.
Mais lire « T ou 2m1? » me dérange beaucoup moins.
Moi aussi j'essaie d'avoir une bonne orthographe et une bonne grammaire, de manière générale une bonne maîtrise de la langue, parce que je considère que connaître le cadre, forcément un peu rigide, est la première étape pour le transcender, et apporter du sens par les transgressions qu'on y apporte.
Sous forme de néologismes, barbarismes, jeux de mots, fautes assumées, etc., si on connaît la « bonne façon » d'écrire, le fait d'écrire mal exprès fait aussi passer des messages.
Et évidemment, ce que j'accepte chez moi, je l'accepte chez les autres.
Alors oui, je tique quand je voit écrit ça, et je pourrais même faire la remarque dans certains cas. Mais les évolutions et les nouveautés, j'adore, c'est ce qu'il y a de plus excitant dans la langue, jouer avec, la faire vivre :)
[^] # Re: Je veux pas être méchant mais...
Posté par Yth (Mastodon) . En réponse au lien COP28 à Dubaï : des scientifiques organisent leur propre sommet en protestation . Évalué à 8.
Chais pas trop, en France, sur l'intégralité de la 5è république, on a eu 70% de présidences de droite (45 ans) et 30% de présidences de gauche (19 ans).
Vers où cet échiquier politique penchait-il donc par le passé ?
En tout cas, il y a eu des écologistes aux présidentielles depuis 1974, soit plus des trois quarts de l'existence de la Vè, mais l'échiquier n'a jamais penché de ce côté là.
[^] # Re: J'y retourne !
Posté par Yth (Mastodon) . En réponse au journal Advent of code 2023. Évalué à 10. Dernière modification le 01 décembre 2023 à 12:36.
Aussi, nous sommes 4 à avoir eu 50 étoiles, et 4 de plus à en avoir eu plus de 40.
Sachant que la fin est relativement fastidieuse, avec des algos qui peuvent prendre du temps, et donc un débuggage allongé d'autant, jusqu'à la veille de Noël où on peut avoir franchement autre chose à faire : ne pas chercher à finir est entièrement compréhensible.
Quand ça cesse d'être fun, ça cesse d'être fun.
Mais vivement dans quelques jours quand ça commencera à devenir fun, et qu'il faudra avoir de vraies idées d'algorithmie pour affronter les épreuves :)
Bon courage à toutes celles et tout ceux qui vont participer !
# J'y retourne !
Posté par Yth (Mastodon) . En réponse au journal Advent of code 2023. Évalué à 10.
Je remet ça cette année :)
Premier conseil pour ceux qui s'y mettent : testez vos programme avec les données de démo avant d'envoyer un résultat.
Les cas particuliers ne sont pas décrits dans les énoncés, mais sont souvent présents dans les données de test.
Par exemple, premier jour de 2023, second challenge ligne 2 : "eightwothree".
L'approche « facile » consiste à faire des remplacement de chaînes : "one" par "1", "two" par "2", etc.
Si on fait ça sans réfléchir et dans l'ordre, notre chaîne devient alors : "eigh23", et on a comme valeur 23.
Mais on devrait remplacer le début de la chaîne, "eight" par 8, et obtenir 83 comme résultat.
Une simple validation avec les données de test montre qu'on s'est planté…
Si ça sent le vécu, c'est parce que ça sent le vécu.
Second conseil, en Python, mais surtout utile à partir de la moitié en général : utilisez PyPy quand les algos commencent à boucler à mort et traiter des millions de cas, ça peut aller de 20 à 50 fois plus vite, sans rien changer au code.
Et abusez des générateurs, pour éviter les explosions de mémoire.
[^] # Re: Dommage
Posté par Yth (Mastodon) . En réponse à la dépêche Comparaison critique de systèmes d'invite de commande. Évalué à 2.
Ton commentaire avait l'air tellement intéressant !
Mais je me suis arrêté à chaosphere.
Dommage…
[^] # Re: Le moi d'il y a 10 ans aurait adoré
Posté par Yth (Mastodon) . En réponse à la dépêche Comparaison critique de systèmes d'invite de commande. Évalué à 6.
Mon prompt est assez basique, il fait :
user@machine:dir$Mais le nom d'utilisateur est en rouge quand c'est root et en vert sinon.
Et le nom de la machine est d'une couleur différente selon la machine.
Et le répertoire est toujours complet, je déteste les répertoires réduits, juste le dernier chemin, ou des pointillés.
Parfois c'est moche et ça fait un prompt de 12 kilomètres.
Parfois.
Et ben ça me fait gagner un temps fou de juste voir le rouge, là, à l'endroit où j'écris ma commande, mais sans être trop intrusif non plus. D'avoir toujours conscience de si l'utilisateur du shell à l'écran peut faire des conneries ou pas.
C'est aussi utile pour se dépatouiller des SSH, le nom de la machine n'est pas toujours évident sans avoir besoin d'être lu, alors qu'une couleur différente, ça va sauter aux yeux qu'on est en SSH sur une autre machine.
En fait t'as besoin de deux couleurs : une pour la machine locale, une pour les machines accessibles uniquement à distance, après je lis le nom de la machine pour bien vérifier où je suis.
Et s'il n'y a aucune couleur, je sais que je suis sur une autre machine, que je ne gère pas, et donc que j'y suis pour une raison précise, et ça saute encore plus aux yeux !
Bah voilà, ça va pas très loin, c'est de la conf statique (la couleur est paramétrée dans le .bashrc), et pif je gagne du temps, et je perds des chances de faire des boulettes.
Pour un effort somme toute assez minimal de paramétrage.
C'est bon, j'ai relevé ton défi, j'ai gagné quoi ?
[^] # Re: Peut-être…
Posté par Yth (Mastodon) . En réponse au lien Faut-il faire peur pour sauver la planète ?. Évalué à 2.
Et donc la façon naturelle de régler les choses c'est de laisser l'environnement se dégrader jusqu'à perte brutale de la population humaine, sans obligatoirement une extinction.
On est sur la bonne voie :)
[^] # Re: Peut-être…
Posté par Yth (Mastodon) . En réponse au lien Faut-il faire peur pour sauver la planète ?. Évalué à 2.
Alors contrairement à ce que cette phrase laisse entendre, un cancer ce n'est pas une croissance dérégulée, mais une absence de décroissance.
En fait nos cellules ont déjà un rythme de reproduction effréné, mais elles sont recyclées à peu près au même rythme.
Dans un cancer il y a défaut de recyclage, les cellules restent, la tumeur grossit, mais pas plus vite que la croissance classique des cellules.
De fait j'ai un peu de mal à faire une analogie avec notre société… Je suppose qu'on a en effet un grave déficit de recyclage, et qu'on aurait bien besoin de ne pas simplement jeter, mais de reconstruire.
C'est le principe de l'économie circulaire : tu produits de la valeur en fabricant un bidule.
Puis tu le récupère et en extrait la matière utile, produisant à nouveau de la valeur.
Cette matière utile sert à reconstruire un autre bidule, en créant donc de la valeur.
On arrive à une création de valeur à chaque étape, sans extraction de matière première après le lancement du cycle.
Toute la subtilité est dans l'énergie employée à chaque étape. Et la quantité de pertes aussi.
[^] # Re: Peut-être…
Posté par Yth (Mastodon) . En réponse au lien Faut-il faire peur pour sauver la planète ?. Évalué à 10.
La France : 2% des émissions pour 0,8% de la population.
Et ce très mauvais résultat est atteint avec une électricité presque entièrement décarbonée (j'ai pas dis non-polluante).
Ça fout un peu la honte cet argument de dernier de la classe…
[^] # Re: avis partial
Posté par Yth (Mastodon) . En réponse au lien «En français, le masculin fait l’homme, le dominant, il ne “fait pas le neutre”» (article partiel). Évalué à 3.
Est-ce que tu dis « D point bidule » à l'oral ?
Non, tu dis Docteur bidule.
C'est pas oralisable, c'est un défaut de cette façon de faire.
Ça ne la rend pas du tout inadaptée pour la plaque en bas de l'immeuble.
Et en plus c'est assez aisé à dérouler : ça remplace un mot unique, donc ça se ré-oralise facilement, ce qui n'est pas le cas de la notation avec le point médian.
Voilà, je pointe un défaut, qui freine son adoption, parce que l'objectif ici c'est d'inclure plus de gens dans les discours, à la fois à l'oral et à l'écrit.
On a une solution qui passe mal de l'un à l'autre.
Jamais je n'ai dis qu'il fallait la jeter, j'ai simplement pointé un défaut.
C'est possible de discuter des qualités et défauts d'un truc quelconque sans que le fait de pointer un défaut ne fasse de nous un fanatique anti-truc-quelconque ?
Je sais que la mode est est au tout noir/tout blanc, si t'es pas avec moi t'es contre moi, blabla, mais je dois être un vieux con, parce que c'est pas ma façon de faire, merci.