OCaml de pied en cap

Un article de Cacophrene    4 Commentaires

Bonjour !

Rien de tel que de commencer la nouvelle année par un jeu. Nous allons donc essayer d’implémenter en OCaml une version proche du jeu Le Compte est bon imaginé par Armand Jammot (dans l’émission Des chiffres et des lettres que regarde votre grand-mère).

Pour ce que ce soit plus pratique, nous allons changer un peu les règles du jeu :

• Le but du jeu est de calculer un nombre N compris entre 100 et 1000.
• On dispose pour cela de 6 entiers choisis dans l’intervalle [1; 100].
• Le choix des nombres est aléatoire et il n’y a pas de doublons.
• Les entiers sont combinés entre eux à l’aide des opérations +, -, * et /.

Contrairement aux candidats du jeu télévisé, l’ordinateur devra trouver toutes les solutions. Nous souhaitons obtenir cette réponse en une seconde au plus sur un ordinateur récent (en natif, bien entendu).

Mais au fait…

Avant de commencer, je ne peux m’empêcher de vous proposer une question préliminaire pour évaluer la faisabilité de ce programme : combien de cas l’ordinateur doit-il analyser ? Je ne donne pas la réponse tout de suite, mais voici tout de même un indice : pour n = 6, cas qui nous intéresse ici, il faut examiner plus de 700 000 expressions.

Définition d’une expression

Pour pouvoir travailler efficacement, nous devons d’abord définir un type capable de représenter une expression mathématique de la forme (((a + b) - c) * d) / e. Il s’agit tout simplement d’une sorte d’arbre binaire dont les feuilles sont des entiers :

type expr =
  | Num of int              (* Entier.      *)
  | Add of expr * expr      (* Somme.       *)
  | Rem of expr * expr      (* Différence.  *)
  | Mul of expr * expr      (* Produit.     *)
  | Div of expr * expr      (* Quotient.    *)

Par commodité, et parce que les constructeurs d’OCaml ne sont pas des fonctions (il y a, je crois, des extensions camlp4 pour obtenir quelque chose dans ce genre), nous allons nous simplifier la vie en définissant dès maintenant les quatre fonctions auxiliaires suivantes :

let add x y = Add (x, y)
let rem x y = Rem (x, y)
let mul x y = Mul (x, y)
let div x y = Div (x, y)

Pour finir, il nous faut une fonction capable de convertir une expression en chaîne de caractères en vue de son affichage. La méthode retenue ici ajoute quelques parenthèses superflues, mais elle a le double mérite d’être simple.

let to_string =
  let rec loop lbr rbr = function
    | Num x -> string_of_int x
    | Add (x, y) -> sprintf "%s%s + %s%s" lbr (inner x) (inner y) rbr
    | Rem (x, y) -> sprintf "%s%s - %s%s" lbr (inner x) (inner y) rbr
    | Mul (x, y) -> sprintf "%s%s * %s%s" lbr (inner x) (inner y) rbr
    | Div (x, y) -> sprintf "%s%s / %s%s" lbr (inner x) (inner y) rbr
  and inner expr = loop "(" ")" expr in loop "" ""

Quelques ensembles utiles

Intéressons-nous maintenant aux données que nous allons manipuler. L’énoncé précise que nous disposons de six entiers uniques choisis au hasard. Dans le cas qui nous intéresse, les ensembles (module Set) sont particulièrement bien adaptés. Définissons donc :

module NSet = Set.Make (
  struct
    type t = int
    let compare = compare
  end
)

Il nous faut aussi de quoi stocker l’ensemble des solutions. Comme nous allons seulement les afficher, nous pouvons définir un ensemble de chaînes (mais on peut aussi envisager de stocker un ensemble d’expressions en vue de traitements ultérieurs) :

module SSet = Set.Make(String)

Fonctions auxiliaires

Écrivons maintenant une fonction qui renvoie un ensemble constitué de six entiers choisis au hasard dans l’intervalle [1; 100]. L’initialisation du générateur de nombres pseudo-aléatoires est contrôlée par un paramètre facultatif, et désactivée par défaut :

let get_numbers ?(init = false) () =
  if init then Random.self_init ();
  let rec loop set = function
    | 0 -> set
    | i -> let n = Random.int 100 + 1 in
      if NSet.mem n set then loop set i
      else loop (NSet.add n set) (i - 1)
  in loop NSet.empty 6

L’algorithme

Définissons d’abord deux listes auxiliaires qui vont nous être fort utile par la suite :

let functions = [add; rem; mul; div]
let operators = [( + ); ( - ); ( * ); ( / )]

À partir de là, il faut réfléchir un peu. L’algorithme d’exploration exhaustive fonctionne de la manière suivante (je donne le noms des variables utilisées en gras dans le texte pour faciliter la compréhension du code donné ultérieurement) :

• Choisir un entier (y) et poursuivre l’exploration avec les 4 opérations de base (opr), en retirant cet entier de l’ensemble des entiers disponibles (num).
• À chaque niveau, comparer le résultat intermédiaire x avec le nombre recherché res. En effet, une expression valide (acc) ne contient pas nécessairement les 6 entiers… elle peut être plus simple !

Il existe plusieurs manières d’écrire ceci en OCaml. Je vous propose une version qui utilise des fonctions d’ordre supérieur de type fold, et qui traite séparément le cas où l’ensemble d’entiers est vide. Il s’agit d’une optimisation qui fait passer le temps d’exécution de 0,2 s à 0,1 s en natif car elle évite de manipuler des fermetures inutilement.

let rec explore res x acc num str =
  let str' = if res = x then SSet.add (to_string acc) str else str in
  if NSet.is_empty num then set' else (
    List.fold_left2 (fun str fct opr ->
      NSet.fold (fun y str ->
        explore res (opr x y) (fct acc (Num y)) (NSet.remove y num) str
      ) num str
    ) str' functions operators
  )

Il ne nous reste plus qu’à écrire une fonction find qui reçoit en entrée le nombre à calculer (res) et l’ensemble des entiers disponibles (num). Elle permet d’appeler explore en lui fournissant des valeurs initiales :

let find res num =
  NSet.fold (fun x -> 
    explore res x (Num x) (NSet.remove x num)
  ) num SSet.empty

Quelques exemples d’application

Contrairement à ce que je pensais avant de coder ce jeu, les solutions sont souvent nombreuses. Par exemple, si vous lancez ce code avec res = 162 et l’ensemble {10; 22; 36; 43; 73; 94}, vous verrez qu’il existe la bagatelle de 854 solutions ! Au contraire, certains tirages ne donnent que très peu de solutions. Voici un exemple de sortie avec peu de solutions :

> Calculer 431 avec les valeurs 34 37 57 58 66 82 
Temps d'exécution : 0.126 s (737280 cas, 4 solutions)
((((37 / 34) + 66) - 58) * 57) - 82
((((37 / 34) - 58) + 66) * 57) - 82
((((66 - 57) * 34) * 82) - 37) / 58
((((66 - 57) * 82) * 34) - 37) / 58

Et la devinette ?

Eh bien, c’est simple. Vous disposez de n entiers à combiner avec 4 opérations. Vous pouvez donc construire un total de n! * 4 ^ (n – 1) expressions (sans tenir compte de la commutativité et des expressions de moins de 6 chiffres).

Le mot de la fin

J’ai dit plus haut que ce code s’exécute en un dixème de seconde environ sur une machine récente. La méthode exhaustive est donc acceptable… mais ça n’a pas toujours été le cas. Ainsi, lors de la création du jeu, aucune implémentation efficace n’était disponible et la recherche d’une solution reposait sur le talent des animateurs (au contraire, le jeu intitulé Le mot le plus long, dans cette même émission, possédait déjà une version informatique efficace). Je reste d’ailleurs toujours admiratif devant l’agilité de certaines personnes à trouver les bonnes combinaisons de nombres et d’opérations, quand je peine à venir à bout d’une multiplication toute bête

Pour aller plus loin…

Il y a de très nombreuses manières de faire évoluer ce code :

• Ajouter la notion de commutativité pour éviter les solutions redondantes.
• Classer les solutions (courtes vs longues, etc.).
• Abstraire le code pour pouvoir utiliser d’autres types que int.

Pour finir, voici le code complet (libre de droits, cela va sans dire) qui a servi de base à la rédaction de ce billet.

À bientôt,
Cacophrène