Discussion on: Daily Challenge #7 - Factorial Decomposition

View post

I’m learning Erlang.

I’m not really happy with my solution yet, I feel it could be simpler. I’d rather keep functions that do one thing, though, and avoid decompose_factorial_into_factors_and_group(X, Y, Z, []) or something. Hence I didn’t save on the single-argument versions, or combine unrelated functions.

-module( decomp ).
-export( [ is_prime/1, decomp/1, fact_decomp/1, print/1 ] ).

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

is_prime( 1 ) ->
    false;
is_prime( N ) when N > 0 ->
    is_prime( N, 2, floor( math:sqrt( N ) ) ).

is_prime( _N, Start, End ) when Start > End ->
    true;
is_prime( N, Start, _End ) when N rem Start == 0 ->
    false;
is_prime( N, Start, End ) ->
    is_prime( N, Start + 1, End ).


decomp( N ) when N > 1 ->
    lists:reverse( decomp( N, 2, [] ) ).

decomp( N, Start, Factors ) when Start > N ->
    Factors;
decomp( N, Start, Factors ) ->
    case is_prime( Start ) and ( N rem Start == 0 ) of
        true -> decomp( N div Start, 2, [ Start | Factors ] );
        false -> decomp( N, Start + 1, Factors )
    end.


group_factors( Factors ) ->
    group_factors( Factors, #{} ).

group_factors( [], Map ) ->
    Map;
group_factors( [ Head | Rest ], Map ) ->
    Current = maps:get( Head, Map, 0 ),
    Updated = maps:put( Head, Current + 1, Map ),
    group_factors( Rest, Updated ).


fact_decomp( N ) ->
    group_factors( lists:flatmap(
        fun decomp/1,
        lists:seq( 2, N )
    ) ).


format_factor( { Fact, Exp } ) ->
    case Exp of
        1 -> io_lib:format( "~p", [ Fact ] );
        _ -> io_lib:format( "~p^~p", [ Fact, Exp ] )
    end.

format_factors( Facts ) ->
    string:join(
        lists:map(
            fun format_factor/1,
            lists:sort( maps:to_list( Facts ) )
        ),
        " * "
    ).


print( N ) ->
    io:fwrite( "~s~n", [ format_factors( fact_decomp( N ) ) ] ).


% TESTS

prime_list_test() -> 
    Primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
    ],

    lists:foreach(
        fun( N ) ->
            ?assert( is_prime( N ) =:= lists:member( N, Primes ) )
        end,
        lists:seq( 1, 1000 )
    ).

decomp_test() -> [
    ?assert( decomp(  2 ) =:= [ 2 ] ),
    ?assert( decomp(  3 ) =:= [ 3 ] ),
    ?assert( decomp(  4 ) =:= [ 2, 2 ] ),
    ?assert( decomp(  5 ) =:= [ 5 ] ),
    ?assert( decomp(  6 ) =:= [ 2, 3 ] ),
    ?assert( decomp(  7 ) =:= [ 7 ] ),
    ?assert( decomp(  8 ) =:= [ 2, 2, 2 ] ),
    ?assert( decomp(  9 ) =:= [ 3, 3 ] ),
    ?assert( decomp( 10 ) =:= [ 2, 5 ] ),
    ?assert( decomp( 11 ) =:= [ 11 ] ),
    ?assert( decomp( 12 ) =:= [ 2, 2, 3 ] ),
    ?assert( decomp( 13 ) =:= [ 13 ] ),
    ?assert( decomp( 14 ) =:= [ 2, 7 ] ),
    ?assert( decomp( 15 ) =:= [ 3, 5 ] ),
    ?assert( decomp( 16 ) =:= [ 2, 2, 2, 2 ] ),
    ?assert( decomp( 17 ) =:= [ 17 ] ),
    ?assert( decomp( 18 ) =:= [ 2, 3, 3 ] ),
    ?assert( decomp( 19 ) =:= [ 19 ] ),
    ?assert( decomp( 20 ) =:= [ 2, 2, 5 ] )
].

fact_decomp_test() -> [
    ?assert( fact_decomp(  2 ) =:= #{ 2 => 1 } ),
    ?assert( fact_decomp(  6 ) =:= #{ 2 => 4, 3 => 2, 5 => 1 } ),
    ?assert( fact_decomp( 13 ) =:= #{ 2 => 10, 3 => 5, 5 => 2, 7 => 1, 11 => 1, 13 => 1 } ),

    ?assert( fact_decomp( 22 ) =:= #{ 2 => 19, 3 => 9, 5 => 4, 7 => 3, 11 => 2, 13 => 1, 17 => 1, 19 => 1 } ),
    ?assert( fact_decomp( 25 ) =:= #{ 2 => 22, 3 => 10, 5 => 6, 7 => 3, 11 => 2, 13 => 1, 17 => 1, 19 => 1, 23 => 1 } ),
    ?assert( fact_decomp( 12 ) =:= #{ 2 => 10, 3 => 5, 5 => 2, 7 => 1, 11 => 1 } )
].

Try with:

% erl
1> c(decomp).
{ok,decomp}
2> decomp:test().
  All 3 tests passed.
ok
3> decomp:print(22).
2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19
ok

Olivier “Ölbaum” Scherler • Aug 13 '19

Too bad @stevemoon didn’t do this one, I would have liked to compare. :-)