(* Automates Cellulaires*)

type automate = {degre : int ; transition : int array};;

(*1*)

(* c'est le tableau [|0;0;1;0;0;0;1;1|] *)


(*2*)

let rec log2 i =
  if i = 1 then true, 0
  else if i mod 2 = 0 then let b, e = log2 (i / 2) in b, (e + 1)
  else false, 0;; 
	
log2 16;;


let auto t = let n = Array.length t in
    let (b, e) = log2 n in
      if b && (e mod 2 = 1) then {degre = e / 2; transition = t}
      else failwith "pas la bonne dimension";;

(*3*)

let compose x r debut =
  let s = ref 0 and p = ref 1 in
    for k = 0 to (2 * r) do
      s := !s + x.(debut + 2 * r - k) * !p;
      p := 2 * !p
    done;
    !s;;


(*4*)
(* On peut calculer F(x)(i) pour i compris (au sens large) entre -N+r et N - r*)

(*5*)

let transition f x =
  let n = Array.length x - 2 * f.degre in
    let y = Array.make n 0 in
      for i = 0 to (n - 1) do
        y.(i) <- f.transition.(compose x (f.degre) i)
      done;
      y;;

let f = {degre = 1 ; transition = [|0;1;1;0;1;1;1;0|]};;

let x =[|0;1;1;0;1;0;0;1;1;0;0;0;1|];;

transition f x;;

(*6*)
let rec iteration f x n =
  if n = 0 then x else iteration f (transition f x) (n - 1);;

iteration f x 3;;

(*7*)
let matrice f x n =
  let largueur = (Array.length x - 2 * (n - 1) * f.degre) in
    let res = Array.make_matrix n largueur 0 in
      let rec remplissage i x =
        if i < n then
          (for j = 0 to (largueur - 1) do
              res.(i).(j) <- x.(j + ((n - 1) - i) * f.degre)
            done;
            remplissage (i + 1) (transition f x)
          )
      in remplissage 0 x;
        res;;
        
 matrice f x 4;;


(*8*)
let wolfram i = let t = Array.make 8 0 in
    let x = ref i in
      for k = 0 to 7 do
        if !x mod 2 = 1 then t.(k) <- 1;
        x := !x / 2
      done;
      {degre = 1 ; transition = t};;
      
wolfram 150;;




(*9*)
let matriceWolfram i n =
  let x = Array.make (3 * n - 2) 0 in
    x.((3 * n - 2) / 2) <- 1;
    matrice (wolfram i) x n;;
   
matriceWolfram 150 20
;;


(* bonus *)
#load "graphics.cma"
open Graphics;;
open_graph " 1024x780";;

let dessineCarre x y ax ay =
  for k = 0 to (ay) do
    moveto x (y - k);
    lineto (x + ax) (y - k);
  done;;


let dessineMatrice m =
  let hauteur = Array.length m in
    let largeur = Array.length m.(0) in
      let tx = size_x () / (largeur ) and ty = size_y () / (hauteur + 1) in
        for i = 0 to (hauteur - 1) do
          for j = 0 to (largeur - 1) do
            if m.(i).(j) = 1 then
              dessineCarre (j * tx) (size_y () - i * ty) tx ty
          done;
        done; 
;;
dessineMatrice (matriceWolfram 150 20);;
clear_graph();;

(*11*)
type automateProba = {degreProba : int ; transitionProba : int array ; proba : float};;


let transitionProba f x =
  let n = Array.length x - 2 * f.degreProba in
    let y = Array.make n 0 in
      for i = 0 to (n - 1) do
      	if Random.float 1. <= f.proba then
        y.(i) <- f.transitionProba.(compose x (f.degreProba) i)
        else
        y.(i) <- x.(i)
      done;
      y;;


let rec iterationProba f x n =
  if n = 0 then x else iterationProba f (transitionProba f x) (n - 1);;



let matriceProba f x n =
  let largueur = (Array.length x - 2 * (n - 1) * f.degreProba) in
    let res = Array.make_matrix n largueur 0 in
      let rec remplissage i x =
        if i < n then
          (for j = 0 to (largueur - 1) do
              res.(i).(j) <- x.(j + ((n - 1) - i) * f.degreProba)
            done;
            remplissage (i + 1) (transitionProba f x)
          )
      in remplissage 0 x;
        res;;
        

(*12*)

let emb = {degre = 1 ; transition = [|0 ; 0 ; 0 ; 1 ; 1; 1 ; 0 ; 1|]};;
let embProba = {degreProba = 1 ; transitionProba = [|0 ; 0 ; 0 ; 1 ; 1; 1 ; 0 ; 1|] ; proba = 0.5};;

let x = Array.make 500 0;; 
for i = 0 to (499) do 
if Random.float 1. <= 0.5 then x.(i) <- 1
done;;

x;;

let m = matrice emb x 100;;
let mProba = matriceProba embProba x 100;;

mProba.(50);;

dessineMatrice m;;

clear_graph();;

dessineMatrice mProba;;