Menu

Subscribe

Project Euler problem 53

on project euler, erlang, python

Combinatoric selections

There are exactly ten ways of selecting three from five, 12345:

        123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, C(3,5) = 10.

In general, C(N,R) = N! / (R!*(N-R)!)

It is not until n = 23, that a value exceeds one-million: C(10,23) = 1144066.

How many, not necessarily distinct, values of C(N,R), for 1 ≤ n ≤ 100, are greater than one-million?

Link to original description
Source code examples on Github

Brutforce python solution:

1
2
3
4
5
6
7
8
9
import math
count = 0

for n in range(1,101):
    for r in range(1,n+1):
        if math.factorial(n) / (math.factorial(r) * math.factorial(n-r)) >= 1000000: count += 1

print("Answer %s" % count)

and same thing with erlang:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p53
% vim:syn=erlang

-mode(compile).

main(_) -> io:format("Answer ~p ~n",[ p53() ]).

c(N, R) -> f(N) / (f(R)*f(N-R)).

f(0) -> 1;
f(1) -> 1;
f(N) -> N*f(N-1).

p53() ->
    Fun = fun(N,A) ->
        lists:foldl(fun(R,B)->
            case c(N,R) >= 1000000 of
                true -> B + 1
                ;_   -> B
            end
        end, 0, lists:seq(1,N)) + A
    end,
    lists:foldl(Fun, 0, lists:seq(1,100)).

For optimization i tryed to memoize factorial function values:

for python i did it with lru_cache decorator

1
2
3
4
5
6
7
8
9
10
11
12
import math, functools
count = 0

@functools.lru_cache(maxsize = 1000)
def f(n,r):
     return math.factorial(n) / (math.factorial(r) * math.factorial(n-r)) 

for n in range(1,101):
    for r in range(1,n+1):
        if f(n,r) >= 1000000: count += 1

print("Answer %s" % count)

for erlang i did it with process dictionary:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p53
% vim:syn=erlang

-mode(compile).

main(_) -> io:format("Answer ~p ~n",[ p53() ]).

c(N, R) -> f(N) / (f(R)*f(N-R)).

f(0) -> 1;
f(1) -> 1;
f(N) ->
    case get({'f', N}) of
        undefined -> R = N*f(N-1), put({'f', N}, R), R;
        Ret       -> Ret
    end.

p53() ->
    Fun = fun(N,A) ->
        lists:foldl(fun(R,B)->
            case c(N,R) >= 1000000 of
                true -> B + 1
                ;_   -> B
            end
        end, 0, lists:seq(1,N)) + A
    end,
    lists:foldl(Fun, 0, lists:seq(1,100)).

but for these calculations it is didn’t make any performance increment.