Misez p'tit Optimisez n°91 : balade du cavalier
Modérateur : Politburo
- C.Ret
- 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
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:
Et je donne l'organigramme:
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.
Re: Misez p'tit Optimisez n°91 : balade du cavalier
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
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
- Marge
- 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
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 ?
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é. ♥ ♠
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é. ♥ ♠
Re: Misez p'tit Optimisez n°91 : balade du cavalier
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;
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
Re: Misez p'tit Optimisez n°91 : balade du cavalier
Joli l’organigramme ! Et les drapeaux
Nickel l’affichage sur CPC
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
- C.Ret
- 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
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.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
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.
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.
- Marge
- 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
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.
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é. ♥ ♠
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é. ♥ ♠
- C.Ret
- 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
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 !
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.
- Marge
- 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
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.
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é. ♥ ♠
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é. ♥ ♠