Monday, July 12, 2010

When there was only busy-work at work, I started working through the Project Euler problems. For the most part, I used the hugs implementation of Haskell, since the problems ought to be solvable without a huge amount of computation. However, some of my solutions were way too slow, so I used Java to solve some of the problems. I haven't submitted any of my answers, so I don't have that verification that my answers are correct.

Problem 1 was a simple one-liner in Haskell

p1 = sum [3,6..999] + sum [5,10..999] - sum [15,30..999]


Problem 2 was a simple 2-liner in Haskell.

For problem 3, I started by computing a list of primes. After getting the answer, I realized that calculating the primes was superfluous. I could just divide out all factors, starting from 2, regardless if they were prime or not, and the remainder would be the largest prime factor.

I just brute forced problem 4, though I can halve the search space since multiplication is commutative.

Problem 5 was a simple one-liner. Haskell's Prelude provides gcd.

Problem 6 was another simple one-liner.

My solution for problem 7 was pretty slow. Adding a type declaration: primes :: [Int], made it over 3 times faster, though still slow, with hugs. The inferred type would have been primes :: [Integer], but since all of the relevant numbers fit into signed 32-bit integers, [Int] would still give the correct result. I sped up a number of slow solutions by adding Int declarations.

I brute forced problem 8. Since the last digit was a 0, I could just do product . take 5 and not worry about a spurious result, which I would have had to worry about if the number had ended with 09999.

Problem 9 was another brute-force search. Since 1000 > c > b > a > 0, I could limit the search to 1000 > c > 333 and c > b > c/2.

My solution to problem 10 in Haskell was just too slow using hugs, so I wrote basically the same algorithm in about 20 lines of Java, which was fast. The result had to be a long, since it was too big to for 32-bit integers. I manually stored the computed primes in an array in the Java solution. Perhaps hugs wasn't memoizing the list of primes that was being computed, causing the algorithm that was supposed to be O(N3/2) to be O(N2).

No comments:

Post a Comment