Dans ce premier article, faisons un peu le tour de « La Grille » à la révision 1.
En ligne, vous pouvez consulter les sources sur GitHub.
Si vous avez cloné le dépôt en local, synchronisez vous sur cette révision : git reset 903668e
La compilation totale du projet (scons all) produit trois exécutables :
output/temp. Il est exécuté automatiquement par le système de construction. Si un test ne passe pas, la construction du projet est mis en erreur.output/testgen et s'exécute à la main. Ce programme est là comme bac à sable des fonctions de la bibliothèque.output/gridgen. De base, il génère des grilles de 2×2. Il peut prendre en paramètre -x et -y suivi d'un espace et d'un chiffre pour indiquer la taille de la grille. Attention, du à l'accès au dictionnaire par un chemin relatif, le programme doit être lancé depuis son répertoire.
Les trois exécutables sont liés à une bibliothèque commune nommé wordgrid qui contient tout le code de génération.
Pour plus de renseignements sur la compilation du projet, dirigez-vous vers la page expliquant comment compiler le programme.
C'est donc dans la bibliothèque que l'on va trouver les choses les plus intéressantes, et c'est sur cette partie que les développements vont se concentrer au fil des articles.
Le cœur du programme est le « Solver » dont une implémentation se trouve dans SolverImpl. C'est une classe squelette qui utilise d'autre objets pour effectuer les traitements réels sur la grille.
Pour une grille donnée, l'appel à la méthode Solve d'une instance de SolverImpl va :
PositionScanner une liste de positions valide pour ajouter des mots à la grille ;WordRequestGenerator une liste de requêtes à destination d'un dictionnaire ;Dictionary une liste de mots valides ;Solver avec la nouvelle grille (l'instance appelée pouvant être elle-même).C'est donc un processus récursif qui fait une recherche en profondeur dans l'arbre des possibilités de la grille. C'est une solution basique et gourmande, mais simple à comprendre et à implémenter.
Le Solver s'appuie donc sur des interfaces de comportement, implémentés actuellement en un exemple pour chaque interface dans une classe concrète. Voici en l'état la stratégie adoptée pour chacune de ces classes :
Implémenté par PositionScannerImpl : une implémentation extrèmement basique, chaque case non noire (et actuellement, le programme ne gère pas les cases noires) est une position à vérifier. Autrement dit, à chaque entrée dans le Solver, toutes les cases seront candidates à une recherche.
Probablement qu'il y aura mieux à faire.
PositionScanner est aussi implémenté pas PositionScannerLog. Les implémentations se terminant en Log dans les classes de comportement sont faites pour s'intercaler entre l'appel du Solver et une implémentation réelle du comportement. Au passage, ces objets écrivent des informations sur un flux.
C'est par exemple comme cela que testgrid affiche les informations sur le déroulement des tests fonctionnels.
WordRequestGenerator est implémenté par FullGridWordRequestGenerator. Cette classe renvoie des requêtes par rapport à une position sur la grille en considérant que l'on ne cherche des mots uniquement de la taille de la grille (verticalement ou horizontalement).
Accessoirement, cela signifie que ce générateur ne renvoie aucune requête si la position à scanner n'est pas sur un des bords haut ou gauche de la grille. Cela élimine beaucoup des positions inutiles de l'implémentation simple de PositionScannerImpl. Bien entendu, on fait beaucoup de traitements pour rien.
Une requête est renvoyée du moment qu'à partir d'une position, on trouve une case vide sur la verticale ou l'horizontal. La requête est une chaîne de caractères dans laquelle les cases à trouver sont laisser à une valeur particulière.
Dictionary est implémenté par DictionarySimpleImpl. Son implémentation est simpliste : pour une requête envoyée, le dictionnaire va chercher dans sa liste de mots, stockée sous forme d'un tableau, tout ce qui est valide. Oui, cela signifie qu'à chaque requête, le dictionnaire va être parcouru dans son intégralité.
On ne peut pas faire plus simple… et difficilement plus lent.
Dictionary est aussi implémenté par DictionaryLog qui donne des informations sur les mots cherchés.
WordWriter est implémenté par WordWriterImpl. Le comportement de cette interface est d'écrire un mot sur une grille (classe Grid) à une position et pour une orientation donnée et de renvoyer ce qui a vraiment été écrit. Cela permet de demander ultérieurement à WordWriter de défaire ce qui a été écrit. Autrement dit, remettre la grille dans l'état avant l'écriture du mot.
WordWriter est aussi implémenté par WordWriterLog.
Oui… Solver. Pour faire son parcours en profondeur, Solver pourrait appeler directement Solve() avec la nouvelle grille. Mais plutôt que de faire cet appel récursif de manière dure, je passe par une instance donnée de Solver.
Dans le cas simple, en passant à une instance de Solver lui-même, on retombe sur la récursivité simple.
Mais ce petit raffinement permet de passer par un SolverLog, qui peut afficher la grille à l'état actuel par exemple. On peut aussi imaginer une classe faisant des statistiques sur le Solver, tracer l'arbre de recherche,…
Au prochain épisode, je montrerai quelques profile du programme en l'état actuel. Vous pensez savoir ce qui prend le plus de temps ? C'est possible, j'avais aussi ma petite idée lors du développement du programme et cela s'est vérifié au profiling. Cependant, ne vous laissez pas avoir par votre instinct, vérifiez toujours ce que vous supposez avec un profiler, que ce soit à propos du temps machine consommé ou de la mémoire prise.
À partir de ce profiling, je pourrai décider de ce qu'il convient d'optimiser.