Menu

Subscribe

Project Euler Problem 15

on project euler, erlang, python

Lattice paths Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
Link to original description
Source code examples on Github

Liitle bit theory

Erlang solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p15
% vim:syn=erlang

-mode(compile).

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

test15(1) -> 2;
test15(N) -> ( 4 * N -2 ) * test15(N-1) div N.

Erlang solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p15
% vim:syn=erlang

-mode(compile).

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

test15i(N) -> fac(2*N) div (fac(N) * fac(N)).

fac(1) -> 1;
fac(N) -> N*fac(N-1).

Python solution

1
2
3
4
5
6
7
8
9
#!/usr/bin/python

def fact(n):
    f = 1
    for x in xrange(1, n+1): f = f * x
    return f

print("Answer: %d" % (fact(40) / fact(20) / fact(20)))