Forum de mathématiques - Bibm@th.net

Bonjour,

Eh oui, je le sais bien, c'est la première chose que je suis allé voir, et c'est là où c'est instructif : avec les outils dont je t'ai parlé, la solution ne va pas du tout être la même, et tout programme va être confronté à l'explosion combinatoire - ces défis sont justement faits pour. :-)

Bonsoir,

Si pour certains vouloir résoudre des problèmes, chercher des solutions et demander l’avis d’une communauté c’est être potentiellement capable du pire, pas pour moi. J’ai toujours plus appris en décortiquant les solutions des autres qu’en ayant affaire à des gens qui distillent leur savoir au compte-gouttes en me faisant mariner. D’ailleurs c’est simple, je ne demande quasiment plus rien ici tellement cet esprit me semble discutable.

Par ailleurs, puisqu’on veut à tout prix voir le mal partout, moi je dis bien fait. Dès qu’on instaure des challenges ou des récompenses même symboliques, on n’a que ce qu’on mérite, à savoir la quête du score (ou du podium) avec toutes les stratégies qui en découlent. Pratiquement tous les parcours ne prennent plus en compte que les épreuves en temps limité, gloire au plus rapide, gloire au mieux préparé, gloire à la compétition, au culte du meilleur, au narcissisme valorisé.

Perso je préfère l’esprit de l’encyclopédie, le savoir pour tous, vulgarisé, sans discrimination, et je ne partage pas les valeurs de ceux qui ont fait de l’apprentissage à l’ancienne leur fonds de commerce (le fameux no pain no gain), qui refusent de donner des réponses toute faites parcours initiatique oblige, et qui surtout exigent la rigueur d’un jargon obscur dont on connaît très bien les fonctions de tri et d'élimination.

Bonjour,

Et merci, tout à fait intéressant. L’explosion combinatoire rend quasiment impossible l’exploration des possibilités, si on décide de dérouler toutes les régates pour ne garder que celles qui répondent parfaitement aux contraintes, on va devoir développer les quatre milliards de régates et y faire les calculs qui vont bien pour ne garder que celles répondant aux contraintes, faut donc trouver le moyen de faire mieux.

Première étape, élagage maxi : on arrête les explorations dès qu’un critère ne pourra plus être rempli, on perd certes du temps à tester, mais on en gagne énormément en abandonnant des branches entières d’exploration de toute façon improductive.

Bon, à ce stade j’aimerais passer en Python de base, sans multi-coeurs ni bibliothèque. Là faut carrément changer d’approche, ne plus tester les séquences de courses, mais plutôt compter les combinaisons qui représentent le même bilan pour toutes les séquences qui y conduisent, ce qui permet de calculer le total exact beaucoup plus rapidement.

Reste maintenant à savoir si c’est juste…

Bonsoir,

Ah magnifique ! J'ai beau essayer de comprendre, il y a toujours des trucs que je loupe, donc un grand merci. Va falloir que je m'y remette, snifff, et donc que je trouve le temps. C'est déjà grâce à toi que j'ai compris que les sommets n'étaient pas à prendre dans l'ordre, et à partir du moment où je pouvais revenir sur certains, j'avais trouvé l'astuce de l'angle 0°, tout content que j'étais.

(hé hé, en fait le problème, pour des gens comme moi, c'est déjà le français)

Bonsoir,

Bonsoir,

Première approche, la projection plane d’un cube. La longueur maximale est obtenue quand une de ses grandes diagonales est parallèle au plan de projection je pense. Faut donc trouver une projection de tétraèdre qui minimise la plus grande longueur de sa projection plane, et appliquer ensuite le coefficient de proportionnalité entre cette longueur et celle de la diagonale sus-dite – et vérifier qu’aucune partie de cette projection ne déborde de la projection du cube bien sûr.

Rigolo.

Bonjour,

Ah oui, tout à fait surprenant. Après le 655 on trouve bien un 1 02 04 08 16 32 … Le 64 va passer à 65 à cause de la retenue du 128 qui suit, j’ai donc voulu en avoir le cœur net, j'ai itéré les puissances de 2 en décimales avec décalage :
0.01
0.0102
0.010204
0.01020408
0.0102040816
0.010204081632
0.01020408163264
0.0102040816326528
0.010204081632653056
0.01020408163265306112
0.0102040816326530612224
0.010204081632653061224448
0.01020408163265306122448896
0.0102040816326530612244897792
0.010204081632653061224489795584
0.01020408163265306122448979591168
0.0102040816326530612244897959182336
0.010204081632653061224489795918364672
0.01020408163265306122448979591836729344
0.0102040816326530612244897959183673458688
0.010204081632653061224489795918367346917376
0.01020408163265306122448979591836734693834752
0.0102040816326530612244897959183673469387669504
0.010204081632653061224489795918367346938775339008
0.01020408163265306122448979591836734693877550678016
0.0102040816326530612244897959183673469387755101356032
0.010204081632653061224489795918367346938775510202712064
0.01020408163265306122448979591836734693877551020405424128
0.0102040816326530612244897959183673469387755102040810848256
0.010204081632653061224489795918367346938775510204081621696512
0.01020408163265306122448979591836734693877551020408163243393024
0.0102040816326530612244897959183673469387755102040816326486786048
0.010204081632653061224489795918367346938775510204081632652973572096
0.01020408163265306122448979591836734693877551020408163265305947144192
0.0102040816326530612244897959183673469387755102040816326530611894288384
0.010204081632653061224489795918367346938775510204081632653061223788576768
0.01020408163265306122448979591836734693877551020408163265306122447577153536
0.0102040816326530612244897959183673469387755102040816326530612244895154307072
0.010204081632653061224489795918367346938775510204081632653061224489790308614144
...

D'une part on retrouve exactement les mêmes décimales, d'autre part on observe un cycle
...551020408163265306122448979591836734693877...

Bonsoir,

Et en plus ça marche avec 9 boules ! Bravo.

Bonsoir,

Arghhh, j'ai conclu trop vite ! Je m'étais focalisé sur l'énoncé de départ, et j'en avais conclu des séquences victorieuses. Eh bien ce n'est pas si simple, la parité concerne aussi le nombre de boîtes...

Bonsoir,

Ce qui a de fascinant, dans ce petit casse-tête, c’est la logique sous-jacente…

Bonsoir,

Les IA ne sont ni fiables ni crédibles. Je m'en sers comme assistants numériques, ni plus ni moins. À les entendre mon code est toujours au maximum de ce que permettrait le langage utilisé. ChatGPT me l'a dit quand j'étais à 0.15 s, puis quand j'étais à 0.041 s, et il me le confirme maintenant que je suis à 0.036 s.

Oui, bon, ok, mais y a-t-il quand même moyen de faire mieux, d'aller plus vite ? Nenni mon bon ami, qu’ils me disent tous.

Pourtant ce qui m'amuse dans ce genre de chose, c'est d’améliorer. Par exemple ici, puisque je pré-calcule les jours et les mois acceptables, eh bien pour trouver les années rien ne m'empêche de leur associer les chiffres restants disponibles, et m’en servir pour construire toutes les permutations de 4 chiffres parmi les 6 restants et de ne valider le couple 29/02 que si l'année est bissextile...

Nombre total de dates surprenantes : 46800
Durée : 0.022 s

Tadaa !

Oui, mais sauf que sur ce coup, c’est débile. D’une part parce que le 29/02 est invalide, donc pas la peine de tester les années bissextiles, ce que je fais pourtant depuis le début – honte à moi – et d’autre part parce qu’il est dès lors inutile de construire les 360 permutations de 4 chiffres parmi 6 vu qu'elles sont  valides par construction.

Résumé : donc en fait pour avoir le nombre de solutions, il suffit d’ajouter 360 chaque fois qu'un couple JJ/MM est valide , et c’est terminé.

Nombre de solutions : 46800
Temps (ms) : 1.0

On notera la concision de la ligne qui teste que les quatre chiffres sont distincts en éliminant les doublons grâce à set.

Une fois encore, merci à @Fred pour ce genre de casse-tête qui se prêtait vraiment bien à l’expérimentation je trouve.

Bonjour,

Oui, normalement, les casse-têtes sont résolubles à la main, avec papier, crayon et ingéniosité, c'est vrai. Maintenant je pense qu’il y a aussi un autre plaisir, celui par exemple de trouver un algorithme efficace pour dénombrer toutes les solutions.

On va faire un code Python le plus efficace possible, et qu’on le fasse avec un assistant numérique n’importe pas. Pour ne pas dépendre de bibliothèques spécialisées ou de puissance d’ordinateur, j’utilise Basthon (on colle le code dans le cadre de gauche et on clique en bas sur ‘Exécuter’). Quand ça dépasse la quinzaine de secondes j’ai une alerte navigateur, mais on peut laisser et le calcul continue tout de même.

Je me suis amusé à le faire et c’est rigolo de voir comment, au fil des améliorations, on peut gagner un temps considérable.

===== 1 =====
Le programme parcourt toutes les dates valides du calendrier grégorien entre les années 0001 et 9999, et compte celles dont les huit chiffres (JJMMAAAA) sont tous distincts — les « dates surprenantes ». Il vérifie l’unicité des chiffres, ainsi que les classes date et timedelta du module datetime pour avancer d’un jour à la fois.

Nombre total de dates surprenantes : 46800
Durée : 8 s

===== 2 =====
Le programme génère toutes les permutations possibles de 8 chiffres distincts et teste pour chacune si elle forme une date valide au format JJ.MM.AAAA. Il utilise une fonction basée sur datetime.date() pour vérifier l’existence réelle de la date. L’optimisation consiste à éviter de parcourir jour par jour le calendrier complet, en ne testant que les combinaisons de chiffres distincts — soit environ 1,8 million de cas au lieu de plus de 3,6 millions de jours.

Nombre total de dates surprenantes : 46800
Durée : 2 s

===== 3 =====
Maintenant le programme parcourt uniquement les années aux chiffres distincts et génère pour chacune uniquement les combinaisons de jours et mois utilisant les chiffres restants, en validant manuellement la date (mois à 30 jours, février et années bissextiles). L’amélioration clé est de réduire drastiquement l’espace de recherche : au lieu de tester 1,8 million de permutations, on ne considère plus que quelques centaines de milliers de combinaisons réellement possibles, ce qui explique le gain spectaculaire de vitesse.

Nombre total de dates surprenantes : 46800
Durée : 0.35 s

===== 4 =====
Cette fois le programme effectue un pré-calcul : pour chaque ensemble de 4 chiffres possibles, on génère toutes les paires jour/mois valides et on les stocke dans un dictionnaire.
- Ensuite, on ne conserve que les années aux 4 chiffres distincts, réduisant fortement l’espace de recherche.
- Pour chaque année, on identifie les chiffres restants qui peuvent être utilisés pour le jour et le mois.
- On récupère dans le dictionnaire toutes les paires JJ/MM possibles parmi ces chiffres restants, sans recalculer toutes les permutations.
- On vérifie la validité des dates (mois à 30 jours, février, années bissextiles) et on compte les dates surprenantes.

Nombre total de dates surprenantes : 46800
Durée : 0.06 s

===== 5 =====
Pour aller encore plus vite, le programme utilise maintenant des pré-calculs et des masques binaires (chaque bit représente un chiffre 0–9, ce qui permet de tester en une seule opération si les chiffres d’une paire JJ/MM sont disponibles dans l’année). Les paires jour/mois valides (JJ/MM) sont pré-calculées pour chaque ensemble de 4 chiffres et sélectionnées via un simple test bit à bit pour chaque année. La validité des dates est vérifiée avec un tableau des jours par mois, incluant février et les années bissextiles.

Nombre total de dates surprenantes : 46800
Durée : 0.04 s

Pour la petite histoire, je n’ai utilisé que ChatGPT. Il n’allait certes pas trouver cela tout seul, mais il a été capable, au fil des demandes et des corrections, de pondre des codes fonctionnels et efficaces.