INF 411 - TD 2

Fruits et tables de hachage


Votre opinion sur le cours de lundi : Votre opinion sur le TD de la semaine dernière :

 Login :  Mot de passe :

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.

Vous pouvez télécharger le code nécessaire pour le TD dans une seule archive ici : code.zip

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
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.java. 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

Question. Dans la classe Row.java, compléter les méthodes

Utiliser Test1.java pour les tester.

Déposez le fichier Row.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2 Dénombrement naïf

Téléchargez le fichier squelette CountConfigurations.java qui contient la classe CountConfigurations.

La méthode fournie static LinkedList<Row> allRows(int width) renvoie une liste de toutes les lignes valides d'une largeur donnée.

Pour dénombrer les grilles, compléter dans la classe CountConfigurations la méthode récursive static long count(Row r1, Row r2, LinkedList<Row> rows, int height) qui 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) =

Déduisez-en une méthode static long count(int n) qui calcule le nombre de grilles à n lignes et n colonnes.

On pourra tester cette méthode à l'aide du Test2.java.

Déposez le fichier CountConfigurations.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Que constatez-vous ?

Le programme est correct, mais avec une si mauvaise complexité qu'il ne termine pas en un temps raisonnable. 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 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 allons d'abord 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 une classe Quadruple pour représenter les entrées de cette table, c'est-à-dire des quadruplets (r1, r2, height, result)r1, r2 sont des Row, height est un entier de type int et result un nombre entier de type long. Dans la suite de l'énoncé, on appellera "entrée pour le triplet (r1, r2, height)" tout quadruplet de la forme (r1, r2, height, result). Cette classe contient :

public class Quadruple {
        Row r1;
        Row r2;
        int height;
        long result;

        Quadruple(Row r1, Row r2, int height, long result) {
                this.r1 = r1;
                this.r2 = r2;
                this.height = height;
                this.result = result;
        }
}

Téléchargez le fichier Quadruple.java.

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 créer une classe HashTable.

3.1 Initialisation

Créer une nouvelle classe HashTable avec :

Écrire un 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, écrivez une méthode int hashCode(Row r1, Row r2, int height) qui calcule une valeur de hachage arbitraire pour le triplet (r1, r2, height). Toute formule arithmétique impliquant à la fois r1.hashCode(), r2.hashCode() et height fera l'affaire.

Dans la classe HashTable, écrivez une méthode int bucket(Row r1, Row r2, int height) qui 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, ajoutez une méthode void add(Row r1, Row r2, int height, long result) pour ajouter le quadruplet correspondant aux paramètres (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, ajoutez une méthode Quadruple find(Row r1, Row r2, int height) qui recherche dans la table une entrée pour le triplet (r1, r2, height). S'il existe dans la table une telle entrée, on la renvoie. Sinon, la valeur null est renvoyée.

On pourra tester avec le Test3.java.

Déposez le fichier HashTable.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4 Dénombrement avec mémoïsation

On revient sur le problème de combinatoire initial et on travaille donc de nouveau dans la classe CountConfigurations.

Décommentez la ligne dans CountConfigurations.java qui déclare et initialise la variable memo de type HashTable.

Modifiez votre méthode static long count(Row r1, Row r2, LinkedList<Row> rows, int height) de la classe CountConfigurations en utilisant le champ memo pour mémoriser les calculs déjà effectués. L'algorithme est maintenant le suivant :

count(r1, r2, rows, height) =

Exécutez de nouveau Test2.java en calculant enfin le nombre de grilles 10x10 (ce qui ne doit pas prendre plus de quelques secondes).

Déposez le fichier CountConfigurations.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

5 Utilisation de HashMap

Créez une classe CountConfigurationsHashMap à partir de la classe CountConfigurations en modifiant votre code pour utiliser 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().

Vous pourrez tester votre code à l'aide du fichier Test5.java.

Déposez le fichier CountConfigurationsHashMap.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer


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.


Voici une solution possible : solution.zip.