-module(torch).
-export([main/0]).
astar(Start,Goal) ->
Closedset = sets:new(), % The set of nodes already evaluated.
Openset = sets:add_element(Start,sets:new()), %The set of tentative nodes to be evaluated
Fscore = dict:append(Start, h_score(Start), dict:new()),
Gscore = dict:append(Start, 0, dict:new()), % Distance from start along optimal path.
CameFrom = dict:append(Start, none, dict:new()),
astar_step(Goal, Closedset, Openset, Fscore, Gscore, CameFrom).
astar_step(Goal, Closedset, Openset, Fscore, Gscore, CameFrom) ->
Size = sets:size(Openset),
if
Size =:= 0 ->
failure;
true ->
X = best_step(sets:to_list(Openset), Fscore, none, infinity),
if
X =:= Goal ->
reconstruct_path(CameFrom, Goal);
true ->
NextOpen = sets:del_element(X, Openset),
NextClosed = sets:add_element(X, Closedset),
Neighbours = neighbour_nodes(X),
{NewOpen, NewF, NewG, NewFrom} = scan(X, Neighbours, NextOpen, NextClosed, Fscore, Gscore, CameFrom),
astar_step(Goal, NextClosed, NewOpen, NewF, NewG, NewFrom)
end
end.
scan(_X, [], Open, _Closed, F, G, From) ->
{Open, F, G, From};
scan(X, [Y|N], Open, Closed, F, G, From) ->
Member = sets:is_element(Y, Closed),
if
Member ->
scan(X, N, Open, Closed, F, G, From);
true ->
[G0] = dict:fetch(X, G),
TrialG = G0 + dist_between(X,Y),
IsOpen = sets:is_element(Y, Open),
if
IsOpen ->
[OldG] = dict:fetch(Y, G),
if
TrialG < OldG ->
{NewF, NewG, NewFrom} = update(X, Y, F, G, From, TrialG),
scan(X, N, Open, Closed, NewF, NewG, NewFrom);
true ->
scan(X, N, Open, Closed, F, G, From)
end;
true ->
NewOpen = sets:add_element(Y, Open),
{NewF, NewG, NewFrom} = update(X, Y, F, G, From, TrialG),
scan(X, N, NewOpen, Closed, NewF, NewG, NewFrom)
end
end.
update(X, Y, OldF, OldG, OldFrom, GValue) ->
KeyG = dict:is_key(Y, OldG),
KeyF = dict:is_key(Y, OldF),
KeyFrom = dict:is_key(Y, OldFrom),
if
KeyG ->
update(X, Y, OldF, dict:erase(Y, OldG), OldFrom, GValue);
KeyF ->
update(X, Y, dict:erase(Y, OldF), OldG, OldFrom, GValue);
KeyFrom ->
update(X, Y, OldF, OldG, dict:erase(Y, OldFrom), GValue);
true ->
NewFrom = dict:append(Y, X, OldFrom),
NewG = dict:append(Y, GValue, OldG),
NewF = dict:append(Y, GValue + h_score(Y), OldF), % Estimated total distance from start to goal through y.
{NewF, NewG, NewFrom}
end.
reconstruct_path(CameFrom, Node) ->
[Value] = dict:fetch(Node, CameFrom),
if
none =:= Value ->
[Node];
true ->
[Node | reconstruct_path(CameFrom, Value)]
end.
best_step([H|Open], Score, none, _) ->
[V] = dict:fetch(H, Score),
best_step(Open, Score, H, V);
best_step([], _Score, Best, _BestValue) ->
Best;
best_step([H|Open], Score, Best, BestValue) ->
[Value] = dict:fetch(H, Score),
if
Value < BestValue ->
best_step(Open, Score, H, Value);
true ->
best_step(Open, Score, Best, BestValue)
end.
%% specialize for the torch-carrier problem
%% bits 0-4 represent torch, 1m, 2m, 5m, 10m
%% set bit = on the near side
%% Every possible crossing of one or two
swaps() ->
[3,5,9,17, 7, 11,13, 19,21,25].
crossing_time(Swap) ->
if
Swap band 16 > 0 ->
10;
Swap band 8 > 0 ->
5;
Swap band 4 > 0 ->
2;
true ->
1
end.
%% presentation form
display(Swap) ->
if
Swap band 16 > 0 ->
compound(Swap, 16);
Swap band 8 > 0 ->
compound(Swap, 8);
Swap band 4 > 0 ->
compound(Swap, 4);
Swap band 2 > 0 ->
compound(Swap, 2);
true ->
""
end.
compound(Swap, Bit) ->
string:concat( erlang:integer_to_list(crossing_time(Swap)),
decorate(display(Swap bxor Bit))).
decorate(Value) ->
Length = string:len(Value),
if
Length > 0 ->
string:concat("+", Value);
true ->
Value
end.
neighbour_nodes(X) ->
Result = [],
compatible(X, equivalent_point(X), Result, swaps()).
equivalent_point(X) ->
if
X band 1 > 0 ->
X;
true ->
31 bxor X
end.
compatible(_X, _Y, Outlist, []) ->
Outlist;
compatible(X, Y, Outlist, [Swap|Inlist]) ->
if
(Y band Swap) =:= Swap ->
New = X bxor Swap,
compatible(X, Y, [New|Outlist], Inlist);
true ->
compatible(X, Y, Outlist, Inlist)
end.
dist_between(X,Y) ->
Swap = X bxor Y,
crossing_time(Swap).
h_score(Node) ->
crossing_time(Node).
main() ->
[H|Trace] = lists:reverse(astar(31, 0)),
Time = print_result(Trace, H, 0),
io:format("Time taken = ~B minutes~n", [Time]) .
print_result([], _Prev, Time) ->
Time;
print_result([H|Trace], Prev, Time) ->
Swap = H bxor Prev,
print_swap(Swap, H band 1),
Interval = Time + crossing_time(Swap),
print_result(Trace, H, Interval).
print_swap(Swap, Side) ->
if
Side =:= 0 ->
io:format( " ~s -->~n", [display(Swap)]);
true ->
io:format( "<-- ~s~n", [display(Swap)])
end.
Where I know that a recursion will be shallow, by construction, I've not attempted to write everything tail-recursively; that I've kept in the main A* algorithm, which should be generic enough to extract, and provide with extra function arguments.
The obvious effects of having to avoid state, with recursion rather than iteration, are more code and longer argument lists to the recursions. Still, an interesting exercise in rewriting the code, changing the way one thinks about the processing.
Of course, now I've had a comment, I can't just refactor in place, like I've done with the Python…
Posts
