(** {C MIAS 24: Devoir sur table du 26 Nov. 2003

 {i Pages engendrées avec l'outil {e ocamldoc}}} *)

(** {1 Exo. I} *)

(** {b Quest. I.1} *)
(** valeur approchée du nombre pi *)
let pi = ((4. *. atan(1. /. 5.)) -. atan(1. /. 239.)) *. 4. 

(** {b  Quest I.2} *)
(** 
  [(cart_of_pol d t)] renvoie les coordonnées cartésiennes
  corespondant aux coordonnées polaires d'angle [t] et de
  mesure [d].
*)
let cart_of_pol d t =
  let x = d *. cos(t) and y = d *. sin(t) in
    (x, y)

(** {b Quest I.3}: voir ci-dessus {!Cdst.cart_of_pol} *)

(** {b Quest I.4} *)
(**
  [spirale()] écrit sur la sortie standard les coordonnées
  cartésiennes des points d'une spirale d'Archimède donnés
  par la suite de coordonnées polaire d'angle variant de 0 à
  13[pi]/2 avaec un pas de [pi]/60
*)
let spirale () =
  let step =  pi /. 60. in
  let fin = ((13. *. pi) /. 2.) /. step in
  let t = ref 0. in
    while !t < fin do
      let (x, y) = cart_of_pol !t !t in
	Printf.printf"(%f, %f)" x y;
	t := !t +. step
    done

(**
  {i Variante:} utilise une boucle [for]
*)
let spirale_a () =
  let step = pi /. 60. in
  let fin = truncate (((13. *. pi) /. 2.) /. step) in
  let t = ref 0. in
    for i = 0 to fin do
      let (x, y) = cart_of_pol !t !t in
	Printf.printf"(%f, %f)" x y;
	t := !t +. step
    done

(** {1 Exo. II} *)

(** {b Quest II.1} *)
(** 
  [(add_elt e s)] ajoute l'élément [e] à la liste [s] 
  s'il n'y figure pas déjà.
*)
let rec add_elt e s =
  match s with
      [] -> [e]
    | e'::s' ->
	if (e = e') then s'
	else e'::(add_elt e s')
(** Jeu de tests pour [add_elt]

[let s = (add_elt 1 []);;]

[let s = (add_elt 1 s);;]

[let s = (add_elt 2 s);;]

[let s = (add_elt 3 s);;]

[let s = (add_elt 3 s);;]

[let s = (add_elt 2 s);;]

[let s = (add_elt 1 s);;]
*)

(** {i Variante:} utilise [List.mem] *)
let add_elt_a e s =
  if (List.mem) e s then s
  else (e::s)


(** {b Quest II.2} *)
(** 
  [set_of_list xs] renvoie l'ensemble (i.e. liste sans redondance)
  des éléments de [xs]
*)
let rec set_of_list xs =
  match xs with
      [] -> []
    | x::xs' ->
	if (List.mem x xs) then (set_of_list xs')
	else x::(set_of_list xs')
(** Jeu de tests pour [set_of_list] 

  [let s = (set_of_list []);;]  

  [let s = (set_of_list [1;2;3]);;] 

  [let s = (set_of_list [1;1;2;3]);;] 

  [let s = (set_of_list [1;2;3;1]);;] 

  [let s = (set_of_list [1;2;2;3]);;] 

  [let s = (set_of_list [1;2;3;2]);;] 

  [let s = (set_of_list [3;1;2;3]);;] 

  [let s = (set_of_list [1;3;2;3]);;] 
*)

(** {i Variante:} utilise {!Cdst.add_elt} (Quest II.1) *)
let rec set_of_list_a xs =
  match xs with
      [] -> []
    | x::xs' -> (add_elt x (set_of_list_a xs'))

(** {i Variante:} fonction locale récursive terminale *)
let set_of_list_b xs =
  let rec loop xs s =
    match xs with
	[] -> s
      | x::xs' -> (loop xs' (add_elt x s))
  in
    loop xs []

(** {i Variante:} utilise l'itérateur [ List.fold_left] *)
let set_of_list_c xs =
  List.fold_left (fun s e -> add_elt e s) [] xs

(** {b Quest II.3} *)
(**
  [(union s1 s2)] revoie l'union des ensembles [s1] et [s2] *)
let rec union s1 s2 =
  match s1 with
      [] -> s2
    | e::s1' -> (add_elt e (union s1' s2))
(** Jeu de tests pour [union]

[(union [] [])]

[(union [] [1;2;3])]

[(union [1;2;3] [])]

[(union [1;2;3] [1;2;3])]

[(union [1;2;3] [2;4;6])]

[(union [1;3;5] [2;4;6])]
*)

(** {i Variante:} récursive terminale; utilise [s2] comme
  accumaulatuer
*)
let rec union_a s1 s2 =
  match s1 with
      [] -> s2
    | e::s1' -> (union s1' (add_elt e s2))

(** {i Variante:} utilise l'itérateur [List.fold_left] *)
let union_b s1 s2 =
  List.fold_left (fun s e -> add_elt e s) s2 s1

(**
  [(inter s1 s2)] renvoie l'intersection des ensembles [s1] et [s2] 
*)
let rec inter s1 s2 =
  match s1 with 
      [] -> []
    | e::s1' ->
	if (List.mem e s2) then (e::(inter s1' s2))
	else (inter s1' s2)
(** Jeu de tests pour [inter]

[(inter [] [])]

[(inter [] [1;2;3])]

[(inter [1;2;3] [])]

[(inter [1;2;3] [1;2;3])]

[(inter [1;2;3] [2;4;6])]

[(inter [1;3;5] [2;4;6])]
*)

(** {i Variante:} fonction locale récursive terminale. *)
let inter_a s1 s2 =
  let rec loop s1 s =
    match s1 with
	[] -> s
      | e::s1' ->
	  if (List.mem e s2) then (loop s1' (e::s))
	  else (loop s1' s)
  in
    loop s1 []

(** {i Variante:} fonction locale récursive terminale;
  utilise le caractère fonctionnel du [if].
*)
let inter_b s1 s2 =
  let rec loop s1 s =
    match s1 with
	[] -> s
      | e::s1' ->
	  (loop s1' (if (List.mem e s2) then (e::s) else s))
  in
    loop s1 []

(** {i Variante:} utilise l'itérateur [List.filtre]:
  les éléments de [s1] inter [s2] sont les élements
  de [s1] qui sont aussi dans [s2].
*)
let inter_c s1 s2 =
  List.filter (fun e -> (List.mem e s2)) s1


(** {1 Exo. III} *)

(** {b Quest. III.1} *)

(** Première possibilité: codage d'une suite par une liste (1). *)
type bin_seq1 = bool list

(** Deuxième possibilité: codage d'une suite par un tableau (2). *)
type bin_seq2 = bool array


(** {b Quest. III.2} 
  on donnera des solution pour les deux codages (1) et (2). 
*)

(** Codage avec des listes (1) *)
(**
  [(nb_occ_elt1 e s)] renvoie le nombre d'occurrences de [e] dans
  la suite binaire [s].
*)
let rec nb_occ_elt1 e s =
  match s with
      [] -> 0
    | e'::s' -> 
	if (e = e') then 1 + (nb_occ_elt1 e s')
	else (nb_occ_elt1 e s')
(** Jeu de tests pour [nb_occ_elt1] 
[(nb_occ_elt1 1 [])]

[(nb_occ_elt1 1 [1])]

[(nb_occ_elt1 1 [1;1])]

[(nb_occ_elt1 1 [1;2;1])]

[(nb_occ_elt1 1 [2;3;4])]

[(nb_occ_elt1 1 [1;2;3;4])]

[(nb_occ_elt1 1 [2;3;4;1])]
*)

(** {i Variante:} utilise la fonctionnalité de [if]. *)
let rec nb_occ_elt1_a e s =
  match s with
      [] -> 0
    | e'::s' -> 
	(if (e = e') then 1 else 0)
	+ (nb_occ_elt1_a e s')

(** {i Variante:} utilise l'itérateur [List.fold_left]. *)
let nb_occ_elt1_b e s =
  List.fold_left (fun n e' -> if (e = e') then n+1 else n) 0 s

(** {i Variante:} utilise l'itérateur [List.iter] 
  ainsi qu'une référence locale.
*)
let nb_occ_elt1_c e s =
  let n = ref 0 in
    List.iter (fun e' -> if (e = e') then incr n) s;
    !n

(** Codage avec des tableaux (2) *)
(**
  [(nb_occ_elt2 e s)] renvoie le nombre d'occurrences de [e] dans
  la suite binaire [s].
*)
let nb_occ_elt2 e s =
  let n = ref 0 in
    for i=0 to (Array.length s) - 1 do
      if (e = s.(i)) then incr n
    done;
    !n

(** {i Variante:} utilise l'itérateur [Array.iter]. *)
let nb_occ_elt2_a e s =
  let n = ref 0 in
    Array.iter (fun e' -> if (e = e') then incr n) s;
    !n
  
(** {b Quest III.3} *)

(** Codage avec des listes (1) *)
(** [(alt_seq1 s)] renvoie [true] si et seulement si [s]
  est une suite binaire alternée.
*)
let rec alt_seq1 s =
  match s with
      [] -> true
    | [e] -> true
    | e1::e2::s ->
	(e1 <> e2) && (alt_seq1 (e2::s))
(** Jeu de tests pour [alt_seq1]

[(alt_seq1 [])]

[(alt_seq1 [0])]

[(alt_seq1 [1])]

[(alt_seq1 [0;1])]

[(alt_seq1 [1;0])]

[(alt_seq1 [0;1;0])]

[(alt_seq1 [1;0;1])]

[(alt_seq1 [0;1;0;1])]

[(alt_seq1 [1;0;1;0])]

[(alt_seq1 [0;1;0;0])]

[(alt_seq1 [1;0;0;1])]
*)

(** Codage avec des tableaux (2) *)
(** [(alt_seq2 s)] renvoie [true] si et seulement si [s]
  est une suite binaire alternée.
*)
let alt_seq2 s =
  let len = Array.length s in
  let r = ref true in
    for i = 1 to len - 1 do
      r := !r && (s.(i-1) <> s.(i))
    done;
    !r

(** {i Variante:} utilise une boucle [while]: la fonction
  retourne [false] dès que la suite n'est plus alternée.

  {e Commentaire:} solution préférable ici.
*)
let alt_seq2_b s =
  let len = Array.length s in
  let r = ref true in
  let i = ref 1 in
    while !r && (!i < len) do
      r := !r && (s.(!i-1) <> s.(!i));
      incr i
    done;
    !r

(** {b Quest. III.4} *)

(** Codage avec des listes (1) *)
(** 
  [(nb_sub_hom1 e s )] renvoie le nombre de sous-suites [e]-homogènes 
  de [s].

  {e Algorithme:} on explore (quand c'est possible) les éléments
  deux par deux, on compte [+1] lorsque l'on {i "sort"} d'une
  (sous)suite de [e].
*)
let rec nb_sub_hom1 e s =
  match s with
      [] -> 0
    | [e1] -> if (e = e1) then 1 else 0
    | e1::e2::s' ->
	if (e1 = e) then
	  if (e2 = e) then (nb_sub_hom1 e (e2::s'))
	  else 1 + (nb_sub_hom1 e (e2::s'))
	else (nb_sub_hom1 e (e2::s'))
(** Jeu de tests pour [nb_sub_hom1]

[(nb_sub_hom1 1 [])]

[(nb_sub_hom1 1 [1])]

[(nb_sub_hom1 1 [1;1])]

[(nb_sub_hom1 1 [1;1;1])]

[(nb_sub_hom1 1 [1;0])]

[(nb_sub_hom1 1 [1;1;0])]

[(nb_sub_hom1 1 [1;1;1;0])]

[(nb_sub_hom1 1 [0;1])]

[(nb_sub_hom1 1 [0;1;1])]

[(nb_sub_hom1 1 [0;1;1;1])]

[(nb_sub_hom1 1 [1;0;1])]

[(nb_sub_hom1 1 [1;1;0;1])]

[(nb_sub_hom1 1 [0;1;0])]

[(nb_sub_hom1 1 [0;1;1;0])]

[(nb_sub_hom1 1 [0;1;1;0;1])]
*)

(** {i Variante:} réécriture (racourcie) des tests *)
let rec nb_sub_hom1_a e s =
  match s with
      [] -> 0
    | [e1] -> if (e = e1) then 1 else 0
    | e1::e2::s' ->
	if (e2 = e) or (e1 = e2) then
	  (nb_sub_hom1_a e (e2::s'))
	else
	  1 + (nb_sub_hom1_a e (e2::s'))

(** {i Variante:} utilise une référence locale (compteur). *)
let rec nb_sub_hom1_b e s =
  let n = ref 0 in
  let rec loop s =
    match s with
	[] -> ()
      | [e1] -> if (e = e1) then incr n
      | e1::e2::s' ->
	  if (e2 = e) or (e1 = e2) then
	    (loop (e2::s'))
	  else (
	    incr n;
	    (loop (e2::s'))
	  )
  in
    loop s;
    !n

(** {i Variante:} utilise un [if] unilatère. *)
let nb_sub_hom1_c e s =
  let n = ref 0 in
  let rec loop s =
    match s with
	[] -> ()
      | [e1] -> if (e = e1) then incr n
      | e1::e2::s' -> (
	  if (e1 = e) && (e2 <> e) then incr n;
	  (loop (e2::s'))
	)
  in
    loop s;
    !n

(** {i Variante:} utilise {e deux} références locales:
  un compteur et un booléen qui sert à déterminé
  la valeur du dernier élément traité ([e] ou non).
*)
let nb_sub_hom1_d e s =
  let n = ref 0 in
  let was_e = ref false in
  let rec loop s =
    match s with
	[] -> if !was_e then incr n
      | e'::s' ->
	  if (e' = e) then
	    if !was_e then (loop s')
	    else (was_e := true; (loop s'))
	  else
	    if (!was_e) then (was_e := false; incr n; loop s')
	    else (loop s')
  in
    (loop s);
    !n

(** {i Variante:} factorisation des tests. *)
let nb_sub_hom1_e e s =
  let n = ref 0 in
  let was_e = ref false in
  let rec loop s =
    match s with
	[] -> if !was_e then incr n
      | e'::s' -> (
	  if (e' = e) <> !was_e then (
	    if !was_e then incr n;
	    was_e := not !was_e
	  );
	  (loop s')
	)
  in
    (loop s);
    !n

(** {i Variante:} autre algorithme: 
  alterner un traitement pour les éléments différents de [e]
  et un second pour les éléments égaux à [e].

  Utilise des définitions (locales) mutuellement récursives.
*)
let nb_sub_hom1_f e s =
  (** loop1: on n'est pas dans une suite de 'e' *)
  let rec loop1 s =
    match s with
	[] -> 0
      | e'::s' -> 
	  if (e' = e) then (loop2 s)
	  else (loop1 s')
  (** loop2 on est dans une suite de 'e' *)
  and loop2 s =
    match s with
	[] -> 1
      | [e'] -> 1
      | e'::s' ->
	  if (e' = e) then (loop2 s')
	  else 1 + (loop1 s)
  in
    (loop1 s)

(** Codage avec des tableaux (2) *)
(** 
  [(nb_sub_hom2 e s)] renvoie le nombre de sous-suites [e]-homogènes 
  de [s].
*)
let nb_sub_hom2 e s =
  let n = ref 0 in
  let len = Array.length s in
    for i = 1 to len - 1 do
      if (s.(i-1) = e) && (s.(i) <> e) then incr n
    done;
    if (len > 0) && (s.(len - 1) = e) then incr n;
    !n

(** {i Variante:} l'autre algorithme avec des boucles [while]. *)
let nb_sub_hom2_a e s =
  let n = ref 0 in
  let len = Array.length s in
  let i = ref 0 in
    while (!i < len) do
      while (!i < len)  && (s.(!i) <> e) do incr i done;
      while (!i < len) && (s.(!i) = e) do incr i done;
      if (!i < len) then incr n
      else if (s.(!i - 1) = e) then incr n
    done;
    !n

(** {b Quest. III.5} *)

(** Codage avec des listes (1) *)
(**
  [(max_sub_hom1 e s)] renvoie la longueur de la plus longue sous-suite 
  [e]-homogène de [s].
*)
let rec max_sub_hom1 e s =
  (** [m]: longueur max. *)
  let m = ref 0 in
  (** [n]: longueur courante. *)
  let n = ref 0 in
  let rec loop s =
    match s with
        [] -> ()
      | [e1] -> if (e = e1) then (incr n; m := max !m !n)
      | e1::e2::s' ->
	  if (e1 = e) then
	    if (e2 = e) then (incr n; (loop (e2::s')))
	    else (incr n; m := max !m !n; n := 0; (loop (e2::s')))
	  else (loop (e2::s'))
  in
    (loop s);
    !m
(** Jeu de tests pour [max_sub_hom1] analogue à [nb_sub_hom1] *)

(** Codage avec des tableaux (2) *)
(**
  [(max_sub_hom2 e s)] renvoie la longueur de la plus longue sous-suite 
  [e]-homogène de [s].
*)
let max_sub_hom2 e s =
  let m = ref 0 in
  let n = ref 0 in
  let len = Array.length s in
    for i = 1 to len - 1 do
      if (s.(i-1) = e) then (
        incr n; 
        if (s.(i) <> e) then (m := max !m !n; n := 0)
      )
    done;
    if (len > 0) && (s.(len - 1) = e) then (incr n; m := max !m !n);
    !m