Sunday, September 8, 2013

Problem 39 done; Erlang used (on 24)

Project Euler Problem #39 asks for the perimeter p <= 1000 which maximiaxes the number of right triangles with integer side lengths which have that perimeter. The best solution I could think of for this problem involved using a table / dictionary data structure, so I decided to use a language that has such a data structure built-in: Python. Now, this is the 3rd problem I have solved in Python (actually more if you were to count the problems I wrote code in Python in to check my other solution...) So I had to replace my most recent use of Python, which was on problem 24. For problem 24, I once used J because it made the problem absolutely trivial, then I used Python because I used J somewhere else and needed a quick replacement. This time around I used Erlang, and essentially just transcribed my answer from Python to Erlang - this was non-trivial as Erlang is structured differently (it is functional, and all), but nonetheless it was not too difficult.

Solution to Problem 24 in Erlang:
-module(e24).
-module(e24).
-on_load(e24/0).

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


list_ref(0, [Head|_]) -> Head;
list_ref(X, [_|Tail]) -> list_ref(X - 1, Tail).

nthLP(N, P, Rem) ->
    if
        length(Rem) == 1 ->
            P ++ Rem;
        true ->
            K    = fac(9 - length(P)),
            Elem = list_ref(trunc(N / K), Rem),
            
            nthLP(N rem  K, P ++ [Elem], Rem -- [Elem])
    end.
e24() -> io:format("~B~B~B~B~B~B~B~B~B~B~n", 
    nthLP(999999, [], [0,1,2,3,4,5,6,7,8,9])).


Solution to Problem 39 in Python:
import math

sols = {}
for a in range(2,500):
    for b in range(a, 500):
        c2 = a ** 2 + b ** 2
        c  = int(math.sqrt(c2))
        if c2 == c * c:
            p = a + b + c
            if p <= 1000:
                if p in sols.keys():
                    sols[p] += 1
                else:
                    sols[p]  = 1

ans = 0
maxsols = 0
for p in sols.keys():
    if maxsols < sols[p]:
        ans = p
        maxsols = sols[p]
print ans

No comments:

Post a Comment