Projet 18 : Générateur de mots mếlés
Description du mini projet
C’est un jeu qui consiste à repérer une liste de mots dissimulée au sein d'une grille, généralement de forme carrée ou rectangulaire. Ils peuvent être cachés à l'endroit, à l'envers, horizontalement, verticalement ou en diagonale.
Votre programme devra générer dans un fichier texte une grille de mot mêlés dont l’utilisateur a fixé la taille en saisissant sa longueur et sa largeur.
La liste des mots présents dans la grille sera aussi fournie par l’utilisateur.
Cahier des charges
Une grille
Considérons une grille carrée, de côté variable n. Elle contient n² cases indexées dans un tableau de 0 à n²-1. Par exemple, pour une grille de côté 5, on a 25 cases, numérotées de 0 à 24 :
0 | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 |
Chaque case contiendra qu'une seule lettre.
Des mots
Chaque mot a les attributs suivants :
Orientation : horizontale, verticale, diagonale
Texte inversé ou non
Une case de départ
Une case de fin
L | ||||
A | ||||
Y | ||||
O | ||||
R |
Dans l'exemple ci-dessus, le mot ROYAL est inversé, il est vertical, commence dans la case 1 et se termine dans la case 21.
Une base de données de mots
Les mots seront piochés au hasard. Pour récupérer la liste de mots autorisés au Scrabble de Jean-Philippe Durand : http://jph.durand.free.fr/scrabble.txt
Simulation : Algorithme
Voici une suggestion :
On part d'une case au hasard. Ceci pour éviter de placer systématiquement un mot en première case de la grille.
On tire au hasard l'orientation et l'inversion du mot.
On tire au hasard une longueur de mot, comprise entre 3 et n (longueur du côté de la grille).
Selon l'orientation :
HORIZONTALE : Si le mot sort de la grille à droite et se retrouve placé sur 2 lignes, on le décale à gauche.
VERTICALE : Si le mot dépasse de la grille en bas, on le décale vers le haut.
DIAGONALE (haut gauche - bas droite) : Si le mot dépasse de la grille à droite, on décale à gauche. Si le mot dépasse de la grille en bas, on décale vers le haut.
DIAGONALE (haut droite - bas gauche) : Si le mot sort de la grille à gauche, on décale à droite. Si le mot dépasse de la grille en bas, on décale vers le haut.
On regarde si le mot placé passe sur des cases déjà occupées et on construit une expression régulière. Par exemple dans l'image précédente contenant le mot
ROYAL. On veut dans la case 11 (contenant le Y), placer un mot horizontal de 4 caractères. Le pattern sera “Y…” .On tire un mot au hasard correspond à ce pattern.
Si on en trouve un, on l'ajoute à la liste des mots à chercher.
Et on recommence avec la case suivante jusqu'à ce qu'elles soient toutes parcourues.
Remarque :
lors de la boucle sur toutes les cases de la grille, on peut en sauter pour réduire le nombre de mots à trouver.
Éviter que des mots se superposant soient sélectionnés (par exemple : 'ENCRE', 'ENCREUR', 'ENCREURS', 'ENCREURS')
Complément : Palier 4 : Une fois le palier 3 franchi
après avoir terminé la grille, certaines lettres restent inutilisées : elles forment alors un mot mystère.
des grilles de différents formats, parfois simplement dans un but pratique, si le support l'exige (par exemple dans le cas des téléphones portables). Toutefois, certaines grilles peuvent revêtir des formes fantaisistes, au gré de l'imagination de leur créateur, à l'image de celle-ci :
