Routes et chemins

La longueur d'une route est le nombre de cases qui la compose, qui est toujours compris entre 1 et 6 (inclus). Par exemple, la route reliant Neuchâtel à Yverdon est de longueur 2, tandis que celle reliant Neuchâtel à Lausanne est de longueur 4.

Une route peut être simple ou double. Par exemple, la route reliant Neuchâtel à Berne est simple, tandis que celle reliant Fribourg à Berne est double.

Certaines routes sont colorées, tandis que d'autres sont neutres. Les routes colorées le sont au moyen des mêmes huit couleurs que celles utilisées pour les cartes wagon, à savoir : noir, violet, bleu, vert, jaune, orange, rouge, et blanc.

Par exemple, la route reliant Neuchâtel à Yverdon est noire, tandis que celle reliant Neuchâtel à Lausanne est neutre, raison pour laquelle elle est dessinée en gris clair sur la carte.

Les routes doubles colorées le sont toujours au moyen de deux couleurs différentes, comme celle reliant Fribourg à Berne, constituée d'une route orange et d'une route jaune. Les routes doubles neutres sont toujours constituées de deux routes neutres, comme celle reliant Berne à Lucerne.

Certaines routes sont en tunnel, tandis que d'autres sont en surface. Les routes en tunnel se reconnaissent à leur contour traitillé.

Par exemple, la route reliant Neuchâtel à Lausanne est en surface, tandis que celle reliant Neuchâtel à La Chaux-de-Fonds est en tunnel.

Pour pouvoir s'emparer d'une route en surface, un joueur doit posséder :

• un nombre de wagons au moins égal à la longueur de la route,
• un nombre de cartes wagon de même couleur que la route au moins égal à la longueur de la route.

Si la route est neutre, les cartes wagon utilisées pour s'en emparer peuvent être de couleur quelconque, mais unique.

Si un joueur désirant s'emparer d'une route en surface dispose des cartes et wagons nécessaire, il peut le faire en se défaussant des cartes puis en plaçant un de ses wagons sur chacune des cases constituant la route. Pour mémoire, les wagons sont symbolisés par des rectangles colorés — en bleu clair ( m ) pour le joueur 1 et en rose ( m ) pour le joueur 2 — ornés de deux disques blancs.

L'image ci-dessous illustre la prise de possession, par le joueur 2, de la moitié rouge de la route Lausanne - Fribourg, qui est en surface.

Dès qu'un joueur s'est emparé d'une route, son adversaire n'a bien entendu plus la possibilité de le faire. D'autre part, dès qu'un joueur s'est emparé d'une des deux moitiés d'une route double, l'autre est condamnée et personne ne peut s'en emparer.

Pour pouvoir s'emparer d'un tunnel, un joueur doit remplir les mêmes conditions que pour une route en surface. Dans le cas d'un tunnel, il peut toutefois aussi utiliser les cartes locomotive, qui sont en quelque sorte multicolores et peuvent donc jouer le rôle d'une carte wagon de couleur quelconque.

Si un joueur désirant s'emparer d'un tunnel dispose des cartes et wagons nécessaires, il doit tout d'abord placer devant lui les cartes qu'il désire utiliser, après quoi les trois cartes se trouvant au sommet de la pioche sont retournées. Ces trois cartes déterminent les éventuelles cartes additionnelles que le joueur doit jouer, en plus de celles qu'il a déjà posées, pour pouvoir s'emparer du tunnel.

Ainsi, chacune des trois cartes retournées qui est soit une carte wagon de même couleur qu'une carte posée initialement, soit une carte locomotive, implique l'utilisation d'une carte additionnelle. Ces cartes additionnelles peuvent être soit des cartes wagon de la même couleur que celles utilisées initialement, soit des cartes locomotive.

Si le joueur possède les cartes additionnelles nécessaires, et s'il accepte de les jouer, alors il peut s'emparer du tunnel. S'il ne possède pas les cartes, ou ne désire pas les jouer, il reprend toutes les cartes en main et termine son tour.

Notez qu'il est parfaitement possible de n'utiliser que des cartes locomotives pour tenter de s'emparer d'un tunnel. Dans ce cas, seules les éventuelles cartes locomotive figurant parmi les trois cartes retournées impliquent l'utilisation de cartes additionnelles, qui doivent alors obligatoirement être des locomotives.

Pour illustrer la prise de possession d'un tunnel, imaginons qu'un joueur désire s'emparer de celui reliant Neuchâtel à La Chaux-de-Fonds, orange et de longueur 1. Pour ce faire, admettons qu'il pose devant lui une carte orange qu'il a en main. Les trois cartes au sommet de la pioche sont alors retournées.

Supposons que ces trois cartes soient une orange, une verte et une locomotive. Elles impliquent que le joueur doit encore jouer deux cartes additionnelles s'il veut s'emparer du tunnel — une pour la carte orange, une pour la locomotive. Chacune de ces deux cartes peut être soit une carte orange, soit une locomotive.

Si le joueur avait décidé d'utiliser initialement une carte locomotive pour tenter de s'emparer du tunnel, alors les mêmes trois cartes retournées impliqueraient l'ajout d'une seule carte additionnelle — pour la locomotive —, mais celle-ci ne pourrait qu'être une locomotive.

À la fin d'une partie de tCHu, le joueur dont le réseau comporte le plus long chemin remporte un bonus de 10 points. Si les plus longs chemins des deux joueurs sont de même longueur, le bonus leur est attribué à tous les deux.

Déterminer le plus long chemin du réseau d'un joueur est un problème plus difficile qu'il n'y paraît. À notre connaissance, il n'existe pas d'algorithme plus efficace qu'une recherche exhaustive. Cela dit, au vu de la petite taille et de la faible complexité des réseaux de tCHu, une telle recherche peut se faire assez rapidement.

Comme son nom l'indique, la recherche exhaustive consiste simplement à énumérer la totalité des chemins possibles dans un réseau, afin de déterminer lequel d'entre eux est le plus long.

L'énumération de tous les chemins possibles se fait en commençant avec les chemins les plus simples possibles — constitués d'une seule route — puis en essayant de les prolonger de toutes les manières possibles, en leur ajoutant des routes adjacentes, jusqu'à ce que cela ne soit plus possible. Sous forme de pseudo-code, cette énumération s'exprime ainsi :

cs = liste des chemins constitués d'une seule route
tant que cs n'est pas vide :
  cs' = liste vide
  pour tout chemin c de cs :
    rs = (routes appartenant au joueur,
          n'appartenant pas à c, et
          pouvant prolonger c)
    pour toute route r de rs :
      ajouter c prolongé de r à cs'
  cs = cs'

L'idée de cet algorithme est qu'au début de l'itération \(n\) de la boucle extérieure, l'ensemble cs contient tous les chemins possibles constitués de exactement \(n\) routes. L'union de tous ces ensembles cs constitue la totalité des chemins possibles du réseau.

Souvenez-vous que la longueur d'un chemin n'est pas égale au nombre de routes qui le composent, mais bien à la somme des longueurs de ces routes. Dès lors, et contrairement à ce qu'on pourrait initialement penser, le plus long chemin ne sera pas forcément produit lors de la dernière itération de la boucle extérieure.

L'algorithme ci-dessus ne fait rien d'autre qu'énumérer tous les chemins possibles, sans se souvenir du plus long. Il est toutefois facile de le modifier dans ce but, ce qui est laissé en exercice.

Le fonctionnement de l'algorithme de recherche exhaustive peut être illustré au moyen du réseau de la figure 3. Pour faciliter la lecture, ce réseau est à nouveau présenté ci-dessous.

La liste cs est initialisée avec les chemins constitués d'une seule route. Comme il y a 6 routes dans le réseau, cs est initialisé avec 12 chemins, parmi lesquels on trouve :

1. Neuchâtel A Yverdon
2. Yverdon A Neuchâtel
3. Neuchâtel B Soleure
4. Soleure B Neuchâtel
5. etc.

Lors de la première itération de la boucle extérieure, les 12 chemins contenus dans cs peuvent chacun être prolongés de différentes manières. Par exemple, le second chemin de la liste, Yverdon A Neuchâtel, peut être prolongé de deux manières différentes pour obtenir les chemins :

1. Yverdon AB Soleure (noté simplement AB),
2. Yverdon AC Berne (noté simplement AC).

Notez bien que la prolongation d'un chemin se fait toujours par ajout d'une route à la fin des routes existantes, pas au début.

Le tableau ci-dessous montre l'ensemble des chemins cs au début de chacune des 5 itérations de la boucle extérieure. La première ligne correspond à la valeur initiale de cet ensemble. Notez que les éléments de la liste cs ont été triés par ordre alphabétique pour faciliter la lecture, mais cet ordre ne joue aucun rôle et peut être quelconque.

En calculant la longueur de ces différents chemins, on constate que ceux constituant l'ensemble cs au début de la cinquième et dernière itération de l'algorithme ont tous une longueur de 13, supérieure à la longueur de tous les autres chemins. Il s'agit de :

1. ECBDF (Lucerne - Berne - Neuchâtel - Soleure - Berne - Fribourg),
2. EDBCF (Lucerne - Berne - Soleure - Neuchâtel - Berne - Fribourg),
3. FCBDE (Fribourg - Berne - Neuchâtel - Soleure - Berne - Lucerne),
4. FDBCE (Fribourg - Berne - Soleure - Neuchâtel - Berne - Lucerne).

Tous ces chemins méritent donc le titre de « chemin le plus long » du réseau, et n'importe lequel d'entre eux peut donc être produit en résultat.

Pour qu'une instance de SortedBag puisse trier les éléments qu'elle contient, ces éléments doivent être comparables deux à deux. Cela signifie qu'il doit être possible, étant donné deux éléments, de déterminer si le premier est plus petit que le second, si les deux sont égaux, ou si le premier est plus grand que le second. Notez que la méthode equals de Object ne suffit pas pour cela, car lorsque deux objets sont différents, elle ne permet pas de savoir lequel est le plus grand.

En Java, l'interface Comparable est destinée à être implémentée par les classes dont les éléments sont comparables. Pour une raison qui sera expliquée ultérieurement au cours, cette interface est générique, mais vous pouvez pour l'instant ignorer la signification de son paramètre de type. La seule méthode de Comparable est compareTo, qui compare le récepteur (this) à l'élément du même type passé en argument et indique s'ils sont égaux ou, sinon, lequel est le plus grand.

Afin de garantir que ses éléments sont comparables, et donc qu'ils implémentent l'interface Comparable, SortedBag place une borne supérieure sur son paramètre de type E. Sa déclaration ressemble donc à ceci :

class SortedBag<E extends Comparable<E>> { /* … */ }

Cette déclaration peut être comprise de la manière suivante : « SortedBag peut stocker des éléments d'un type quelconque, appelé E, à condition toutefois que ces éléments soient comparables entre eux au moyen de la méthode compareTo de Comparable. »

En plus de la classe elle-même, les différentes variantes de sa méthode de construction statique of, qui sont aussi génériques, placent la même borne sur leur paramètre de type à elles — que nous avons choisi de nommer également E, mais qui n'est pas pour autant le paramètre de type de la classe. Ainsi, la première variante de cette méthode est déclarée de la manière suivante :

static <E extends Comparable<E>> SortedBag<E> of() { /* … */ }

Le fait que SortedBag soit immuable implique que les méthodes qui « modifient » le contenu du multiensemble ne le modifient bien entendu pas, mais retournent un nouveau multiensemble. Il est très important de garder cela en tête !

Par exemple, la méthode union permet de calculer l'union de deux multiensembles et est donc similaire à la méthode addAll de ArrayList, mais avec une différence de taille : alors que addAll modifie le récepteur (this) en lui ajoutant les éléments de l'argument, union ne modifie pas le récepteur mais retourne un nouveau multiensemble. Pour cette raison, addAll ne retourne rien — son type de retour est void — tandis que union retourne une valeur de type SortedBag.

Pour faciliter la construction progressive de multiensembles, SortedBag est accompagnée d'un bâtisseur nommé Builder, imbriqué dans SortedBag. L'exemple ci-dessous, similaire à celui donné à l'étape précédente pour illustrer l'utilisation de TreeSet, montre comment ce bâtisseur peut être utilisé pour construire le multiensemble des mots to be or not to be :

SortedBag.Builder<String> wordsB = new SortedBag.Builder<>();
for (String w: List.of("to","be","or","not","to","be"))
  wordsB.add(w);
SortedBag<String> words = wordsB.build();

// s est égale à "{2×be, not, or, 2×to}"
String s = words.toString();

Cet exemple illustre le fait que les éléments d'un multiensemble trié sont toujours triés (ici dans l'ordre alphabétique), exactement comme avec un ensemble de type TreeSet. Par contre, il est possible qu'un même élément figure plusieurs fois dans un multiensemble, comme les mots be et to dans cet exemple, qui y apparaissent chacun 2 fois (d'où le préfixe 2× dans la représentation textuelle). Pour mémoire, un ensemble simple (p.ex. de type TreeSet) ne contient quant à lui jamais de doublons.

Afin d'avoir une idée des méthodes offertes par la classe SortedBag, lisez maintenant la totalité des commentaires Javadoc qui leur sont attachés. Bien entendu, vous avez également le droit de lire le code de ces méthodes, mais soyez conscients qu'elles utilisent de nombreux concepts qui n'ont pas encore été vus au cours, et il est donc probable que vous ne compreniez pas tout.

Dans cette étape et les suivantes, nous vous indiquerons les méthodes de SortedBag à utiliser dans les différents contextes, il n'est donc pas nécessaire d'essayer de les mémoriser.

La méthode possibleClaimCards n'est pas très facile à écrire, donc réfléchissez bien à une solution avant de tenter de la programmer ! En particulier, notez qu'il est tout à fait possible de directement générer les ensembles de carte possibles dans l'ordre demandé, ce qui évite de devoir trier la liste avant de la retourner. Nous vous suggérons fortement de songer à une solution de ce type.

Dans la méthode longest, pour déterminer si une route donnée appartient déjà à un chemin à prolonger, vous pouvez soit :

• utiliser la méthode contains de List, qui retourne vrai ssi l'objet qu'on lui passe se trouve dans le récepteur (this),
• utiliser la méthode removeAll de List, qui supprime du récepteur (this) tous les éléments de la collection qu'on lui passe en argument, ce qui vous permet de calculer l'ensemble des routes encore inutilisées.

La seconde solution est un peu plus efficace, mais aussi plus difficile à mettre en œuvre.