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 entiers :

  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 (comme pour le produit cartésien de listes).

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 (peu importe pour l'instant si la division n'est pas exacte, ou si l'opération retourne un entier négatif).
• 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". Utiliser ^ pour concaténer des chaînes de caractères. Attention aux parenthèses ! (dans un premier temps, vous pouvez mettre autant de parenthèses que vous le souhaitez, ensuite si vous avez le temps vous pourrez revenir sur cette question.)

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

Pour une liste $l$ d'entiers, nous allons calculer pour tout entier $u$ s'il existe une expression $\text{expr}_u$ arithmétique utilisant $l$ comme litéraux, et s'évaluant en $u$. Nous allons stocké toutes ces expressions dans une application partielle, associant $\text{expr}_u$ à l'entier $u$, dès qu'une telle expression existe. Avant de voir comment faire cela, nous allons juste écrire une fonction ajoutant un lien $(u,\text{expr}_u)$ dans notre stock.

Pour cela, on écrit la fonction suivante, qui considère une expression arithmétique, et l'ajoute dans l'application partielle. Comme il peut y avoir une expression de même valeur déjà stockée, on vérifiera si c'est le cas, et si oui on gardera seulement l'expression de plus petit score.

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

Nous voulons maintenant tester toutes les expressions possibles avec une liste $l$. Nous procédons par induction sur la longueur de la liste.

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.

Question 8 : Mémoïsation

Lorsque nous prenons les sous-listes des sous-listes, nous retombons plusieurs fois sur les mêmes listes. Notre calcul n'est donc pas efficace puisque nous recalculons les solutions pour chaque sous-liste plusieurs fois.

Examinons le code suivant.

Il s'agit d'une version mémoïsée de la fonction de Fibonacci. Puisqu'on ne dispose pas de mémoire à proprement parler, on garde une table d'association entre les entiers et leurs images par Fibonacci en argument de la fonction. Dès qu'on calcule une nouvelle valeur, on l'ajoute dans la table.

Nous pouvons faire la même chose avec les sous-listes. Ajouter en argument une map sur les sous-listes, qui associe à chaque sous-liste une map des entiers vers les expressions arithmétiques construites sur cette sous-liste.

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.

À vous de jouer.

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étries, comme $a + b = b + a$ ou $a + (b + c) = (a + b) + c$.
• écrire dans un fichier toutes les solutions atteignables par une liste.
• afficher un problème, attendre 30 secondes et afficher la solution.