Défi Turing : du MPO à la pelle

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 429
Inscription : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Défi Turing : du MPO à la pelle

Message par caloubugs » 15 nov. 2014 22:38

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...
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...

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1355
Inscription : 27 oct. 2010 20:46

Re: Défi Turing : du MPO à la pelle

Message par Gilles59 » 16 nov. 2014 00:27

caloubugs a écrit :J
Quel est le plus grand nombre de 8 chiffres de ce type : abcdefgh = abcd^2 + efgh^2 ?[/i].
oublions déjà la méthode brutale,même sur une calculatrice rapide genre HP PRIME

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;
Bon j'attends encore (en espérant qu'il n'y a pas d'erreur, je n'ai rien testé avant ;D)

EDIT : OK je l'ai, pas d'erreur dans le programme mais beaucoup plus lent que la HP71 :D
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+

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4174
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Défi Turing : du MPO à la pelle

Message par bernouilli92 » 16 nov. 2014 01:27

@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?

Code : Tout sélectionner

<< 2 -> I <<
    WHILE
      I I SQ - 25e6 + SQRT DUP FP
    REPEAT
       DROP
      'I' 1 STO+
    END
    5000 - 10000 * I +
  >>
>>
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.
HP, Casio, Sharp, Psion, quelques TI et divers autres

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2286
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Défi Turing : du MPO à la pelle

Message par C.Ret » 16 nov. 2014 10:57

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:

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 »
Il ne me reste plus qu'à étendre le principe pour des nombres à 6, 8, 10 ou 12 chiffres :

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 »
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.
Dernière édition par C.Ret le 16 nov. 2014 11:29, édité 1 fois.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4174
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Défi Turing : du MPO à la pelle

Message par bernouilli92 » 16 nov. 2014 11:21

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.
Les durées données précédemment sont pour la solution à 8 chiffres.
HP, Casio, Sharp, Psion, quelques TI et divers autres

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1355
Inscription : 27 oct. 2010 20:46

Re: Défi Turing : du MPO à la pelle

Message par Gilles59 » 16 nov. 2014 11:21

bernouilli92 a écrit :@Gilles59 : ton programme utilise la méthode brute, il revient à tester toutes les combinaisons..
Hello Bernouilli, C'est bien ce que je voulais dire avec ma formulation ambigue :
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+

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2286
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Défi Turing : du MPO à la pelle

Message par C.Ret » 16 nov. 2014 12:01

bernouilli92 a écrit :Les durées données précédemment sont pour la solution à 8 chiffres.
A zut, il me faut presque 18 min pour tester tous les nombres de 2 à 8 chiffres ! (J'en trouve 5 d'ailleurs)
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)
A zut, si en plus il faut faire en moins de 10 min, je ne suis plus dans le coup.

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 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4174
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Défi Turing : du MPO à la pelle

Message par bernouilli92 » 16 nov. 2014 12:21

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 !
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.

ÉDIT : cela devrait prendre de l'ordre de 14h sur une hp48sx.
HP, Casio, Sharp, Psion, quelques TI et divers autres

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1355
Inscription : 27 oct. 2010 20:46

Re: Défi Turing : du MPO à la pelle

Message par Gilles59 » 16 nov. 2014 13:05

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à.
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+

Avatar de l’utilisateur
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6933
Inscription : 31 janv. 2008 15:24
Localisation : Banlieue Paârisienne
Contact :

Re: Défi Turing : du MPO à la pelle

Message par gege » 16 nov. 2014 17:49

Bonjour,
Intéressant, les problèmes vont de 'semble simple' à 'oulà dur dur'...
De longues soirées d' "amusement" en vue, merci.
G.E.

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 429
Inscription : 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

Message par caloubugs » 16 nov. 2014 22:47

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 :mrgreen: )

Je vais suivre le classement avec intérêt :geek:

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...

Avatar de l’utilisateur
bellamy
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 346
Inscription : 18 nov. 2011 15:08
Localisation : Nantes

Re: Défi Turing : du MPO à la pelle

Message par bellamy » 17 nov. 2014 19:05

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 :mrgreen:
______________
Bellamy

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4174
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Défi Turing : du MPO à la pelle

Message par bernouilli92 » 17 nov. 2014 19:13

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 :mrgreen:
Oui, sur un PC.
HP, Casio, Sharp, Psion, quelques TI et divers autres

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1355
Inscription : 27 oct. 2010 20:46

Re: Défi Turing : du MPO à la pelle

Message par Gilles59 » 17 nov. 2014 21:24

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....
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+

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 429
Inscription : 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

Message par caloubugs » 17 nov. 2014 23:19

Gilles59 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....
Cool ! J'ai vu ton pseudo vite grimper 8O
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...

Répondre

Revenir vers « Tous les Pockets »