Manœuvres et cabotage

[bogie-wogie]

Jeuvret sur HP50g

En ayant un peu marre de gaspiller du papier pour étudier les solutions aux innombrables problèmes de triage de Jeuvret, j’ai récemment entrepris d’écrire un petit programme sur ma calculette HP50g, d’une part pour faire des économies sur cette denrée précieuse qu’est le papier, d’autre part pour me faciliter la tâche et éviter de bêtes erreurs de transcription. Pour vous donner une première idée de ce que fait ce programme voici le résultat pour la résolution du triage de la rame BCFDEA en 5 coups.

Je dois m’empresser de dire que le programme ne calcule en rien la solution. Pas la moindre triche ici ! Son seul et unique rôle est de servir de support pour élaborer soi-même la solution, comme nous allons le voir plus loin. En pratique il remplace simplement le calepin que j’utilisais jusque là pour mes (souvent infructueux) essais de solutions, comme le montre la photo suivante.

On notera une petite particularité (ou bizarrerie) de mes transcriptions sur papier, que j’ai (provisoirement) conservée sur la calculette : les voies alternent à chaque coup, ou plutôt la voie sur laquelle se trouve la loco ("X" sur l’écran de la HP50, rien sur le papier) est systématiquement celle de gauche. Sur papier cette convention m’évite justement de coder ou d’indiquer la position de la loco et la séparation des voies est simplement marquée d’une petit croix. Sur HP50 cela simplifie considérablement le programme qui n’a pas à chercher sur quelle voie elle se trouve (il y a tout de même un test de validité qui affiche le message "PAS DE LOCO" si la première des deux chaînes de caractères ne débute pas par la lettre X).

Comment ça marche ? En fait, pour me faciliter la tâche au maximum il y a deux programmes. Le premier est un petit programme d’initialisation ou plus précisément de mise en forme. Il suffit d’introduire une chaîne de caractères représentant la rame à trier, sans la loco, par exemple "ACGDEBF" et d’actionner la touche [INIT] en haut du clavier :

Le résultat est une liste (délimitée par des accolades : { et }) de deux chaînes de caractères. La première représente le contenu de la voie sur laquelle se trouve la loco "X" (notre chaîne de caractères en tête de laquelle a été rajouté un X), la seconde donne le contenu de l’autre voie, ici au départ vide.

On notera que cette liste est en outre indicée au moyen d’un « tag », le « 0: » juste devant. Cet indice, partant de zéro pour la configuration de départ, augmente automatiquement à chaque coup pour donner le nombre de coups effectués depuis le début. Très pratique : on sait ainsi toujours où on en est et on peut s’arrêter à tout moment si on dépasse un nombre de coups limite fixé à l’avance.

Alors, comment joue-t-on un « coup » ? En introduisant tout simplement le nombre de wagons qu’on désire déplacer de la première voie vers l’autre. Par exemple, si on veut déplacer les trois premiers wagons de la rame ACGDEBF, on tapera [3] au clavier puis on lancera le programme [SJV] (pour « Simulation de JeuVret ») en actionnant la touche correspondante en haut du clavier.

Le résultat est instantané (elles carburent ces petites machines !) On notera que le programme, s’il a « déplacé » les trois wagons ACG, a bien laissé les quatre derniers wagons de la rame sur « l’autre voie ». Certes, on a l’impression du contraire, mais rappelez-vous : à chaque coup les deux voies alternent. Je changerai peut-être ça lors d’une prochaine version…

Si on change d’avis, ou si on s’est trompé, ou si on veut essayer une autre solution, il suffit d’effacer le dernier résultat sur l’écran, au bas de la pile (ou même plusieurs successivement si on veut revenir plus loin) et d’introduire une nouvelle valeur. Le programme [SJV] repartira automatiquement de la dernière étape affichée à l’écran. Finies les horribles ratures rendant certaines solutions totalement illisibles ! Et on peut à tout moment revenir en arrière en quelques clics pour tester une autre solution si on s’aperçoit au bout de quelques coups que celle en cours n’aboutit pas.
J’ajouterai pour terminer que le programme [SJV] est élémentaire, en particulier parce qu’il n’effectue que très peu de vérifications sur les données introduites. Si on n’a pas une valeur numérique en bas de la pile lors du lancement de [SJV], ou une liste taguée contenant deux chaînes de caractères juste au-dessus, le programme se plantera alors joliment ! Mais il suffit d’éliminer les débris laissés sur la pile affichée à l’écran pour recommencer (certes on aura aussi perdu le coup joué précédemment : il suffit alors de le rejouer pour retomber sur ses pattes…)

Quelques autres « bizarreries » de ce programme :
– Quand je parle de chaînes de caractères ces derniers peuvent être quelconques. On peut ainsi utiliser des chiffres si on préfère ceux-ci aux lettres, et même mélanger les deux. Le programme ne fait aucune vérification à ce niveau.
– Si on introduit une valeur non entière comme nombre de wagons à déplacer, par exemple 2,3, le programme arrondit à l’entier le plus proche (dans ce cas il arrondira à 2, mais si 2,4999 donne toujours 2 par contre 2,5 devient 3).
– Si on introduit une valeur négative le programme se contente d’intervertir les deux voies (et la loco X se retrouve alors dans la deuxième chaîne de caractères ce qui ne plaira pas au programme pour la suite des opérations : il indiquera bêtement "PAS DE LOCO" sans voir qu’elle est sur l’autre voie).

Bref, plein de petits détails qu’on pourrait corriger (ou exploiter) dans une future version de ce programme… Citons comme améliorations possibles la conservation dans une liste du nombre de wagons déplacés à chaque coup et/ou un total cumulé de ce nombre de wagons déplacés pour pouvoir comparer des solutions similaires entre elles. La principale difficulté ici est la gestion des corrections, c’est-à-dire des retours en arrière par simple élimination des derniers coups joués. Certes c’est possible sans trop de mal, mais cela alourdirait alors le programme de manière considérable. Le jeu en vaut-il la peine ?

Les programmes :

INIT [47 octets]
« "X" SWAP + "" 2 ->LIST 0 R->I ->TAG »
Paramètres : [1 : chaîne de caractères]

SJV [179 octets]
« OVER DTAG OBJ-> DROP
-> n v0 v1
« IF v0 HEAD "X" ==
THEN v0 1 n 1 + SUB v1 +
v0 n 2 + OVER SIZE SUB 2 ->LIST OVER
OBJ-> SWAP DROP OBJ-> 1 + R->I ->TAG
ELSE "PAS DE LOCO" END » »
Paramètres :
[2 : liste taguée de deux chaînes de caractères]
[1 : nombre de wagons à déplacer]

Note : ces deux programmes peuvent également être utilisés sur calculettes HP49 et HP48. Sur HP49 aucune modification n’est nécessaire ; sur HP48 il convient d’éliminer la commande R->I qui apparaît une fois dans chacun des programmes et qui n’existe pas sur cette machine (de toute façon elle est inutile dans ce cas, le formatage des nombres y étant différent).

bw

[pierre du rail - 61]

Bonsoir,

Plus que 24 heures avant de découvrir le grand gagnant de la semaine, maintenant, il faut que ça tape

Le plus surprenant est que Dania, si prompt à donner ses astuces pour trouver le nombre de coups pour la meilleurs solution, n'ai pas encore fait suffisamment fait chauffer ses neurones pour me faire parvenir une solution pour ce petit problème assez facile, je dois dire, d'autant plus que j'ai donné un précieux indice.

Nouvelle règle que je propose : les commentaires et autre textes concernant le défi en cours, ne seront autorisés qu'après publication des résultats. Seuls le Grand Maitre, alias BW, aura le droit s'il en ressent le besoin.

À demain.

Cordialement.
Pierre

[bogie-wogie]

Tout en regardant tomber la neige cet après-midi (et ce n’est pas fini !...) je me suis lancé dans une petite amélioration du programme 'SJV' présenté plus haut. Ou plutôt je lui ai ajouté une fonctionnalité supplémentaire annoncée à la fin de mon dernier article : la conservation dans une variable séparée 'WD' (pour Wagons Déplacés) de la solution obtenue sous forme de liste. Il est en effet très vite apparu que de ne pas disposer de cette solution sous forme pratique et facilement lisible était un handicap sérieux pour tirer pleinement profit du programme.

Le plus délicat a en fait été de tenir compte des retours en arrière (ou de l’élimination des dernières étapes effectuées) pour corriger de manière synchrone cette liste solution WD. En fait le programme triche un peu : il ne modifie la liste WD qu’au moment où on joue une étape de remplacement. Tant qu’on n’a pas à nouveau déplacé des wagons la liste WD reste inchangée et conserve l’ancienne solution. Mais cela n’est pas vraiment gênant.

Le programme 'SJV' est ainsi augmenté d’une centaine d’octets et le programme 'INIT' est lui-même affecté (avec une quinzaine d’octets supplémentaires) puisqu’il doit créer la variable WD si elle n’existe pas déjà ou bien la réinitialiser avec une liste vide lorsqu’on commence un nouveau jeu de triage. Je vous fais grâce des nouveaux programmes mais s’il y en a que cela intéresse je peux sans problème les poster ici.

A tout à l'heure...

bw

[bogie-wogie]

Le "tout à l'heure" est là et bientôt passé. Mais rien n'est annoncé, pas le moindre petit résultat.

Pour demain alors...

bw

[Jojo37]

Bonsoir à tous.
En effet Pierre à du s'endormir sur toutes les réponses reçues tant le classement était difficile.
On verra celà demain maintenant.

[pierre du rail - 61]

Bonjour,

La faute est dû à EDF qui nous a collé des jours de pointes, ce qui fait que ces jours là, je ne me connecte qu'entre 1h et 7h si je suis réveillé ne souhaitant pas enrichir les actionnaires et éviter la construction d'une nouvelle source de pollution

Cette semaine a vu le nombre de participant passer à TROIS avec la présence de trois résultats identiques par ailleurs identiques au mien également

C'est donc la réactivité qui départage les récipiendaires avec un beau podium
Dans l'ordre d'arrivée à Aldayo suivit de Joël et de Bernard

Souhaitons que le nombre de participants continue sa progression et vois la participation de Dania.

Je retourne en laissant notre ami Aldayo réceptionner les prochains résultats.

Cordialement.
Pierre

[bogie-wogie]

aux trois participants, avec un supplémentaire pour Aldayo !

Tout le monde a trouvé la même solution, identique à la mienne... Je crois (j'en suis presque sûr à 97,341 %) qu'il n'en existe pas d'autre.

Il existe une relation très simple entre la résolution d'une rame de wagons XY (où X et Y sont deux segments quelconques), et celle de la rame X+Y scindée et répartie sur les deux voies. Si [a b c d...] est une solution (en nombre de wagons déplacés selon Dania) pour la rame complète XY, alors [n a b c d...] est en général une solution pour X et Y séparés, avec la loco sur le segment X comportant n wagons.

Un exemple simple : la rame ACB, qui se résout selon : [2-1+2]
Dans ma notation, dérivée de celle de Dania, les crochets et les signes intercalaires (+/-) sont très importants. Nous allons d'ailleurs tout de suite voir comment en ce qui ces signes intercalaires (qui indiquent, en pratique, dans quel sens se déplace la loco : soit de la voie 0 de départ vers la voie 1 (signe +), soit inversement de la voie 1 vers la voie de départ 0 (signe -), indication commode et bien utile parfois).
Dans un premier temps, coupons la rame en deux en isolant XA (loco + wagon A) sur une voie, CB sur l'autre. On a n=1 wagon derrière la loco, la solution, en appliquant directement la petit règle donnée plus haut, donne :
S = [1-2+1-2]. Vous pouvez vérifier que ça marche et que c'est la meilleure solution.
Dans un deuxième temps, scindons notre rame ACB en AC+B avec cette fois-ci deux wagons derrière la loco. Et appliquons encore une fois notre petite règle sympa. Que donne-t-elle ? S = [2-2+1-2].
Ah ! Il y a un problème... mais pas vraiment : ce "2-2" au début, il s'élimine tout simplement, automatiquement et naturellement. Et puis 2-2=0...
Il nous reste donc : S = [1-2] en deux coups. Et vous pouvez vérifier que ça marche !

Tout ce long discours pour dire que c'est le même raisonnement qu'on peut appliquer à notre problème.
La rame BEDFCAG se résout en 8 coups par [3-2+4-0+1-4+2-4]. Si on la coupe en deux, en ne conservant que 3 wagons derrière la loco sur voie 0, les autres étant garés sur voie 1, l'application de la règle donne a priori une solution en 9 coups, soit : [3-3+2-4+0-1+4-2+4] où les deux premiers coups s'éliminent pour n'en laisser que 7, à savoir : [2-4+0-1+4-2+4] qui n'est autre que celle que nous avons tous trouvée

Petite remarque avant de terminer : j'ai dit que cette règle était "générale", elle n'est pas absolue. Sur quelques centaines de cas étudiés je n'ai jusqu'ici trouvé que 2 exceptions, c'est-à-dire des rames scindées où la méthode donne une solution mais celle-ci n'est pas la meilleure. Pour l'une ou l'autre raison particulière (qu'il me reste à déterminer) il existe une solution radicalement différente et plus courte... On en reparlera une autre fois.

Pour l'instant vous êtes, j'en suis sûr, impatients de découvrir le nouveau problème. Alors le voici ! Rien que du très classique, mais sans doute pas aussi évident qu'il y paraît A vous de voir...

Vos solutions sont donc à adresser à Aldayo, cette fois-ci, disons d'ici lundi soir prochain (18.02).

Bon amusement
bw

[Jojo37]

Bonjour à tous.
Bravo à Aldayo. Qu'il se prépare à recevoir ma solution.
En effet,que le nombre de participants progresse,serait bien et relancerait encore plus le plaisir de jouer.

[Aldayo]

C'est vrai que je l'ai trouvé tellement simple que la première chose que je me suis dite : si je trouve une solution en 7, c'est qu'il en existe une en 6 (comme à chaque fois que je joue )

Et ben non, pas cette fois

Je posterai lundi soir la meilleur solution de ce nouveau problème !!

[bogie-wogie]

On est mardi, la matinée touche à sa fin et... toujours pas de résultat ?

Pour ne pas trop perturber le schéma je vous soumets sans plus attendre le problème suivant :

C'est "un peu" différent cette fois, histoire de ne pas s'enliser dans les mauvaises habitudes.

Alors, que faut-il donc faire ? Eh bien : les ouagons bleus doivent être placés sur la voie du haut (avec heurtoir bleu) et les ouagons rouges sur la voie du bas (avec heurtoir rouge). Et bien sûr ces ouagons doivent être dans l'ordre A-B-C sur chaque voie. La loco peut-être sur n'importe laquelle des deux voies à la fin.

Et comme toujours : effectuer le tri en un minimum de mouvements et (comme il y a plusieurs solutions possibles en N mouvements) en déplaçant le moins de ouagons possible.

Pas de panique Pour ce premier exemple dans cette catégorie, la solution n'est pas difficile du tout. J'en ai des plus coriaces en réserve...

bw