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 de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2318
Inscription : 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 » 17 oct. 2020 09:33

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) Consulté 511 fois
Et je donne l'organigramme:
mpo91_Organigram_HP15C_wansdorff.png
mpo91_Organigram_HP15C_wansdorff.png (222.21 Kio) Consulté 509 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. .

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

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

Message par Gilles59 » 21 oct. 2020 23:10

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+

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5271
Inscription : 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 » 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 ?
3 hommes, 3 demis, un 3a... Magnéto, Serge !

« Boris », c'est juste Maurice enrhumé.

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

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

Message par Gilles59 » 21 oct. 2020 23:46

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;
Dernière édition par Gilles59 le 22 oct. 2020 00:27, édité 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+

Avatar de l’utilisateur
Danny
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 326
Inscription : 28 déc. 2013 17:34

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

Message par Danny » 22 oct. 2020 00:04

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:
Casio fx-3900p, 7000G, 6000G, 6800G, 8500G, 9900GC, 9950GB +, Graph 100+ USB
HP 35, 45, 65, 21, 25, 33E, 41CX, 42S, 28S, 32SII, 48SX, 48GX, 50g, Prime
Sharp EL-9000

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2318
Inscription : 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 » 22 oct. 2020 17:33

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

Répondre

Revenir vers « Tous les Pockets »