Generator of Befunge script for numbers using * and + operations written in Erlang.

polish_numbers.erl

-module(polish_numbers).

-export([generate/1]).

generate(N) when is_integer(N), N >= 0 ->
  Self = self(), % spawn subprocess to avoid process dictionary pollution by put/get
  Pid = spawn_link(fun() -> Self ! {result, self(), gen(N, 999999)} end),
  [X || {_,X} <- receive {result, Pid, R} -> R end].

gen(N, _) when N < 10 -> [{1, [N+$0]}];
gen(N, Min) ->
  case get(N) of
    undefined -> gen_(N, Min);
    {S, []} when Min > S -> gen_(N, Min);
    {_, X} -> X
  end.

gen_(N, Min) ->
  Max = sqrt(N),
  Mults = minimals(
      [ {SA + SB + 1, A ++ B ++ [$*]}
       || X <- lists:seq(2,Max), N rem X =:= 0,
          {SA, A} <- gen(X, Min-2), {SB, B} <- gen(N div X, Min-SA-1),
          SA + SB < Min]
      ),
  NewMin = case Mults of
    [{X, _}|_] when X < Min -> X;
    _ -> Min
  end,
  Pluses = [ {SA + SB + 1, A ++ B ++ [$+]}
            || X <- lists:seq(1, (N-1) div 2),
               {SA, A} <- gen(X, NewMin-2), SA+1 < NewMin,
               {SB, B} <- gen(N-X, NewMin-SA-1), SA + SB < NewMin ],
  Mins = minimals(Mults ++ Pluses),
  put(N, {Min, Mins}),
  Mins.

minimals([]) -> [];
minimals(L) ->
  {Min, _} = lists:min(L),
  minimals(Min, L).

minimals(Min, L) ->
  [ X || {S,_} = X <- L, S =:= Min ].

sqrt(X) -> sqrt(X, trunc(math:sqrt(X)) + 1).

sqrt(X, E) ->
  % Newton-Raphson method of solving square root
  Err = E * E - X,
  E2 = E - Err div (2 * E),
  if
    E2 =/= E -> sqrt(X, E2);
    Err > 0 -> E - 1;   % Solve rounding error
    true -> E
  end.