État d'un joueur

Ayant décidé de représenter la connectivité du réseau d'un joueur par une partition des gares, il reste encore à savoir comment représenter effectivement, par exemple en Java, une partition.

Pour ce projet, nous allons utiliser une technique connue de représentation des partitions, qui a l'avantage d'être simple, élégante et efficace. Elle consiste à choisir, pour chacun des sous-ensemble de la partition, un unique élément pour jouer le rôle de représentant (representative) du sous-ensemble. Comme son nom l'indique, cet élément représente tous les éléments du sous-ensemble auquel il appartient.

Pour notre exemple, on pourrait ainsi choisir la gare d'Interlaken comme représentant de son sous-ensemble, la gare de Neuchâtel comme représentant du sien, etc. Chaque sous-ensemble ne contenant qu'une gare n'a qu'un représentant possible, par contre pour tous les autres sous-ensembles il y en a plusieurs, et le choix exact importe peu. Seul compte le fait que chaque sous-ensemble ait exactement un représentant.

Ainsi, la partition correspondant au réseau plus haut pourrait être représentée par les sous-ensembles ci-dessous, où les représentants sont en gras :

1. { Lausanne, Fribourg, Berne, Interlaken },
2. { Neuchâtel, Soleure, Olten },
3. { Lucerne, Zoug, Schwyz, Wassen },
4. { Delémont },
5. { La Chaux-de-Fonds },
6. { Yverdon },
7. { Zürich }.

Avec cette représentation, déterminer si un trajet entre deux gares est possible revient à déterminer si les représentants des sous-ensembles contenant les deux gares sont identiques ou non.

Par exemple, déterminer si le trajet Lucerne - Wassen est possible revient à déterminer si les représentants des sous-ensemble les contenant (ici Zoug et Zoug resp.) sont identiques, ce qui est bien le cas. De même, déterminer si le trajet Neuchâtel - Lausanne est possible revient à déterminer si les représentants des sous-ensembles les contenant (ici Neuchâtel et Interlaken resp.) sont identiques, ce qui n'est pas le cas.

Une question subsiste toutefois encore : comment obtenir facilement le représentant du sous-ensemble auquel un élément quelconque appartient ? Simplement en s'assurant que chaque élément référence le représentant du sous-ensemble auquel il appartient ! Visuellement, ces liens peuvent être représentés par des flèches allant des éléments vers le représentant de leur sous-ensemble, et notre réseau d'exemple peut donc être visualisé ainsi :

Comme cette image l'illustre, les représentants se référencent eux-mêmes, et c'est à cela qu'on les reconnaît.

La discussion ci-dessus semble indiquer que les liens allant d'un élément à son représentant — les flèches du diagramme — sont stockés dans les éléments eux-mêmes. Dans notre cas, cela signifierait que chaque gare, c-à-d chaque instance de Station, devrait contenir une référence vers la gare la représentant.

Même si une telle solution serait envisageable, elle n'est pas forcément idéale, car elle implique de stocker directement dans les gares une information qui est plutôt liée à une partition de gares qu'à la gare elle-même. De plus, une telle organisation implique qu'une gare ne peut faire partie que d'une seule partition, puisqu'elle ne peut avoir qu'une seule référence vers le représentant de son sous-ensemble.

Il est donc préférable de stocker les liens non pas de manière interne aux gares, mais de manière externe. Cela est même particulièrement simple car nous avons pris soin de numéroter toutes les gares du réseau en leur affectant à chacune une identité allant de 0 au nombre de gares moins un.

Grâce à cette identité, il est possible de représenter les liens au moyen d'un simple tableau d'entiers, contenant autant d'éléments qu'il y a de gares. À chaque position du tableau correspond donc une gare, et l'élément stocké dans chacune de ces positions est l'index du représentant du sous-ensemble auquel la gare en question appartient. Autrement dit, à chaque élément du tableau correspond une flèche de la figure ci-dessus, l'index de l'élément étant l'identité de la gare au départ de la flèche, l'élément lui-même étant l'identité de la gare à l'arrivée de la flèche.

Par exemple, admettons que les gares du réseau ci-dessus soient numérotées dans l'ordre alphabétique, ainsi :

Dans ce cas, la partition présentée plus haut est représentée par le tableau d'entiers suivant :

Grâce à ce tableau, déterminer si Lucerne (index 6) et Wassen (index 11) sont connectées revient à regarder si la valeur qui se trouve aux deux index correspondants du tableau (à savoir 13 et 13) sont identiques, ce qui est bien le cas.

À ce stade, la manière dont nous représenterons les partitions de gares devrait être claire. Ce qui ne l'est toutefois pas encore est comment construire ces partitions à partir du réseau d'un joueur.

Le réseau d'un joueur n'est rien d'autre que l'ensemble des routes dont il s'est emparé. La partition des gares qui correspond peut s'obtenir en deux étapes :

1. une représentation, dite profonde, de cette partition est construite,
2. cette représentation profonde est aplatie afin d'obtenir celle décrite ci-dessus.

La représentation profonde d'une partition est très similaire à celle ci-dessus. La seule différence est que les éléments ne sont pas forcément liés directement au représentant de leur sous-ensemble. Au lieu de cela, ils sont liés entre eux de manière à ce que, en suivant les références, on finisse par arriver au représentant. Comme avant, celui-ci se reconnaît au fait qu'il se référence lui-même.

L'image ci-dessous montre une possibilité de représentation profonde de la partition décrite plus haut. On voit par exemple que Lausanne n'est plus liée directement au représentant de son sous-ensemble (Interlaken), mais est liée à Berne, qui est elle liée à Interlaken.

La représentation profonde a l'avantage d'être très facile à construire à partir du réseau d'un joueur. En effet, il suffit de partir d'une partition maximale des gares, c-à-d d'une partition dans laquelle chaque gare appartient à son propre sous-ensemble, qui ne contient donc qu'elle. Ensuite, les routes dont le joueur s'est emparé sont parcourues, et les sous-ensembles contenant chacune des deux gares reliées par la route sont joints.

Joindre deux sous-ensembles se fait très facilement dans la représentation profonde : il suffit de déterminer les représentants des deux sous-ensembles et d'en choisir arbitrairement un comme représentant du sous-ensemble joint. Pour ce faire, il suffit de faire en sorte que l'autre représentant le référence comme son propre représentant, et le tour est joué !

Par exemple, pour construire la représentation profonde du réseau d'exemple plus haut, on commence avec la partition maximale des gares de ce réseau, dans laquelle chaque gare est dans son propre sous-ensemble :

On parcourt ensuite les routes du réseau dans un ordre quelconque. Admettons que la première soit Fribourg - Berne. On modifie alors la partition afin de joindre les sous-ensembles contenant Fribourg et Berne. Pour ce faire, on cherche les représentants de ces sous-ensembles, qui sont simplement Fribourg et Berne. Ensuite, on en choisit arbitrairement un comme nouveau représentant, disons Berne, et on fait en sorte que l'autre représentant (Fribourg) le référence lui. On obtient donc la partition représentée ainsi, la référence modifiée étant indiquée par une flèche grasse :

Admettons que la seconde route parcourue soit Lausanne - Fribourg. Là encore, on recherche les représentants des sous-ensembles correspondants, qui sont respectivement Lausanne et Berne. On en choisit arbitrairement un comme nouveau représentant, disons Berne, et on fait donc en sorte que l'autre (Lausanne) le référence. On obtient alors :

Et ainsi de suite jusqu'à ce que toutes les routes du réseau aient été parcourues, et les sous-ensembles correspondants joints.

Une fois la représentation profonde construite, il ne reste plus qu'à l'aplatir. Pour cela, il suffit de parcourir tous les éléments de la partition, de déterminer le représentant de chacun, et de lier directement l'élément à son représentant.

La vidéo ci-dessous présente un exemple de construction et d'aplatissement d'une partition de gare, et peut être utile aux personnes auxquelles les explications ci-dessus ne suffiraient pas.

Il est fortement recommandé d'équiper le bâtisseur d'une méthode privée nommée p.ex. representative prenant en argument le numéro d'identification d'une gare et retournant celui du représentant du sous-ensemble la contenant. Une fois cette méthode définie, les méthodes connect et build sont relativement simples à écrire.

Pour éviter de recalculer le nombre de wagons que possède un joueur, ou le nombre de points de construction qu'il a obtenus, stockez ces informations dans des attributs de la classe.

Une manière de déterminer les cartes additionnelles possibles dans la méthode possibleAdditionalCards est de procéder en trois étapes, ainsi :

1. calculer le multiensemble de toutes les cartes utilisables parmi celles qui restent au joueur une fois les cartes initiales retirées de sa main — c-à-d les locomotives et les cartes de même couleur qu'une initiale,
2. déterminer tous les sous-ensembles de ce multiensemble contenant le nombre de cartes additionnelles requis,
3. trier cette liste de sous-ensembles par ordre croissant de nombre de cartes locomotives.

Par exemple, admettons qu'un joueur possède en main trois cartes vertes, deux bleues et deux locomotives et qu'il essaie de s'emparer d'un tunnel de couleur verte et de longueur 1 au moyen d'une de ses cartes vertes. Admettons de plus que les trois cartes tirées de la pioche impliquent l'ajout de deux cartes additionnelles. Le calcul des cartes additionnelles possibles peut se faire ainsi :

1. les cartes utilisables sont au nombre de quatre : les deux vertes (le joueur en a trois en main, mais une est déjà utilisée comme carte initiale) et les deux locomotives,
2. les sous-ensembles de taille 2 de ce multiensemble de taille 4 sont :
   • deux vertes,
   • deux locomotives,
   • une verte et une locomotive,
3. une fois triés par ordre croissant de nombre de cartes locomotives, ces sous-ensembles sont :
   1. deux vertes,
   2. une verte et une locomotive,
   3. deux locomotives.

Le calcul des sous-ensembles de la bonne taille (point 2) peut se faire au moyen de la méthode subsetsOfSize de SortedBag. Cette méthode retourne un ensemble, dont le contenu doit être placé dans une liste pour pouvoir être trié (point 3). Le tri de cette liste se fait facilement, mais comme il utilise une notion qui n'a pas encore été vue au cours — une lambda —, nous vous donnons directement le code à écrire :

List<SortedBag<Card>> options = …; // point 2
options.sort(
  Comparator.comparingInt(cs -> cs.countOf(Card.LOCOMOTIVE)));

Vous pouvez lire ce code de la manière suivante : la liste options doit être triée par ordre croissant (sort), en comparant (comparingInt) le nombre de locomotives (countOf(Card.LOCOMOTIVE)) de chaque élément cs.

La méthode ticketPoints doit construire la partition des gares correspondant au joueur, et pour cela doit savoir quelle valeur passer au constructeur de StationPartition.Builder. Pour cela, il lui suffit de parcourir les routes dont le joueur s'est emparé, de déterminer l'identité maximum de ces gares, et d'ajouter 1 à cette valeur.