Le compte est bon

Des jeux comme Le compte est bon ou son équivalent anglais countdown ont pour objectif de trouver,
à partir d une liste d entiers et d un entier cible, une expression construite avec cette liste et qui soit égale à l'entier cible.

Utilisation : Ici

(à gauche l'entier cherché, à droite ceux à disposition séparés par un espace)

Les contraintes sont :

• seules les opérations d'addition, de soustraction, de multiplication et de division, ainsi que les parenthèses.
• Toutes les valeurs y compris celles intermédiaires doivent être positives.
• L'utilisation de fractions non égales a un entier sont interdites, par exemple 10/5 est autorisée, mais 2/3 ne l'est pas .

Définition d'une expression arithmétique.

Un type similaire mais plus complexe a été évoqué Ici.

Pour l'usage actuel ce type peut être simplifié

type Expr = Val Int
            |App Op Expr Expr

type Op = 
    Add
    |Sub  
    |Mul 
    |Div2

// Définition des opérations

apply2 : Op -> Int -> Int ->Int
apply2 e x y = 
    case e of 
        Add     ->  x + y 
        Sub     ->  x - y
        Mul     ->  x * y 
        Div2    ->  x//y

---

Spécification des contraintes et simplification

• L'addition et la multiplication sont commutatives (a+b = b+a , et de même ab = ba)
• L'élément neutre de l'addition est 0, celui de la multiplication est 1. (a+0 = 0+a = a, et de même a1 = 1 a = a)

valid : Bin -> Int -> Int ->Bool
valid e x0 y0 = 
    case (e,x0,y0) of 
        (Plus,x,y)  -> x<=y
        (Moins,x,y) ->(x > y)
        (Fois,x,y)  -> (x /= 1 && y/=1 && x<=y)
        (Div,x,y)   -> (y/=1 && modBy y x ==0)

Selon ces règles on va établir toutes les expressions possibles puis parmi elles filtrer celles égales au nombre demandé initialement.

---

Astuces

Pour générer toutes les combinaisons d'expressions possibles il a fallu utiliser des éléments de combinatoire, disponibles ici

---

Indications concernant les paramètres d'entrée

Il y a deux paramètres X et L , lesquels vont recevoir une chaîne de caractère représentant respectivement : un entier et une liste d'entiers.

Pour le premier il faut récupérer l'entier si c'est possible.

toInt2 : String -> Result String Int 
toInt2 str = Result.fromMaybe "nope" (String.toInt str)

Pour le second il faut récupérer la liste d'entiers si c'est possible.
En utilisant les Applicatives et plus particulièrement sequence.

Pour rappel, sequence sur Maybe transforme une List Maybe a en Maybe List a.

Utilisation :

toListe  : String -> Result String (List Int)
toListe str = 
    let 
        l : List String
        l = String.split " " str 
        li : List (Maybe Int)
        li  = List.map(\elt -> String.toInt elt) l 
        lm : Maybe (List Int)
        lm = sequenceM li
    in Result.fromMaybe "Nope" lm