Nous apprenons à utiliser les modules Map et Set. Ce faisant, nous allons écrire un algorithme résolvant le problème du compte est bon, faisant parti du célèbre jeu télévisé Des chiffres et des lettres.

Question 1 : Modules sur les entiers

• Définir le module de type Set.OrderedType sur les entier :

  1. module Int :
     
  2. sig
     
  3. type t = int
     
  4. val compare : int -> int -> int
     
  5. end
     
• Utiliser le foncteur Map.Make pour obtenir un module des applications partielles (map) d'entiers IMap.
• Définir une fonction de comparaison sur les listes. On utilisera pour cela l'ordre total suivant : $[e_1;e_2;\ldots e_n] < [f_1;f_2;\ldots;f_p]$ si :
  • il existe $1 \leq i \leq n$ tel que $e_i < f_i$ et pour tout $1 \leq j < i$, $e_j = f_j$,
  • ou bien $p>n$ et $e_i = f_i$ pour tout $1 \leq i \leq n$.
• En déduire un module d'application partielle sur les listes d'entiers.

Question 2 : Un peu de combinatoire

• Nous allons avoir besoin d'énumérer toutes les sous-listes d'une liste d'entiers, et de faire des opérations dessus. Une sous-liste de $l$ est une liste d'éléments de $l$ apparaissant dans le même ordre (mais pas nécessairement consécutivement).

  1. (* exemple *)
     
  2. let sl = sublists [1;2;3;4];;
     
  3. val sl : int list list =
     
  4. [[]; [4]; [3]; [3; 4]; [2]; [2; 4]; [2; 3]; [2; 3; 4]; [1]; [1; 4];
     
  5. [1; 3]; [1; 3; 4]; [1; 2]; [1; 2; 4]; [1; 2; 3]; [1; 2; 3; 4]]
     

  Coder la fonction sublists correspondante, en utilisant une récurrence. On s'assurera que :

  1. les éléments apparaissent toujours dans le même ordre dans les sous-listes,
  2. la liste obtenu respecte l'ordre d'inclusion : si $l'$ est une sous-liste de $l''$, $l'$ apparait avant $l''$.
• Nous aurons aussi besoin d'énumérer les partitions d'une liste en deux sous-listes (une bipartition). On utilise à nouveau une définition récursive. Toute bipartition d'une liste non-vide s'obtient en ajoutant la tête à une des deux parties d'une bipartition de la queue.

  1. let bp = bipartitions [1;2;3;4];;
     
  2. val bp : (int list * int list) list =
     
  3. [([1; 2; 3; 4], []); ([2; 3; 4], [1]); ([1; 3; 4], [2]); ([3; 4], [1; 2]);
     
  4. ([1; 2; 4], [3]); ([2; 4], [1; 3]); ([1; 4], [2; 3]); ([4], [1; 2; 3]);
     
  5. ([1; 2; 3], [4]); ([2; 3], [1; 4]); ([1; 3], [2; 4]); ([3], [1; 2; 4]);
     
  6. ([1; 2], [3; 4]); ([2], [1; 3; 4]); ([1], [2; 3; 4]); ([], [1; 2; 3; 4])]
     

  Coder la fonction bipartitions.

• Enfin, nous utiliserons une fonction qui prend deux applications partielles $f$ et $g$ sur les entiers, et énumère toutes les paires $(f(i),g(j))$ pour $i$ et $j$ tels que $f(i)$ et $g(j)$ soient définies. Vous utiliserez deux IMap.fold imbriqués.

Question 3 : Opérateurs

Dans le jeu le compte est bon, seules quatre opérations arithmétiques sont autorisés : addition, soustraction, produit et division entière exacte (on ne peut diviser que si le reste est $0$). De plus, les résultats négatifs ou nuls sont interdits.

On définit le type algébrique :

• Donner une fonction qui à chaque opérateur, associe la fonction arithmétique qui lui correspond.
• Donner une fonction qui à chaque opérateur lui associe son score entier : 20 pour l'addition, 40 pour la soustraction, 50 pour la multiplication et 100 pour la division.

Question 4 : Expressions arithmétiques

• Une expression arithmétique est soit un litéral entier, soit un opérateur appliqué à deux autres expressions arithmétiques. Définir le type des expressions arithmétiques expr.
• Donner une fonction eval qui calcule la valeur d'une expression arithmétique.
• Donner une fonction score calculant le score d'une expression arithmétique : le score d'une expression est la somme des valeurs de ses litéraux et des scores des opérateurs qui la composent. Ainsi plus une expressions est complexe, plus son score sera élevé.
• Donner une fonction valid_combination op a b qui prend un opérateur op et deux expressions arithmétiques, et qui décide si cet opérateur peut être appliqué à $a$ et $b$. Il s'agit par exemple de vérifier que les divisions sont entières ou que les soustractions donnent des valeurs positives.

  1. # valid_combination Div (Literal 12) (Literal 5);;
     
  2. - : bool = false
     
• En déduire une fonction qui prenant deux expressions, calcule toutes les expressions valides pouvant être construites à partir de ces deux expressions en utilisant un opérateur.

  1. val combine : expr -> expr -> expr list = <fun>
     

Question 5 : Écriture d'une expression arithmétique

• Écrire une fonction qui associe à chaque opérateur une chaine de caractère représentant l'opérateur en question.
• Écrire une fonction transformant une expression arithmétique en chaine de caractères, par exemple "100 * 10 - (10 - 1) * 9 * 4". Attention aux parenthèses !

Question 6 : Ajout d'une expression à un ensemble de solutions.

À chaque liste $l$ d'entiers, on associe une application partielle (de type expr IMap.t), qui associe à chaque entier $n$ de son domaine une expression arithmétique de valeur $n$ utilisant seulement les litéraux de $l$. Nous allons avoir besoin d'une fonction qui ajoute une expression arithmétique à une telle application partielle. Écrire la fonction expr_imap_add expr map qui prend une expression arithmétique et une map, et qui ajoute expr dans map à l'indice eval e si cet indice n'existe pas encore, ou sinon, si l'expression arithmétique déjà associé à cet indice a un score plus élevé que e.

Question 7 : Résolution générale, version naïve.

Le principe de l'algorithme est le suivant. Étant donné une liste d'entiers $l$ avec au moins 2 éléments (sinon c'est facile), on calcule toutes les bipartitions de cette liste. Pour chaque bipartition, on calcule récursivement les solutions pour les deux parties (on obtient deux maps), puis en utilisant all_pairs et combine, on génère toutes les expressions arithmétiques pour cette bipartition. Chaque expression pour chaque bipartition est ajoutée avec expr_imap_add à une application partielle codant la solution pour $l$.

Écrire l'algorithme correspondant. Le tester.

La suite du TP est optionnelle.

Un peu de théorie.

Examiner le code suivant.

On définit avec fib0 la suite de Fibonacci, en prenant en argument la fonction à appeler récursivement. Nous n'avons rien perdu, puisqu'il suffit de dire que l'appel récursif doit utiliser fib0 pour retrouver la version naïve standard, ce qui est fait dans un deuxième temps avec fib_naive.

Nous savons aussi par les cours sur la programmation dynamique que tout va plus vite si on calcule la suite en partant des petites valeurs, d'abord $0$, puis $1$, $2$, … jusqu'à $n$. Je définis donc :

pour ensuite calculer la suite dans le bon sens :

Je calcule les valeurs de ma suite et les stocke dans map, dans le bon sens. Du coup, pour l'appel récursif, il me suffit de consulter les valeurs déjà calculées.

Plus généralement, je peux donner le foncteur suivant:

Le foncteur prend un module de type Map.S qui permet de stocker les solutions calculées de chaque instance. La fonction memoize prend en premier argument la liste des valeurs à calculer, dans l'ordre adéquat pour la programmation dynamique. Son second argument est la fonction calculant une étape d'induction, telle que fib0, cette fonction doit prendre en argument la fonction pour les appels récursifs. Enfin elle prend l'instance que l'on cherche à résoudre (un entier $n$ pour Fibonacci, pour lequel on veut calculer $F(n)$).

Reprendre et comprendre ce code. Utiliser le foncteur pour écrire Fibonacci.

Question 8 : Résolution générale, version programmation dynamique

Utiliser le foncteur DynamicProg pour améliorer l'algorithme de résolution du compte est bon.

Question 9 : Générer une instance aléatoirement

Une instance est composée d'un objectif et de six entiers choisis parmi la liste

$$[ 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 25; 50; 75; 100]$$

L'objectif est un entier entre 100 et 999 , tiré uniformément aléatoirement.

Utiliser le module Random pour générer des instances aléatoires.

Question 10 : Conclure et compiler

Ajouter le code suivant (en renommant les variables libres au besoin) :

Compiler, en ajoutant <nom_du_fichier.{byte,native}>: use_unix dans le fichier _tags.

Vous pouvez ensuite tenter d'améliorer le programme. Par exemple :

• réduire au minimum nécessaire le nombre de parenthèses affichées lors de l'écriture d'une expression arithmétique,
• réduire le nombre d'expressions arithmétiques calculées, en supprimant certaines symmétrie, comme $a + b = b + a$ ou $a + (b + c) = (a + b) + c$.