From 5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e Mon Sep 17 00:00:00 2001
From: Trygve Laugstøl <trygvis@inamo.no>
Date: Fri, 23 Feb 2024 07:08:18 +0100
Subject: wip

---
 learn-you-some-erlang/road.erl | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)
 create mode 100644 learn-you-some-erlang/road.erl

(limited to 'learn-you-some-erlang/road.erl')

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)}.
-- 
cgit v1.2.3