print_endline Sys.ocaml_version;;
Sys.command "ocaml -version";;

let print = Printf.printf;;

type etat = int array;;
type liste_rdv = (int array) array;;

let ex1_1 : etat = [| 1; 1; 2 |];;
let ex1 : liste_rdv = [|
    [| 1; 3 |];
    [| 1; 2 |];
    [| 2; 3 |]
|];;

let trouve (x:int) (a:int list) : int =
    let rec aux (x:int) (a:int list) (i : int) : int =
        match a with
        | [] -> -1
        | t :: _ when (t = x) -> i
        | _ :: q -> aux x q (i+1)
    in
    aux x a 0
;;

let trouve_array (x : int) (a : int array) : int =
    trouve x (Array.to_list a)
;;

let _ = trouve_array 2 ex1_1;; (* 2 *)

let rdv (u : etat) : ((int * int) list) = 
    let n = Array.length u in
    let ls = ref [] in (* plus simple que d'imbriquer les List.filter et List.map... *)
    for k = 0 to n - 1 do
        let i = trouve_array u.(k)
            (Array.sub u (k + 1) (n - (k + 1)))
        in
        if i >= 0 then
            ls := (k, i + k + 1) :: !ls;
    done;
    !ls
;;

let _ = rdv ex1_1 ;;

let ex3_1 = [| 1; 2; 1; 4; 4 |];;
let _ = rdv ex3_1 ;;

let realise_rdv (u : etat) (lr : liste_rdv) (xy : int * int) : etat =
    let x, y = xy in
    let ux = u.(x) and uy = u.(y) in
    let rx, ry = lr.(x), lr.(y) in
    u.(x) <- rx.(((trouve_array ux rx) + 1) mod (Array.length rx));
    u.(y) <- ry.(((trouve_array uy ry) + 1) mod (Array.length ry));
    u
;;

let u = [| 0; 0; 1 |];;
let l = [| [|0; 2|]; [|1; 2|]; [|2; 0|] |];;
let _ = realise_rdv u l (0, 1) ;;

u;;

let transition (u0 : etat) (l0 : liste_rdv) : etat =
    List.iter (fun u -> ignore (realise_rdv u0 l0 u)) (rdv u0);
    u0
;;

let rec n_transitions_trop_couteux (u : etat) (l : liste_rdv) (n : int) : etat =
    if (n = 0) then
        u
    else
        n_transitions_trop_couteux (transition u l) l (n-1)
;;

let n_transitions (u : etat) (l : liste_rdv) (n : int) : etat =
    for _ = 1 to n do
        ignore (transition u l)  (* u est changé en place *)
    done;
    u
;;


let _ = ex1;;
let _ = ex1_1;;

let _ = transition ex1_1 ex1;;
let _ = transition ex1_1 ex1;;
let _ = transition ex1_1 ex1;;
let _ = transition ex1_1 ex1;;

let ex2 = [| [|0; 1; 2|]; [|0|]; [|1; 3|]; [|2; 3|] |];;

let ex2_1 = [| 0; 0; 1; 2 |];;
let _ = n_transitions ex2_1 ex2 3;;

let ex2_1 = [| 0; 0; 1; 2 |];; (* il faut l'écrire, il a été modifié *)
let _ = transition ex2_1 ex2;;
let _ = transition ex2_1 ex2;;
let _ = transition ex2_1 ex2;;
let _ = transition ex2_1 ex2;;

let ex2_2 = [| 0; 0; 3; 2 |];;

let _ = transition ex2_2 ex2;;
let _ = transition ex2_2 ex2;; (* On bloque !*)
let _ = transition ex2_2 ex2;; (* On bloque !*)

let ex2_3 = [| 0; 0; 3; 3 |];;

let _ = transition ex2_3 ex2;;
let _ = transition ex2_3 ex2;;
let _ = transition ex2_3 ex2;; (* On a un cycle de taille 3 *)
let _ = transition ex2_3 ex2;;

Random.init 0;;

let weight_sampling (pi : float array) () =
    let p = Random.float 1. in
    let i = ref (-1) in
    let acc = ref 0. in
    while !acc < p do
        incr i;
        acc := (!acc) +. pi.(!i);
    done;
    !i
;;

let compte (a : 'a array) (x : 'a) : int =
    Array.fold_left (fun i y -> if y = x then i + 1 else i) 0 a
;;
    
let echantillons = Array.init 100
    (fun _ -> weight_sampling [| 0.5; 0.1; 0.4 |] ())
;;

compte echantillons 0;;
compte echantillons 1;;
compte echantillons 2;;

let markov_1 (a : float array array) (i : int) : int =
    let pi = a.(i) in
    weight_sampling pi ()
;;

let a = [|
            [| 0.4; 0.3; 0.3 |];
            [| 0.3; 0.4; 0.3 |];
            [| 0.3; 0.3; 0.4 |]
    |]
;;

print "\n";;
for _ = 0 to 100 do
    print "%i" (markov_1 a 0);
done;;
flush_all ();;

let markov_n (a : float array array) (etat : int) (n : int) : int =
    let u = ref etat in
    for _ = 0 to n-1 do
        u := markov_1 a !u;
    done;
    !u
;;

markov_n a 0 10;;

let markovs_n (a : float array array array) (robots : int array) (n : int) : int array =
    Array.mapi (fun i u -> markov_n a.(i) u n) robots
;;

markovs_n [|a; a; a|] [|0; 1; 2|] 10;;

(* Fonctions utiles *)
Array.init;;
Array.make_matrix;;
Array.iter;;

let mat_proba_depuis_rdv (ts : int array array) : (float array array) array =
    let n = Array.length ts in
    let a = Array.init n (fun _ -> Array.make_matrix n n 0.) in
    for i = 0 to n-1 do
        (* Pour le robot R_i, ses rendez-vous T_i sont ts.(i) *)
        let r = ts.(i) in
        let m = Array.length r in
        let p_i = 1. /. (float_of_int m) in
        (* Pour chaque rendez-vous L_j dans T_i,
           remplir a.(j).(k) par 1/m,
           et aussi a.(k).(j) par 1/m
           pour chaque autre k dans L_j
        *)
        for j = 0 to m-1 do
            for k = 0 to m-1 do
                a.(i).(r.(j)).(r.(k)) <- p_i;
                a.(i).(r.(k)).(r.(j)) <- p_i;
            done;
        done;
    done;
    a
;;

let simule_markov_robots (ts : int array array)
    (etats : int array) (n : int)
    : int array =
    let a = mat_proba_depuis_rdv ts in
    markovs_n a etats n
;;

let ex3 = [| [|0; 2|]; [|1; 0|]; [|2; 1|]|] ;;

let premier_etat (rdvs : int array array) : int array =
    Array.init (Array.length rdvs) (fun i -> rdvs.(i).(0))
;;

let ex3_1 = premier_etat ex3;;

mat_proba_depuis_rdv ex3;;

simule_markov_robots ex3 ex3_1 0;;  (* rien à faire ! *)

simule_markov_robots ex3 ex3_1 1;;

let print = Printf.printf;;

let affiche_etat (etat : int array) =
    Array.iter (fun u -> print "%i " u) etat;
    print "\n";
    flush_all ();
;;

affiche_etat ex3_1;;

let u = ref ex3_1 in
for _ = 0 to 10 do
    affiche_etat !u;
    u := simule_markov_robots ex3 !u 1;
done;;

let u = ref [| 0; 1; 1 |] in
for _ = 0 to 10 do
    affiche_etat !u;
    u := simule_markov_robots ex3 !u 1;
done;;

let ex4 = [| [|0; 3|]; [|0; 1|]; [|1; 2|]; [|2; 3|] |];;

let ex4_1 = premier_etat ex4;;

mat_proba_depuis_rdv ex4;;

simule_markov_robots ex4 ex4_1 0;;  (* rien à faire ! *)

simule_markov_robots ex4 ex4_1 1;;

let u = ref ex4_1 in
for _ = 0 to 10 do
    affiche_etat !u;
    u := simule_markov_robots ex4 !u 1;
done;;