(* Ricochet Robots - partie 3 *)

(* Correction partie 2 - ce qui sera utile pour la partie 3 *)

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|] |];;

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;;

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 *)

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;;

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)
;;

(* calcule les 4 déplacements possibles pour le robot  (a,b) en fonction de la liste des autres robots *)
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 *)


(* Partie 3 : on démarre ici ! *)

(* Fonctions utiles *)
let rec inserer liste x = 
  (* insere x dans une liste triée par ordre croissant.
     renvoie une nouvelle liste *)
  failwith "A faire"
;;

let rec exclure liste x =
  (* exclure x d'une liste, supposé présent. 
     renvoie une nouvelle liste *)
  failwith "A faire"
;;

(* Une configuration du jeu. 
   robot : robot principal
   autres_robots : liste maintenue triée *)
type config = { robot : int * int; autres_robots : (int * int) list }

let affiche_config cfg =
  Printf.printf "robot:(%d,%d) autres:" (fst cfg.robot) (snd cfg.robot);
  List.iter (fun (x,y) -> Printf.printf "(%d,%d)" x y ) cfg.autres_robots;
  print_newline ()
;;

(* calcul des 16 configurations voisines *)
let config_voisines cfg =
  failwith "A faire"
;;

(* résolution avec un parcours en largeur *)
let resol_largeur (cfg0:config) =
  let gagne = ref false in
  (* A COMPLETER *)
  if (not !gagne) then Printf.printf "Pas de solution\n"
;;

Printf.printf "configuration facile:\n";
resol_largeur {robot = (5,12); autres_robots = [(0,7);(3,1);(4,0)]};;

Printf.printf "configuration initiale:\n";
resol_largeur {robot = (5,12); autres_robots = [(0,0);(2,1);(4,7)]};;