1. (* Ricochet Robots - partie 3 *)
  2.  
  3. (* Correction partie 2 - ce qui sera utile pour la partie 3 *)
  4.  
  5. let obs_l = [| [|0; 4; 10; 16|]; [|0; 14; 16|]; [|0; 6; 16|];
  6. [|0; 9; 16|]; [|0; 3; 15; 16|]; [|0; 7; 16|]; [|0; 1; 12; 16|]; [|0; 7; 9; 16|];
  7. [|0; 7; 9; 16|]; [|0; 4; 13; 16|]; [|0; 6; 16|]; [|0; 10; 16|]; [|0; 8; 16|];
  8. [|0; 2; 15; 16|]; [|0; 4; 10; 16|]; [|0; 5; 12; 16|] |];;
  9.  
  10. let obs_c = [| [|0; 5; 11; 16|]; [|0; 6; 13; 16|]; [|0; 4; 16|];
  11. [|0; 15; 16|]; [|0; 10; 16|]; [|0; 3; 16|]; [|0; 10; 16|]; [|0; 6; 7; 9; 12; 16|];
  12. [|0; 7; 9; 16|]; [|0; 3; 12; 16|]; [|0; 14; 16|]; [|0; 16|]; [|0; 7; 16|];
  13. [|0; 2; 10; 16|]; [|0; 4; 13; 16|]; [|0; 2; 12; 16|] |];;
  14.  
  15. let dichotomie a t =
  16. let i = ref 0 in (* inclus *)
  17. let j = ref (Array.length t) in (* exclu *)
  18. while (!j - !i > 1) do
  19. let m = (!i + !j) / 2 in
  20. if t.(m) > a then j := m else i := m
  21. done; !i;;
  22.  
  23. let deplacements_grille (a,b) =
  24. let imurG = dichotomie b obs_l.(a) in
  25. let imurH = dichotomie a obs_c.(b) in
  26. [| (a,obs_l.(a).(imurG)); (* ouest : même ligne, mur Gauche *)
  27. (a,obs_l.(a).(imurG+1)-1); (* est : même ligne, mur Droit -1 *)
  28. (obs_c.(b).(imurH),b); (* nord : mur Haut, même colonne *)
  29. (obs_c.(b).(imurH+1)-1,b)|];; (* sud : mur Bas -1, même colonne *)
  30.  
  31. let matrice_deplacements () =
  32. let m = Array.make_matrix 16 16 [||] in
  33. for i = 0 to 15 do
  34. for j = 0 to 15 do
  35. m.(i).(j) <- deplacements_grille (i,j)
  36. done
  37. done;
  38. m;;
  39.  
  40. let mat_depl = matrice_deplacements ();;
  41.  
  42. let modif t (a,b) (c,d) =
  43. if (a = c && b < d) then (* gene à l'est ? *)
  44. let (x,y) = t.(1) in
  45. t.(1) <- (x , min y (d-1))
  46. else if (a = c && b > d) then (* gene à l'ouest ? *)
  47. let (x,y) = t.(0) in
  48. t.(0) <- (x, max y (d+1))
  49. else if (b = d && a > c) then (* gene au nord ? *)
  50. let (x,y) = t.(2) in
  51. t.(2) <- (max x (c+1), y)
  52. else if (b = d && a < c) then (* gene au sud ? *)
  53. let (x,y) = t.(3) in
  54. t.(3) <- (min x (c-1), y)
  55. ;;
  56.  
  57. (* calcule les 4 déplacements possibles pour le robot (a,b) en fonction de la liste des autres robots *)
  58. let deplacements_robots (a,b) q =
  59. let t = Array.copy mat_depl.(a).(b) in (* les deplacements sans gene *)
  60. List.iter (fun (c,d) -> modif t (a,b) (c,d)) q; t;; (* modification pour chaque robot *)
  61.  
  62.  
  63. (* Partie 3 : on démarre ici ! *)
  64.  
  65. (* Fonctions utiles *)
  66. let rec inserer liste x =
  67. (* insere x dans une liste triée par ordre croissant.
  68. renvoie une nouvelle liste *)
  69. failwith "A faire"
  70. ;;
  71.  
  72. let rec exclure liste x =
  73. (* exclure x d'une liste, supposé présent.
  74. renvoie une nouvelle liste *)
  75. failwith "A faire"
  76. ;;
  77.  
  78. (* Une configuration du jeu.
  79. robot : robot principal
  80. autres_robots : liste maintenue triée *)
  81. type config = { robot : int * int; autres_robots : (int * int) list }
  82.  
  83. let affiche_config cfg =
  84. Printf.printf "robot:(%d,%d) autres:" (fst cfg.robot) (snd cfg.robot);
  85. List.iter (fun (x,y) -> Printf.printf "(%d,%d)" x y ) cfg.autres_robots;
  86. print_newline ()
  87. ;;
  88.  
  89. (* calcul des 16 configurations voisines *)
  90. let config_voisines cfg =
  91. failwith "A faire"
  92. ;;
  93.  
  94. (* résolution avec un parcours en largeur *)
  95. let resol_largeur (cfg0:config) =
  96. let gagne = ref false in
  97. (* A COMPLETER *)
  98. if (not !gagne) then Printf.printf "Pas de solution\n"
  99. ;;
  100.  
  101. Printf.printf "configuration facile:\n";
  102. resol_largeur {robot = (5,12); autres_robots = [(0,7);(3,1);(4,0)]};;
  103.  
  104. Printf.printf "configuration initiale:\n";
  105. resol_largeur {robot = (5,12); autres_robots = [(0,0);(2,1);(4,7)]};;
  106.