loading...

re: Daily Challenge #17 - Double Trouble VIEW POST

FULL DISCUSSION
 

I couldn’t figure out the formula like @alvaromontoro did, but here’s my blunt Erlang version. It was really easy to write and it still runs under a second for N = 10 million:

-module( double ).

-include_lib("eunit/include/eunit.hrl").

% when it’s the first person, return the head
double( [ Person | Rest ], 1, More ) ->
    Person;
% when it’s not the first person, add the head to the More list twice and decrement N
% the More list is the rest of the queue, where we can append at the head
% imagine that the full queue at all times is Queue ++ lists:reverse( More )
double( [ Person | Rest ], N, More ) ->
    double( Rest, N - 1, [ Person, Person | More ] );
% when the queue is empty, take the More list, reverse it and start over
double( [], N, More ) ->
    double( lists:reverse( More ), N, [] ).

double( Queue, N ) when N > 0 ->
    double( Queue, N, [] ).

double_test_() ->
    Three = [ sheldon, leonard, penny ],
    Everyone = [ sheldon, leonard, penny, rajesh, howard ],
    [
        ?_assertEqual( sheldon, double( [ sheldon ], 1 ) ),
        ?_assertEqual( sheldon, double( [ sheldon ], 2 ) ),
        ?_assertEqual( sheldon, double( [ sheldon ], 3 ) ),
        ?_assertEqual( sheldon, double( [ sheldon ], 4 ) ),

        ?_assertEqual( sheldon, double( [ sheldon, leonard ], 1 ) ),
        ?_assertEqual( leonard, double( [ sheldon, leonard ], 2 ) ),
        ?_assertEqual( sheldon, double( [ sheldon, leonard ], 3 ) ),
        ?_assertEqual( sheldon, double( [ sheldon, leonard ], 4 ) ),
        ?_assertEqual( leonard, double( [ sheldon, leonard ], 5 ) ),
        ?_assertEqual( leonard, double( [ sheldon, leonard ], 6 ) ),

        ?_assertEqual( sheldon, double( Everyone, 1 ) ),
        ?_assertEqual( penny,   double( Everyone, 3 ) ),
        ?_assertEqual( sheldon, double( Everyone, 6 ) ),
        ?_assertEqual( leonard, double( Everyone, 8 ) ),
        ?_assertEqual( leonard, double( Everyone, 9 ) ),
        ?_assertEqual( sheldon, double( Everyone, 19 ) ),

        ?_assertEqual( sheldon, double( Three, 1 ) ),
        ?_assertEqual( leonard, double( Three, 2 ) ),
        ?_assertEqual( penny,   double( Three, 3 ) ),
        ?_assertEqual( sheldon, double( Three, 4 ) ),
        ?_assertEqual( sheldon, double( Three, 5 ) ),
        ?_assertEqual( leonard, double( Three, 6 ) ),
        ?_assertEqual( leonard, double( Three, 7 ) ),
        ?_assertEqual( penny,   double( Three, 8 ) ),
        ?_assertEqual( penny,   double( Three, 9 ) ),
        ?_assertEqual( sheldon, double( Three, 10 ) ),
        ?_assertEqual( sheldon, double( Three, 11 ) ),
        ?_assertEqual( sheldon, double( Three, 12 ) ),
        ?_assertEqual( sheldon, double( Three, 13 ) ),
        ?_assertEqual( leonard, double( Three, 14 ) ),
        ?_assertEqual( leonard, double( Three, 15 ) ),
        ?_assertEqual( leonard, double( Three, 16 ) ),
        ?_assertEqual( leonard, double( Three, 17 ) ),
        ?_assertEqual( penny,   double( Three, 18 ) ),
        ?_assertEqual( penny,   double( Three, 19 ) ),
        ?_assertEqual( penny,   double( Three, 20 ) ),
        ?_assertEqual( penny,   double( Three, 21 ) ),
        ?_assertEqual( sheldon, double( Three, 22 ) )
    ].
code of conduct - report abuse