Had a slice of free time, so decided to look at the next problem. Here's the initial naive solution:
divisors n = [x | x <- [1 .. n-1], n `mod` x == 0] isAbundant n = n < (sum $ divisors n) abundants n = filter isAbundant $ [1 .. n] expressSum z nums = not $ null [(x,y) | x <- nums, y <- nums, x + y == z] sumAbundants n = let a = abundants n in sum $ filter (\x -> not $ expressSum x a) [1 .. n]
While it gave the correct answer, it did so in
3133.33 seconds, which is ... embarrassing.
This is just too inefficient, even the following ...
(defun divisors (n) (loop for i from 1 below n when (= 0 (mod n i)) collect i)) (defun abundantp (n) (< n (reduce #'+ (divisors n)))) (defun abundants (n) (loop for i from 1 below n when (abundantp i) collect i)) (defun possible-summands (z nums) (loop for x in nums do (loop for y in nums when (= z (+ x y)) do (return-from possible-summands (cons x y))))) (defun sum-abundants (n) (let* ((ab (abundants n)) (summands (loop for i from 1 to n when (null (possible-summands i ab)) collect i))) (reduce #'+ summands)))
... takes no less than half as long, at
Anyway, I'm ashamed to say I didn't put in the effort to learn how to profile Haskell programs (next time ?) and profiled the Lisp version instead, which showed that (duh) all the time was going in finding divisors. Obviously, we can just loop till the square root of N instead of looping all the way to N. After this change:
(defun divisors (n) (declare (type fixnum n)) (loop for i from 1 below (floor (sqrt n)) when (= 0 (mod n i)) collect i))
... it runs in
38 milliseconds !!
And a similar change to the Haskell version:
divisors :: Int -> [Int] divisors n = [x | x <- [1 .. round $ sqrt $ fromIntegral n], n `mod` x == 0]
gave the expected answer in
180 milliseconds. Not bad (though it should be noted we're still an order of magnitude away in efficiency).