(* Chèvres et moutons *)
			(* version affichage texte *)

let n=7;; (* effectif des troupeaux *)

(* on initialise le chemin *)
let chemin = String.make (2*n+5) '_';;
let initialise()=
	for k=1 to n do
		chemin.[k+1]<-'C';
		chemin.[n+k+2]<-'M'
	done;
	chemin.[0] <- '_';
	chemin.[1] <- '_';
	chemin.[n+2] <- '_';
	chemin.[2*n+3] <- '_';
	chemin.[2*n+4] <- '_';
;;

(* la commande montre() affiche l'état du chemin *)
let montre() = print_string (chemin);print_newline() ;;

(* quand bouge sera invoqué, la case b sera vide, mais éventuellement elle 
sera hors du chemin *)
let bouge chemin a b =
   if (b>=0 & b<=(2*n+4))
   then (chemin.[b] <- chemin.[a];
         chemin.[a] <- '_';
         montre())
   else if (a>=0 & a<=(2*n+4))
        then (chemin.[a] <- '_'; montre())
;;

(* "tout se passe ici" dans cette paire de commandes récursives *)
let rec sauter_fait p i j=
    if p=1
    then (bouge chemin i (i+1); bouge chemin j (j-2))
    else begin
           fait_sauter (p-1) (i+1) (j-1);
           bouge chemin i (i+1);
           let k=ref (i+2) in while !k<=j do begin
                                               bouge chemin !k (!k-2);
                                               k:=!k+2
                                             end done
         end
and
    fait_sauter p i j=
    if p=1
    then (bouge chemin j (j-1); bouge chemin i (i+2))
    else begin
           sauter_fait (p-1) (i+1) (j-1);
           bouge chemin j (j-1);
           let k=ref (j-2) in while !k>=i do begin
                                               bouge chemin !k (!k+2);
                                               k:=!k-2
                                             end done
         end
;;

(* evacue_droite et les autres ne servent qu'au départ des troupeaux *)
let evacue_droite()=
    for k=1 to 3 do bouge chemin (2*n+1+k) (2*n+k+2) done
;;

let evacue_gauche p=
    for k = p downto 0 do bouge chemin k (k-1) done
;;

let au_revoir() =
    evacue_droite();
    for l=1 to (n-1) do
                      for k=1 to l do
                                    bouge chemin (2*(n-l+k)) (2*(n-l+k)+2);
                                    evacue_droite()
                                   done
                    done;
    for l=1 to n do evacue_gauche (1+2*l) done
;;


let tout()=
	initialise();
    	montre();
    	fait_sauter n 2 (2*n+2);
	au_revoir()
;;