Estás en un avión que aterrizará en el aeropuerto de Heathrow en las próximas horas. Tienes que llegar a Londres lo más rápido posible; tu tío rico se está muriendo y quieres ser el primero en llegar para reclamar su herencia.
Hay dos carreteras que van de Heathrow a Londres y un montón de calles más pequeñas que las unen. Debido a los límites de velocidad y al tráfico habitual, algunas partes de las carreteras y calles más pequeñas requieren más tiempo que otras. Antes de aterrizar, decides maximizar tus posibilidades encontrando el camino óptimo hacia su casa. Aquí tienes el mapa que has encontrado en tu portátil:
Un pequeño mapa con una carretera principal 'A' con 4 segmentos de longitud 50, 5, 40 y 10, B con 4 segmentos de longitud 10, 90, 2 y 8, donde cada uno de estos segmentos está unido por caminos 'X' de longitud 30, 20, 25 y 0.
Para que te resulte más fácil trabajar con el mapa, ingresas los datos de la siguiente manera en un archivo llamado road.txt:
50
10
30
5
90
20
40
2
25
10
8
0
La carretera está trazada según el siguiente patrón: A1, B1, X1, A2, B2, X2, ..., An, Bn, Xn, donde X es una de las carreteras que une el lado A con el lado B del mapa. Insertamos un 0 como último segmento X, porque no importa lo que hagamos, ya estamos en nuestro destino. Los datos probablemente se puedan organizar en tuplas de 3 elementos (triples) de la forma {A,B,X}.
Al escribir una función recursiva, lo primero que hay que hacer es encontrar nuestro caso base. Para nuestro problema en cuestión, esto sería si tuviéramos solo una tupla para analizar, es decir, si solo tuviéramos que elegir entre A, B (y cruzar X, que en este caso es inútil porque estamos en el destino)
Entonces la elección es solo entre elegir cuál de los caminos A o B es el más corto. Si has aprendido bien la recursión, sabes que debemos intentar converger hacia el caso base. Esto significa que en cada paso que daremos, querremos reducir el problema a elegir entre A y B para el siguiente paso.
Extendamos nuestro mapa y comencemos de nuevo:
Camino A: 5, 10. Camino B: 1, 15. Camino de cruce X: 3.
¡Ah! ¡Se pone interesante! ¿Cómo podemos reducir la triple {5,1,3} a una elección estricta entre A y B? Veamos cuántas opciones son posibles para A. Para llegar a la intersección de A1 y A2 (lo llamaré el punto A1), puedo tomar la carretera A1 directamente (5), o venir desde B1 (1) y luego cruzar X1 (3). En este caso, la primera opción (5) es más larga que la segunda (4). Para la opción A, el camino más corto es [B, X]. Entonces, ¿cuáles son las opciones para B? Puedes proceder desde A1 (5) y luego cruzar X1 (3), o tomar estrictamente el camino B1 (1).
Lo que tenemos es una longitud 4 con el camino [B, X] hacia la primera intersección A y una longitud 1 con el camino [B] hacia la intersección de B1 y B2. Entonces tenemos que decidir qué elegir entre ir al segundo punto A (la intersección de A2 y el punto final o X2) y al segundo punto B (intersección de B2 y X2). Para tomar una decisión, sugiero que hagamos lo mismo que antes.
Todos los caminos posibles a tomar en este caso se pueden encontrar de la misma manera que en el caso anterior. Podemos llegar al siguiente punto A tomando el camino A2 desde [B, X], que nos da una longitud de 14 (14 = 4 + 10), o tomando B2 y luego X2 desde [B], que nos da una longitud de 16 (16 = 1 + 15 + 0). En este caso, el camino [B, X, A] es mejor que [B, B, X].
El mismo dibujo que el anterior, pero con los caminos dibujados encima.
También podemos llegar al siguiente punto B tomando el camino A2 desde [B, X] y luego cruzando X2 por una longitud de 14 (14 = 4 + 10 + 0), o tomando la carretera B2 desde [B] por una longitud de 16 (16 = 1 + 15). Aquí, el mejor camino es elegir la primera opción, [B, X, A, X].
Entonces, cuando todo este proceso está hecho, nos quedan dos caminos, A o B, ambos de longitud 14. Cualquiera de ellos es el correcto. La última selección siempre tendrá dos caminos de la misma longitud, dado que el último segmento X tiene una longitud 0. Al resolver nuestro problema de forma recursiva, nos hemos asegurado de obtener siempre el camino más corto al final. No está mal, ¿verdad?
Teníamos listo el archivo que vamos a introducir como entrada. Para realizar manipulaciones de archivos, el módulo de archivos es nuestra mejor herramienta. Contiene muchas funciones comunes a muchos lenguajes de programación para trabajar con los archivos (establecer permisos, mover archivos, renombrarlos y eliminarlos, etc.)
También contiene las funciones habituales para leer y/o escribir desde archivos, como: file:open/2 y file:close/1 para hacer lo que dicen sus nombres (¡abrir y cerrar archivos!), file:read/2 para obtener el contenido de un archivo (ya sea como cadena o binario), file:read_line/1 para leer una sola línea, file:position/3 para mover el puntero de un archivo abierto a una posición determinada, etc.
También hay un montón de funciones de acceso directo, como file:read_file/1 (abre y lee el contenido como binario), file:consult/1 (abre y analiza un archivo como términos de Erlang) o file:pread/2 (cambia una posición y luego lee) y pwrite/2 (cambia la posición y escribe el contenido).
Con todas estas opciones disponibles, será fácil encontrar una función para leer nuestro archivo road.txt. Como sabemos que nuestra carretera es relativamente pequeña, llamaremos a file:read_file("road.txt").':
1> {ok, Binary} = file:read_file("road.txt").
{ok,<<"50\r\n10\r\n30\r\n5\r\n90\r\n20\r\n40\r\n2\r\n25\r\n10\r\n8\r\n0\r\n">>}
2> S = string:tokens(binary_to_list(Binary), "\r\n\t ").
["50","10","30","5","90","20","40","2","25","10","8","0"]
Tenga en cuenta que en este caso, agregué un espacio (" ") y una tabulación ("\t") a los tokens válidos, por lo que el archivo también podría haberse escrito en el formato "50 10 30 5 90 20 40 2 25 10 8 0". Dada esa lista, necesitaremos transformar las cadenas en números enteros. Usaremos un método similar al que usamos en nuestra calculadora RPN:
3> [list_to_integer(X) || X <- S].
[50,10,30,5,90,20,40,2,25,10,8,0]
Comencemos un nuevo módulo llamado road.erl y escribamos esta lógica:
-module(road).
-compile(export_all).
main() ->
File = "road.txt",
{ok, Bin} = file:read_file(File),
parse_map(Bin).
parse_map(Bin) when is_binary(Bin) ->
parse_map(binary_to_list(Bin));
parse_map(Str) when is_list(Str) ->
[list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")].
La función main/0 es aquí la responsable de leer el contenido del archivo y pasarlo a parse_map/1. Debido a que utilizamos la función file:read_file/1 para obtener el contenido de road.txt, el resultado que obtenemos es un binario. Por este motivo, he hecho que la función parse_map/1 coincida tanto con listas como con binarios. En el caso de un binario, simplemente llamamos a la función nuevamente con la cadena convertida en una lista (nuestra función para dividir la cadena funciona solo con listas).
El siguiente paso para analizar el mapa sería reagrupar los datos en la forma {A,B,X} descrita anteriormente. Lamentablemente, no existe una forma genérica simple de extraer elementos de una lista de a 3 por vez, por lo que tendremos que hacer una coincidencia de patrones en una función recursiva para hacerlo:
group_vals([], Acc) ->
lists:reverse(Acc);
group_vals([A,B,X|Rest], Acc) ->
group_vals(Rest, [{A,B,X} | Acc]).
Esa función funciona de manera recursiva estándar; no hay nada demasiado complejo en juego aquí. Solo tendremos que llamarla modificando un poco parse_map/1:
parse_map(Bin) when is_binary(Bin) ->
parse_map(binary_to_list(Bin));
parse_map(Str) when is_list(Str) ->
Values = [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")],
group_vals(Values, []).
Si intentamos compilarlo todo, ahora deberíamos tener una carretera que tenga sentido:
1> c(road).
{ok,road}
2> road:main().
[{50,10,30},{5,90,20},{40,2,25},{10,8,0}]
Ah, sí, eso parece correcto. Obtenemos los bloques que necesitamos para escribir nuestra función que luego encajará en un pliegue. Para que esto funcione, es necesario encontrar un buen acumulador.
Para decidir qué usar como acumulador, el método que me parece más fácil de usar es imaginarme a mí mismo en medio del algoritmo mientras se ejecuta. Para este problema específico, imaginaré que actualmente estoy tratando de encontrar el camino más corto del segundo triple ({5,90,20}). Para decidir cuál es el mejor camino, necesito tener el resultado del triple anterior. Afortunadamente, sabemos cómo hacerlo, porque no necesitamos un acumulador y ya tenemos toda esa lógica. Entonces, para A:
Y tomemos el más corto de estos dos caminos. Para B, fue similar:
Ahora sabemos que el mejor camino actual que viene de A es [B, X]. También sabemos que tiene una longitud de 40. Para B, el camino es simplemente [B] y la longitud es 10. Podemos usar esta información para encontrar los siguientes mejores caminos para A y B volviendo a aplicar la misma lógica, pero contando los anteriores en la expresión. El otro dato que necesitamos es el camino recorrido para poder mostrárselo al usuario. Dado que necesitamos dos caminos (uno para A y otro para B) y dos longitudes acumuladas, nuestro acumulador puede tomar la forma {{DistanciaA, CaminoA}, {DistanciaB, CaminoB}}. De esa manera, cada iteración del pliegue tiene acceso a todo el estado y lo construimos para mostrárselo al usuario al final.
Esto nos da todos los parámetros que necesitará nuestra función: los triples {A,B,X} y un acumulador de la forma {{DistanciaA,RutaA}, {DistanciaB,RutaB}}.
Para obtener nuestro acumulador, podemos introducir esto en el código de la siguiente manera:
shortest_step({A,B,X}, {{DistA,PathA}, {DistB,PathB}}) ->
OptA1 = {DistA + A, [{a,A}|PathA]},
OptA2 = {DistB + B + X, [{x,X}, {b,B}|PathB]},
OptB1 = {DistB + B, [{b,B}|PathB]},
OptB2 = {DistA + A + X, [{x,X}, {a,A}|PathA]},
{erlang:min(OptA1, OptA2), erlang:min(OptB1, OptB2)}.
Aquí, OptA1 obtiene la primera opción para A (pasando por A), OptA2 la segunda (pasando por B y luego por X). Las variables OptB1 y OptB2 reciben un tratamiento similar para el punto B. Finalmente, devolvemos el acumulador con las rutas obtenidas.
Sobre las rutas guardadas en el código anterior, tenga en cuenta que decidí usar la forma [{x, X}] en lugar de [x] por la sencilla razón de que podría ser bueno para el usuario saber la longitud de cada segmento. La otra cosa que estoy haciendo es que estoy acumulando las rutas hacia atrás ({x, X} viene antes de {b, B}). Esto se debe a que estamos en un pliegue, que es recursivo de cola: toda la lista se invierte, por lo que es necesario poner el último recorrido antes de los demás.
Finalmente, uso erlang:min/2 para encontrar la ruta más corta. Puede sonar extraño usar una función de comparación de este tipo en tuplas, pero recuerde que cada término de Erlang se puede comparar con cualquier otro. Como la longitud es el primer elemento de la tupla, podemos ordenarlos de esa manera.
Lo que queda por hacer es colocar esa función en un pliegue:
optimal_path(Map) ->
{A,B} = lists:foldl(fun shortest_step/2, {{0,[]}, {0,[]}}, Map),
{_Dist,Path} = if hd(element(2,A)) =/= {x,0} -> A;
hd(element(2,B)) =/= {x,0} -> B
end,
lists:reverse(Path).
Al final del pliegue, ambas rutas deberían terminar teniendo la misma distancia, excepto que una pasa por el segmento final {x,0}. El if observa el último elemento visitado de ambas rutas y devuelve el que no pasa por {x,0}. Elegir la ruta con la menor cantidad de pasos (comparar con length/1) también funcionaría. Una vez que se ha seleccionado la más corta, se invierte (se construyó de manera recursiva de cola; debe invertirla). Luego puede mostrarla al mundo o mantenerla en secreto y obtener la herencia de su tío rico. Para hacer eso, debe modificar la función principal para llamar a optimal_path/1. Luego se puede compilar.
main() ->
File = "road.txt",
{ok, Bin} = file:read_file(File),
optimal_path(parse_map(Bin)).
¡Mira! ¡Tenemos la respuesta correcta! ¡Buen trabajo!
1> c(road).
{ok,road}
2> road:main().
[{b,10},{x,30},{a,5},{x,20},{b,2},{b,8}]
O, para decirlo de forma visual:
El camino más corto, pasando por [b,x,a,x,b,b]
Pero, ¿sabes qué sería realmente útil? Poder ejecutar nuestro programa desde fuera del shell de Erlang. Tendremos que cambiar nuestra función principal nuevamente:
main([FileName]) ->
{ok, Bin} = file:read_file(FileName),
Map = parse_map(Bin),
io:format("~p~n",[optimal_path(Map)]),
erlang:halt().
La función principal ahora tiene una aridad de 1, necesaria para recibir parámetros desde la línea de comandos. También he añadido la función erlang:halt/0, que apagará la máquina virtual Erlang después de ser llamada. También he envuelto la llamada a optimal_path/1 en io:format/2 porque esa es la única forma de tener el texto visible fuera del shell de Erlang.
Con todo esto, tu archivo road.erl ahora debería verse así:
-module(road).
-compile(export_all).
main([FileName]) ->
{ok, Bin} = file:read_file(FileName),
Map = parse_map(Bin),
io:format("~p~n",[optimal_path(Map)]),
erlang:halt(0).
%% Transform a string into a readable map of triples
parse_map(Bin) when is_binary(Bin) ->
parse_map(binary_to_list(Bin));
parse_map(Str) when is_list(Str) ->
Values = [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")],
group_vals(Values, []).
group_vals([], Acc) ->
lists:reverse(Acc);
group_vals([A,B,X|Rest], Acc) ->
group_vals(Rest, [{A,B,X} | Acc]).
%% Picks the best of all paths, woo!
optimal_path(Map) ->
{A,B} = lists:foldl(fun shortest_step/2, {{0,[]}, {0,[]}}, Map),
{_Dist,Path} = if hd(element(2,A)) =/= {x,0} -> A;
hd(element(2,B)) =/= {x,0} -> B
end,
lists:reverse(Path).
%% actual problem solving
%% change triples of the form {A,B,X}
%% where A,B,X are distances and a,b,x are possible paths
%% to the form {DistanceSum, PathList}.
shortest_step({A,B,X}, {{DistA,PathA}, {DistB,PathB}}) ->
OptA1 = {DistA + A, [{a,A}|PathA]},
OptA2 = {DistB + B + X, [{x,X}, {b,B}|PathB]},
OptB1 = {DistB + B, [{b,B}|PathB]},
OptB2 = {DistA + A + X, [{x,X}, {a,A}|PathA]},
{erlang:min(OptA1, OptA2), erlang:min(OptB1, OptB2)}.
Y ejecutando el código:
$ erlc road.erl
$ erl -noshell -run road main road.txt
[{b,10},{x,30},{a,5},{x,20},{b,2},{b,8}]
¡Y sí, es correcto! Es prácticamente todo lo que necesitas hacer para que las cosas funcionen. Puedes crear un archivo bash/batch para encapsular la línea en un solo ejecutable, o puedes consultar el script para obtener resultados similares.
