(* == Exo 1 *)

(* -- Q.1 (3 pts) *)

(* Hypothese: n et p sont positifs et p <= n *)
let rec c n p =
  if (p = 0 ) || (p = n) then 1
  else (c n (p - 1)) + (c (n - 1) (p - 1))

(* -- Q.2 (3 pts) *)
(* Deux cas sont a considerer:
    - p > n
    - n < 0 ou p < 0

   ce qui donne la version defensive suivante: *)
let c n p =
  let rec loop n p =
    if (p = 0 ) || (p = n) then 1
    else (loop n (p - 1)) + (loop (n - 1) (p - 1))
  in
    if (p > n) || (p < 0) || (n < 0) then
      invalid_arg "c"
    else
      loop n p



(* == Exo 2 *)

(* -- Q. 1 (2 pts) *)
let rec all_assoc k kvs =
  match kvs with
      [] -> []
    | (k',v)::kvs' ->
	if (k = k') then v::(all_assoc k kvs')
	else (all_assoc k kvs)

(* -- Q. 2 (5 pts) *)
let rec add_assoc k v kvs =
  match kvs with
      [] -> [(k,v)]
    | (k',v')::kvs' ->
	if (k = k') then
	  (k,v)::kvs'
	else
	  (k',v')::(add_assoc k v kvs')

(* == Exo 3 *)

(* -- Q. 1 (2 pts) *)
let rec sorted_list ns =
  match ns with
      n1::n2::ns' -> (n1 <= n2) && (sorted_list (n2::ns))
    | _ -> true

(* -- Q. 2 (4 pts) *)
(* Version "optimale": on sort de la boucle si l'on trouve 
   deux elements non ordonnes. *)
let sorted_array ns =
  let r = ref true in
  let i = ref 0 in
    while !r && (!i < (Array.length ns) -1) do
      r := ns.(!i) <= ns.(!i+1);
      incr i
    done;
    !r && (!i >= (Array.length ns) - 1)

(* Version "brute force": on va jusqu'au bout du tableau.
 Noter:
   - la conjonction dans la boucle pour "accumuler" le resultat;
   - la borne finale du "for". *)
let sorted_array ns =
  let r = ref true in
    for i = 0 to (Array.length ns) - 2 do
      r := !r && ns.(i) <= ns.(i+1)
    done;
    !r

(* Version recursive: gourmande en memoire car cree un nouveau 
   (sous) tableau a chaque iteration. DECONSEILLEE *)
let rec sorted_array ns =
  let len = Array.length ns in
    if len < 2 then true
    else (ns.(0) <= ns.(1)) && sorted_array (Array.sub ns 1 (len - 1))

(* Version "maligne" mais un peu gourmande en memoire. 
   NB: je n'y avais pas songer: bravo a celles et ceux
   qui ont ainsi gagne facilement des points :*)
let sorted_array ns =
  sorted_list (Array.to_list ns)

(* -- Q. 3 (des points en plus...) *)
(* Telle quelle la question n'avait pas de reponse car
   [(4,5); (3,7)] est ordonnee pour l'ordre (n+m) < (n'+m')
   mais ne peux pas l'etre pour l'ordre n < m < n' < m' *)
exception Not_sorted

(* La reponse "attendue" etait celle-ci: *)
let rec resort nms =  
  match nms with 
      (n,m)::(n',m')::nms' ->
	if (n+m) < (n'+m') then
	  if (n < m) then (n,m)::(resort (n',m')::nms')
	  else (m,n)::(resort (n',m')::nms')
	else
	  raise Not_sorted
    | _ -> nms

(* Avec le "patch" de derniere minute: declencher l'exception
   Not_resortable si la liste n'etait pas ordonnable pour le
   deuxieme ordre, on pouvait repondre: *)
exception Not_sortable

let rec resort nms =  
  match nms with 
      (n,m)::(n',m')::nms' ->
	if (min n' m') < (max n m) then
	  raise Not_resortable
	else
	  if (n+m) < (n'+m') then
	    if (n < m) then (n,m)::(resort (n',m')::nms')
	    else (m,n)::(resort (n',m')::nms')
	  else
	    raise Not_sorted
    | [(n,m)] -> [(min n m), (max n m)]
    | [] -> []

(* MERCI ET FELICITATIONS A TOUTES CELLES ET A TOUT CEUX QUI ONT 
   PRIS LA PEINE DE REPONDRE A CETTE QUESTION *)