(*ENS 2002 Epreuve Pratique, beta version*)
(*exemple de code Ocaml par Laure DANTHONY*)

(*x_0=13*)


let tab = Array.make  10001 0;;
(*seul le sous-tableau tab[1..10000] est considéré par la suite*)

let init () =
  let last = ref 13 in
    tab.(0)<-13 mod 2;
    for i=1 to 9999 do
      last := (!last)*(!last) mod 3953;
      tab.(i)<- !last mod 2
    done;;

init();;
tab;;

let question_1 () = 
  let compteur = ref 0 and indice_dernier = ref (-1) in
    for i=1 to 10000 do
      if tab.(i)=1 then 
	(compteur := !compteur + 1;
	 indice_dernier :=i)
    done;
    (!compteur,!indice_dernier);;
(*val question_1 : unit -> int * int = <fun>*)

question_1 ();;
(*- : int * int = 4714, 9999*)

tab.(9999),tab.(10000);;
(*- : int * int = 1, 0*)


let question_2 () = 
  let compteur = ref 0 and deuxieme_indice = ref (-1) in 
    for i=1 to 9993 do
      if (tab.(i)=tab.(i+6) && tab.(i+1)=tab.(i+5) && tab.(i+2)=tab.(i+4))
      then (compteur:=!compteur + 1;
	    if !compteur =2 then deuxieme_indice:=i)
    done;
    (!compteur,!deuxieme_indice);;
(*val question_2 : unit -> int * int = <fun>*)


question_2 ();;
(*- : int * int = 999, 20*)

Array.sub tab 20 7;;
(*- : int array = [|1; 1; 0; 0; 0; 1; 1|]*)

exception Bidule of int*int*int;;
(*on se base sur le fait que si il n'existe pas de palindrome de longueur 12 et 
pas non plus de longueur 13, il n'y en a pas de plus grand*)

let question_3 ()=
  let rec palindrome x0 l=
    (l<=1) || ((tab.(x0)=tab.(x0+l-1)) && (palindrome (x0+1) (l-2)))
  in
  let rec trouve_un x0 l=((x0+l)<=10000) && ((palindrome x0 l)|| (trouve_un (x0+1) l))
  in let compter l= let cpt=ref 0 and secd=ref (-1515) in
    for d=1 to 10001-l do
      if palindrome d l then
	(cpt:= !cpt+1;
	 if !cpt=2 then secd:=d);
    done;
    !cpt,!secd
  in try
      (for longueur=2 to 9999  do
	 if (not(trouve_un 1 longueur)&& not(trouve_un 1 (longueur+1))) then
	   let (a,b)=compter (longueur-1) in
	     raise(Bidule(longueur-1,a,b))
       done; -1000,-100,-10)
    with
	Bidule(n,p,q) -> n,p,q
      | _ -> -1515,-1789,-10;;
(* val question_3 : unit -> int * int * int = <fun>*)
   
question_3 ();;
(*- : int * int * int = 18, 71, 205 *)



let question_4 ()=
  let maxi=ref 0 and pos_maxi=ref (-1515)
		 and pos_provi=ref 1  and c=ref 1 in
    while tab.(!c)=1 do c:= !c+1 done;
    pos_provi:= !c;
    while !c<10000 do
      while (!c<10000 && tab.(!c)=0) do c:= !c+1 done;
      if !c- !pos_provi> !maxi then
	(maxi:= !c- !pos_provi; pos_maxi:= !pos_provi);
      while !c<=10000 && tab.(!c)=1 do c:= !c+1 done;
      pos_provi:= !c;
    done;
    !maxi,!pos_maxi;;
(*val question_4 : unit -> int * int = <fun>*)

question_4 ();;
(*- : int * int = 8, 47*)
Array.sub tab 46 10;;
(*- : int array = [|1; 0; 0; 0; 0; 0; 0; 0; 0; 1|]*)

let question_5 ()=
  let rec desequilibre x0 l=
    if l<1 then 0 else
      if tab.(x0)=0 then 1+(desequilibre (x0+1) (l-1))
      else -1+(desequilibre (x0+1) (l-1))
  in
  let rec trouve_un x0 l=((x0+l)<=10000) &&
			 ((desequilibre x0 l)=0|| (trouve_un (x0+1) l))
  in let compter l= let cpt=ref 0 and secd=ref (-1515) in
    for d=1 to 10001-l do
      if (desequilibre  d l)=0 then
	(cpt:= !cpt+1;
	 if !cpt=2 then secd:=d);
    done;
    !cpt,!secd
  in try
      (for longueur=2 to 10000  do
	 if longueur mod 50 = 0 then (print_int longueur;print_newline ());
	 if (not(trouve_un 1 longueur)&& not(trouve_un 1 (longueur+1))) then
	   let (a,b)=compter (longueur-1) in
	     raise(Bidule(longueur-1,a,b))
       done; -1000,-100,-10)
    with
	Bidule(n,p,q) -> n,p,q
      | _ -> -1515,-1789,-10;;
(* val question_5 : unit -> int * int * int = <fun>*)

(*
question_5 ();;
(*- : int * int * int = 132, 71, 195*)
*)

Array.sub tab 195 132;;
(*- : int array =
[|1; 0; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 1; 1; 0; 1; 1; 0; 0; 1; 1; 0; 1; 1;
  0; 0; 0; 0; 1; 0; 1; 1; 0; 0; 1; 1; 1; 0; 1; 1; 1; 1; 1; 0; 1; 0; 0; 1; 1;
  1; 1; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 1; 0; 1; 0; 0; 0; 0; 0; 0; 1;
  0; 0; 1; 1; 0; 0; 0; 0; 1; 1; 0; 1; 0; 0; 1; 0; 0; 1; 1; 1; 1; 0; 0; 0; 0;
  1; 1; 0; 1; 1; 1; 1; 0; 0; 0; 1; 1; 0; 0; 1; 0; 0; 1; 0; 1; 0; 1; 1; 0; 1;
  0; 0; 0; 1; 1; 1; 1|]  *)

let c = ref 0 in for i=0 to 131 do if (Array.sub tab 195 132).(i)=0 then c:=!c+1 done; !c;;
(*- : int = 66*)


let est_repetee x0 l (tab:int array)=
  if l mod 2 <> 0 then false
  else 
    begin
      let loupe = ref false and i=ref 0 in 
	while ((!i<= (l/2-1)) && not(!loupe)) do
	  if tab.(x0+ !i)<> tab.(x0+ l/2+ !i) then loupe := true;
	  i:=!i+1
	done;
	not(!loupe)
    end;;
(*val est_repetee : int -> int -> int array -> bool = <fun>*)


est_repetee 0 6 [|1;0;0;1;1;0|] ;;
(*- : bool = false*)
est_repetee 0 6 [|1;0;0;1;0;0|] ;;
(*- : bool = true*)

let question_6 ()= (*cette fois on est bien obligé de tout parcourir*)
  let long_max = ref 0 
  in
  let est_repetee x0 l=
    if l mod 2 <> 0 then false
    else 
      begin
	let loupe = ref false and i=ref 0 in 
	  while ((!i<= (l/2-1)) && not(!loupe)) do
	    if tab.(x0+ !i)<> tab.(x0+ l/2+ !i) then loupe := true;
	    i:=!i+1
	  done;
	  not(!loupe)
      end
  in
  let rec trouve_un x0 l=((x0+l)<=10000) &&
			 ((est_repetee x0 l)|| (trouve_un (x0+1) l))
  in let compter l= let cpt=ref 0 and secd=ref (-1515) in
    for d=1 to 10001-l do
      if (est_repetee  d l) then
	(cpt:= !cpt+1;
	 if !cpt=2 then secd:=d);
    done;
    !cpt,!secd
  in 
    for longueur=2 to 10000  do
      if longueur mod 10 = 0 then (print_int longueur;print_newline ());
      if (trouve_un 1 longueur) then
	(let (a,b)=compter (longueur) in 
	   print_string "succes avec l=";
	   print_int longueur;
	   print_newline ();
	   long_max:=longueur;)
    done;
    let (a,b)=compter !long_max in 
      (!long_max,a,b);;
(*val question_6 : unit -> int * int * int = <fun>*)

(*question_6 ();;*)
(*- : int * int * int = 9800, 200, 2 : on a un w^2 avc w de taille 4900*)
(*de plus, dans la trace, on a une périodicité de succes de 560*)

(*vérification que x_560=x_0*)
let verif () = let tmp = ref 13 in for i=1 to 560 do tmp:=!tmp * !tmp mod 3953 done;!tmp;;
(*- : int = 3940 : en fait  x_560=-x_0*)
let verif_2 () = let tmp = ref 13 in for i=1 to 561 do tmp:=!tmp * !tmp mod 3953 done;!tmp;;
(*- : int = 169*)



exception Trouve of int;; 
(*l'indice est celui du tableau initial, pour vérifier il faut lire le tableau
  à l'envers à partir de cet indice*)


(*La coupe donnée est-elle dans le tableau inversé ?*)
let est_inversee x0 l (tab:int array) dernier_indice_tab=
  let ind_inv i = dernier_indice_tab-i+1 in
    try(
      for i=1 to dernier_indice_tab-l do (*parcours du tableau inversé*)
	let j=ref 0 and loupe = ref false in 
	  while ((!j<l) && not(!loupe)) do
	    if tab.(ind_inv (i + !j ))<>tab.(x0+ !j) then loupe:=true;
	    j:= !j+1
	  done;	
	  if (!j=l & not(!loupe)) then raise (Trouve (ind_inv i));
      done;
      (false,-2000);
    )
    with
      |Trouve(n)->(true,n)
      |_  ->(false,-15);;
(* val est_inversee : int -> int -> int array -> int -> bool * int = <fun>*)

est_inversee 2 3 [|0;0;1;0;1;0|] 5;;
(*- : bool * int = true, 4*)

exception Bidule2 of int*int*int*int;;

let question_7a () =
  let rec trouve_un x0 l=((x0+l)<=10000) &&
			 (fst (est_inversee x0 l tab 10000)||
			  (trouve_un (x0+1) l))
  in let compter l= 
      let cpt=ref 0 and secd=ref (-1515) and ind_inv = ref (-10) in
	for d=1 to 10001-l do
	  let (a,b)=est_inversee  d l tab 10000 in
	    if a then
	      (cpt:= !cpt+1;
	       if !cpt=2 then (secd:=d;ind_inv:=b));
	done;
	(!cpt,!secd,!ind_inv);
  in
    try
      (for longueur=1 to 10000  do
	 print_int longueur;print_newline ();
	(* if longueur mod 50 = 0 then (print_int longueur;print_newline ());*)
	 if not(trouve_un 1 longueur) then 
	   let (a,b,c)=compter (longueur-1) in
	     begin
	       print_string "( ";
	       print_int (longueur-1);print_string " , ";
	       print_int a;print_string " , ";
	       print_int b;print_string " , ";
	       print_int c;print_string " )";
	       raise(Bidule2(longueur-1,a,b,c));
	     end
       done; -1000,-100,-10,-1)
    with
	Bidule2(n,p,q,r) -> (
	 
	  n,p,q,r)
      | _ -> -1515,-1789,-10,-6;;

(*question_7a ();;*)
(*-: int * int * int * int = 18, 71 , 205 , 9882 obtenu en compilant avec ocamlopt*) 
(*time (Celeron 366 320Mo RAM) donne : 
  41.830u 0.030s 0:42.53 98.4%   0+0k 0+0io 114pf+0w*)

Array.sub tab 205 18;;
(*- : int array = [|0; 0; 0; 1; 1; 0; 1; 1; 0; 0; 1; 1; 0; 1; 1; 0; 0; 0|]*)
Array.sub tab (9882-18) 19;;
(*- : int array = [|1; 0; 0; 0; 1; 1; 0; 1; 1; 0; 0; 1; 1; 0; 1; 1; 0; 0; 0|]*)

(*vu le temps pris par 7a, on prend une solution plus "sioux" tout de suite*)
(*il s'agit de trouver la plus longue sous-suite commune de Tab et Tab_inv*)

(*on suppose les longueurs égales*)

let plssc (t1:int array) t2 = (*programmation dynamique*) 
  let n=ref (Array.length t1) in 
  let mat = Array.make_matrix !n !n 0
  in 
    print_string "debut ";
    print_newline ();
    (*initialisation*)
    for i=1 to !n-1 do mat.(i).(1)<-(if t1.(i)=t2.(1) then 1 else 0) done;
    for j=1 to !n-1 do mat.(1).(j)<-(if t2.(j)=t1.(1) then 1 else 0) done;    
    (*on remplit colonne par colonne*)
    for i=2 to !n-1 do
      print_int i;print_newline ();
      for j=2 to !n-1 do
	mat.(i).(j)<-(if t1.(i)=t2.(j) then (1+mat.(i-1).(j-1)) else max (mat.(i-1).(j)) (mat.(i).(j-1)))
      done
    done;
    mat.(!n-1).(!n-1);;


(*plssc [|1;3;2;5;7;0|] [|0;4;5;10;7;8|];;*)
(*- : int = 2*)

(*plssc [|1;4;2;0;7;8|] [|0;4;5;10;7;8|];;*)
(*- : int = 3*)

(*la premiere version de plssc ne depasse pas le stade d'initialisation*)
(*on se restreint donc a deux colonnes : seule la taille de la plssc comptera*)
(*on ne recupere pas la sous-suite commune, mais on pourrait*)

let plssc_bis (t1:int array) t2 = 
  let n=ref (Array.length t1) in 
  let mat = Array.make_matrix  2 (!n) 0
  in 
    print_newline ();
    (*initialisation : premiere colonne*)
    for j=0 to !n-1 do mat.(0).(j)<-(if t2.(j)=t1.(0) then 1 else 0) done;
    for i=1 to !n-1 do
      for j=1 to !n-1 do
	if i mod 2 = 0 then mat.(0).(j)<-
	  (if t1.(i)=t2.(j) then (1+mat.(1).(j-1)) else max (mat.(1).(j)) (mat.(0).(j-1)))
	else mat.(1).(j)<-
	  (if t1.(i)=t2.(j) then (1+mat.(0).(j-1)) else max (mat.(0).(j)) (mat.(1).(j-1)))
      done
    done;
    mat.((!n-1) mod 2).(!n-1);;


(*plssc_bis [|1;4;2;0;7;8|] [|0;4;5;10;7;8|];;*)
(*- : int = 3*)


(*plssc_bis [|1;3;2;5;7;0|] [|0;4;5;10;7;8|];;*)
(*- : int = 2*)

let question_7b () = 
  let t= Array.make 10001 0 in
    for i=1 to 10000 do t.(i)<-tab.(10000-i+1) done;
    let t = plssc_bis (Array.sub t 0 10000)  (Array.sub tab 1 10000) in 
      print_int t;
      print_newline ();
      t;;


(*question_7b ();;*)
(*- int = 8270*)
(*time : 25.030u 0.050s 0:25.44 98.5%    0+0k 0+0io 116pf+0w*)


let divise2 n = (n mod 2,n/2);;


let calcule_somme x0 x1 l tab=
  let res = Array.make (l+1) 0 and retenue = ref 0 in 
(*attention à l'éventuelle retenue d'où l'ajout d'une case*)
    for i=l downto 1 do
      let (a,b)=divise2 (!retenue + tab.(x0+i-1) + tab.(x1+i-1)) in 
	res.(i)<-a; 
	retenue := b;
    done;
    res.(0)<- !retenue;
    res;;

(*calcule_somme 2 6 4 [|1;0;0;1;0;1;1;1;0;1;1;0;0|];;*)
(*- : int array = [|1; 0; 0; 1; 0|]*)

(*calcule_somme 2 6 4 [|1;0;0;1;0;1;0;0;0;1;1;0;0|];;*)
(*- : int array = [|0; 0; 1; 1; 0|]*)

exception Trouve of int;;

let est_une_coupe (t:int array) l tab l_tab = 
(*on considere t à partir de l'indice 0, tab a partir de 2*)
  try (
    for i=2 to (l_tab-1) do 
      let j=ref 0 and loupe = ref false in 
	while ((!j<l) && not(!loupe)) do
	  if t.(!j)<>tab.(i + !j) then loupe:=true;
	  j:= !j+1
	done;	
	if (!j=l & not(!loupe)) then raise (Trouve i);
    done;
    (false,-60)
  )
  with
      Trouve(n)->(true,n)
    | _ -> (false,-2002);;

est_une_coupe [|0;0;1;0;0;1|] 6 [|0;0;0;0;1;0;0;1|] 8 ;;	
(*   - : bool * int = true, 2*)

let question_8 () = 
  try (
    for longueur=6220 to 9999 do
      if longueur mod 50 = 0 then print_int longueur;print_newline ();
      for x0=1 to 9998 do
	for x1=x0 +1 to 9999 do
	  let t=calcule_somme x0 x1 longueur tab in
	  let (a,b)= est_une_coupe t (longueur+1) tab 10000 in
	    if a then (
	      print_string "succes avec l= ";print_int longueur;
	      print_string " positions = ( ";print_int x0;
	      print_string ",";print_int x1;
	      print_string ",";print_int b;
	      print_string ")";print_newline ();)	      
	done;
      done;
    done;
    (-60,0,-10,-1515)
  )
  with 
      Bidule2(long,ind1,ind2,ind3)->(long,ind1,ind2,ind3)
    | _ -> (-60,0,-10,-1515);;

calcule_somme 1 141 5000 tab;;
Array.sub tab 141 30;;
Array.sub tab 1 30;;


question_8 ();;
(*je tatonne a l'aide du parametre longueur*)
(*succes avec l= 5000 : positions = (1,141,141) ou (1,281,141) etc *) 
(*succes avec l= 6000 positions = ( 1,141,141)*)
(*echec a 6500,6250*)
(*succes avec l= 6100 positions = ( 1,141,141)*)
(*succes avec l= 6100 positions = ( 1,281,141)*)
(*succes avec l= 6100 positions = ( 1,421,141)*)
(*la plus grande est de taille 6219*)