diff options
author | Trygve Laugstøl <trygvis@inamo.no> | 2024-02-23 07:08:18 +0100 |
---|---|---|
committer | Trygve Laugstøl <trygvis@inamo.no> | 2024-02-23 07:08:18 +0100 |
commit | 5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e (patch) | |
tree | 982ca2e7f9ac4e8c350dfb5c4f60bcfdfff5afaf /learn-you-some-erlang/road.erl | |
parent | 05ae56e5e89abf2993f84e6d52b250131f247c35 (diff) | |
download | erlang-workshop-5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e.tar.gz erlang-workshop-5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e.tar.bz2 erlang-workshop-5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e.tar.xz erlang-workshop-5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e.zip |
wip
Diffstat (limited to 'learn-you-some-erlang/road.erl')
-rw-r--r-- | learn-you-some-erlang/road.erl | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/learn-you-some-erlang/road.erl b/learn-you-some-erlang/road.erl new file mode 100644 index 0000000..fa34f5a --- /dev/null +++ b/learn-you-some-erlang/road.erl @@ -0,0 +1,39 @@ +-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(). + +%% 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)}. |