Et 6h30 après la publication du problème, il n'y avait que 2500 personnes à avoir eu une solution complète.
Pour ma part j'ai mis 25 minutes à coder la seconde partie à partir de la première, et la valider sur les données de test, en pleine visio boulot.
Puis 5 minutes à installer pypy et vérifier comment ça marche (réponse : bien).
Et 15 minutes de calculs pour avoir une solution... (J'ai killé la version cpython au bout de 20 minutes)
J'ai laissé tourner en espérant que ça allait marcher.
À noter que je stocke tous les chemins, puis je trie et je pond le dernier.
C'est utile pour le débuggage, mais complètement crétin : on peut toujours comparer au fur et à mesure et ne conserver que le dernier !
Fallait s'en douter déjà : sur les données de test, j'explore toujours les 720 possibilités, donc il y a sûrement une optimisation possible, pourtant aujourd'hui j'ai suivi mon conseil : réfléchir avant d'agir.
Pas assez...
J'ai recodé pour ne garder en mémoire que le meilleur chemin, et pas tous les chemins triés après coup.
Données de test, avec python3, plus rapide que pypy3 sur un délais aussi court : Ex1 en 0.05s : Score 1651, 720 chemins explorés AA->DD->BB->JJ->HH->EE->CC Ex2 en 0,07s : Score 1707, 720 chemins explorés AA->JJ->BB->CC AA->DD->HH->EE
Données réelles, avec pypy : Ex1 en 0,5s : Score 1871, 106 839 chemins explorés Ex2 en 2min21 : Score 2416, 37 306 254 chemins explorés
Et là, je réalise que les 15 minutes c'était 13 minutes pour afficher 37 millions de foutues lignes dans mon terminal débile, et peut-être un peu de temps pour gérer la RAM explosive de la liste de 37 millions d'entrées, et la trier à la fin...
Non mais sérieux...
Au passage cpython prends 2,1 secondes pour l'exo 1 réel contre 0,5 secondes pour pypy3.
Mais pour l'exo 2, pypy prend 2min21 quand cpython monte à plus de 20 minutes (il a pas terminé là).
pypy3 prend 108Mo de RAM, fixe quand on fait pas le crétin.
cpython3 reste à 12Mo de RAM, là aussi quand on ne fait pas l'idiot.
Et j'ai découvert que quand la RAM se réduit, Firefox décharge naturellement les onglets ouverts, pour rétrécir plutôt que de mourir !
# Ça chauffe, ça chauffe !
Posté par Yth (Mastodon) . En réponse au message Avent du Code jour 16. Évalué à 3.
Et 6h30 après la publication du problème, il n'y avait que 2500 personnes à avoir eu une solution complète.
Pour ma part j'ai mis 25 minutes à coder la seconde partie à partir de la première, et la valider sur les données de test, en pleine visio boulot.
Puis 5 minutes à installer pypy et vérifier comment ça marche (réponse : bien).
Et 15 minutes de calculs pour avoir une solution... (J'ai killé la version cpython au bout de 20 minutes)
J'ai laissé tourner en espérant que ça allait marcher.
À noter que je stocke tous les chemins, puis je trie et je pond le dernier.
C'est utile pour le débuggage, mais complètement crétin : on peut toujours comparer au fur et à mesure et ne conserver que le dernier !
Fallait s'en douter déjà : sur les données de test, j'explore toujours les 720 possibilités, donc il y a sûrement une optimisation possible, pourtant aujourd'hui j'ai suivi mon conseil : réfléchir avant d'agir.
Pas assez...
J'ai recodé pour ne garder en mémoire que le meilleur chemin, et pas tous les chemins triés après coup.
Données de test, avec python3, plus rapide que pypy3 sur un délais aussi court :
Ex1 en 0.05s : Score 1651, 720 chemins explorés
AA->DD->BB->JJ->HH->EE->CCEx2 en 0,07s : Score 1707, 720 chemins explorés
AA->JJ->BB->CC AA->DD->HH->EEDonnées réelles, avec pypy :
Ex1 en 0,5s : Score 1871, 106 839 chemins explorés
Ex2 en 2min21 : Score 2416, 37 306 254 chemins explorés
Et là, je réalise que les 15 minutes c'était 13 minutes pour afficher 37 millions de foutues lignes dans mon terminal débile, et peut-être un peu de temps pour gérer la RAM explosive de la liste de 37 millions d'entrées, et la trier à la fin...
Non mais sérieux...
Au passage cpython prends 2,1 secondes pour l'exo 1 réel contre 0,5 secondes pour pypy3.
Mais pour l'exo 2, pypy prend 2min21 quand cpython monte à plus de 20 minutes (il a pas terminé là).
pypy3 prend 108Mo de RAM, fixe quand on fait pas le crétin.
cpython3 reste à 12Mo de RAM, là aussi quand on ne fait pas l'idiot.
Et j'ai découvert que quand la RAM se réduit, Firefox décharge naturellement les onglets ouverts, pour rétrécir plutôt que de mourir !
Donc merci à Steph pour l'idée d'utiliser pypy :)