TP Noté de Programmation Fonctionnelle

Durée : 1h.

On s'intéresse aux grilles de mots-croisés. Chaque case dans une grille est repérée par ses coordonnées (i,j), où 1<=i<=M et 1<=j<=N et où M est le nombre de lignes et N, le nombre de colonnes de la grille. Voici un exemple de grille de mots croisés de taille 6x5 (à 6 lignes et 5 colonnes)

N
 O
 T
 E
 R
I
 ¤ A
 N
 E
V
 ¤ B
 A
 C
E
 ¤ L
 ¤
 U
A
 R
 E
 T
 E
U
 ¤ S
 A
 S


1.     Définir la fonction spell qui, étant donné un mot horizontal et les coordonnées de sa première lettre, retourne la liste des lettres de ce mot avec leurs coordonnées :

spell ((5,1),"SAC") = [((5,1),"S");((5,2),"A");((5,3),"C")]

On utilisera la fonction String.sub s start len, qui retourne la souschaine de s qui commence à la position start et de longeur len, et la fonction String.length s qui retourne la longueur de s.


2.     Définir la fonction scan_h qui, étant donnés les dimensions M et N d'une grille, retourne la liste de ses cases dans l'ordre de leur parcours. On choisit de parcourir les cases horizontalement.

scan_h (3,2) = [(1,1);(1,2);(2,1);(2,2);(3,1);(3,2)]


3.    Définir la fonction scan_v identique à la fonction scan_h de la question 2. excepté que l'on choisit de parcourir les cases verticalement.

scan_v (2,3) = [(1,1);(2,1);(1,2);(2,2);(1,3);(2,3)]

Il est imposé de se servir de la fonction scan_h et du schéma List.map en remarquant que le résultat de scan_v (2,3) est identique à celui de scan_h (3,2) excepté que les coordonnées à l'intérieur de chaque couple sont données dans le désordre ((j,i) au lieu de (i,j)).


Dans la suite, on appelle solution d'une grille de mots-croisés, la liste de ses mots horizontaux avec les coordonnées de leur première lettre. Par exemple :

let soluce =
  [((1,1),"NOTER");((2,1),"I");((2,3),"ANE");
   ((3,1),"V");((3,3),"BAC");((4,1),"E");
   ((4,3),"L");((4,5),"U");((5,1),"ARETE");
   ((6,1),"U");((6,3),"SAS")];;

est solution de la grille donnée en exemple.


4.     Définir la fonction letters qui étant donnée une solution de grille de mots-croisés retourne la liste de toutes les lettres de la grille avec leur coordonnées.

letters soluce =
  [((1,1),"N");((1,2),"O");((1,3),"T");((1,4),"E");((1,5),"R");
   ((2,1),"I");((2,3),"A");((2,4),"N");((2,5),"E");((3,1),"V");
   ((3,3),"B");((3,4),"A");((3,5),"C");((4,1),"E");((4,3),"L");
   ((4,5),"U");((5,1),"A");((5,2),"R");((5,3),"E");((5,4),"T");
   ((5,5),"E");((6,1),"U");((6,3),"S");((6,4),"A");((6,5),"S")]


5.     Définir la fonction size qui étant donnée une solution de grille de mots-croisés retourne les dimensions N et M de la grille.

size soluce = (6,5)