5 replies to this topic

[Sysop_fb]

Think the last time I went through euler was in C, no clue how far I made it. Anyway started redoing them in lisp and then started redoing them in haskell.

Just going to post my code in this thread, it will be uncommented until I start getting into the harder problems.
My lisp code is under SBCL. My haskell code is using Haskell Platform 2011.4.0.0

If someone wants to post there own feel free, if you've never tried Project Euler before and get as bored around the holidays as I do then I'd recommend trying it.

Problem 1

(defun prob1 ()
  (let ((x 0) 
        (total 0))
    (loop (setq total (+ total 
                         (cond 
                           ((or (= 0 (mod x 3)) (= 0 (mod x 5))) x)
                           (t 0))))
          (when (= x 999)
            (return total))
          (incf x))))

(defun newprob1 (x)
  (cond
    ((= x 1000) 0)
    ((or (= 0 (mod x 3)) (= 0 (mod x 5))) (+ x (newprob1 (incf x))))
    (t (+ 0 (newprob1 (incf x))))))

sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

Problem 2

(defun fib(x)
  (if (or (= x 1) (= x 2))
      1
      (+ (fib (1- x)) (fib (- x 2)))))
(defun prob2 (x)
  (let ((f (fib x)))
    (if (> f 4000000)
        0
        (if (evenp f)
            (+ f (prob2 (1+ x)))
            (prob2 (1+ x))))))

prob2 a b [] = prob2 a b [a, b]
prob2 a b lst = if ((a + b) < 4000000)
                then prob2 b (a + b) (filter even lst ++ [(a + b)])
                else sum lst

Problem 3

(defun prob3(num &optional (x 2))
  (if (= num x)
      (print x)
      (if (= (mod num x) 0)
          (progn
            (print x)
            (prob3 (/ num x)))
          (prob3 num (1+ x)))))

Problem 4

(defun palindrome?(num)
  (= num (read-from-string (reverse (write-to-string num)))))

(defun prob4(a b &optional (largest 0))
  (if (and (= a 999) (or (= b 999) (> b 999)))
      (print largest)
      (if (and (< a 999) (= b 1000))
          (prob4 (1+ a) 100 largest)
          (if (and (palindrome? (* a b)) (> (* a b) largest))
              (prob4 a (1+ b) (* a b))
              (prob4 a (1+ b) largest)))))

Problem 5

(defun mod2to20?(num &optional (x 2))
  (if (= x 21)
      t
      (if (= 0 (mod num x))
          (mod2to20? num (1+ x))
          nil)))

(defun prob5(num)
  (if (mod2to20? num)
      (print num)
      (prob5 (1+ num))))

Problem 6

(defun sum-of-squares(begin end)
  (if (> begin end)
      0
      (+ (* begin begin) (sum-of-squares (+ 1 begin) end))))

(defun square(x)
  (* x x))

(defun square-of-sum(begin end)
  (let ((total 0))
    (loop 
     (when (> begin end)
       (return (square total)))
     (setq total (+ total begin))
     (incf begin))))

(defun prob6(begin end)
  (- (square-of-sum begin end) (sum-of-squares begin end)))

(defun newprob6(begin end)
    (loop for i from begin to end
      sum i into nums
      sum (* i i) into squares
      finally (return (- (* nums nums) squares))))

[Sysop_fb]

Haskell for problem 3

prob3 n x
    | n == x     = n
    | (n `mod` x) == 0 = prob3 (n `div` x) 2
    | otherwise = prob3 n (x + 1)

ghci> prob3 317584931803 2
3919

And a different one

findsmallprime x = head [y | y <- [2..], x `mod` y == 0]
prob3' n lst
    | n == 1     = lst
    | otherwise = prob3' (n `div` (findsmallprime n)) lst++[findsmallprime n]

ghci> prob3' 317584931803 []
[3919,1459,829,67]

Problem 4 in Haskell

This makes a list of every palindrome from the product of every 3 digit whole number

[x*y | x <- [100..999], y <- [100..999], (reverse (show (x*y))) == (show (x*y))]

ghci> maximum [x*y | x <- [100..999], y <- [100..999], (reverse (show (x*y))) == (show (x*y))]
906609

---------- Post added at 04:04 PM ---------- Previous post was at 03:31 PM ----------

Was about to watch a movie when I read problem 9 and thought of a one liner in haskell
It takes a bit of time to complete though

Problem 9 in Haskell

[(a, b, c) | c <- [1..500], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a+b+c == 1000]

[Sysop_fb]

problem 16 while slightly drunk on christmas eve

prob16 = sum [fromEnum x - fromEnum '0' | x <- show (2^1000)]

[Sysop_fb]

so.. problem 7 in haskell either my function is broken or it really will take that long for it to finish.... anyway I'll come back to that one.

Problem 8 in haskell

import Data.Char

nums = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

numlist = [ord x - 48 | x <- nums, isDigit x]

prob8 a (b:c:x:y:z:xs) 
    | b*c*x*y*z > a = prob8 (b*c*x*y*z) (c:x:y:z:xs)
    | otherwise = prob8 a (c:x:y:z:xs)
prob8 a _ = a

main = print $ prob8 0 numlist

problem 13 just copy and paste the giant list of long arse nums into a list named nums and do

 sum nums

[WingedPanther]

Problem 7 shouldn't take long.

[Sysop_fb]

I realized my function was basically iterating over the list each time, technically I still am but I was doing it about 4x more than in that function.
I scratched it and rewrote eratosthenes sieve. I know there's faster ways to do this mod is slow, you could make a new list using the multiples of each prime and compare the lists to sieve them out.

prob7' m = esieve [3,5..m] 10000  where
    esieve [] _ = [] 
    esieve (p:xs) a
        | a == 1 = [p]
        | otherwise = esieve (filter ((/= 0) . (mod' p)) xs) (a - 1)

mod' x y = mod y x