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 »

Ca c'est un algorithme prometteur !

Image

De plus utiliser des grains de nectar microscopiques, ce sera plus facile que mes lentilles vertes. du coup l'échiquier tout entier tiens dans sa calculette !
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 »

ledudu a écrit : 28 oct. 2019 11:21 Quelles sont vos pistes d'optimisation ?
J'attends impatiemment vos retours.
Oui, alors : figure-toi que j'en ai parlé à mon cheval... ou, pour mieux dire, à ma mule.

Et je l'ai appelée, tu peux me croire ! Mais jusqu'à présent, rien, pas le moindre indice, pas un hennissement, pas un fétu d'avoine qui indiquerait sa présence à la ronde ; nous voilà, C.Ret et moi, aussi esseulés que Don Quichotte et Sancho Panza sur le plateau d'Avila à attendre que nos montures, volées par on ne sait quels bandits, nous reviennent. Et, Madre de Dios, qu'Elle me pardonne, nous avons faim ! à dire vrai surtout moi, à sentir mon ventre vide et gémissant, car mon maître est davantage affamé de prestige et de vertu quand je songe à notre dernière taverne visitée et ses jambons dodus où je soupçonne deux ou trois malfrats d'avoir manigancé ce tour, dérobé nos bêtes à deux lieues de cette halte déjà si loin et arrêté nos routes pour nous empêcher de combler nos estomacs !

Misère, misère, misère, comme le chantait un artiste disparu.
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
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, ça bosse. Enfin, il semblerait...

El trabajo del Sancho.JPG
El trabajo del Sancho.JPG (87.53 Kio) Vu 10466 fois

Et ça paraît laborieux !
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
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 »

Concentration...

Le vingt-cinq septembre douze cent soixante-quatre, au petit jour, le duc d'Auge se pointa sur le sommet du donjon de son château pour y considérer, un tantinet soit peu, la situation historique. Elle était plutôt floue. Des restes du passé traînaient encore çà et là, en vrac. Sur les bords du ru voisin, campaient deux Huns ; non loin d'eux un Gaulois, Eduen peut-être, trempait audacieusement ses pieds dans l'eau courante et fraîche. Sur l'horizon se dessinaient les silhouettes molles de Romains fatigués, de Sarrasins de Corinthe, de Francs anciens, d'Alains seuls. Quelques Normands buvaient du calva.

Le duc d'Auge soupira mais n'en continua pas moins d'examiner attentivement ces phénomènes usés.

Les Huns préparaient des stèques tartares, le Gaulois fumait une gitane, les Romains dessinaient des grecques, les Sarrasins fauchaient de l'avoine, les Francs cherchaient des sols et les Alains regardaient cinq Ossètes. Les Normands buvaient du calva.

– Tant d'histoire, dit le duc d'Auge au duc d'Auge, tant d'histoire pour quelques calembours, pour quelques anachronismes. Je trouve cela misérable. On n'en sortira donc jamais ?

Fasciné, il ne cessa pendant quelques heures de surveiller ces déchets se refusant à l'émiettage ; puis, sans cause extérieure décelable, il quitta son poste de guet pour les étages inférieurs du château en se livrant au passage à son humeur qui était de battre.

Il ne battit point sa femme parce que défunte, mais il battit ses filles au nombre de trois ; il battit des serviteurs, des servantes, des tapis, quelques fers encore chauds, la campagne, monnaie et, en fin de compte, ses flancs. Tout de suite après, il décida de faire un court voyage et de se rendre dans la ville capitale en petit arroi, accompagné seulement de son page Mouscaillot.

Parmi ses palefrois, il choisit son percheron favori nommé Démosthène parce qu'il parlait, même avec le mors entre les dents.

– Ah ! mon brave Démo, dit le duc d'Auge d'une voix plaintive, me voici bien triste et bien mérancolieux.

– Toujours l'histoire ? demanda Sthène.

– Elle flétrit en moi tout ébaudissement, répondit le duc.

– Courage, messire ! Courage ! Mettez-vous donc en selle que nous allions promener.

– C'était bien là mon intention et même plus encore.

– Quoi donc ?

– Partir pendant quelques jours.

– Voilà qui me réjouit fort. Où, messire, voulez-vous que je vous emmène ?

– Loin ! Loin ! Ici la boue est faite de nos fleurs.

– ... bleues, je le sais. Mais encore ?

– Choisis.

Le duc d'Auge monta sur le dos de Sthène qui fit la proposition suivante :

– Que diriez-vous d'aller voir où en sont les travaux à l'église Notre-Dame ?

– Comment ! s'écria le duc, ils ne sont pas encore terminés ?

– C'est ce dont nous nous rendrons compte.

– Si on traîne tellement, on finira par bâtir une mahomerie.

– Pourquoi pas un bouddhoir ? un confucius-sonnal ? un sanct-lao-tsuaire ? Il ne faut pas broyer du noir comme ça, messire ! En route ! et par la même occasion nous présenterons notre feudal hommage au saint roi Louis neuvième du nom.


Déconcentration...

Raymond Queneau, Les Fleurs bleues, 1963 (c'est juste le début de ce bouquin que j'ai trouvé bien plus tordant que le Don Quichotte).
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 »

A, je vois que ça bosse très dur…

Moi aussi j'ai pris l'habitude d'utiliser un tableur (en l'occurrence Excel) pour composer le code. Les mouvements de la pile et la position des arguments sont plus faciles à composer.

Surtout dans la phase d'optimisation, où les copier-coller-insérer-supprimer sont nombreux et souvent fastidieux sans les astuces que permet un tableur.

Par contre, je n'ai pas un assistant numérique aussi portable et collector que Marge

A mon avis, le dernier code qu'a publié notre amis concernant les Tours de Hanoï a été composé de cette façon et c'est pour cela qu'il utilise avec autant d'adresse les quatre niveaux de la pile RPN !!
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 »

C.Ret a écrit : 11 déc. 2019 21:17 [...]
A mon avis, le dernier code qu'a publié notre ami concernant les Tours de Hanoï a été composé de cette façon [avec un tableur] et c'est pour cela qu'il utilise avec autant d'adresse les quatre niveaux de la pile RPN !!
C'est vrai et (un peu) faux : j'ai en effet utilisé ce tableur très utile, mais je suis persuadé que les champions de la pile tels qu'on pouvait en rencontrer ici et qu'on peut en rencontrer sur le forum du HP Museum feraient mieux. J'hésite d'ailleurs encore à publier ce code là-bas (en dehors du fait que je n'aime pas trop leur nouvelle façon de classer les programmes par machines : en gros, tout pour la Prime et la 41, le reste pour toutes les autres machines) bien que les programmes pour la 34C y soient encore rares. Mais je le ferai sans doute dans un accès d'orgueil, ainsi que pour Alien (HP-67) que je trouve plutôt bon.

Quant à celui qui nous préoccupe cette semaine, je ne le publierai certainement pas sur le HP Museum car il sera vraiment bourrin ! Le tien en revanche, C.Ret, y fera à coup sûr très bonne figure, ainsi que sur un autre site dont je parlerai en temps et en heure.
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
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5632
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

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

Message par ledudu »

Vos travaux sont très intéressants. Merci de nous en faire profiter.
Je finalise actuellement une solution sur ti-57, je la publierai sous peu.
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 »

Image
Illustration de Luca Pucci

Devant la pression mise par nos deux brillants cavaliers - 40 à 50 pas pour ce problème, mazette ! -, j'ai choisi de vous informer d'ores et déjà de ma manière de procéder ; au moins, vous comprendrez pourquoi mon code pourrait peser de 5 à 10 fois plus que le vôtre, messieurs !
Mais vous savez ce que c'est, Noël approche, l'âne meugle et le bœuf brait, en conséquence je devrais ne pas avoir le temps de fournir mon précieux programme avant longtemps, en voici donc le principe :

1. Je pars de l'idée de Warnsdorf, à savoir que le problème du cavalier peut être résolu si à chaque éventail d'options possibles pour le déplacement du canasson, on choisit celle où la case d'arrivée propose le moins d'options possibles (par exemple, la case d'angle A1 ne propose que deux options de déplacement, B3 et C2, alors si elle est à portée du cavalier, elle devra être parcourue en priorité) ;

2. Les 64 cases de l'échiquier peuvent être "pesées" de cette manière :

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
3. C'est là que les choses se compliquent pour nos petits engins : j'ai simplement décidé d'entrer ces valeurs dans huit registres sous la forme 0,23444432 pour le premier, etc., et d'analyser le problème en étudiant chaque décimale !
« Je sais qui je suis »...

Rien que d'entrer les valeurs nécessite trente pas (avec initialisation). Déceler les huit cases (maximum) qui entourent la bourrique nécessite 150 pas (sans aucune optimisation) ; choisir la décimale de moindre poids et diminuer le poids des autres cases optionnelles devrait en prendre à peu près autant... cette manière d'utiliser sa monture écarte d'emblée la 67 et la 34C, j'ai donc choisi la 15C.

4. Il n'y a aucun retour en arrière prévu : je considère que la théorie devrait fonctionner, mais comme je n'ai pas tout lu sur le sujet, il est possible que je me fourre l'oreille de ma mule dans l'œil.

Je ne lirai plus rien dans ce fil jusqu'à publication dudit code. Souhaitons bonne chance aux participants : No hay moros en la costa, caballeros!
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 »

Marge a écrit : 13 déc. 2019 11:49[…]« Je sais qui je suis »...Rien que d'entrer les valeurs nécessite trente pas (avec initialisation). […]
J'ai moi aussi décider de coder l'échiquier avec les 8 décimales de 8 registres. C'est très efficace et compact. Par contre, pour l'HP-15C je n'utilise pas la méthode du Chevalier Wansdorf de Bohème. Cette méthode est implémentée sur mon SHARP PC-1360 et donne d'excellents résultats.

J'ai pris deux décisions qui ont formater la façon de résoudre le problème pour une HP-15C:
  1. - De ne pas gaspiller les pas de programme à saisir les valeurs des 8 registres décrivant l'échiquier dans le programme. Je laisse à l'utilisateur le soin de saisir le contenu de ces 8 registres (ainsi que quelques une supplémentaires) après avoir programmer son HP. Ceci ne doit poser aucun problème l'HP-15C étant une Constant Memory complète, le contenu des registres et le programme seront conservés entre chaque utilisation.
  2. - De ne pas mémoriser les paramètres qui permettent de trouver une solution, mais bel est bien d'y coder une solution. Codage obtenu par la méthode de conversion polaire/rectangle. En effet, sur les HP présentant les fonctions d' interconversion des coordonnées polaires et rectangles, il est très facile et court de convertir la direction du saut du cavalier en coordonnées rectangles pointant sur la décimale du registre suivant.
L'optimisation du code m'a ensuite conduit à utiliser 8 chiffres au lieu de décimales, mais le principe reste exactement le même. La partie décimale a été zappée afin de gagner une ou deux instructions dans le code.

Et concernant la pesée de l'échiquier indiqué par notre ami Marge, si vous compter bien, vous y trouverez les 336 lentilles vertes bien sèches nécessaires à l'exécution de l'algorithme du Noble Conte de Bohémie :
MPO91_KNIGHT's TOUR (Wansdorf) Initial board.gif
MPO91_KNIGHT's TOUR (Wansdorf) Initial board.gif (31.97 Kio) Vu 10315 fois
Je laisse aux plus courageux d'entre vous le plaisir de trouver à quoi ces poids correspondent…

Et donne ci-dessous le contenu des registres pour la résolution par dé-mnémodirection-polaire-rectangle.
HP-15C Registers Initialisation.gif
HP-15C Registers Initialisation.gif (33.91 Kio) Vu 10312 fois
Le code pour HP-15C à saisir (avant ou après avoir saisi les valeurs des registres ci-dessus - on peut laisser la répartition mémoire par défaut de son HP-15C, le code ne fait que 42 pas).
MPO91_HP-15C_Code.gif
MPO91_HP-15C_Code.gif (66.49 Kio) Vu 9822 fois
Modifié en dernier par C.Ret le 29 déc. 2019 10:08, modifié 1 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.
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 »

ledudu a écrit : 12 déc. 2019 23:03[…]Je finalise actuellement une solution sur ti-57, je la publierai sous peu.
Je suis impatient de voir cela, car concernant ma TI-57LCD, sur ce problème son manque de mémoire ne me permet pas de l'utiliser pour trouver comment déplacer un cavalier sur l'échiquier !
Et sa taille ne permet pas non plus de s'en servir comme jeton. :x

Je n'ai pas encore pris le temps de refaire l'alimentation de ma CE-122 et je donne donc le –programme pour SHARP PC-1211 sans pouvoir scanner quelques impressions.

Le code suivant permet de trouver, à partir de toute position initiale, une solution au déplacement du cavalier. Ce SHARP n'ayant pas de capacités alphanumériques très étendues et ne souhaitant pas perdre trop d'octets aux tâches d’affichage, les positions sur l'échiquier seront indiquées et saisies de la façon numérique.

Il vous faudra donc numéroter les cases de votre échiquier de la façon suivante:
MPO91 _ 0 to 63 Board numbering.gif
MPO91 _ 0 to 63 Board numbering.gif (40.88 Kio) Vu 10266 fois
-En réalité le sens de la numérotation n'a pas d'importance, toute numérotation continue de 0 à 63 conviendra ; de droite à gauche ou de haut en bas, peu importe pourvu que la numérotation soit continue !-

Techniquement ce code implémente l'algorithme de H.C. Wansdorf(1) en utilisant 80 registres :
  1. (8 registres pour l'adressage des huit sauts du cavalier mémorisé dans l'ordre de rotation horaire - règle importante car sélectionner les saut dans le mauvais ordre met à mal l’algorithme basé sur la sélection dans le bon ordre des sauts vers les case de moindre degré de liberté –
  2. 8 registres de travail (pointeur, valeur, code affichage,...)
    et
  3. 64 registres pour coder l'échiquier (1 registre par case donc !) qui permet de noter pour chaque case au fur et à mesure du parcours si celle-ci est libre (en indiquant entre -8 … 0 son degré de liberté c'est à dire le nombre de cases encore libres qui lui sont accessibles d'un saut de cavalier) ou si celle-ci est occupée (en indiquant entre 1 et 64 le numéro de jeton).
mpo91_SHARP_PC1211.gif
mpo91_SHARP_PC1211.gif (71.59 Kio) Vu 10266 fois
Une fois le code saisi, l'utilisation du programme se fait en trois étapes :
  1. Initialisation: le PC-1211 va peser chaque case de l'échiquier en lui déterminant le degré de liberté de celle-ci sur l'intervalle -8 … -2. On obtient à l'issu de cette première étape l'échiquier indiqué par Marge dans son précèdent post.
    Lancez cette première étape en mode DEF ou RUN en tapant sur votre Pocket [ R ][ U ][ N ][ENTER]
    Mon SHARP PC-1211 a besoin de presque 11 min pour réaliser cette première étape. ce qui me laisse le temps de rassembler et trier mes 63 jetons numéroté, mon cavalier d'échec et de disposer mon échiquier sur un coin de table.
  2. Détermination du parcours:A la fin de l'initialisation, le PC-1211 sonne deux fois et attend la saisie de la position initiale en affichant 0-63 POS _. Saisir la position initiale sous forme numérique entre (0 = case A1 et 63= case H8).
    Le SHARP PC-1211 affiche ou imprime la position de chacun des 64 jetons à placer sur l'échiquier. Chaque jeton est distant du précèdent par un saut de cavalier. A la fin de la série, l'échiquier est parcouru entièrement sans doublon ou omission.
    Si votre imprimante est opérationnelle (ce qui n'est pas le cas de la mienne aujourd'hui) le listing des 64 positions numériques est imprimé.
    Il faut successivement environ 50 secondes pour déterminer chaque position, l'entièreté de l'échiquier est donc obtenue en un peu moins d'une heure.
  3. Impression des échiquiers: cette dernière étape est maintenant optionnelle. Elle permet d'imprimer l'un ou l'autre des 64 échiquiers. Les cases claires sont marquées par un '0' et les cases sombres par un '8'. La position du cavalier par un '2'. Les cases déjà parcourues sont marquées alternativement par un '1' ou un '7'.
    Pour imprimer un échiquier, il suffit de saisir son numéro de jeton (de 1 à 64).
    Cette étape étant devenue facultative, les lignes de code 4: 5: et 9: peuvent être supprimées ou simplifiées (par exemple 3:END et 9:RETURN
Utilisation des registres:

Code : Tout sélectionner

 A(1): D1   -17    Incréments de direction (rotation horaire)	
 A(2): D2   -15		
 A(3): D3    -6		
 A(4): D4    10		
 A(5): D5    17		
 A(6): D6    15		
 A(7): D7     6		
 A(8): D8   -10		

 A(9): I   0...63  Position initale/Position Idéale            Indice de ligne  (i, )
A(10): J   0...63  Position du saut -Jump POS-                 Indice de colone ( ,j)
A(11): K   1...8   Indice directions D()                       N° jeton case    (i,j)
A(12): L  -7...7   Module du saut (détection des bords)        Affichage ligne  (i)
A(13): M  -9...0   Degré de liberté minimum	
A(14): N   1...64  Nombre cases occupées (n° du jeton )        Id. échiquier (1...64)
A(15): O     ~     D.d.L. destination saut                     Code fond de case vide
A(16): P   0...63  Position en cours d'investigation           Code fond de case occupée

A(17): E0 -8...64 Echiquier: 
A(18): E1 -8...64       -8... 0   d.d.l.        (case libre)   K<N          (case libre)
A(19): E2 -8...64        1...64   N° de jeton (case occupée)   K=N        (case occupée)
  .. : ... 		
A(78):E61 -8...64	
A(79):E62 -8...64	
A(80):E63 -8...64	
Contrairement à l'utilisation sur HP-15C, l'utilisateur n'a pas à saisir de données dans les registres, mais la phase d'initialisation est loin d'être rapide. Il est possible de faire bien plus vite, mais cela a immédiatement un effet sur la longueur du code. Et comme c'est un MPO, je ne publie que cette version utilisant 252 octets et 80 registres.

Code : Tout sélectionner

·1:CLEAR :E=17,A=-E,F=15,B=-F,G=6,C=-G,D=10,H=-D:FOR P=0TO 63:GOSUB 5:NEXT P:BEEP 2:INPUT "0-63 INI.POS ";I·· 79
·2:FOR N=1TO 64:P=I,A(P+E)=N:GOSUB 5:PRINT N,P:NEXT N:END···················································· 36
·5:M=-9:FOR K=1TO 8:J=P+A(K),L=J-P+8*(INT .125P-INT .125J:IF J>=0IF J<64IF ABS L<3GOSUB 7+SGN N·············· 66
·6:NEXT K:RETURN·····························································································  7
·7:A(P+E)=A(P+E)-1:RETURN···················································································· 20
·8:O=A(J+E):IF O<0LET A(J+E)=O+1:IF O>MLET M=O,I=J··························································· 40
·9:RETURN······································································TOTAL:252 octets··············  4
J'attends de voir comment cela se passe avec une TI-57 !?!?




REF(1): H.C. Warnsdorff, „Des Rösselsprungs einfachste und allgemeinste Lösung" (Schmalkalden, 1823).
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
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 »

Dans l'espoir de voir apparaitre avant la fin de l'année la version pour TI-57 et éventuellement quelque(s) version(s) pour CASIO ou HP, je publie ci-dessous l'adaptation pour les pockets SHARP PC1360 et consœur de la méthode de Wansdorf publiée précédemment pour SHARP PC-1211.
mpo91_SHARP_PC1360.gif
mpo91_SHARP_PC1360.gif (28.64 Kio) Vu 9820 fois
L'utilisation des instructions READ et de quelques DATA en ligne 1: permet de réduire considérablement le temps d'initialisation de l'échiquier (les initiations des degrés de libertés initiaux et des directions horaires des sauts de cavalier sont d'ailleurs intimement mêlées afin de gagner quelque octet). Ce qui fait que le pocket met moins de 7 secondes à demander la position initiale. j'ai donc retiré toutes les instructions BEEP du code.

Les postions sur l'échiquier sont affichées et la postion initiale est saisie de façon alphanumérique en désignant de façon classique les cases de A1 à H8.

Les positions des 64 jetons sont affichées successivement. Il suffit de placer le jeton sur son échiquier et de presser la touche [ENTER] pour obtenir la position suivante en moins de 3 secondes. L'entièreté de l'échiquier est donc parcourue en moins de 5 min. Evidemment cela dépend surtout de mon habileté à placer le jeton sur l'échiquier.

Cela me donne l'idée de suggérer d'organiser une compétition de Speed Knigth's Tour-Boarding aux prochains pockéticaires.

Code : Tout sélectionner

RUN_                                 [MODE][ R ][ U ][ N ][ENTER]           (7s.)
Initial POS _                        [ D ][ 5 ][ENTER]
          1.D5                       [ENTER]
          2.B4                       [ENTER]
          3.A2                       [ENTER]
          4.C1                       [ENTER]
...
         62.F2                       [ENTER]
         63.H1                       [ENTER]
         64.G3                       [ENTER]
La dernière ligne du code est optionnelle, elle permet d'afficher l'échiquier final sur une imprimante de type CE-126P. Celui-ci affiche comme le faisait Léonhard Euler en donnant le numéro de jeton, c'est à dire l'ordre des déplacements de 1 (case initiale) à 64 (case finale).

Voici l'impression de la route suivie par le cavalier en commençant comme ci-dessus à la case D5. La position finale est numérotée 64 à la case G3 :
mpo91_SHARP_PC1360+CE126P.gif
mpo91_SHARP_PC1360+CE126P.gif (16.86 Kio) Vu 9820 fois
J'ai ajouté au crayon les noms des lignes et colonnes, on retrouve bien la séquence des déplacements D5-B4-A2-C1-...-F2-H1-G3. Faire imprimer ces labels était un peu long pour un MPO.

Je laisse le soin aux plus audacieux d'entre vous de modifier le code afin de pouvoir tracer le parcours du cavalier sur le ploter CE-140P !
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 à tous,

Ce petit mot pour vous signaler que je me relance sur ce problème après avoir passé bien du temps sur... un échiquier à peaufiner un mode d'emploi correct pour mon ordinateur d'échecs Sapphire (plus sur ce sujet un peu plus tard et ailleurs...).

Le problème est que je ne retrouve plus mes notes au sujet du canasson d'Euler. En fait, c'est peut-être mieux. :mrgreen:
Taïaut !
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
steste
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 551
Enregistré le : 18 sept. 2015 18:59

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

Message par steste »

Salut,

Je vais tenter un portage pour un affichage graphique
sur E500s, je décompose les CHR$ de la 1350, je copie
dans le code de C.Ret deux variables X,Y

(les deux CHR$ de la ligne 7.) - Me dire si je me trompe !

Si c'est le bon endroit, je
fais une nouvelle matrice graphique.

le but et de voir se déplacer le cavalier en DRAW
dans un cadre d’échiquier sur l'écran de la E500s.

Ce serait plus simple avec le code de la Commodore 128,
quoique graphiquement et en couleur, c'est presque plus
compliqué.

A+, ste
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 »

Attention, les variables X et Y du code pour PC-3560 ne sont pas les coordonnées sur l'échiquier.

La position sur l'échiquier est donnée par l'unique indice P (variant de 0 à 63 pour les 64 cases de l'échiquier). Le registre P indique la position courante du cavalier et le registre J la position résultante après le K-ième saut depuis la cafe P.

Les variables X et Y sont les restes modulo 8 respectivement des indices de cafe P et J. Ces restes congrus à 8 permettent de détecter les sauts hors de l'échiquier; un écart entre X et Y supérieur à 2 indique un saut impossible car hors de l'échiquier. (cf. test ABS Y<3)

Par contre , à la ligne 7, le reste X et utilisé conjointement à P pour l'affichage alphanumérique de la position P. En effet, la valeur de X calculée au début de la boucle est toujours valable au moment d'afficher la position d'indice P.

Le codage se fait selon le tableau suivant :

Code : Tout sélectionner

        X   :   0     1     2     3     4     5     6     7
     72-X   :  72    71    70    69    68    67    66    65
CHR$(72-X)  :   H     G     F     E     D     C     B     A    avec X = P AND 7 soit X = P MOD 8

        P   :  0-7  8-15 16-23 24-31 32-39 40-47 48-55 54-63 
        P/8 :  0.~  1.~   2.~   3.~   4.~   5.~   6.~   7.~
INT (49+P/8):  49.  50.   51.   52.   53.   54.   55.   56.
CHR$(49+P/8):    1    2     3     4     5     6     7     9
Ce qui revient à avoir un échiquier indicé de cette façon (effet miroir):

Code : Tout sélectionner

    A  B  C  D  E  F  G  H
8:(63)62(61)60(59)58(57)56 :8
7: 55(54)53(52)51(50)49(48):7
6:(47)46(45)44(43)42(41)40 :6
5: 39(38)37(36)35(34)33(32):5
4:(31)30(29)28(27)26(25)24 :4   (entre parenthèses les cafes blanches)
3: 23(22)21(20)19(18)17(16):3 
2:(15)14(13)12(11)10( 9) 8 :2 
1:  7( 6) 5( 4) 3( 2) 1( 0):1
    A  B  C  D  E  F  G  H
MPO 91 Gage et le Roi sur un échiquier indicé miroir.jpg
MPO 91 Gage et le Roi sur un échiquier indicé miroir.jpg (13.23 Kio) Vu 7859 fois
Numérotation des cases de l'échiquier pertinent avec le décodage de la saisie de l'utilisateur:

Code : Tout sélectionner

4: INPUT "Initial POS ";P$ : Q=8* VAL RIGHT$(P$,1)-( ASC P$ AND 15)
Où VAL donne indirectement le numéro de ligne qu'il faut multiplier par 8 pour avoir l'indice correspondant. Enfin pas tout à fait , les lignes vont de 1 à 8, il y a donc un décalage d'une unité, on aurait préféré des lignes allant de 0 à 7.

et

Où ASC P$ AND 15 retourne la colonne mais en sens inverse et là aussi décalé de 1. La soustraction salvatrice permet d'éliminer les deux décalages et épargne quelques calculs pour le décodage et l'affichage alphanumérique. Mais elle donne l'effet miroir de ma numérotation .
Et comme le sens de numérotation ne change rien à l'algorithme cela va bien pour un MPO.

On comprend mieux pourquoi steste en perd son latin, c'est un peu tordu :) :) :)
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
steste
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 551
Enregistré le : 18 sept. 2015 18:59

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

Message par steste »

Merci éternellement. :P

Donc, je passe prochainement sur la 1211/12...

J'imprime un quadrillage dument noté, et j’attends
12 minutes, et environ une heure de calculs si je t'ai
bien lu ?

Je vire les lignes d'imprimante, mes CE-122 sont en panne.

Autre idée:
--------------
Je porte sur la 500s la version 1211/12, mais la formule
basic de:

.125J et .125P n'est pas vraiment basic.*

Sinon, ça semble possible, :P

(et merci pour le boulot sur les graphiques et
les explications !) :P :P :P

-------------------------------------------------------------
* Et si tu peux m'expliquer le truc juste plus haut,
merci, ou il y a l'étoile s.t.p.

ste
Répondre

Retourner vers « Tous les Pockets »