Ce TP nous permet de revoir la plupart des fonctionnalités que nous avons vu tout au long du cours : fonctionnelles, types algébriques et paramétrés, foncteurs, listes, etc. Le but est d'écrire un solveur pour le jeu "le compte est bon" . Dans ce jeu, plusieurs entiers sont donnés, qui doivent être combinés à l'aide des opérateurs arithmétiques, afin d'atteindre un objectif entier. Par exemple, si l'objectif est 643 et les entiers disponibles sont 3,3,5,8,10,2 5 , une solution est $(10 \times 8 \times (3 + 5)) + 3$.

Dictionnaires d'entiers, de listes.

Définissez le module de type Set.OrderedType sur les entiers. En déduire le module d'un dictionnaire d'entier.

Définissez le module de type Set.OrderedType sur les listes d'entiers. En déduire un module de dictionnaire de listes d'entiers.

Combinatoires de listes.

Vous pouvez utiliser Base.List pour avoir accès à plus de fonctions sur les listes (documentation).

Programmez une fonction qui énumère toutes les sous-listes d'une liste (utilisez (>>=) sur les listes) :

Ajoutez une fonction énumérant toutes les bipartitions d'une liste :

Expressions arithmétiques.

Dans le jeu le compte est bon, seules quatre opérations arithmétiques sont autorisées : 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 :

Donnez une fonction qui à chaque opérateur, associe la fonction arithmétique qui lui correspond. La fonction retourne une option, afin de gérer les cas non-valides (résultat négatif ou non-entier).

Donnez 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. Le score sera utilisée pour évaluer la simplicité d'une expression: plus un score est faible, plus l'expression est simple.

Mettez le tout dans un module, dont voici l'interface.

Utilisez Operator.t pour définir le type des expressions arithmétiques, avec des litéraux entiers et des opérateurs arithmétiques binaires.

Ajoutez une fonction d'évaluation pour obtenir la valeur entière d'une expression arithmétique. Le résultat est une option puisque l'expression peut-être mal-définie (division non-entière, division par zéro, résultat négatif).

Créez un prédicat déterminant si une expression est valide.

La valeur d'une expression est la somme des scores de ces opérateurs, plus la somme de ces litéraux. Définissez une fonction calculant le score d'une expression.

Définissez une fonction qui étant donnée deux expressions, calcule la liste des expressions formable avec ces deux expressions plus un opérateur.

Ajoutez une fonction de formattage pour les expressions arithmétiques (Reprenez les exemples des TP précédents).

Vous obtiendrez le module (faites-en un fichier expr.ml) :

Résolution.

Le principe de l'algorithme de résolution est le suivant :

• on génère toutes les bipartitions de la liste d'entiers,
• pour chaque bipartition, on génère récursivement toutes les valeurs constructibles avec les entiers de chacune des deux parties,
• on teste toutes les combinaisons d'une valeur de la partie droite avec une valeur de la partie gauche,
• on garde pour chaque valeur obtenue celle de plus petit score.

Les solutions seront stockées dans un dictionnaire d'entier : à $n$ on associe la combinaison de plus faible score permettant d'atteindre $n$. Pour toujours garder la combinaison de plus faible score, nous modifions la fonction d'insertion : on ajoute une combinaison que si son score est meilleure (plus petit) que la combinaison précédemment trouvée.

Donnez donc la fonction d'insertion d'une expression dans le dictionnaire :

Définissez une fonction récursive qui, à une liste d'entiers, construit le dictionnaire qui à chaque objectif entier associe l'expression de plus petit score utilisant tous les entiers de la liste.

Cette version n'est pas très efficace, car on recalcule sans cesse les mêmes sous-listes de la liste initiale. Pour cela, il faut utiliser la programmation dynamique. Il faut garder pour chaque sous-liste possible le dictionnaire de ces solutions. Autrement dit, il faut mémoïser la fonction de résolution. Puisque les instances sont des listes d'entiers, il faut un dictionnaire de liste d'entiers pour stocker les solutions. Créez donc la version mémoïsée :

Si la liste est déjà dans la mémoire, on retourne la solution déjà connue, sinon on la calcule et on l'ajoute à la mémoire.

Génération aléatoire d'instances.

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.

Définissez une fonction pour choisir uniformément $k$ éléments dans une liste de $n$ éléments (quelle est la probabilité d'avoir le premier élément dans cette liste ?).

Ajoutez ensuite une fonction générant aléatoirement des instances du compte est bon.

À vous de jouer...

• Le solveur actuel utilise tous les entiers de la liste. Le jeu autorise à n'utiliser qu'une partie des entiers. Comment modifier le solveur pour cela ?
• Définissez une fonction permettant de lire une expression arithmétique.
• Créez une interface interactive en ligne de commande pour pouvoir jouer au jeu.
• Dans la résolution, on considère souvent des expressions équivalentes, comme $a+b$ et $b+a$. Ajoutez des tests pour éviter le plus possible de tester des cas symétriques.