Défi Turing : du MPO à la pelle
Modérateur : Politburo
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Défi Turing : du MPO à la pelle
Je suis inscrit dans une sympathique compétition de petits programmes à monter pour répondre à des énigmes mathématiques.
Défi Turing http://www.apprendre-en-ligne.net/turing/index.php.
Certains sont inaccessibles à nos vieilles compagnes (des milliards de calculs parfois) mais il y a matière à s'amuser un peu pour nos longues soirées d'hiver...
Par exemple le n°77 qui parait impossible mais avec une petite astuce ma HP71B la résout en 34 secondes...
Problème 77
Somme de deux carrés
Deux nombres de 4 chiffres ont la propriété suivante : abcd = ab^2 + cd^2.
1233 = 12^2 + 33^2
8833 = 88^2 + 33^2
Quel est le plus grand nombre de 8 chiffres de ce type : abcdefgh = abcd^2 + efgh^2 ?
Avis aux amateurs ! Il y a un problème nouveau chaque semaine et 100 actuellement en stock...
Défi Turing http://www.apprendre-en-ligne.net/turing/index.php.
Certains sont inaccessibles à nos vieilles compagnes (des milliards de calculs parfois) mais il y a matière à s'amuser un peu pour nos longues soirées d'hiver...
Par exemple le n°77 qui parait impossible mais avec une petite astuce ma HP71B la résout en 34 secondes...
Problème 77
Somme de deux carrés
Deux nombres de 4 chiffres ont la propriété suivante : abcd = ab^2 + cd^2.
1233 = 12^2 + 33^2
8833 = 88^2 + 33^2
Quel est le plus grand nombre de 8 chiffres de ce type : abcdefgh = abcd^2 + efgh^2 ?
Avis aux amateurs ! Il y a un problème nouveau chaque semaine et 100 actuellement en stock...
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
Re: Défi Turing : du MPO à la pelle
oublions déjà la méthode brutale,même sur une calculatrice rapide genre HP PRIMEcaloubugs a écrit :J
Quel est le plus grand nombre de 8 chiffres de ce type : abcdefgh = abcd^2 + efgh^2 ?[/i].
Code : Tout sélectionner
EXPORT MPO()
BEGIN
X:=1e8;
REPEAT
X:=X-1;Z:=X/1e4;
UNTIL X==IP(Z)²+(FP(Z)*1E4)²;
RETURN X;
END;
EDIT : OK je l'ai, pas d'erreur dans le programme mais beaucoup plus lent que la HP71
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5270
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Défi Turing : du MPO à la pelle
@Gilles59 : ton programme utilise la méthode brute, il revient à tester toutes les combinaisons.
C'est équivalent à avoir deux boucles imbriquées, chacune de 1 à 9999.
J'ai une autre piste, elle donne une solution, il se trouve que c'est le plus grand nombre mais la méthode ne garantie pas que le nombre trouvé soit le plus grand.
Par contre elle est beaucoup plus lente que celle de la hp71b : 114s au lieu de 34s.
C'est l'algo ou est ce que la hp71b est beaucoup plus rapide que la hp48sx?
Il faut remplacer SQRT par le symbole racine carrée.
ÉDIT : j'ai testé le même programme sur hp71b et il trouve la solution en 3min26. C'est bien l'algo qu'il faut améliorer.
C'est équivalent à avoir deux boucles imbriquées, chacune de 1 à 9999.
J'ai une autre piste, elle donne une solution, il se trouve que c'est le plus grand nombre mais la méthode ne garantie pas que le nombre trouvé soit le plus grand.
Par contre elle est beaucoup plus lente que celle de la hp71b : 114s au lieu de 34s.
C'est l'algo ou est ce que la hp71b est beaucoup plus rapide que la hp48sx?
Code : Tout sélectionner
<< 2 -> I <<
WHILE
I I SQ - 25e6 + SQRT DUP FP
REPEAT
DROP
'I' 1 STO+
END
5000 - 10000 * I +
>>
>>
ÉDIT : j'ai testé le même programme sur hp71b et il trouve la solution en 3min26. C'est bien l'algo qu'il faut améliorer.
HP, Casio, Sharp, Psion, quelques TI et divers autres
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Défi Turing : du MPO à la pelle
Tout cela est bien long, je trouve les deux solutions 1233 et 8833 en 5s avec mon HP28S, qui pourtant n'est pas un foudre de guerre.
L'algorithme suivit est le suivant,
Pour déterminer les entier abcd, je cherche à calculer la partie cd pour ab donné.
L'égalité abcd = ab² + cd² est transcrite à l'aide de deux variables, la donnée ab et le résultat cherché cd :
On doit donc trouver cd tel que 100*ab + cd = ab*ab + cd*cd
On résoud ainsi une équation du second degré en cd et les solution possible sont de la forme : 2*cd = (1 ± √(1+4*(100-ab)*ab)
Evidemment, en parcourant le domaine des valeur de ab, on ne retiendra que les solution entières, c'est à dire celle dont le terme sous le radical de la racine sont des carrés parfaits.
Par ailleurs, cd étant positif, seule la solution 2*cd = (1 + √(1+4*(1000-ab)*ab) est à retenir.
J'obtient donc le code suivant:
Il ne me reste plus qu'à étendre le principe pour des nombres à 6, 8, 10 ou 12 chiffres :
Je trouve { 1233 8833 990100 ... } en environ 1 min (en évitant les affiches de m)
Evidemment cela va de moins en moins vite.
Reste à trouver un moyen de ne pas tester toutes les valeurs m, mais uniquement celles qui sont proches (de part et d'autre) d'un carré parfait.
L'algorithme suivit est le suivant,
Pour déterminer les entier abcd, je cherche à calculer la partie cd pour ab donné.
L'égalité abcd = ab² + cd² est transcrite à l'aide de deux variables, la donnée ab et le résultat cherché cd :
On doit donc trouver cd tel que 100*ab + cd = ab*ab + cd*cd
On résoud ainsi une équation du second degré en cd et les solution possible sont de la forme : 2*cd = (1 ± √(1+4*(100-ab)*ab)
Evidemment, en parcourant le domaine des valeur de ab, on ne retiendra que les solution entières, c'est à dire celle dont le terme sous le radical de la racine sont des carrés parfaits.
Par ailleurs, cd étant positif, seule la solution 2*cd = (1 + √(1+4*(1000-ab)*ab) est à retenir.
J'obtient donc le code suivant:
Code : Tout sélectionner
« 10 99 FOR ab
1 100 ab - ab * 4 * + √
IF DUP FP NOT THEN
1 + 2 / ab 100 * +
ELSE DROP END
NEXT »
Code : Tout sélectionner
« {} @ Initialise la liste des nombres
1 6 FOR p @ Recherche les nombre de 2, 4, ... et 12 chiffres
p ALOG → b @ Ce qui revient à travailler en base 10, 100, 1000 .... 10000
« p 1 - ALOG 1 + b 1 - FOR m @ Pour m variant de 1…1 à 9…9
m 4 DISP @ Affiche afin de faire patienter
1 b m - m * 4 * + √ @ Evalue la solution
IF DUP FP NOT THEN @ Vérifie que le carré est parfait
1 + 2 / m b * + + @ Ajoute le nombre ab…fg à la liste des nombres
DUP 1 DISP @ Affiche afin de faire patienter
ELSE DROP END
NEXT »
NEXT »
Evidemment cela va de moins en moins vite.
Reste à trouver un moyen de ne pas tester toutes les valeurs m, mais uniquement celles qui sont proches (de part et d'autre) d'un carré parfait.
Modifié en dernier par C.Ret le 16 nov. 2014 10:29, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5270
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Défi Turing : du MPO à la pelle
Les durées données précédemment sont pour la solution à 8 chiffres.C.Ret a écrit :Tout cela est bien long, je trouve les deux solutions 1233 et 8833 en 5s avec mon HP28S, qui pourtant n'est pas un foudre de guerre.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Re: Défi Turing : du MPO à la pelle
Hello Bernouilli, C'est bien ce que je voulais dire avec ma formulation ambigue :bernouilli92 a écrit :@Gilles59 : ton programme utilise la méthode brute, il revient à tester toutes les combinaisons..
Que ma méthode brute est à oublier sur nos machines même avec une HP PRIME (quoique ca marche en quelques dizaines de minutes)
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Défi Turing : du MPO à la pelle
A zut, il me faut presque 18 min pour tester tous les nombres de 2 à 8 chiffres ! (J'en trouve 5 d'ailleurs)bernouilli92 a écrit :Les durées données précédemment sont pour la solution à 8 chiffres.
A zut, si en plus il faut faire en moins de 10 min, je ne suis plus dans le coup.Gilles59 a écrit :Que ma méthode brute est à oublier sur nos machines même avec une HP PRIME (quoique ca marche en quelques dizaines de minutes)
Mais, sur nos calculettes, 10 min c'est rapide ! Ce qui prouve bien que c'est parfaitement réalisable sur une HP prime !
J'ose pas sortir mon SHARP PC-1211 !
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5270
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Défi Turing : du MPO à la pelle
Si cela met 10 min sur une Prime, ce qui reste acceptable, je me demande combien cela prendrait sur une hp 41, sûrement plus d'une journée.C.Ret a écrit : Mais, sur nos calculettes, 10 min c'est rapide ! Ce qui prouve bien que c'est parfaitement réalisable sur une HP prime !
J'ose pas sortir mon SHARP PC-1211 !
ÉDIT : cela devrait prendre de l'ordre de 14h sur une hp48sx.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Re: Défi Turing : du MPO à la pelle
C'est bien plus de 10mn sur Prime en recherche exhaustive (et encore on a la chance que ... )
Si on commence à calculer par les chiffres de droite comme on le ferait à la main, les contraintes fortes apparaissent ...
Par exemple: abcd = ab^2 + cd^2.
si d=0 alors forcément b=0 alors c<>0 alors cd² finit par 00 => impossible (10% de recherche en moins)
si d=1 alors forcément b=0 alors etc ....
si d=2 alors b=? impossible puisque b²+4 doit finir par 2 (çà divise le temps de recherche par 2)
etc etc
je me demande même si quelque chose de tres proche (voir la même chose) n'est pas dans ce forum déjà.
Si on commence à calculer par les chiffres de droite comme on le ferait à la main, les contraintes fortes apparaissent ...
Par exemple: abcd = ab^2 + cd^2.
si d=0 alors forcément b=0 alors c<>0 alors cd² finit par 00 => impossible (10% de recherche en moins)
si d=1 alors forcément b=0 alors etc ....
si d=2 alors b=? impossible puisque b²+4 doit finir par 2 (çà divise le temps de recherche par 2)
etc etc
je me demande même si quelque chose de tres proche (voir la même chose) n'est pas dans ce forum déjà.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
- gege
- Fonctionne à 14400 bauds
- Messages : 7148
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Défi Turing : du MPO à la pelle
Bonjour,
Intéressant, les problèmes vont de 'semble simple' à 'oulà dur dur'...
De longues soirées d' "amusement" en vue, merci.
G.E.
Intéressant, les problèmes vont de 'semble simple' à 'oulà dur dur'...
De longues soirées d' "amusement" en vue, merci.
G.E.
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Défi Turing : du MPO à la pelle
Hello à tous,
La solution évidente est trop longue pour nos grands-mères, en Python je l'avais joué bourrin.
Par contre un participant a fait un algo qui rend ce pb accessible (15 s sur z1gr).
J'en suis à 60 problèmes de résolus (donc pas si mal classé que ça... C'est pour titiller certains ici )
Je vais suivre le classement avec intérêt
Et pour les sujets oulala, y'a le 75 :
Un dialogue de fous. Quoique...
X et Y sont deux nombres entiers différents, supérieurs à 1, avec X+Y < 100.
Simon et Paul sont deux mathématiciens. Simon connaît la somme S=X+Y. Paul connaît le produit P=X*Y. Simon sait que Paul connaît le produit et Paul sait que Simon connaît la somme.
Une conversation s'engage entre les deux mathématiciens :
Paul dit: "Je ne peux pas trouver ces nombres."
Simon dit: "J'étais sûr que vous ne pouviez pas les trouver. Je ne peux pas les trouver non plus."
Paul dit: "Alors, j'ai trouvé ces nombres."
Simon dit: "Si vous avez pu les trouver, alors je les ai aussi trouvés."
Quels sont ces nombres ? Donner comme réponse le produit X*Y*S*P
La solution évidente est trop longue pour nos grands-mères, en Python je l'avais joué bourrin.
Par contre un participant a fait un algo qui rend ce pb accessible (15 s sur z1gr).
J'en suis à 60 problèmes de résolus (donc pas si mal classé que ça... C'est pour titiller certains ici )
Je vais suivre le classement avec intérêt
Et pour les sujets oulala, y'a le 75 :
Un dialogue de fous. Quoique...
X et Y sont deux nombres entiers différents, supérieurs à 1, avec X+Y < 100.
Simon et Paul sont deux mathématiciens. Simon connaît la somme S=X+Y. Paul connaît le produit P=X*Y. Simon sait que Paul connaît le produit et Paul sait que Simon connaît la somme.
Une conversation s'engage entre les deux mathématiciens :
Paul dit: "Je ne peux pas trouver ces nombres."
Simon dit: "J'étais sûr que vous ne pouviez pas les trouver. Je ne peux pas les trouver non plus."
Paul dit: "Alors, j'ai trouvé ces nombres."
Simon dit: "Si vous avez pu les trouver, alors je les ai aussi trouvés."
Quels sont ces nombres ? Donner comme réponse le produit X*Y*S*P
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- bellamy
- Fonctionne à 1200 bauds
- Messages : 332
- Enregistré le : 18 nov. 2011 14:08
- Localisation : Nantes
Re: Défi Turing : du MPO à la pelle
Je me suis inscrit à ce site merci pour le tuyau !
Précision : le challenge c'est de trouver la réponse en moins d'une minute
Précision : le challenge c'est de trouver la réponse en moins d'une minute
______________
Bellamy
Bellamy
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5270
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Défi Turing : du MPO à la pelle
Oui, sur un PC.bellamy a écrit :Je me suis inscrit à ce site merci pour le tuyau !
Précision : le challenge c'est de trouver la réponse en moins d'une minute
HP, Casio, Sharp, Psion, quelques TI et divers autres
Re: Défi Turing : du MPO à la pelle
12 résolus en RPL (pseudo nemo59)... j'ai mis les sources dans les solutions...
Sur une calculatrice la limite de la minute n'a pas grand sens comparé à des quadri-coeurs 4Ghz et autres bêtes de course ;D L'idée de la limite de temps est plutôt pour inciter à trouver des algo malins (ce que je n'ai pas beaucoup fait encore) ... d'ailleurs cette limite de temps a aboutit à des effets pervers sur Euler Project (çà ressemble beaucoup dans l'esprit, j'en ai résolu une centaine largement en RPL) : même en optimisant çà ne tient plus du tout sur calculatrice ou même sur l'émulateur....
Sur une calculatrice la limite de la minute n'a pas grand sens comparé à des quadri-coeurs 4Ghz et autres bêtes de course ;D L'idée de la limite de temps est plutôt pour inciter à trouver des algo malins (ce que je n'ai pas beaucoup fait encore) ... d'ailleurs cette limite de temps a aboutit à des effets pervers sur Euler Project (çà ressemble beaucoup dans l'esprit, j'en ai résolu une centaine largement en RPL) : même en optimisant çà ne tient plus du tout sur calculatrice ou même sur l'émulateur....
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Défi Turing : du MPO à la pelle
Cool ! J'ai vu ton pseudo vite grimperGilles59 a écrit :12 résolus en RPL (pseudo nemo59)... j'ai mis les sources dans les solutions...
Sur une calculatrice la limite de la minute n'a pas grand sens comparé à des quadri-coeurs 4Ghz et autres bêtes de course ;D L'idée de la limite de temps est plutôt pour inciter à trouver des algo malins (ce que je n'ai pas beaucoup fait encore) ... d'ailleurs cette limite de temps a aboutit à des effets pervers sur Euler Project (çà ressemble beaucoup dans l'esprit, j'en ai résolu une centaine largement en RPL) : même en optimisant çà ne tient plus du tout sur calculatrice ou même sur l'émulateur....
Et tu auras vu l'optimisation de jodyl sur le défi 77... Fallait quand même le trouver !
Par contre y parvenir en moins d'une minute, c'est pas toujours facile sur nos vieux tromblons. Sans compter quelques programmes qui nécessitent du récursif...
On va pouvoir partager nos expériences !
Je ne connaissais pas Euler Project excepté les références mises sur le défi Turing (qui pompe du coup largement sur eux). Avec ces 2 là, on en a jusqu'à Noël 2020...
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...