Misez p'tit Optimisez n°91 : balade du cavalier

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
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par C.Ret »

Bon, en publiant le code ci-dessus, j'ai vu le moyen de gagner quelques trois octets : j'en profite pour mettre en évidence la structure du code:
MPO91 - HP-15C méthode  Wansdorf  - Code rapide.gif
MPO91 - HP-15C méthode Wansdorf - Code rapide.gif (201.02 Kio) Vu 5350 fois
Et je donne l'organigramme:
mpo91_Organigram_HP15C_wansdorff.png
mpo91_Organigram_HP15C_wansdorff.png (222.21 Kio) Vu 5348 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.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Gilles59 »

La qualité des contributions (des articles devrais-je dire !) de C.Ret m'épate toujours!

Mon programme en Turbo Pascal pour Amstrad CPC6128 lui ne gagnera pas ce MPO, mais il m'a permis de tester les possibilités graphiques du duo TPv3/CPC6128. Vous remarquerez dans la vidéo que le programme trouve de nombreuses solutions en partant de la même case. En fait chaque fois que l'algorithme trouve plusieurs cases de "même valeur" il en sélectionne une au hasard. Il est théoriquement possible qu'il soit parfois bloqué avant la fin mais ça semble extrêmement rare... La vidéo est à la vitesse réelle du CPC.

https://youtu.be/T7Q0yJRmKzk
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
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Marge »

En tout cas il est sacrément rapide, moins de trois secondes pour afficher tout le parcours ! Bravo.
Tu as suivi l'heuristique de Warnsdorf ou autre chose ?
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Gilles59 »

Marge a écrit : 21 oct. 2020 23:18 En tout cas il est sacrément rapide, moins de trois secondes pour afficher tout le parcours ! Bravo.
Tu as suivi l'heuristique de Warnsdorf ou autre chose ?
Oui, j'ai suivi Warnsdorf... Je pense que la plus grosse partie du temps consommé est due à l'affichage graphique. La choix aléatoire (qaund plusieurs coups ont la même valeur) fait perdre un peu de temps aussi.

La partie recherche du coup suivant est celle-ci :

Code : Tout sélectionner

   Echiquier[PCav.x,PCav.y]:=False;
   Repeat
    Mini:=9; iMini:=0;
    For i:=1 To 8 Do Begin
     nPCav.x:=PCav.x+Dep[i].x; nPCav.y:=PCav.y+Dep[i].y;
     Total:=0;
     If Echiquier[nPCav.x,nPCav.y] Then Begin
      For j:=1 To 8 Do
       If Echiquier[nPCav.x+Dep[j].x,nPCav.y+Dep[j].y] Then Total:=Total+1;
      If  (Total<Mini) Or ((Total=Mini) And (Random(10)>5)) Then Begin
       Mini:=Total; iMini:=i
      End;
     End;
    End;
    If iMini<>0 Then Begin
     PCav.x:=PCav.x+Dep[iMini].x;PCav.y:=PCav.y+Dep[iMini].y;
     Echiquier[PCav.x,PCav.y]:=False;
    End;
Avec :

Code : Tout sélectionner

Type TCoord=Record
        x,y: Integer;
      End;
Const
  Dep: Array[1..8] Of TCoord =
  ((x: 1;y: 2),(x: 2;y: 1),(x: 2;y:-1),(x: 1;y:-2),
   (x:-1;y:-2),(x:-2;y:-1),(x:-2;y: 1),(x:-1;y: 2));

Var x,y,i,j : Integer;
    Mini,iMini,Total: Byte;
    PCav, nPCav: TCoord;
    Echiquier:Array[-1..10,-1..10] Of Boolean;
Modifié en dernier par Gilles59 le 22 oct. 2020 00:27, modifié 1 fois.
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
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Danny »

C.Ret a écrit : 17 oct. 2020 09:33 Et je donne l'organigramme:
mpo91_Organigram_HP15C_wansdorff.png
Joli l’organigramme ! Et les drapeaux :D 8)
Gilles59 a écrit : 21 oct. 2020 23:10 https://youtu.be/T7Q0yJRmKzk
Nickel l’affichage sur CPC :geek:
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par C.Ret »

Gilles59 a écrit : 21 oct. 2020 23:10 [...]Mon programme en Turbo Pascal pour Amstrad CPC6128 lui ne gagnera pas ce MPO, mais il m'a permis de tester les possibilités graphiques du duo TPv3/CPC6128. Vous remarquerez dans la vidéo que le programme trouve de nombreuses solutions en partant de la même case. En fait chaque fois que l'algorithme trouve plusieurs cases de "même valeur" il en sélectionne une au hasard. Il est théoriquement possible qu'il soit parfois bloqué avant la fin mais ça semble extrêmement rare... La vidéo est à la vitesse réelle du CPC.

https://youtu.be/T7Q0yJRmKzk
Excellente vidéo, c'est très rapide à afficher. En voyant le code, c'est une version qui correspond grosso modo à ma dernière version pour HP-41C c'est à dire sans initialisation de l'échiquier, les cases non encore visitées sont calculées au fur et à mesure. Cela nécessite deux boucle des "saut", mais avec une machine rapide, cela ne pose pas de problème.

Tu pourrais aussi utiliser mon approche de Wansdorff par masques binaires (le dernier code pour PC-1360), c'est exactement l'inverse, ce sont les boucles de sauts qui sont précalculées, la résolution de chaque pas se fait alors par un nombre vraiment limité de tests. En Pascal, cela va donner l'impression que le plus long est d'afficher une solution instantanée.
Danny a écrit : 22 oct. 2020 00:04[...]Joli l’organigramme ! Et les drapeaux :D 8) [...]
J'ai eut du mal, dans les versions précèdante de PowerPoint, il y avait facilement accessible tout un jeu d'images ClipArt avec de petits drapeaux de ce type qui est facile de lever ou baisser :)

Où est passé le ClipArt ???
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.
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Marge »

Bonjour,

Petite mise à jour avec la mention de ce programme "Knight's Tour" de Jean-Marc Baillard pour HP-41.

Le site http://hp41programs.yolasite.com de notre concitoyen, professeur de mathématiques et brillant contributeur du HP Museum, regroupe probablement l'un des plus grands nombres de programmes pour ce magnifique calculateur.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par C.Ret »

Les programmes de Jean-Marc sont impressionnants, ils utilisent une logique d'emboitement qui me fait penser à du RPL.

C'est vrai qu'avec Marge, nous avons une vision mono-block de notre production. Nous avons pour le problème du cavalier rédigé un programme mono-block et autonome. C'est un peu la règle du jeu des MPO.

La stratégie mise en œuvre par Jean-Marc est fort différente et correspond peut-être mieux à l'esprit original d'utilisation d'une HP-41, il compose et rédige tout un ensemble de sous-programmes indépendant ou inter-dépendants réalisant chaque opération élémentaire. Il les emboite ensuite en fonction des problèmes à résoudre. Pour cela il faut avoir un module spécifique, un module XFunction (j'ai vu des REGMOVE dans son code...) et au moins une 41CV vu le nombre de registres utilisés... et la longueur des programmes (i.e; pas moins de 95 pas pour gérer les huits mouvement du cavalier là où Marge et moi en cumulant pas plus d'une douzaine !

C'est peut-être une façon de faire plus naturelle et plus commune, en tout cas la façon de faire que j'imagine historique sur ce type de micro-poche.

En résumé, c'est tout l'inverse de nos productions où une HP-41C de base (ou presque) ou une HP-15C suffisent munis d'un seul bout de code suffisent !
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.
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°91 : balade du cavalier

Message par Marge »

Moi, je m‘incline devant vous deux, n‘arrivant même pas à la cheville de quiconque ; mais les objectifs n‘étant pas les mêmes (Jean-Marc résout la difficulté pour un échiquier de n*m<319 dans la version CV), il est normal qu‘il mette à profit son expérience en emboîtant, comme tu le dis, les éléments.
Et je te tire une nouvelle fois mon chapeau pour ta version m.p.optimisée au maximum, sans retirer aucun mérite à notre ami : deux courses finalement bien différentes.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Répondre

Retourner vers « Tous les Pockets »