Menu

Subscribe

Project Euler Problem 39

on project euler, erlang, python

Integer right triangles

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Link to original description
Source code examples on Github

Brutforce python solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/python

maxp, maxsol = 0, 0
for p in xrange(12, 1001, 2):
    solutions = 0
    for a in xrange(1, p/3):
        a2 = a*a
        for b in xrange(a, (p-a)/2):
            c = p - a - b
            if a2 + b*b == c*c: solutions = solutions + 1
    if solutions > maxsol: maxp, maxsol = p, solutions

print maxp

For right angle trinangle:

        a^2 + b^2 = c^2

and perimeter p = a + b + c, so c = p - a - b and:

        a^2 + b^2 = (p-a-b)^2 = p^2 + a^2 + b^2 -2pa – 2pb + 2ab
        b = (p^2 -2pa) / (2p-2a)

Furthermore we know a < c and b < c and without loss of generality we can assume that a ≤ b (otherwise we could switch them) which gives us that 

        a ≤ b < c
That implies a < p/3 and thus we don’t need to check values higher than that.

Optimized python solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/python3

import operator

def get_abc(a, p):
    b = (p**2 - 2*p*a) / (2*p - 2*a)
    c = (a**2 + b**2)**0.5
    return (a, b, c)

d = dict()
for p in range(12,1001):
    d[p] = 0
    for a in range(1,p//3):
        (a, b, c) = get_abc(a, p)
        if c.is_integer(): 
            d[p] += 1

print("P: %s number:%s" % sorted(d.items(), key=operator.itemgetter(1))[-1])

Erlang version

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
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p39
% vim:syn=erlang

get_abc(A, P) ->
    B = (P*P - 2*P*A) / (2*P - 2*A),
    C = math:sqrt(A*A + B*B),
    case round(C) == C of
        true -> 1
        ;_   -> 0
    end.

count([], A)    -> [{P,_}|_] = lists:sort(fun({_,C},{_,D})-> C > D end, A), P;
count([H|T], A) -> count(T, [{H, proplists:get_value(H,A,0)+1}] ++ proplists:delete(H,A)).

t39() ->
    L = lists:filter(fun({_,0})-> false;(_)-> true end,
            lists:flatten([[{P,get_abc(A,P)} ||A<-lists:seq(1, P div 3)]||P<-lists:seq(12,1000)])),
    count([P||{P,_}<-L], []).


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

found interesting but super slow another erlang version:

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 p39
% vim:syn=erlang

answer() ->
    Tris = [ A+B+C || C <- lists:seq(1, 500),
                      B <- lists:seq(1, C-1),
                      A <- lists:seq(1, B),
                      (A*A + B*B) =:= (C*C),
                      (A+B+C) =< 1000 ],
    Sorted = lists:sort(Tris),
    find_p(Sorted, hd(Sorted), 0, 0, hd(Sorted)).

find_p([], _, _, _, MaxP)            -> MaxP;
find_p([P | Ps], P, C, Max, MaxP)    -> find_p(Ps, P, C+1, Max, MaxP);
find_p([P | Ps], CurP, C, Max, MaxP) ->
    case C > Max of
        true  -> find_p(Ps, P, 0, C, CurP);
        false -> find_p(Ps, P, 0, Max, MaxP)
    end.


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