Principal

Red de Metro

A continuación muestro el enunciado de un ejercicio práctico bastante útil para practicar CAML, consiste en lo siguiente:

Se dispone de una red de metro con las siguientes líneas bidireccionales:

La Red de Metro se codifica como una lista de tuplas cuyo primer elemento es el número de la línea y el segundo elemento es la lista formada por las estaciones de la línea, en concreto para el ejemplo:

[(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

(2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

(3,["Est_C";"Est_F";"Est_E";"Est_G";;"Est_K";"Est_M";"Est_P"]);

(4,["Est_I";"Est_H";"Est_L";"Est_Q"])]

Se pide codificar una función en CAML que a partir de la red de metro, una estación de origen y una estación de destino, muestre todos los trayectos directos entre ambas, sin efectuar transbordos.

Para cada línea en la red de metro, se debe mostrar el par (número de línea, lista de estaciones que forman el trayecto incluyendo el origen y el destino). Si en una determinada línea no hay trayecto posible, se devuelve una lista vacía. Dentro de una línea, puede ocurrir que la estación de destino se encuentre antes o después que la estación de origen. En cualquier caso, las estaciones que componen el trayecto deben aparecer en el orden correcto.

La función pedida sigue el siguiente algoritmo: Buscar en todas las líneas de la Red de Metro las estaciones comprendidas entre la estación de origen y la estación de destino. Considérese que para calcular la lista de estaciones de una línea comprendidas entre la estación de origen y la de destino es conveniente apoyarse en la definición de dos funciones:

  1. La primera devolverá la lista de las estaciones de la línea desde la estación de origen hasta el final de la lista pasada como argumento.

  2. La segunda devolverá la lista de las estaciones comprendidas desde el principio de la lista pasada como argumento hasta la estación de destino.

Seguramente serán necesarias funciones como Concatenar o Invertir.

A continuación se muestran una serie de ejemplos: 
      # RedMetro([(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

      (2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

      (3,["Est_C";"Est_F";"Est_E";"Est_G";;"Est_K";"Est_M";"Est_P"]);

      (4,["Est_I";"Est_H";"Est_L";"Est_Q"])],"Est_A","Est_H");;

      -:(int * string list )list = [1,[] ; 2,[] ; 3,[]; 4,[] ]

      # RedMetro([(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

      (2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

      (3,["Est_C";"Est_F";"Est_E";"Est_G";"Est_K";"Est_M";"Est_P"]);

      (4,["Est_I";"Est_H";"Est_L";"Est_Q"])],"Est_F","Est_K");;

      -:(int * string list)list = [1,[]; 2,[]; 3,["Est_F";"Est_E";"Est_G";"Est_K"]; 4,[]]

      # RedMetro([(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

      (2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

      (3,["Est_C";"Est_F";"Est_E";"Est_G";"Est_K";"Est_M";"Est_P"]);

      (4,["Est_I";"Est_H";"Est_L";"Est_Q"])],"Est_J","Est_A");;

      -:(int * string list)list = [1,["Est_J";"Est_G";"Est_D";"Est_A"]; 2,[]; 3,[]; 4,[]]

      # RedMetro([(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

      (2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

      (3,["Est_C";"Est_F";"Est_E";"Est_G";"Est_K";"Est_M";"Est_P"]);

      (4,["Est_I";"Est_H";"Est_L";"Est_Q"])],"Est_E","Est_M");;

      -:(int * string list)list = [1,[]; 2,["Est_E";"Est_J";"Est_M"]; 3,["Est_E";"Est_G";"Est_K";"Est_M"]; 4,[]]

El código de la solución será el siguiente: 
(* Función recursiva para invertir una lista *)
let rec rev = function ([],y) -> y | (x,y) -> rev(tl(x),hd(x)::y);;


(* Función recursiva para concatenar dos listas *)
let rec append = function (x,[]) -> rev(x,[]) | (x,y) -> rev(append(rev(hd(y)::rev(x,[]),[]),tl(y)),[]);;


(* Función para buscar un elemento en una lista (la devuelve troceada en dos listas) *)
let rec buscar = function (x,[],ele) -> (x,[]) | (x,y,ele) -> if 
ele=hd(y) then (x,y) else buscar(append(x,[hd(y)]),tl(y),ele);;


(* Función para saber si un elemento esta contenido en una lista *)
let rec contenido = function ([],y) -> false | (x,y) -> if y=hd(x) 
then true else contenido(tl(x),y);;


(* Función para saber si tanto la estación de origen como la de destino están en una línea *)
let ambas = function (x,y,z) -> if contenido(x,y)=true && contenido(x,z)=true 
then true else false;;


(* Función que recibe la línea y devuelve los trayectos entre las estaciones como listas *)
let interna = function (x,y,z) -> if contenido( snd( buscar([],x,y) ),z )=true
then append(fst(buscar([],snd(buscar([],x,y)),z)),[z])
else append( append([y],fst(buscar([],rev(fst(buscar([],x,y)),[]),z))),[z]);;


(* Función propia que realiza todo el algoritmo *)
let rec resol = function ([],y,z,a) -> a |
(x,y,z,a) -> if ambas(snd(hd(x)),y,z)=true
then resol(tl(x),y,z,append(a,[(fst(hd(x)),interna(snd(hd(x)),y,z))]))
else resol(tl(x),y,z,append(a,[(fst(hd(x)),[])]));;


(* Función principal que llama a una propia que realiza todo el algoritmo *)
let redmetro = function (x,y,z) -> resol(x,y,z,[]);;


			(* Pruebas de funcionamiento del programa *)

  
redmetro([(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

        (2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

        (3,["Est_C";"Est_F";"Est_E";"Est_G";"Est_K";"Est_M";"Est_P"]);

        (4,["Est_I";"Est_H";"Est_L";"Est_Q"])],"Est_A","Est_H");;

      
redmetro([(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

        (2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

        (3,["Est_C";"Est_F";"Est_E";"Est_G";"Est_K";"Est_M";"Est_P"]);

        (4,["Est_I";"Est_H";"Est_L";"Est_Q"])],"Est_F","Est_K");;

      
redmetro([(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

        (2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

        (3,["Est_C";"Est_F";"Est_E";"Est_G";"Est_K";"Est_M";"Est_P"]);

        (4,["Est_I";"Est_H";"Est_L";"Est_Q"])],"Est_L","Est_A");;

      
redmetro([(1,["Est_A";"Est_D";"Est_G";"Est_J";"Est_L";"Est_N";"Est_R"]);

        (2,["Est_B";"Est_E";"Est_J";"Est_M";"Est_0"]);

        (3,["Est_C";"Est_F";"Est_E";"Est_G";"Est_K";"Est_M";"Est_P"]);

        (4,["Est_I";"Est_H";"Est_L";"Est_Q"])],"Est_E","Est_M");;

Para obtener un fichero con el código haga clic aquí.

El enunciados (sin la solución) en formato pdf está aquí.

vidalmb_admin – Jue, 30/03/2006 – 18:48