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
steste
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 657
Inscription : 18 sept. 2015 18:59

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

Message par steste » 19 août 2020 22:22

Bravo....

?

....Marge, jolis et long
programme, on sent la sueur due
a la météo capricieuse. boul boul boul, super!

Salut, st

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5208
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 août 2020 03:30

Merci, steste, mais bon, la météo a bon dos...

Je trouve que je faiblis... si c'était encore possible tant j'étais déjà faible ;)

Mais on va y arriver !
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

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

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

Message par gege » 20 août 2020 11:22

Bonjour,
Aurais-tu un listing pour tester le problème du x=0? ?
Très intéressant !
Merci,
G.E.

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5208
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 août 2020 15:12

Bonjour, gege,
Oui, c'est prévu, mais chaque chose en son temps - ah, ces jeunes, toujours pressés ! :wink:
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5208
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 » 26 août 2020 00:19

a2 - c1 - a2 - b4 - a6 - b8 - d7 - f8 - h7 - f6 - g8 - e7 - g6 - h8 - f7 - d8 - b7 - a5 - b3 - a1 - c2 - a1 - a1 - a1 (ad lib.)...

Mais qu'a-t-il dans la caboche, ce maudit canasson ? :evil:

P.-S. : Problème identifié (ein großes Problem...)
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
steste
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 657
Inscription : 18 sept. 2015 18:59

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

Message par steste » 27 août 2020 12:32

Salut marge,

Donc, ce qui est en rouge, c'est
les sauts faux.
(Ce qui devrait être un désastre pour la suite mais
les sauts suivants, pourquoi son-t’ils justes ?)

A tu une explication logique (des problèmes) a nous fournir
avant de laisser tomber.

Ton programme est plus impressionnants, tout
les programmes longs sont impressionnants.

Pourquoi ces chiffres rouges de m.... ? :P

SIC:
Je crois avoir compris le principe de l'analyse
"polaire/triangulaire" !

c'est tout, salut tout le monde, bonne journée, ste

..

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5208
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 » 27 août 2020 19:16

Bonjour, Steste,

En fait, les coordonnées rouges ne devraient pas apparaître parce que la case a déjà été parcourue. Dans ma représentation de la balade du cavalier avec les registres 1 à 8 contenant les valeurs de sauts potentiels de chacune des cases de l'échiquier sur huit décimales, cette erreur se produit parce qu'un décalage involontaire est malheureusement effectué lors de la routine de séparation du registre en trois parties entières si le début de la rangée commence par la valeur '0', ce qui est le cas grâce au placement initial qui met le cavalier sur la première colonne. Le décalage provoque alors l'erreur car le zéro est remplacé par le '4' qui devrait correspondre à B2 - et non A2.

Je ne désespère pas de trouver une solution à ce problème : il suffit de retourner les parties de gauche et de droite en décimales, et non en entiers, mais ça prend beaucoup de pas supplémentaires et je me trouve vraiment à la limite de ce que peut la 15C. Pour le moment, j'ai essayé de gagner de la place mais je crains de devoir commencer à mordre sur l'initialisation - ce que je n'aime pas car je préfère largement un programme totalement autonome : on entre l'emplacement initial et zou...

Dans le pire des cas, j'adapterai le programme à la HP-41CV, au besoin en utilisant un module Double-MEM ; je préférerais tout de même terminer cela relativement rapidement sur la 15C.



copie.jpg
copie.jpg (45.09 Kio) Consulté 748 fois

Photo Chess Bazaar
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5208
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 » 28 août 2020 17:05

Mission accomplie :

Springer.png
Springer.png (126.21 Kio) Consulté 718 fois



J'éditerai les commentaires plus tard. Le code est finalement plus court que prévu. :D

Entrez x, [ENTER], y [GSB] [A], puis R/S entre chaque coup. C'est quasi-instantané sur la 15C LE.

P.-S. : la routine 8 est en cours d'amélioration (ce qui saute au yeux...).
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 : 2282
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 » 28 août 2020 20:57

Woaw...

Là il va falloir que je prennes un bon café noir et que je m'y colle sérieusement... Il y a de la technique.
D'abord, il va falloir que je révise mes bases, je ne sais plus comment dans quel ordre les labels multiples sont appelés. Car là il y a plusieurs fois le même label, et je sais plus... :(

En suite, il y a des GTO et des GSB B C D .0 , ça c'est OK. Mais tous plein de labels de 0 à 8 mais pas de GTO ou GSB 1,2 ,3 etc. Ruse ?
Ah! Il y a un GTO I, faut donc aussi que je révise les appels indexés, je sais plus non plus ... :( :(

Enfin, il y une utilisation plus qu'astucieuse des drapeaux, j'attends avec impatience les explications et indices pour comprendre, parce que là ça fait beaucoup d'info à gérer d'un seul coup.

Chapeau bas et Coup de Maitre très cher Marge.

Je commence à comprendre pourquoi je n'arrivais pas à implémenter un Wansdorf sur une HP-15C...

Et le détail qui me tue, "c'est instantané sur une HP-15 LE" -Pfouf je suis jaloux comme un poux ...
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
steste
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 657
Inscription : 18 sept. 2015 18:59

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

Message par steste » 28 août 2020 22:25

Salut !

BEAUCOUP ! ...de travail....

Les limites (?) de la série Pionnier
il me semble.

Tu est certainement le seul a le
comprendre ce programme...

BRVO ! :P

a plus,

very well...

st

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5208
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 » 29 août 2020 03:03

Merci, C.Ret. Je dois avouer que je n'aurais jamais pu terminer ce programme sans ton allant ni tes encouragements.

Merci également, Steste, pour avoir manifesté ton intérêt et ton enthousiasme pour mon petit travail :D (finalement à la portée de tous, avec de l'opiniâtreté).

Il est tard et la semaine a été longue, j'ai commencé une explication mais viens de me rendre compte que je pouvais encore gagner trois pas : cela modifie le programme, la représentation du code et les explications elles-mêmes, permettez-moi donc de les remettre à demain samedi après-midi, en soirée pour vous. À bientôt !
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

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

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

Message par gege » 29 août 2020 11:21

Bonjour;
Ca a l'air super, on attend avec impatience les explications !
Une lecture rapide et hop... je n'ai rien compris.
A+
G.E.

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3256
Inscription : 06 sept. 2011 14:57
Localisation : Normandie

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

Message par Hobiecat » 29 août 2020 14:18

Avec les couleurs, on comprend à peu près la structure générale, mais ensuite viennent les LBL identiques et le GSB I et là ça se corse un peu. :wink:

En tout cas, ça reste plus lisible que du RPL. :mrgreen:

Avatar de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5208
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 » 29 août 2020 15:02

Voici donc le programme a priori définitif(*) qui permet à une HP-15C, une HP-15C Limited Edition - ou une quelconque application pour téléphone ou ordinateur se comportant de la même manière - de résoudre ce problème. Il doit être possible de le faire également fonctionner sur une HP-41CV sans trop de modifications, et même sur une HP-67 - mais pas encore plus facilement, comme j'ai pu l'écrire un peu vite... et même peut-être pas du tout.

L'heuristique utilisée est celle du génial Herr Warnsdorf qui découvrit en 1823 un moyen infaillible de parcourir toutes les cases de l'échiquier sans perte de temps (comme on le dit aux échecs, c'est-à-dire sans perte de mouvement) en choisissant toujours une case de plus faible valeur de potentiel de sauts parmi celles légalement disponibles. Chaque case de l'échiquier est à cet effet définie par sa valeur initiale telle que décrite dans le diagramme suivant :

Code : Tout sélectionner

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
Le programme est complet : une fois introduit dans la machine, on presse l'abscisse d'entrée (x), puis [ENTER], puis l'ordonnée (y) et enfin [GSB] [A]. Le programme affiche d'abord les coordonnées de cette première case ainsi que le numéro du coup (par exemple : 1,2______01) ; une pression sur [R/S] commence et poursuivra le cheminement du cavalier.

Voici le code suivi de quelques nécessaires explications.

Knight15.png
Knight15.png (118.63 Kio) Consulté 605 fois

Pas 001-038 : Initialisation

Une fois les coordonnées entrées, la pression sur [A] formate l'affichage, puis efface tous les registres ; suit le stockage des coordonnées initiales puis l'emplissage des registres 1 à 8 sous forme décimale inférieure à 1 (la partie entière servira dans la routine 9) ; on termine par l'initialisation du registre 0 avec sa limite supérieure en partie décimale.

Pas 039-146 : Boucle principale et Calcul déplacement

Les couleurs utilisées dans le code doivent permettre, je l'espère, de comprendre que cet ensemble constitue l'âme du programme : ici on gère l'affichage (pas 54 , R/S) et le déplacement du cavalier (le registre I sert dans ce premier cas à connaître le numéro du mouvement sur l'échiquier) : si le numéro du déplacement atteint 64, on s'arrête avec le Return (pas 57).
Le pas 58 voit apparaître un deuxième LBL B (une vieille habitude maintenant de réutiliser les étiquettes antérieures du programme héritée de l'utilisation de la HP-29C, simplement un saut pour reprendre la course si la case 64 n'est toujours pas atteinte) et on procède à une interversion des registres 0 et I pour la suite : le registre 0 ne sera plus nécessaire pendant ces opérations mais le registre I, grandement !
Le travail qui commence alors est de mettre la valeur de la case où se trouve le cavalier à zéro : on place donc les coordonnées actuelles dans les registres I (y, ou ligne) et x (x, ou colonne), puis on appelle les routines 9 (séparation de la ligne I en trois parties pour la pile : x : Valeur en entier ; y : 1ère partie et z : 2ème partie, toutes deux en décimales inférieures à 1) et 8 (assemblage de l'ensemble de la ligne) avec la mise à zéro de la valeur de la case où se trouve le cavalier entre les deux routines. C'est à cet endroit que j'avais perdu beaucoup de pas lors de la confection du précédent programme à laisser ces deux extrêmes de la ligne de l'échiquier représentés par des entiers - mais vous savez ce que c'est : on commence quelque chose de bizarre, on continue sur la même pente, et à la fin, on se retrouve à pester jusqu'à trouver la lumière qui était placée juste au-dessus. Finalement, j'ai opté pour la conservation du facteur d'isolation (i.e. la puissance de 10 qui permet d'isoler la décimale dans la ligne) pour un gain vraiment étonnant de pas de programme. La partie entière du registre indexé par I permet de retenir temporairement la décimale isolée.

Une fois la ligne modifiée et enregistrée (pas 67), les drapeaux sont initialisés, opération nécessaire au début du programme et à chaque tour de la boucle B ; les drapeaux 0 et 3 représentent l'avers et le revers de la même médaille car l'armement de l'un exige le désarmement de l'autre, ils permettent de choisir avec quel registre sera effectuée l'opération :

Code : Tout sélectionner

(R9 ou R10) (+ ou -) 1 ---> R11 ou R12
└─────────┘└─────────┘     └─────────┘
   F0&F3        F1            F0&F3

(R10 ou R9) (+ ou -) 2 ---> R12 ou R11
└─────────┘└─────────┘     └─────────┘
   F0&F3        F2            F0&F3  
Les drapeaux 1 et 2 permettent le choix de l'addition ou de la soustraction des entiers 1 et 2 nécessaires pour le déplacement du cavalier. Cette manière de procéder nécessite un changement rigoureux des états des drapeaux qui est géré par le registre I qui envoie le curseur aux étiquettes successives 7 à 1, le huitième ((2^3)-ième) état étant l'actuel (partie jaune du code).

Au cours de l'opération, les tests de sortie de l'échiquier sont effectués (pas 82, 86, 99 et 103) et envoient si nécessaire à la case (dont il faut tester la valeur) suivante au moyen d'un saut pour le même label 0.

Pas 147-178 : Comparaison

Quand une case fait une bonne candidate, il faut comparer son contenu (qui sera diminué de un puisqu'en raison de la présence du cavalier à sa portée, elle perd son potentiel d'autant) avec la valeur la plus faible précédente - ou placer sa valeur dans le registre de comparaison si elle est la première du cycle des huit cases à vérifier. Cette grosse manœuvre est assurée par la routine C (en vert clair) qui va à son tour appeler les routines 9 et 8 d'isolation et d'assemblage en utilisant de nouveau le registre I, raison des échanges R12<->R I. Il faut aussi vérifier si les valeurs des cases ne sont pas nulles (pas 153), si la case n'est pas la première (pas 162) et enfin si elle est intéressante car de moindre valeur que la précédente enregistrée (pas 164) : c'est alors la routine E qui se charge de conserver la valeur et les coordonnées de la case retenue (pas 167-173).
Tant que les huit états de drapeaux n'ont pas été modifiés, cela signifie que le cycle alentour du cavalier n'a pas été accompli et qu'il faut donc recommencer.

Le curseur revient enfin au pas 110, on vérifie si la case 64 est atteinte et si ce n'est pas le cas, on place les nouvelles coordonnées (registres 13 et 14) en tant que coordonnées officielles (registres 9 et 10), sans oublier de vider le registre 15 (valeur initiale du cycle égale à zéro) aux pas 113 à 118. Et c'est reparti pour un tour.

Épilogue

Sur la 15C Limited Edition, j'ai à peine le temps de voir clignoter "running" entre chaque mouvement - et encore, parce que j'ai modifié la fin pour gagner quelques pas, je crois que c'est la routine 11 qui provoque ce retard. Je n'ose pas chronométrer sur la 15C d'origine, mais je le ferai peut-être.

Comme le programme est assez ramassé finalement, je tenterai peut-être une version pour l'HP-41 afin de conserver une trace imprimée des parcours, voire de les comparer entre eux... par exemple, pour trouver ceux qui sont fermés, c'est-à-dire qui permettent au cavalier de revenir à sa position d'origine. Plus tard, peut-être, un poème... et j'écumerai les tavernes de Suisse à la recherche de ceux qui ne connaissent pas l'histoire d'Euler et de son cavalier.

(*) J'ai tout de même gagné encore quelques pas...
Dernière édition par Marge le 03 sept. 2020 22:40, édité 18 fois.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

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

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3256
Inscription : 06 sept. 2011 14:57
Localisation : Normandie

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

Message par Hobiecat » 29 août 2020 16:21

Merci Marge pour les explications ! Je relirai ça à tête reposée. :wink:

Répondre

Revenir vers « Tous les Pockets »