(* Corrigé - TP07 Ricochet Robots - partie 2 *)

let obs_l = [| [|0; 4; 10; 16|]; [|0; 14; 16|]; [|0; 6; 16|];
   [|0; 9; 16|]; [|0; 3; 15; 16|]; [|0; 7; 16|]; [|0; 1; 12; 16|]; [|0; 7; 9; 16|];
   [|0; 7; 9; 16|]; [|0; 4; 13; 16|]; [|0; 6; 16|]; [|0; 10; 16|]; [|0; 8; 16|];
   [|0; 2; 15; 16|]; [|0; 4; 10; 16|]; [|0; 5; 12; 16|] |];;

let obs_c = [| [|0; 5; 11; 16|]; [|0; 6; 13; 16|]; [|0; 4; 16|];
   [|0; 15; 16|]; [|0; 10; 16|]; [|0; 3; 16|]; [|0; 10; 16|]; [|0; 6; 7; 9; 12; 16|];
   [|0; 7; 9; 16|]; [|0; 3; 12; 16|]; [|0; 14; 16|]; [|0; 16|]; [|0; 7; 16|];
   [|0; 2; 10; 16|]; [|0; 4; 13; 16|]; [|0; 2; 12; 16|] |];;

(* Q1 *)
let dichotomie a t =
let i = ref 0 in (* inclus *)
let j = ref (Array.length t) in (* exclu *)
while (!j - !i > 1) do
   let m = (!i + !j) / 2 in
   if t.(m) > a then j := m else i := m
done; !i;;

(* Tests dichotomie *)
Printf.printf "Test dichotomie : %d\n" (dichotomie 3 [|0;1;5;15;21;30|]);;
assert (dichotomie 3 [|0;1;5;15;21;30|] = 1);;
assert (dichotomie 5 [|0;1;5;15;21;30|] = 2);;
assert (dichotomie 29 [|0;1;5;15;21;30|] = 4);;

let seq a t = (* version séquentielle - moins efficace *)
   let i = ref 0 in (* on avance dans le tableau trié *)
   while (t.(!i+1) <= a) do
      i := !i + 1
   done; !i;;
   
   (* Tests dichotomie *)
   Printf.printf "Test seq : %d\n" (seq 3 [|0;1;5;15;21;30|]);;
   assert (seq 3 [|0;1;5;15;21;30|] = 1);;
   assert (seq 5 [|0;1;5;15;21;30|] = 2);;
   assert (seq 29 [|0;1;5;15;21;30|] = 4);;
   

(* Q2 *)
let deplacements_grille (a,b) =
   let imurG = dichotomie b obs_l.(a) in
   let imurH = dichotomie a obs_c.(b) in
   [| (a,obs_l.(a).(imurG));  (* ouest : même ligne, mur Gauche *)
      (a,obs_l.(a).(imurG+1)-1); (* est : même ligne, mur Droit -1 *)
      (obs_c.(b).(imurH),b); (* nord : mur Haut, même colonne *)
      (obs_c.(b).(imurH+1)-1,b)|];; (* sud : mur Bas -1, même colonne *)

(* affichage d'un tableau de positions *)
let affichePos tab =
Array.iter (fun (a,b)->Printf.printf "(%d,%d)" a b) tab; print_newline ();;

Printf.printf "Test deplacement solo :\n";;
affichePos (deplacements_grille (0,0));;
assert (deplacements_grille (0,0) = [|(0,0);(0,3);(0,0);(4,0)|]);;
assert (deplacements_grille (2,7) = [|(2,6);(2,15);(0,7);(5,7)|]);;
assert (deplacements_grille (9,7) = [|(9,4);(9,12);(9,7);(11,7)|]);;

(* Q4 *)
let matrice_deplacements () =
  let m = Array.make_matrix 16 16 [||] in
  for i = 0 to 15 do
    for j = 0 to 15 do
      m.(i).(j) <- deplacements_grille (i,j)
    done
  done;
  m;;

(* Q6 *)
let mat_depl = matrice_deplacements ();;

let modif t (a,b) (c,d) =
  if (a = c && b < d) then (* gene à l'est ? *)
     let (x,y) = t.(1) in
     t.(1) <- (x , min y (d-1))
  else if (a = c && b > d) then (* gene à l'ouest ? *)
     let (x,y) = t.(0) in
     t.(0) <- (x, max y (d+1))
  else if (b = d && a > c) then (* gene au nord ? *)
     let (x,y) = t.(2) in
     t.(2) <- (max x (c+1), y)
  else if (b = d && a < c) then (* gene au sud ? *)
     let (x,y) = t.(3) in
     t.(3) <- (min x (c-1), y)
;;

Printf.printf "Test deplacement vs. 1 robot :\n";;
let t0 = deplacements_grille (2,7) in
modif t0 (2,7) (2,12);
affichePos t0;
assert (t0 = [|(2,6);(2,11);(0,7);(5,7)|]);;


(* Q8 *)
let deplacements_robots (a,b) q =
  let t = Array.copy mat_depl.(a).(b) in (* les deplacements sans gene *)
  List.iter (fun (c,d) -> modif t (a,b) (c,d)) q; t;; (* modification pour chaque robot *)

Printf.printf "Test deplacement vs. plusieurs robots :\n";;
let t1 = deplacements_robots (2,7) [(2,6); (4,7); (2,15); (2,10)] in
affichePos t1;
assert (t1 = [|(2,7);(2,9);(0,7);(3,7)|]);;

(* Q10 *)

(* affichage d'un tableau de positions *)
let direction_of_int x = match x with
| 0 -> "ouest"
| 1 -> "est"
| 2 -> "nord"
| 3 -> "sud"
| _ -> failwith "direction invalide"

let afficheSol lst =
  List.iter (fun (a,b)->Printf.printf "robot %d vers %s\n" a (direction_of_int b)) lst;;

let rec resol_backtracking deplacements robots p =
   if robots.(0) = (14,3) then
      begin
         Printf.printf("victoire\n");
         afficheSol (List.rev deplacements)
      end
   else if p > 0 then
      let nr = Array.length robots in
      let listr = Array.to_list robots in
      for i = 0 to nr - 1 do
         (* déplacements pour le robot i ? *)
         let depl = deplacements_robots robots.(i) listr in
         for j = 0 to 3 do
              let robots2 = Array.copy robots in
              robots2.(i) <- depl.(j);
              (* NB: on peut aussi modifier le tableau robots 
              et ne pas faire de copie ; mais il faut alors
              impérativement remettre le robot i à sa position 
              initiale après la boucle for sur j *)
              resol_backtracking ((i,j)::deplacements) robots2 (p-1)
         done
      done
   ;;

Printf.printf "configuration facile:\n";
resol_backtracking [] [|(5,12);(4,0);(3,1);(0,7)|] 6;;

Printf.printf "configuration initiale:\n";
resol_backtracking [] [|(5,12);(0,0);(2,1);(4,7);|] 6;;