INF 411 - TD 2

Fruits et tables de hachage

Dans ce TD, on cherche à résoudre un problème de combinatoire d'un jeu de type match three. Pour y parvenir, on utilise la technique de mémoïsation, à l'aide d'une table de hachage. On compare l'approche de mémoïsation avec l'approche naïve.

Créez un nouveau projet TD2 dans votre espace de travail Visual Studio Code INF411. Téléchargez le fichier src.zip qui contient le code nécessaire pour le TD, et décompressez-le dans le répertoire de votre projet TD2. Comme pour le TD1, vous devrez activer assert dans votre machine virtuelle Java. Pour plus de détails, voir la partie « Préambule » du TD1.

Formulation du problème

On étudie le jeu suivant. On dispose d'une grille rectangulaire sur laquelle on peut placer et bouger des fruits. Chaque case de la grille ne peut contenir qu'un seul fruit. Il y a plusieurs types de fruits. Dès qu'au moins trois fruits de même type sont adjacents dans une ligne ou dans une colonne, ils sont éliminés et disparaissent de la grille. Le joueur reçoit des points en fonction du nombre de fruits ainsi éliminés. Étant données les dimensions de la grille et le nombre de types de fruits, on cherche à compter les configurations stables, c'est-à-dire les configurations où il n'y a jamais trois fruits du même type adjacents dans une ligne ou dans une colonne. Ce sont les configurations où aucun fruit n'est éliminé. L'objectif du TD est de compter le nombre de configurations stables sur une grille de taille 10x10 avec deux types de fruits.

Un jeu match three

1. Modélisation du jeu

Pour dénombrer les grilles, on va d'abord représenter les lignes de la grille. Les lignes sont représentées par les objets de la classe Row. Cette classe possède un champ private final int[] fruits qui est un tableau d'entiers, chaque entier représentant un type de fruits.

Pour simplifier, on suppose qu'il n'y a que deux types de fruits différents, représentés par les deux entiers 0 et 1.

Dans la classe Row, on vous fournit :

• deux constructeurs Row() et Row(int[] fruits) ;
• une méthode public String toString() qui donne une représentation agréable d'une ligne ;
• une méthode public boolean equals(Object o) qui compare deux lignes ;
• une méthode public int hashCode() dont on ne se soucie pas pour le moment.

Dans la classe Row, complétez les méthodes :

• Row extendedWith(int fruit) pour qu'elle renvoie une nouvelle ligne construite à partir de this à laquelle on ajoute une nouvelle case à la fin avec un fruit de type fruit.
• static LinkedList<Row> allStableRows(int width) pour qu'elle génère et renvoie la liste de toutes les lignes stables de largeur width (i.e. qui ne contiennent pas trois fruits consécutifs identiques). Indication : pour créer toutes les lignes stables de largeur width, on parcourt toutes les lignes stables de largeur width-1 et on ajoute un fruit fruit (0 ou 1) à chaque ligne dont au moins l'un des deux derniers fruits est distinct de fruit.
• boolean areStackable(Row r1, Row r2) pour qu'elle renvoie true si r1 et r2 sont de même longueur que this et peuvent être empilées au dessus ou en dessous de this (ou dans un autre ordre quelconque) sans qu'il n'y ait trois fruits du même type dans une même colonne.

Testez votre code en exécutant Test1.java.

Déposez le fichier TD2.java :

2. Dénombrement naïf

On va maintenant procéder à un dénombrement naïf des configurations stables, en travaillant dans la classe CountConfigurationsNaive.

Dans la classe CountConfigurationsNaive, complétez la méthode récursive static long count(Row r1, Row r2, LinkedList<Row> rows, int height) pour qu'elle détermine le nombre de grilles dont les premières lignes sont r1 et r2, dont les lignes sont des lignes de rows et dont la hauteur est height. L'algorithme est le suivant :

count(r1, r2, rows, height) =

• si height est inférieure ou égale à 1, renvoyer 0 ;
• si height est égale à 2, renvoyer 1 ;
• sinon,
  • faire la somme, pour toute ligne r3 de rows qui peut être empilée sur r1 et r2, du résultat de count(r2, r3, rows, height-1),
  • renvoyer ce résultat.

Dans la classe CountConfigurationsNaive, complétez la méthode static long count(int n) pour qu'elle calcule le nombre de grilles à n lignes et n colonnes.

Testez votre code en exécutant Test2.java.

Déposez le fichier TD2.java :

Que constatez-vous ?

Le programme est correct, mais avec une si mauvaise complexité, il ne termine pas en un temps raisonnable au-delà de n=6. Ceci est dû au fait que count(r1, r2, rows, height) est appelé de très nombreuses fois pour les mêmes valeurs r1, r2, height. Pour régler le problème, il suffit de mémoriser dans une table le quadruplet (r1, r2, height, count(r1, r2, rows, height)) la première fois que l'on calcule count(r1, r2, rows, height) (la valeur de rows ne change jamais, il n'est donc pas nécessaire de la stocker). Les fois suivantes, on ira directement chercher l'information (ici le nombre de grilles associées à r1, r2 et height) dans la table sans recalculer la valeur. On pourrait utiliser la classe HashMap de Java pour réaliser une telle table. Cependant, afin de bien comprendre le principe de cette structure de données, nous commencerons par réaliser nous-mêmes une table de hachage.

3. Table de hachage

On va écrire une structure de données qui associe à deux lignes r1 et r2 et une hauteur height une valeur de type long.

On utilise la classe Quadruple pour représenter les éléments de cette table, c'est-à-dire des quadruplets (r1, r2, height, result) où r1, r2 sont des lignes de la classe Row, où height est un entier de type int et où result un nombre entier de type long. La classe Quadruple est donnée dans le fichier TD2.java et il n'y a rien à modifier dans cette classe.

Une table de hachage n'est rien d'autre qu'un tableau de listes chaînées de quadruplets, où l'élément d'indice i contient les quadruplets pour lesquels la valeur de hachage vaut i modulo la taille du tableau. On utilise la classe LinkedList pour représenter les listes et on choisit une valeur arbitraire (ici 50000) pour la taille du tableau. On va donc travailler avec une classe HashTable contenant :

• une constante final static int M correspondant au nombre de "seaux" de la table, i.e. le nombre de cases du tableau, que l'on fixe à 50000 dans ce qui suit.
• un champ Vector<LinkedList<Quadruple>> buckets qui représente la table, c'est-à-dire la collection des seaux dans lesquels on va stocker les quadruplets selon leur valeur de hachage.

3.1. Initialisation

Complétez le constructeur de la classe HashTable pour que chaque élément du tableau buckets soit bien initialisé avec une nouvelle LinkedList<Quadruple>.

Attention : un appel à new Vector<...>(M) renvoie un nouveau tableau redimensionnable dont la capacité est M mais dont la taille est 0. Il faut ensuite le remplir, par exemple en utilisant la méthode add. Voir la documentation de la classe Vector.

3.2. Fonction de hachage

Dans la classe HashTable, complétez la méthode static int hashCode(Row r1, Row r2, int height) pour qu'elle calcule une valeur de hachage arbitraire pour le triplet (r1, r2, height). Toute formule arithmétique non triviale impliquant à la fois r1.hashCode(), r2.hashCode() et height fera l'affaire. Si la formule est trop naïve, les entrées sont mal réparties entre les seaux de la table, et l'efficacité de la mémoïsation est moins bonne.

Dans la classe HashTable, complétez la méthode int bucket(Row r1, Row r2, int height) pour qu'elle renvoie la valeur de hashCode(r1, r2, height) modulo M.

Attention : le résultat de l'opérateur modulo de Java (%) sur des entiers négatifs peut être lui-même négatif. On veillera donc ici à garantir un résultat entre 0 (inclus) et M (exclus).

3.3. Ajout dans la table

Dans la classe HashTable, complétez la méthode void add(Row r1, Row r2, int height, long result) pour qu'elle ajoute le quadruplet (r1, r2, height, result) dans le seau indiqué par la méthode bucket. On ne cherchera pas à vérifier si l'entrée existe déjà ; on se contentera de l'ajouter systématiquement à la liste.

3.4. Recherche dans la table

Dans la classe HashTable, complétez la méthode Long find(Row r1, Row r2, int height) pour qu'elle recherche dans la table un quadruplet de la forme (r1, r2, height, result). S'il existe dans la table un tel quadruplet, on renvoie un Long de valeur result. Sinon, la valeur null est renvoyée.

Attention : il est nécessaire d'utiliser la classe Long plutôt que le type primitif long pour renvoyer result lorsqu'on trouve un quadruplet de la forme (r1, r2, height, result). Afin de convertir un entier de type primitif en un objet de la classe Long, on pourra utiliser Long() ou Long.valueOf(). Aussi, on peut renvoyer la valeur null pour indiquer qu'aucun tel quadruplet n'est présent dans la table.

Testez votre code en exécutant Test3.java.

Déposez le fichier TD2.java :

4. Dénombrement avec mémoïsation

On revient sur le problème de combinatoire initial. On travaille maintenant dans la classe CountConfigurationsHashTable, dans laquelle on a un champ memo de type HashTable.

En vous inspirant de votre méthode static long count(Row r1, Row r2, LinkedList<Row> rows, int height) de la classe CountConfigurationsNaive, complétez la méthode static long count(Row r1, Row r2, LinkedList<Row> rows, int height) de la classe CountConfigurationsHashTable en utilisant le champ memo pour mémoriser les calculs déjà effectués.

En vous inspirant de votre méthode static long count(int n) de la classe CountConfigurationsNaive, complétez également la méthode static long count(int n) de la classe CountConfigurationsHashTable pour qu'elle calcule le nombre de grilles à n lignes et n colonnes.

Testez votre code en exécutant Test4.java, qui calcule enfin le nombre de grilles 10x10 (ce qui ne doit pas prendre plus de quelques secondes).

Déposez le fichier TD2.java :

5. Utilisation de HashMap

En vous inspirant de votre classe CountConfigurationsHashTable, complétez les méthodes static long count(Row r1, Row r2, LinkedList<Row> rows, int height) et static long count(int n) de la classe CountConfigurationsHashMap, en utilisant la classe HashMap de la bibliothèque standard de Java à la place de votre classe HashTable.

Indication : les clés étant des triplets (Row, Row, int), il vous faudra introduire une classe Triple pour les représenter, afin de pouvoir utiliser l'instance HashMap<Triple, Long>. Cette classe Triple devra redéfinir ses méthodes public boolean equals(Object o) (Attention : cette méthode prend un Object en argument et non un Triple) et public int hashCode(). Pour cette dernière méthode, on pourra faire appel à la méthode static int hashCode(Row r1, Row r2, int height) de la classe HashTable. Ajouter l'annotation @Override avant ces deux méthodes est une bonne idée.

Testez votre code en exécutant Test5.java.

Déposez le fichier TD2.java :

Vous venez de calculer les entrées diagonales de la suite A203407 de l'On-Line Encyclopedia of Integer Sequences. Si vous avez aimé ce problème, vous adorerez le Projet Euler.