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