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.
[^] # 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.