Once more with feeling… — A-star shortest path finder in Erlang

The same problem as in the previous post, only this time in Erlang:

-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.

Later

Of course, now I've had a comment, I can't just refactor in place, like I've done with the Python…