(* ---------- *)
(* Exercice 1 *)

let l4 = 4;;
let l3 = 3, ref l4;;
let l2 = 2, ref l3;;
let l1 = 1, ref l2;;
let l0 = 0, ref l1;;

fst !(snd !(snd l1));;
fst !(snd !(snd l0));;


(* ---------- *)
(* Exercice 2 *)

(* Question 1 *)

let eratosthene n =
  let crible = Array.make (n+1) true in
  crible.(0) <- false;
  crible.(1) <- false;
  let i = ref 2 in
  let k = ref 0 in
  while !i * !i <= n do
    if crible.(!i) then
      (k := 2* !i;
      while !k <= n do
        crible.(!k) <- false;
        k:=!k+ !i
      done);
    incr i;
  done;
  crible;;

(* Question 2 *)



let decompose_somme t s =
  if s > 2 && (s = 4 || s mod 2 = 1) then
    t.(s-2)
  else
    begin
      let b = ref false in
      let k = ref 3 in
      while not !b && 2 * !k <= s do
        b :=  t.(!k) && t.(s - !k);
        k := !k+2
      done;
      !b
    end
;;

(* en admettant la conjecture de Goldbach
   voir https://fr.wikipedia.org/wiki/Conjecture_de_Goldbach
*)
let decompose_somme_Gb t s = (s>2) && (s mod 2 = 0 || t.(s-2) );;


(* ---------- *)
(* Exercice 3 *)

(* Question 1 *)

(* addition *)
let (++) p q =
  let lp = Array.length p
  and lq = Array.length q
  in
  let r = Array.make (max lp lq) 0 in
  for i = 0 to lp - 1 do
    r.(i) <- p.(i)
  done;
  for i = 0 to lq - 1 do
    r.(i) <- r.(i) + q.(i)
  done;
  r
;;

let p = [| 1; 2; 3 |]     (* 1 + 2x + 3x^2 *)
and q = [| 4; 5; 6; 7|]   (* 4 + 5x + 6x^2 + 7x^3 *)
;;

p ++ q;;

(* soustraction *)
let (--) p q =
  let lp = Array.length p
  and lq = Array.length q
  in
  let r = Array.make (max lp lq) 0 in
  for i = 0 to lp - 1 do
    r.(i) <- p.(i)
  done;
  for i = 0 to lq - 1 do
    r.(i) <- r.(i) - q.(i)
  done;
  r
;;

p -- q;;


(* multiplication *)
let ( ** ) p q =
  let lp = Array.length p
  and lq = Array.length q
  in
  let r = Array.make (lp + lq) 0 in
  for k = 0 to (lp + lq - 1) do
    for i = 0 to min k (lp - 1) do
      let j = k - i in
      if j < lq then (* Somme double *)
        r.(k) <- r.(k) + p.(i) * q.(j) ;
    done;
  done;
  r
;;

p ** q;;


(* Question 2 *)

(* Mauvaise solution récursive *)
let rec tchebychev k =
  if k = 0 then
    [| 1 |]
  else if k = 1 then
    [| 0 ; 1 |]
  else
    [| 0 ; 2 |] ** tchebychev (k-1) -- tchebychev (k-2)
;;

tchebychev 7;;
(* - : int array = [|0; -7; 0; 56; 0; -112; 0; 64; 0; 0; 0; 0; 0; 0|] *)


(* Solution avec un tableau *)

let tchebychev k =
  let t = Array.make_matrix (k+1) (k+1) 0 in
  t.(0).(0) <- 1 ;
  t.(1).(1) <- 1 ;
  for i = 2 to k do
    let ti = t.(i-1) ** [|0;2|] -- t.(i-2) in
    let lti = Array.length ti in
    for j = 0 to min k (lti-1) do
      t.(i).(j) <- ti.(j);
    done;
  done;
  t.(k)
;;

tchebychev 7;;
(* - : int array = [|0; -7; 0; 56; 0; -112; 0; 64|] *)


(* Solution récursive terminale *)

let tchebychev k =
  let rec tchebychev_recursive d t_prec t_ante =
    if d = k then
      t_ante
    else
      tchebychev_recursive (d+1) ([|0;2|] ** t_prec -- t_ante) t_prec
  in
  tchebychev_recursive 0 [|0;1|] [|1|]
;;

tchebychev 7;;
(* - : int array = [|0; -7; 0; 56; 0; -112; 0; 64; 0; 0; 0; 0; 0; 0|] *)


(* Question 3 *)

let compose p q =
  let n = Array.length p in
  let rec compose_Horner p q i =
    if i >= n then
      [||]
    else
      [|p.(i)|] ++ (q ** (compose_Horner p q (i+1)))
  in
  compose_Horner p q 0;;

compose [|0; 0; 0; 0; 0; 0; 1|] [|1; 1|]


(* Question 4 *)

let degre p =
  let n = ref ((Array.length p) - 1) in
  while p.(!n) = 0. do
    decr n;
  done;
  !n
;;

let division a b =
  let n = degre a in
  let m = degre b in
  if  n < m then
    [|0.|], a
  else
    let r = Array.copy a in
    let q = Array.make (n-m+1) 0. in
    let u = (1. /. b.(m)) in
    for i = (n-m) downto 0 do
      let d = degre r in
      if d = m+i then
        begin
          q.(i) <- r.(d) *. u;
          for j = 0 to m do
            r.(j+i) <- r.(j+i) -. q.(i) *. b.(j)
          done;
        end
      else
        q.(i) <- 0.;
    done;
    q, r
;;


(* ---------- *)
(* Exercice 4 *)
(* ---------- *)

let voisins i j n =

  if i = 0 then                (* première ligne *)

    if j = 0 then              (* - coin en haut à gauche *)
      [(0,1);(1,0)]
    else if j = n-1 then       (* - coin en haut à droite *)
      [(0,n-1);(1,n-1);(1,n-2)]
    else                       (* - première ligne, cas général *)
      [(i+1,j) ; (i,j-1) ; (i,j+1) ; (i+1,j-1)]

  else if i  = n - 1 then      (* dernière ligne *)

    if j = 0 then              (* - coin en bas à gauche *)
      [(i-1,0);(i-1,1);(i,1)]
    else if j = n-1 then       (* - coin en bas à droite *)
      [(i,n-2);(i-1,n-1)]
    else                       (* - dernière ligne, cas général *)
      [(i-1,j) ; (i,j-1) ; (i,j+1) ; (i-1,j-1)]

  else                         (* ligne générale *)

    if j = 0 then              (* - colonne gauche *)
      [(i-1,j) ; (i-1,j+1) ; (i,j+1) ; (i+1,j)]
    else if j = n-1 then       (* - colonne droite *)
      [(i-1,j) ; (i+1,j-1) ; (i,j-1) ; (i+1,j)]
    else                       (* - cas général *)
    [(i-1,j) ; (i+1,j) ; (i,j-1) ; (i,j+1) ; (i-1,j+1) ; (i+1,j-1)]
;;


let hex jeu =
  let n = Array.length jeu in
  let plateau = Array.make_matrix n n ' ' in
  for i = 0 to n-1 do
    plateau.(i) <- Array.copy jeu.(i)
  done;  (* On commence par copier le plateau pour pouvoir le modifier *)
  let minusc = function 'O' -> 'o' | 'X' -> 'x' | c -> c in
  (* On indique par des minuscules les cases déjà visités *)
  let cherchevictoire joueur =
    let init () = (* cherche une pièce du joueur sur le bord haut ou gauche *)
      let k = ref 0 in
      let i0 = ref (-1) in
      let j0 = ref (-1) in
      while !k < n do
        begin
          if plateau.(!k).(0) = joueur then
            begin
              i0 := !k;
              j0 := 0;
              plateau.(!k).(0) <- minusc joueur; (* on marque la pièce comme étant vue *)
              k := n;
            end
          else if plateau.(0).(!k) = joueur then
            begin
              i0 := 0;
              j0 := !k;
              plateau.(0).(!k) <- minusc joueur;
              k := n;
            end;
        end;
        incr k;
      done;
      let cond_victoire i j = if !i0 = 0 then i = n-1 else j = n-1 in
      if !k = n+1 then
        (true, !i0, !j0, cond_victoire)
      else
        (false, -1, -1, fun _ _ -> false)
    in
    let rec parcours l condition_victoire=
      match l with
      | [] -> let b, i0,j0, c_v = init () in
              if b then
                parcours (voisins i0 j0 n) c_v
              else false
      | (i,j) :: _ when (plateau.(i).(j) = joueur) && (condition_victoire i j) ->  true
      | (i,j) :: _ when plateau.(i).(j) = joueur -> begin
          plateau.(i).(j) <- minusc joueur;
          parcours (l @ (voisins i j n)) condition_victoire
        end
      | _ :: q -> parcours q condition_victoire
    in
  parcours [] (fun _ _ -> false)
  in
  if cherchevictoire 'O' then
    "vainqueur : O"
  else if cherchevictoire 'X' then
      "vainqueur : X"
  else
    "pas (encore) de vainqueur";;