Message bien reçu...
Aucun problème majeur pour reprendre les petits problèmes de triage s’il y a suffisamment de personnes intéressées. Ma dernière tentative pour relancer ces problèmes remontent à avril dernier et n’avaient rencontré aucun succès : j’avais donc abandonné l’idée. Après tout j’ai suffisamment d’autres activités pour occuper mon temps.
Mais pour mettre toutes les chances de notre côté et essayer d’attirer de nouveaux amateurs il n’est sans doute pas inutile de reprendre les principes du jeu et de les expliquer clairement tout en présentant quelques changements par rapport au jeu antérieur, changements de présentation surtout comme nous le verrons plus loin, sorte de version « light ».
A la base le jeu du triage comprend les éléments suivants :
A – Une gare composée de deux voies en impasse, voie 0 et voie 1 (ce choix sera justifié plus loin).
B – Sur la voie 0, au départ, une loco en tête d’une rame de n wagons (ou ouagons dans le jargon local).
C – Chaque ouagon de la rame porte une lettre indiquant sa destination (A, B, C,…)
D – Au départ les ouagons sont dans le désordre.
Le but du jeu est de mettre tous les ouagons de la rame dans l’ordre alphabétique avec un minimum de manœuvres (ou de « coups ») et subsidiairement en déplaçant le plus petit nombre de ouagons possible. A la fin de la partie la rame bien ordonnée peut se trouver sur l’une ou l’autre des deux voies, cela n’a aucune importance. Et habituellement il n’y a aucun restriction sur le nombre ou le type de ouagons que la loco peut déplacer.
Tout déplacement de la loco (avec ou sans wagons) de l’une des deux voies vers l’autre en passant par le tiroir de manœuvre compte pour « 1 » coup.
Tout est dit, me semble-t-il, mais comme la théorie est sans doute trop rébarbative, un exemple permettra de mettre tout cela en perspective. Et comme exemple, très simple, je vous propose la rame ABA illustrée dans la première figure ci-dessous :
La seconde figure donne la meilleure solution en 3 coups, la situation à la fin de chaque coup étant illustrée par un schéma :
Cette présentation graphique de la solution est probablement la plus claire. Elle est cependant lourde à mettre en œuvre. Personnellement, lorsque j’étudie ces problèmes de triage j’utilise une notation beaucoup plus compacte pour représenter les solutions : la liste des Wagons Déplacés (ou notation WD). La solution illustrée dans la figure ci-dessus s’écrit alors, dans cette notation :
[2-0+1] et elle se lit ainsi :
- Chaque nombre entre les crochets représente une manœuvre ou coup ; 3 nombres ici signifient 3 coups.
- Au premier coup la loco déplace 2 wagons de la voie 0 à la voie 1.
- Au second coup la loco revient seule (0 wagon) de la voie 1 à la voie 0. Le signe « - » devant le 0 sert à bien montrer ce mouvement « descendant » de 1 vers 0.
- Au troisième et dernier coup la loco déplace 1 wagon, le seul restant sur la voie 0, vers la voie 1. Ici, comme on « monte » d’une voie, on fait précéder le 1 du signe « + ».
En fait les signes « + » et « - » servent surtout de séparateurs, pour bien distinguer les coups successifs. Les seuls espaces ne sont pas toujours très clairs, en particulier lorsqu’on a plus de 10 wagons à déplacer (mais à vrai dire cela n’arrivera en principe jamais dans les problèmes proposés ici).
Ces signes ont toutefois un autre rôle qui peut être bien utile dans les solutions complexes. Ils permettent, en effectuant l’addition algébrique (c’est-à-dire en tenant compte des signes) des wagons successivement déplacés, de vérifier la validité de la solution obtenue. Dans notre exemple la somme
2 – 0 + 1 = 3 indique que 3 wagons en tout ont au final été déplacés de la voie 0 vers la voie 1. Pour mieux comprendre examinons une deuxième solution à notre problème de la première figure :
Elle ne nécessite que 3 manœuvres elle aussi, mais elle déplace davantage de wagons. En notation WD cette solution s’écrit :
[2-1+2]. Si on effectue la somme algébrique on obtient :
2 – 1 + 2 = 3 là aussi. Mais le nombre total de wagons déplacés est :
2 + 1 + 2 = 5 (obtenu en ajoutant tous les nombres entre les crochets sans tenir compte des signes).
Mon propos en décrivant aussi longuement cette présentation n’est pas de vous forcer à l’utiliser vous-même mais de vous donner les éléments nécessaires pour mieux comprendre les solutions que je vous présenterai occasionnellement. Car je n’ai désormais plus vraiment ni le courage ni l’envie de faire tous ces petits schémas détaillés dont j’illustrais mes propos autrefois. Certes, j’avais développé une bonne technique et ces schémas me prenaient rarement plus de 10 minutes pour dessiner une solution complète. Mais quand 10 secondes suffisent pour quelques chiffres entre deux crochets, le choix de la méthode est vite fait…
La notation WD (avec quelques extensions) a d’autres avantages, surtout quand on étudie de manière plus globale les solutions à ces problèmes de triage. Si l’occasion se présente ou le nécessite j’évoquerai certains de ces avantages et l’une ou l’autre extension commode. En attendant, pour amorcer le jeu, je vous propose un premier problème dans cette nouvelle série. Trier la rame suivante :
Il existe 20 solutions différentes nécessitant le même nombre de coups. Trouvez celle qui déplace le plus petit nombre de ouagons (elle est unique).
Pour ce premier tour je vous propose de rester aussi informels que possible. Si vous pensez avoir trouvé LA meilleure solution, postez-la sur ce fil. Nous verrons d’ici lundi prochain qui aura effectivement trouvé la meilleure solution, et nous déterminerons alors la façon de poursuivre ce jeu au cours des semaines suivantes.
bw
cela représente un gros travail pour lui 
