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

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2029
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 » 30 oct. 2019 21:30

ledudu a écrit :
28 oct. 2019 12:21
[…]Quelles sont vos pistes d'optimisation ?
J'attends impatiemment vos retours.[…]
Comme à mon habitude, je gruge…

Le code pour le SHARP PC-1211 est prêt et fonctionne à merveille. Mieux que l'imprimante CE-122 dont les accus ne chargent plus. Je vais devoir vérifier le circuit ! Juste histoire d'imprimer un peu est de vous scanner quelques échiquiers …

Je suis en parallèle sur quatre algorithmes :
  • très efficace et court pour le SHARP PC-1211 avec optimisation en vue d'implémenter le même sur HP-19C
  • un frère jumeaux à celui de notre ami Ledudu avec comme optimisation en cours l'utilisation d'arbres de choix pour fluidifier lse mouvements d'aller retour du backscatering (retour en arrière en cas d'impasse), une heuristique de choix des nœuds en fonction des degré de liberté restant (au niveau en cours, sur deux niveau ou un vrai min-max), un arbre de classement type "heap"
  • un réseau de neurones très particulier dont l'optimisation utilise beaucoup de grandes matrices (typiquement 64x64) très efficace par nature mais dont le souci majeur est comment faire sans ces grandes matrices. par contre pourrait bien être l'algo type pour une machine RPL !?
  • un automate epicyclique à transformée de Fourrier discrète afin de déplacer le cavalier sur l'échiquier selon une fonction complexe périodique qui garantirait de parcourir l'entièreté du l'échiquier.
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
ledudu
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4787
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

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

Message par ledudu » 30 oct. 2019 22:16

:slime: :slime: :slime:

Avatar de l’utilisateur
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4702
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 » 31 oct. 2019 02:08

C.Ret a écrit :
30 oct. 2019 21:30
[...]
Je suis en parallèle sur quatre algorithmes :
  • très efficace et court pour le SHARP PC-1211 avec optimisation en vue d'implémenter le même sur HP-19C
  • un frère jumeaux à celui de notre ami Ledudu avec comme optimisation en cours l'utilisation d'arbres de choix pour fluidifier lse mouvements d'aller retour du backscatering (retour en arrière en cas d'impasse), une heuristique de choix des nœuds en fonction des degré de liberté restant (au niveau en cours, sur deux niveau ou un vrai min-max), un arbre de classement type "heap"
  • un réseau de neurones très particulier dont l'optimisation utilise beaucoup de grandes matrices (typiquement 64x64) très efficace par nature mais dont le souci majeur est comment faire sans ces grandes matrices. par contre pourrait bien être l'algo type pour une machine RPL !?
  • un automate epicyclique à transformée de Fourrier discrète afin de déplacer le cavalier sur l'échiquier selon une fonction complexe périodique qui garantirait de parcourir l'entièreté du l'échiquier.
8O

(4x)
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2029
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 » 04 nov. 2019 18:43

Bon, d'accord quatre algos en même temps c'est un peu ambitieux.

Mais l'idée est de les comparer les uns avec les autres en les implémentant et en les essayant sur un même environnement.

Juste histoire de se faire une idée, l'environnement en question fonctionne (encore) très bien :
MPO91_KNIGHT's TOUR (Wansdorf).gif
MPO91_KNIGHT's TOUR (Wansdorf).gif (21.96 Kio) Consulté 1296 fois

Bon, je laisse mon Commodore C128D tourner un peu seul, j'en profite pour aller faire quelques pas.


edit 18:10
J'ai pris l'air juste le temps de faire un aller-retour jusqu'à la boulangerie voisine :
MPO91_KNIGHT's TOUR (Wansdorf)_2.gif
MPO91_KNIGHT's TOUR (Wansdorf)_2.gif (35.33 Kio) Consulté 1288 fois
[/color]
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
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2029
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 » 09 nov. 2019 11:12

BON !

SUIS-JE en BONNE COMPAGNIE ??

Je suis un peu dans la déconvenue, parmi les quatre approches envisagées, nombreuses sont celles qui ne mènent à rien d'efficace. Je veux dire à quelque algorithme qui m'aurait permis de trouver une solution à cet MPO sur une HP-19C (ou à défaut une HP-15C puisque l'impression n'est plus obligatoire).
Je dois avouer que je comptais beaucoup m'inspirer des idées, codes et algorithmes donnés ici en réponse. Mais force et de constater que peu de monde a, pour le moment, posté quelque solution ou même quelque simple capture laissant entrevoir leur progression.

Heureusement pour moi, quelques grands hommes ont laissé leur trace dans l'Histoire en publiant le fruit de leurs recherches. Je suis donc en mesure de vous donner ci-dessous l'algorithme que j'implémente sur mon HP-15C afin de répondre élégamment au problème n°91.

EULER's solution for Ledudu knight's quest.gif
EULER's solution for Ledudu knight's quest.gif (164.97 Kio) Consulté 1183 fois
REF: «Solution d'une question curieuse qui ne paraît soumise à aucune analyse», Mémoires de l'Académie Royale des Sciences et Belles Lettres, Année 1759, vol.15, pp.310-337, Berlin 1766


Pour les personnes qui souhaiteraient ce Week-end tester mon algorithme dont je publierai sous peu le code sur leur HP-19C / HP-15C / SHARP PC1210 / SHARP PC1211 / SHARP PC1212 / SHARP PC1350 / SHARP PC1360 / HP-28C / HP-28S / HP-Prime / Commodore C128 / Commodore C128D (*), je les averti qui devront se munir des ingrédients suivant :
  • Un échiquier de bonne taille (n'oublier pas de positionner la cafe A1 en bas à gauche - il doit s'agir d'une cafe foncée)
  • Une pièce d'un jeu d'échec. Le plus logique serai de se procurer un cavalier. Noir ou Blanc cela n'a pas d'importance.
  • 336 jetons de petites taille (surtout si l'échiquier est étroit). L'idéal étant peut-être d'utiliser des lentilles vertes bien sèches.
  • 63 jetons de plus grande taille. J'ai pris les jetons numérotés d'un jeu de loto. Mais utiliser les jetons unis de jeux de dames est possible aussi, Mais il faudra dévaliser les pièces d'ua moins deux plateaux.
  • Eventuellement une Calculatrice ou un Pocket convenablement programmé afin de manipuler virtuellement les jetons.
    (A défaut une pince à épiler permettra de manipuler les 336 lentilles et dérouler l'algorithme).
  • En option (puisque ledudu n'impose plus d'impression) une imprimante branchée à votre calculatrice ou pocket; Les matériels ayant des capacités alphanumériques permettront de se passer de l'échiquier préconiser ci-dessus.
    (Par contre, les utilisateurs démunis d'assistants numériques devront peut-être se munir d'un stylo et de la page d'un petit block-note pour noter leur progression).

Je vous laisse le temps de préparer tout cela, je reviens de la boulangerie et je vais vite aller au bistro qui fait le coin prendre mon apéro. J'espère que ce soir Ben me donnera son programme pour statistique du nombre de pas et de levées des coudes.

(*) rayer les mentions inutiles
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
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4702
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 » 09 nov. 2019 12:08

Bravo pour ton enthousiasme communicatif !

Personnellement, je suis un mammouth de la programmation et je n'ai pas avancé d'un lychen. J'ai néanmoins quelques circonstances atténuantes à faire valoir, notamment que j'ai préparé hier soir un plat de tagliatelles à la carbonara pour ma belle-mère et une partie de sa descendance et que tout le monde s'est couché bien tard.

Je reste cependant très impressionné par ta culture, la puissance de ton analyse et je ne doute pas que tes résultats seront à la hauteur - surtout si tu réussis à empiler les lentilles, je viens d'essayer avec trois et ça n'a pas l'air évident.

Nulle garantie que je parviendrai à fournir quoi que ce soit avant lundi (je dois notamment raccompagner ma belle-mère jusqu'à son nid douillet), mais je suivrai les résultats de tes efforts avec grand plaisir, comme toujours. Merci !
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2029
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 » 19 nov. 2019 22:33

Bon, je voulais publier dès ce soir ma solution pour HP-15C.

J'ai trouvé une astuce pour répondre au problème posé en moins de 50 pas de programme et l'exécution du code permet d'avoir une solution quelque soit la case de départ. l'ensemble de l'échiquier est parcouru en moins d'un quart d'heure.

C'était le challenge n°1 sur cette machine qui manque cruellement de vélocité.

Mais je préfère poser une colle. Ceux qui ont déjà réfléchi à ce problème trouveront bien vite. Surtout avec une HP-15C, le calcul peut se faire en exactement six pressions de touches !

MPO91_Trigonometric KNIGHT's move.gif
MPO91_Trigonometric KNIGHT's move.gif (35.13 Kio) Consulté 775 fois

Que valent R et alpha ?
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
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4702
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 » 20 nov. 2019 01:58

Sqr(5) et environ 26,56 degrés, non ?

Si Marge a trouvé, c'est que tout le monde a trouvé... :wink:
Dernière édition par Marge le 07 déc. 2019 02:05, édité 1 fois.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2029
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 » 20 nov. 2019 20:47

C'est bien cela.
La séquence sur HP-15C (et consœurs) est:
HP-15C Déplacement +1.+2.gif
HP-15C Déplacement +1.+2.gif (4.64 Kio) Consulté 728 fois
Ce qui fait bien 6 touches à presser si l'on ne compte pas les séquences de mémorisation. (Mais vous pouvez le faire si vous souhaiter utiliser mon code, ce qui est fait n'est plus à faire)


Toute impression à partir d'une HP-15C étant impossible, il vous faudra vous munir d'un échiquier, d'une pièce de cavalier (noir ou blanc peu importe) et de 63 jetons (si vous en trouvez utiliser des jetons numérotés).

Une fois le programme saisi et les registres de données initialisés, il vous suffira d'entrer la case initiale sous la forme décimale y.x et lancer le programme par f-A.

Dans l'exemple ci-dessous, j'utilise y pour indiquer les lignes ( de 1 à 8 ) et x pour indiquer les colonnes (de A à H). Mais rien ne vous empêche de procéder différemment. Cela ne changera rien.
MPO91_HP-15C_Chessboard_(initial D5).gif
MPO91_HP-15C_Chessboard_(initial D5).gif (7.88 Kio) Consulté 728 fois
Le programme s'arrête à chaque saut en affichant la position sous la forme Y.X et en indiquant le numéro nn du jeton à poser.
Une pression sur R/S permet de passer à la détermination du saut suivant et ainsi de suite jusqu'à parcourir l'intégralité des 64 cases de l'échiquier.
Sans, bien sûr, passer deux fois sur la même case, en manquer une ou revenir en arrière grâce à son efficace algorithme de dé-mnémodirection-polaire-rectangle.
A tout moment, il est possible de recommencer un nouvel échiquier, simplement en saisissant une nouvelle position initiale Y.X et en pressant f-A.

Mon HP-15C met environ 9 secondes pour déterminer chaque saut, il me faut donc un peu plus d'un quart d'heure pour remplir l'échiquier avec mes 63 jetons (je n'ai pas de jeton n°0, le cavalier reste à la case départ).
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
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4702
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 » 20 nov. 2019 22:11

Eh bien : bravo !

(Pour l'instant je suis sur un autre problème du même acabit, donc je garde tout cela au chaud... 8) )
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4702
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 » 03 déc. 2019 16:32

Salut,

J'y retourne. Pour l'instant, piano : je lis Euler, je ne vais pas réinventer la roue (plus le temps, hélas...). Il avait de la ressource, le grand-oncle (ou arrière-grand-oncle ?) de Cendrars...

Et en parlant de ressources, je me demande si la 34 pourra relever ce défi, même s'il n'est bien sûr pas question d'imprimer, car d'après ce que je comprends, il va falloir mémoriser des parcours. Bon, j'y travaille. @+

D'autre part (j'édite), je suis surpris de ce que tu annonces pour le temps de calcul du HP-15C, C.Ret : que tu puisses dire que la détermination d'un coup dure 9 secondes sans préciser qu'il s'agit d'une moyenne tend à indiquer que ton coup est toujours sûr : j'en reste ébahi... Il nous faudrait zpalm pour démêler cela.
Dernière édition par Marge le 03 déc. 2019 22:16, édité 1 fois.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2029
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 » 03 déc. 2019 19:14

Selon les machines , j'utilise deux stratégies diamétralement différentes. Certaines machines produisent un code fort court en mémorisant un parcours, l'indexation par le registre I de certaines facilite et garanti un effet rapide et efficace.

D'autre au contraire, disposent de plus de mémoire qu'il est facile de manipuler sous forme de tableaux 2D et le code le plus court utilise leur capacité à calculer une solution au fur et à mesure. Les effets sont tout aussi efficaces mais parfois un peu plus long surtout pour les versions où la la taille du code est optimisée.

Ceci me permet de jouer dans les deux concours, celui de ceux qui opteront pour une solution universelle mémorisée et ceux qui utiliseront une démarche algorithmique.
Le tout en proposant un code M.P.O. décent.

héhé … je vais donc encore un peu patienter afin de laisser à chacun l'occasion d'y réfléchir encore un peu…. :)

Je n'ai pour le moment pas de code efficace à proposer pour les approches heuristiques, la méthode des fourmis et les réseaux neuronaux ou pseudo-aléatoires. Mais j'entrevois l'existence de telles approches. c'est juste que mes quelques tentatives n'étaient pas convaincantes !


PS: La version HP-15C fait actuellement 41 pas. Et le calcul et affichage de chaque pas fait bien à chaque fois un tout petit peu moins de 9 secondes. C'est magique de simplicité et d'efficacité.
Dernière édition par C.Ret le 13 déc. 2019 20:57, é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
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4702
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 » 05 déc. 2019 03:06

Bonsoir,

C'est un problème très intéressant. J'aimerais bien trouver une solution heuristique sur une petite machine...
J'imagine néanmoins que des solutions à base d'angles seraient en effet plus économiques (en registres et en traitement de la mémoire), avec par exemple un choix orienté a priori vers les coins de l'échiquier pour avoir plus de chance de tomber sur des cases à moindre potentiel, tel que conseillé par le chevalier Warnsdorf.

Compte tenu de mes capacités et de mon temps, je crois ne pas pouvoir donner de réponse avant le week-end du 14-15. Rien ne vous empêche de publier une réponse d'ici-là, mais je ne la lirai pas avant cette date !

Merci à ledudu pour ce casse-tête. Ledudu ? Es-tu là ?
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4702
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 » 05 déc. 2019 18:36

Ha ha ! c'est super dur, j'adore !

Bien qu'intrigué par les idées développées par C.Ret, j'ai décidé de ne pas partir dans cette direction : d'abord il serait illusoire de faire mieux que toi, mon ami, surtout si j'ignore encore comment tu résous la difficulté d'éviter de repasser sur une case déjà utilisée, et j'avoue que ça ne me gêne pas de servir de faire-valoir dans cette histoire (il en faut bien un, et qui de mieux qu'un littéraire, hein ?), mais en plus j'ai vraiment envie de faire quelque chose d'un peu lourdingue sur la 34C : et je suis servi ! déjà, rien qu'à initialiser l'engin, j'ai bouffé trente pas. Attendez-vous donc à un programme lent et lourd !

Je suis un peu étonné du peu de réactions du public silicien, quand on sait que ce problème est un classique des TP d'info, et que les tours de Hanoï (classique également) avait engendré bien plus de remarques et d'observations.Vous vieillissez, les gars ! :lol:
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
Marge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4702
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 » 07 déc. 2019 02:00

Knight and bees
knight.png
knight.png (97.28 Kio) Consulté 187 fois
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Répondre

Revenir vers « Tous les Pockets »