\documentclass{tp-caml}

\tp{
  title=Petit Poucet dans le métro parisien,
  number=1er ENS,
  date=Lundi 27 mai,
  class=MP1
}

\begin{document}

\begin{abstract}
\begin{flushright}
"There must be some way out of here," said the joker to the thief,\\
"There's too much confusion, I can't get no relief."\\
-- Extrait de la chanson "All along the watchtower" de B. Dylan --
\end{flushright}
\end{abstract}
\begin{corpus}
\section{Petit Poucet dans son labyrinthe}
Dans toute cette section un labyrinthe c'est un string vect. '\#' représente un obstacle, '.' représente un chemin. Par exemple :
\begin{caml}
let laby = [|
"######";
".....#";
"###..#";
"#..#..";
"#.#..#";
"..##.#";
".#####"
 |];;
\end{caml}
est un labyrinthe.

\subsection{DFS :: Depth-first search}
Voici un algorithme assez simple pour parcourir le labyrinthe :
\begin{verbatim}
DFS(case laby)
    Si la case n'a pas déjà été marquée
        marquer la case
        Pour chacune des cases voisines
            DFS(voisine)
\end{verbatim}

\begin{exo}
Programmer l'algorithme du DFS.
\end{exo}
\begin{solc}
let rec dfs (x,y) = 
  let vois = it_list 
    (fun ac (x,y) -> try (laby.(y).[x] ; (x,y)::ac) with |_ -> ac)
    []  [(x-1,y);(x+1,y);(x,y+1);(x,y-1)] in
  if laby.(y).[x] = `.` then
    begin
      laby.(y).[x] <- `v` ;
      do_list dfs vois ;
    end
;;
\end{solc}

\begin{exo}
Programmer un algorithme qui donne le nombre de cases accessible depuis une certaine case.
\end{exo}
\begin{solc}
let accessible (x,y) (x',y') laby = 
  dfs (x,y) laby ;
  laby.(y).[x]=`v`
\end{solc}

\subsection{BFS :: Breadth-first search}
Cette fois-ci, on ne s'intéresse plus seulement à savoir s'il existe un chemin mais à trouver le plus court chemin.

\begin{exo}
Écrire un programme qui étant donné les cases à distance $n$ et les cases marquées déjà vues, donne les cases à distance $n+1$ et écrit dans un tableau pour chaque case à distance $n+1$ une case voisine à distance $n$.
\end{exo}
\begin{solc}
let do_dist_n laby prec dn = 
  let do_case c = 
    let vois = vois laby c in
    do_list (fun (x,y) -> laby.(y).[x] <- `m` ; prec.(y).(x) <- c) vois ;
    vois
  in
  flat_map do_case dn
;;

let rec do_dist laby c prec = 
  let a = do_dist_n laby prec c in
  if a <> []
  then do_dist laby a prec
;;
\end{solc}

\begin{exo}
En déduire un programme qui affiche le plus court chemin entre deux points du labyrinthe.
\end{exo}
\begin{solc}
let plus_court laby c1 (x,y) = 
  let p = (make_matrix (vect_length laby) (vect_length laby) (0,0)) in
  let rec remonte (x,y) = 
    if (x,y) = c1 
    then []
    else (x,y)::(print_int x ; print_string " " ; print_int y ; print_string "\n"; remonte p.(y).(x))
  in
  do_dist laby [c1] p ;
  remonte (x,y)
;;
\end{solc}

\section{Métro parisien}
\subsection{DFS dans le metro parisien}
\begin{exo}
Récupérer le fichier def.ml sur internet
\end{exo}

\begin{exod}
Essayer de comprendre la fonction traduit
\end{exod}

\begin{exo}
Écrire, en utilisant traduit, une fonction int\_ligne, qui transforme une ligne où les stations sont des string, en ligne où les stations sont des int.
\end{exo}
\begin{solc}
let int_lignes = map (fun x-> map traduit x) lignes ;;
\end{solc}
\begin{exo}
Définir metro, un int list vect. Dans la $i$ ième case on mets la liste des voisins de $i$ sur le plan de metro.
\end{exo}
\begin{solc}
let metro = 
  let graphe = make_vect (!nb_trad+1) [] in
  
  let rec aj_ligne  = function
    | [] -> ()
    | [a] -> ()
    | a :: ( t :: q) -> graphe.(a) <- t::graphe.(a) ; aj_ligne (t::q)
  in
  
  do_list aj_ligne int_lignes ;
  graphe
;;
\newpage
\end{solc}

\begin{exod}
Écrire une fonction qui renvoie le plus court chemin entre deux stations données.
\end{exod}
\begin{solc}
exception Pas_de_chemin ;;

let bfs graphe depart arrivee = 
  
  let prec = make_vect (vect_length graphe) (-1) in

  let d = make_vect (vect_length graphe) 1000000 in
  
  let rec foo dist suiv = function 
    | [] -> 
      if suiv <> []
      then foo (dist+1) [] suiv
      else raise Pas_de_chemin
    | a::q -> 
      if a = arrivee 
      then dist
      else
        foo dist (it_list (fun x y -> if d.(y) = 1000000 
        							  then (d.(y) <- dist+1 ; prec.(y) <- a ; y::x) 
        							  else x) suiv graphe.(a)) q
  in
  d.(depart) <- 0 ;
  let dist = foo 0 [] [depart] in
  let rec remonte x l = if x = -1 then l else remonte (prec.(x)) (recupere x::l) in
  (dist,remonte arrivee [])
;;
\end{solc}
\begin{exo}
Comment aller :
\begin{itemize}
\item de Rambuteau  à Chemin Vert ?
\item de Charonne   à Lozere, ecole Polytechnique ?
\item de Luxembourg à Lozere, ecole Polytechnique ?
\item de Luxembourg à Bagneux ?
\item de Luxembourg à nulle part ?
\end{itemize}
\end{exo}
\begin{sol}
.
\newpage
\begin{verbatim}

- : int * string list =
 4,
 ["Rambuteau"; "Hotel de Ville"; "Saint Paul, Le Marais"; "Bastille";
  "Chemin Vert"]
- : int * string list =
 18,
 ["Charonne"; "Rue des Boulets"; "Nation"; "Gare de Lyon";
  "Maison-Alfort, Alfortville"; "Le Vert de Maisons"; "Villeneuve-Prairie";
  "Villeneuve-Triage"; "Villeneuve-Saint-Georges"; "Juvisy-sur-Orge";
  "Savigny-sur-Orge"; "Petit-Vaux"; "Gravigny-Balizy"; "Chilly-Mazarin";
  "Longjumeau"; "Massy-Palaiseau"; "Palaiseau"; "Palaiseau-Villebon";
  "Lozere, ecole Polytechnique"]
- : int * string list =
 16,
 ["Luxembourg"; "Port Royal"; "Denfert Rochereau"; "Cite Universitaire";
  "Gentilly"; "Bagneux"; "Bourg-la-Reine"; "Parc de Sceaux";
  "Croix de Berny"; "Antony"; "Fontaine Michalon"; "Les Baconnets";
  "Massy-Verrieres"; "Massy-Palaiseau"; "Palaiseau"; "Palaiseau-Villebon";
  "Lozere, ecole Polytechnique"]
- : int * string list =
 5,
 ["Luxembourg"; "Port Royal"; "Denfert Rochereau"; "Cite Universitaire";
  "Gentilly"; "Bagneux"]
#Uncaught exception: Pas_de_chemin
\end{verbatim}
\end{sol}
.\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\
\\

\end{corpus}
\end{document}
	
