Little Erlang Exercise 5

Problem Definition: Euler Problem 5

I am rather happy with this python version because I can basically get it done in about 15 min in total. Some useful primitives have been developed in module p3 (See my previous post, little erlang exercise 3)


“”“
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
”“”


from p3 import isprime, factorise

def product(x, y):
 return x * y

if name == “main”:
 factors = dict()
 for l in [factorise(i) for i in xrange(2, 21)]:
     tmp = dict()
     # count them
     for n in l:
         tmp[n] = 1 + tmp.get(n, 0)
     # reguster the max frequency of factor
     for k, v in tmp.items():
         factors[k] = max(factors.get(k, 0), v)

 print reduce(product, [pow(k, v) for k,v in factors.items()])

However, the erlang version took me a considerable time to complete. The problem is mainly to switch from a procedural mindset to a functional mindset.



-module(p5).
-import(p3).
-export([main/0, get_factor_freq_lst/1]).

%% run this to print the result
main() –>
  L = [ p3:factorise(X) || X <– lists:seq(1, 20)],   
  io:format(“~f~n”, [product(get_factor_freq(L))]).   

get_factor_freq(L) –>
  Dict = dict:new(),
  get_factor_freq(L, Dict).

%% spec: H, T are list of list of number
%% e.g. [ [N1, N1, N2…], [N1, N2…], …]
get_factor_freq([H|T], Dict) –>
  Dist = get_factor_freq_lst(H),
  D1 = dict:from_list(Dist),
  D2 = dict:merge(fun(K, X, Y) –> update_if_bigger(K, X, Y) end, D1, Dict),
  get_factor_freq(T, D2);
get_factor_freq([], Dict) –>
  dict:to_list(Dict).  %% has to convert to list

%% Aux function
update_if_bigger(, Initial, NewValue) when Initial < NewValue –>
  NewValue;
update_if_bigger(, Initial, _) –>
  Initial.

%% This function assumes the list is sorted
%% This function is to delinate a list of number
%% into a list of {Key, Frequency}
get_factor_freq_lst([A|T]) when is_integer(A) –>
  get_factor_freq_lst([{A, 1}|T]);
get_factor_freq_lst([{A, N}, A|T]) when is_integer(A) –>
  get_factor_freq_lst([{A, N + 1}|T]);
get_factor_freq_lst([{A, N}, B|T]) when is_integer(A), is_integer(B), A /= B –>
  get_factor_freq_lst([{B, 1}|T] ++ [{A, N}] );
get_factor_freq_lst(L) –>
  L.

%% find the product of a list of tuple {Base, Power)
product(L) –>
  product(L, 1).
product([], Sum) –>
  Sum;
product([{Base, Power}|T], Sum) –>
  product(T, Sum * math:pow(Base, Power)).

Timeline

My development logbook

Little Erlang Exercise 5