(* Corrigé - 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 *)

(* Fonctions utiles *)
let rec inserer liste x = 
  (* insere x dans une liste triée par ordre croissant.
     renvoie une nouvelle liste *)
  match liste with
  | [] -> [x]
  | e::ll -> if x < e then x :: liste else e :: (inserer ll x)
;;

let rec exclure liste x =
  (* exclure x d'une liste, supposé présent.
     renvoie une nouvelle liste *)
  match liste with 
  | [] -> failwith "impossible"
  | e :: ll -> if x = e then ll else e :: exclure ll x
;;

(* 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 =
  let voisins = ref [] in
  (* 4 voisins : on déplace le robot principal *)
  let t = deplacements_robots cfg.robot cfg.autres_robots in
  for i = 0 to 3 do
    voisins := { robot = t.(i); autres_robots = cfg.autres_robots } :: !voisins
  done;
  (* On déplace un des autres robots *)
  let traite_autre (rlig, rcol) =
    let autres_immobiles = exclure cfg.autres_robots (rlig, rcol) in
    let t = deplacements_robots (rlig, rcol) (inserer autres_immobiles cfg.robot) in
    for i = 0 to 3 do
      voisins := { robot = cfg.robot; autres_robots = inserer autres_immobiles t.(i) } :: !voisins
    done;
  in List.iter traite_autre cfg.autres_robots;
  (* Printf.printf "VOISINS\n"; List.iter affiche_config !voisins; Printf.printf "FIN VOISINS\n"; *)
  !voisins
;;

(* résolution avec un parcours en largeur : 
   sans affichage du chemin vers la config gagnante *)
let resol_largeur0 (cfg0:config) =
  let gagne = ref false in
  let dico = Hashtbl.create 1000 in (* association config -> () *)
  let file = Queue.create () in
  Hashtbl.add dico cfg0 ();
  Queue.add cfg0 file;
  while not !gagne && not (Queue.is_empty file) do
    let cfg = Queue.take file in 
    let voisins = config_voisines cfg in
    let traite_voisin v =
      if not (Hashtbl.mem dico v) then begin
        Hashtbl.add dico v ();
        Queue.add v file
      end;
      if v.robot = (14,3) then begin
        gagne := true;
        Printf.printf "Gagné !"
      end
    in List.iter traite_voisin voisins
  done;
  if (not !gagne) then Printf.printf "Pas de solution"
;;

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

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

(* résolution avec un parcours en largeur : 
   avec affichage des configurations menant à la config gagnante la plus proche *)
let resol_largeur (cfg0:config) =
  let gagne = ref false in
  let dico = Hashtbl.create 1000 in (* association config -> config pere *)
  let file = Queue.create () in
  Hashtbl.add dico cfg0 cfg0;
  Queue.add cfg0 file;
  while not !gagne && not (Queue.is_empty file) do
    let cfg = Queue.take file in 
    let voisins = config_voisines cfg in
    let traite_voisin v =
      if not (Hashtbl.mem dico v) then begin
        Hashtbl.add dico v cfg;
        Queue.add v file
      end;
      if v.robot = (14,3) then begin
        gagne := true;
        (* remontée *)
        let rec remonte cfg =
          let pere = Hashtbl.find dico cfg in
          if pere <> cfg0 then begin
            remonte pere;
            affiche_config pere
          end
        in affiche_config cfg0; remonte v; affiche_config v
      end
    in List.iter traite_voisin voisins
  done;
  if (not !gagne) then Printf.printf "Pas de solution"
;;

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