(*
    Programme qui résous le jeu des "chiffres" dans
    "Des chiffres et des letres".
    (C) Mathias Kende, 2006
    Distribué sous licence CeCIlL-B :
    http://www.cecill.info/licences/Licence_CeCILL-B_V1-fr.txt 
*)

type op = ADD | SOU | MUL | DIV | IDIV | ISOU
type oper = int * int * op
type etat = int * int list * oper list

let rec fold_pair f o = function
      a::s -> fold_pair f (List.fold_left (f a) o  s) s
    | [] -> o

let meilleur o = function
      [] -> failwith "impossible"
    | a::s -> let rec f b c = if abs(b-o) < abs(c-o) then b else c in List.fold_left f a s

let dist (o,l1,_:etat) = abs (o - meilleur o l1)

let ordre ((_,_,v1:etat) as a) ((_,_,v2:etat) as b) = (* 1 < 2 *)
    let da = dist a and db = dist b in
    da < db || (da = db && List.length v1 < List.length v2)

let rec remove a = function
      b::c when b=a -> c
    | b::c -> b::(remove a c)
    | [] -> []

let oper a b = function
      ADD -> a + b
    | SOU -> a - b
    | MUL -> a * b
    | DIV -> a / b
    | IDIV -> b / a
    | ISOU -> b - a

let rec cherche ((o,l,v) as e:etat) =
    let f a e b = 
        let h e op = 
                let (e2:etat) = (o, (oper a b op)::(remove a (remove b l)),(a,b,op)::v) in
                let e3 = cherche e2 in
                let e4 = if ordre e3 e2 then e3 else e2 in
                if ordre e4 e then e4 else e
        in
        let g e = function
              ADD | MUL | SOU | ISOU as o -> h e o
            | DIV -> if b <> 0 && a mod b = 0 then h e DIV else e
            | IDIV -> if a <> 0 && b mod a = 0 then h e IDIV else e
        in
        List.fold_left g e [ADD;SOU;MUL;DIV;ISOU;IDIV]
    in
    fold_pair f e l

let print ((_,_,v:etat) as e) =
    let print_op (a,b,o:oper) = let a,b,c = match o with
          ADD -> a,b,'+'
        | SOU -> a,b,'-'
        | MUL -> a,b,'*'
        | DIV -> a,b,'/' 
        | IDIV -> b,a,'/' 
        | ISOU -> b,a,'-' in Printf.printf "%d %c %d = %d\n" a c b (oper a b o) in
    List.iter print_op (List.rev v);
    Printf.printf "%s" (if dist e = 0 then "Le compte est bon !\n" else "Le compte n'est pas bon !\n")

let main =
    Printf.printf "Quel est le resultat auquel il faut arriver ? ";
    flush_all ();
    let r = Scanf.scanf "%d\n" (fun r -> r) in
    Printf.printf "Entrez les chiffres, un par lignes, en terminant par un 0.\n";
    flush_all ();
    let l = let rec f = function 0 -> [] | v -> v::(g f) and g f = Scanf.scanf "%d\n" f in g f in
    print (cherche (r,l,[]))