Wednesday, September 3, 2008

Beust Challenge in Erlang

There was a challenge posted by Cedric Beust. I tried reuse my older solution of permutation generator and aplly this aproach on this issue. Here is result:
-module(cbchallenge).

-export([test/1]).

combine(Sufix, 0, Acc, _L) ->
   accept(list_to_integer(lists:reverse(Sufix)), Acc);
combine(Sufix, N, Acc, L) ->
   combine(Sufix, N, Acc, L, []).

combine(_Sufix, _N, Acc, [], _D) -> Acc;
combine(Sufix, N, Acc, [X | T], D) ->
   combine(Sufix, N,
     _NewAcc = combine([X | Sufix], N - 1, Acc,
         lists:reverse(D, T)),
     T, [X | D]).

accept(X, {Count, undefined}) -> {Count + 1, {X, 0}};
accept(X, {Count, {Last, MaxDistance}})
   when X - Last > MaxDistance ->
   {Count + 1, {X, X - Last}};
accept(X, {Count, {_, MaxDistance}}) ->
   {Count + 1, {X, MaxDistance}}.

count(Log10) ->
   {Count, {_, MaxDistance}} = combine([], Log10,
     {0, undefined}, lists:seq($1, $9),
     [$0]),
   {Count, MaxDistance}.

test(MaxLog10) ->
   lists:foldl(fun (Log10, AccIn) ->
   collectResult(count(Log10), AccIn)
  end,
  {0, 0}, lists:seq(1, MaxLog10)).

collectResult({Count, Max}, {OldCount, OldMax})
   when Max > OldMax ->
   {OldCount + Count, Max};
collectResult({Count, _}, {OldCount, Max}) ->
   {OldCount + Count, Max}.
It is more than twice faster than Kevin's crazybob solution on my laptop (kevin ~18s, mine ~8.5s).
> [{X, timer:tc(cbchallenge, test, [X])} || X<-lists:seq(1,10)].
[{1,{16,{9,1}}},
 {2,{52,{90,2}}},
 {3,{420,{738,11}}},
 {4,{3073,{5274,105}}},
 {5,{20019,{32490,1047}}},
 {6,{105757,{168570,10469}}},
 {7,{459955,{712890,104691}}},
 {8,{1587747,{2345850,1046913}}},
 {9,{4522205,{5611770,10469135}}},
 {10,{8563146,{8877690,104691357}}}]
I guess, there is much more faster solution closer to original crazybob's solution which is arithmetical and applicable just only to numbers. My approach is applicable to any non repeated combination of members of any set, but slower.