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.
