Si vous le souhaitez, vous pouvez donner votre opinion sur l’amphi et le TD :
On étudie dans ce TD un problème de combinatoire inspiré d’un jeu de type match-three. Le jeu se joue sur une grille rectangulaire sur laquelle on place des fruits. Dès qu’au moins trois fruits identiques sont adjacents dans une ligne ou dans une colonne, ils sont éliminés et disparaissent de la grille.
On considère ici le cas particulier où il n’y a que deux types de fruits. Le but du TD est d’écrire un programme qui dénombre les configurations stables du jeu, c’est-à-dire les grilles entièrement remplies sans alignement horizontal ni vertical de trois fruits identiques adjacents. Le programme doit être suffisamment efficace pour calculer le nombre de configurations stables de taille 10 × 10 en quelques secondes au plus.
Créez un nouveau projet TD2 dans votre espace de travail
CSC_41011.
Téléchargez l’archive TD2.zip qui contient le
code de test, et placez son contenu dans le répertoire de votre projet
TD2.
On rappelle que pour que les tests fonctionnent correctement, vous
devez activer les assertions lors de leur exécution. Si vous ne
l’avez pas déjà fait, reportez-vous au préambule du TD1 pour la procédure
à suivre.
public class Row {
private final int[] fruits;
Row() {
// ...
}
// ...
}Créez une classe Row qui modélisera les lignes de la
grille.
On représente le contenu d’une ligne par un tableau privé
fruits, de longueur égale à la longueur de la ligne, où les
deux types de fruits possibles sont codés par les entiers 0 et 1.
La classe Row doit posséder deux constructeurs :
Row(), qui crée une ligne vide,Row(int[] fruits), qui initialise une ligne dont le
champ fruits fait référence au tableau d’entiers
donné en paramètre.@Override
public boolean equals(Object o) {
// equals prend en argument un objet quelconque o
// ici on suppose que o est de la classe Row et on le convertit
Row that = (Row) o;
if (this.fruits.length != that.fruits.length)
return false;
for (int i = 0; i < this.fruits.length; ++i) {
if (this.fruits[i] != that.fruits[i])
return false;
}
// si on arrive ici, les deux lignes sont de même longueur et les
// fruits à la même position coïncident : on a donc égalité
return true;
}
@Override
public String toString() {
StringBuffer s = new StringBuffer();
for (int i = 0; i < fruits.length; ++i)
s.append(fruits[i]);
return s.toString();
}Recopiez également dans la classe Row les
spécialisations des méthodes standard equals et
toString fournies dans l’énoncé (ci-contre ou
ci-dessus).
Testez votre code. Par exemple, vérifiez que vous parvenez à créer et afficher une ligne vide, puis une ligne de longueur 2.
Pour parcourir toutes les configurations stables, on se propose de générer d’abord toutes les lignes stables (lignes qui ne contiennent pas trois fruits identiques consécutifs), puis « d’empiler » des lignes stables de manière à ne pas créer d’alignement vertical de trois fruits identiques adjacents.
On produit les lignes stables par largeur de grille croissante : pour
obtenir les lignes stables de width + 1 fruits, on parcourt
les lignes stables de width fruits et, pour chacune de ces
lignes, on cherche quel(s) fruit(s) il est possible d’ajouter en fin de
ligne de sorte à obtenir à nouveau une ligne stable.
import java.util.LinkedList;
public class Row {
// ...
}Ajoutez à la classe Row des méthodes :
Row extendedWith(int fruit) qui renvoie une nouvelle
ligne construite en ajoutant à la fin de la ligne courante
(this) une case contenant le fruit fruit,static LinkedList<Row> allStableRows(int width)
qui renvoie la liste de toutes les lignes stables de width
fruits,boolean areStackable(Row r1, Row r2) qui renvoie
true si et seulement si les trois lignes this,
r1 et r2 sont de même longueur et peuvent être
empilées 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 Row.java.
On suppose maintenant la largeur width de la grille
fixée. On observe que le nombre total de configurations stables à
height rows et dont les deux premières lignes
r1 et r2 (supposées stables) sont connues
s’exprime récursivement. Plus précisément :
height ≤ 1, il n’y en a aucune,height = 2, il y en a exactement une,height ≥ 3, chaque configuration stable à
height lignes dont les premières lignes sont
r1 et r2 s’obtient de façon unique en empilant
r1 au-dessus d’une configuration stable à
height - 1 lignes dont les premières lignes
r2 et r3 sont choisies de manière à respecter
la condition d’empilement.import java.util.LinkedList;
public class CountConfigurationsNaive {
// ...
}Créez une classe CountConfigurationsNaive qui implémente
le dénombrement récursif des configurations stables par application
directe des observations précédentes. On organisera le code en deux
méthodes :
static long count(Row r1, Row r2, LinkedList<Row> rows, int height)
qui renvoie le nombre de configurations stables à height
lignes dont les premières lignes sont r1 et r2
et dont les toutes les autres lignes sont prises parmi les éléments de
la liste rows,static long count(int n) qui utilise la méthode
précédente pour calculer le nombre de configurations stables à
n lignes et n colonnes.Testez votre code en exécutant Test2.java.
Déposez le fichier CountConfigurationsNaive.java :
On constate que le programme de la question précédente ne termine pas
en un temps raisonnable au-delà de n = 6.
Cependant, au fil des appels récursifs, la méthode
count(r1, r2, rows, height) est appelée de très nombreuses
fois sur les mêmes valeurs r1, r2, height. On peut rendre
le programme considérablement plus efficace en mémorisant le quadruplet
(r1, r2, height, result) la première fois que l’on calcule
result = count(r1, r2, rows, height). Lors des
appels suivants, on ira directement chercher le résultat dans la table
au lieu de le recalculer. (La valeur de rows ne changeant
pas au cours du calcul, il n’est pas nécessaire de la stocker.)
On a besoin pour cela d’une structure de dictionnaire, permettant
d’associer à un triplet (r1, r2,
height) une valeur de type long.
public class Quadruple {
Row r1;
// ...
}On réalise le dictionnaire à l’aide une table de hachage implémentée
comme un tableau de listes chaînées de quadruplets (r1,
r2, height, result). La case
d’indice h du tableau contient la liste des éléments de la
table de hachage dont le haché est égal à h modulo la taille du
tableau. Cette liste est aussi appelée seau ou bucket
d’indice h.
Créez d’abord une classe Quadruple pour représenter les
quadruplets.
import java.util.LinkedList;
import java.util.ArrayList;
public class HashTable {
static final int M = 50000;
ArrayList<LinkedList<Quadruple>> buckets;
// ...
}Ensuite, créez une classe HashTable pour la table
elle-même. On représente chaque seau par un objet de la classe standard
LinkedList, et la collection des seaux par un objet de la
classe standard ArrayList, stocké dans le champ
buckets de l’objet HashTable. Le nombre de
seaux est fixé une fois pour toutes et stocké dans le
champ M.
Ajoutez à la classe HashTable un constructeur qui fait
en sorte que chaque élément du tableau buckets soit
initialisé avec une liste vide de quadruplets.
Attention : un appel à
new ArrayList<...>(M) renvoie un nouveau tableau
redimensionnable dont la capacité initiale vaut M
mais dont la taille initiale est nulle. Il faut ensuite le remplir, par
exemple en utilisant la méthode add. Voir la documentation
de la classe ArrayList ou les transparents
de l’amphi 1 (transparent 28).
@Override
public int hashCode() {
int hash = 0;
for (int i = 0; i < fruits.length; ++i) {
hash = 2 * hash + fruits[i];
}
return hash;
}Il nous faut maintenant un moyen de calculer un haché à partir d’un triplet, et pour cela d’en calculer un à partir d’une ligne.
On vous propose une méthode public int hashCode(), à
ajouter à la classe Row, qui calcule le haché d’une
ligne.
En utilisant cette dernière, écrivez dans la classe
HashTable une méthode
static int hashCode(Row r1, Row r2, int height) qui calcule
une valeur de hachage pour le triplet (r1, r2,
height). Toute formule arithmétique impliquant à la fois
r1.hashCode(), r2.hashCode() et
height peut faire l’affaire. Cependant, 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. Essayez par exemple
de ne pas implémenter une formule qui ne donne que des résultats
pairs…
Écrivez ensuite une méthode
static int bucket(Row r1, Row r2, int height) qui renvoie
l’indice du seau associé au triplet (r1, r2,
height).
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 à garantir un résultat compris entre 0 (inclus)
et M (exclu). Voir à ce sujet les transparents
de l’amphi 2.
Dans la classe HashTable, écrivez une méthode
void add(Row r1, Row r2, int height, long result) qui
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.
Ajoutez à la classe HashTable une méthode
Long find(Row r1, Row r2, int height) qui recherche dans la
table un quadruplet de la forme (r1, r2,
height, result). S’il existe dans la table un
tel quadruplet, find renvoie un objet Long de
valeur result. S’il n’en existe pas, find
renvoie null.
Note : La valeur de retour de find est un
objet de type Long et non une valeur du type
primitif long. (Il ne serait pas possible de renvoyer
null sinon — voyez-vous pourquoi ?) On peut convertir un
entier primitif en un objet de la classe Long avec
Long.valueOf(long x) (documentation).
Cependant, quand on écrit return l; où l est
de type long dans une fonction qui déclare renvoyer un
objet de type Long, la conversion est faite automatiquement
(autoboxing).
Testez votre code en exécutant Test3.java.
Déposez le fichier HashTable.java.
En vous inspirant de votre classe
CountConfigurationsNaive, créez une classe
CountConfigurationsHashTable avec une méthode
static long count(int n) qui calcule le nombre de
configurations stables à n lignes et
n colonnes en utilisant un objet HashTable
pour éviter de calculer plusieurs fois le même résultat
intermédiaire.
Testez votre code en exécutant Test4.java.
Le calcul du nombre de configurations stables de taille 10 × 10 ne doit pas prendre plus de quelques secondes.
Déposez le fichier
CountConfigurationsHashTable.java.
En vous inspirant de votre classe
CountConfigurationsHashTable, créez une classe
CountConfigurationsHashMap, toujours avec la même
interface, mais utilisant la classe HashMap
de la bibliothèque standard de Java à la place de votre classe
HashTable.
Les clés étant maintenant des triplets (Row,
Row, int), il vous faudra introduire une
classe Triple pour les représenter et utiliser une table de
type HashMap<Triple, Long>. La classe
Triple devra redéfinir les méthodes standard
public boolean equals(Object o) et
public int hashCode().
Ajouter l’annotation @Override avant les redéfinitions
(comme dans le code fourni pour Row) est une bonne idée
pour éviter les erreurs. Notez bien que la méthode equals
prend un argument de type Object et non de type
Triple. Voir à ce sujet les transparents
de l’amphi 2.
Naturellement, la méthode hashCode() pourra faire appel
à la méthode
static int hashCode(Row r1, Row r2, int height) de la
classe HashTable.
Testez votre code en exécutant Test5.java.
Déposez le fichier CountConfigurationsHashMap.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.