Commits

Lars Yencken committed b1a53d4

Add initial solutions in Python and Clojure.

  • Participants

Comments (0)

Files changed (13)

+.DS_Store
+*.pyc
+*.pyo
+*.orig
+*.bak
+Project Euler Solutions
+=======================
+
+Solutions to project Euler problems in many languages.
+
+http://projecteuler.net/problems

clojure/01-sum-numbers.clj

+#!/usr/bin/env clj
+;
+;  01-sum-numbers.clj
+;
+;  Sum all numbers from 1 to 1000 which are multiples of 3 or 5.
+;
+
+(ns euler
+  (:use clojure.test))
+
+(defn sum [xs]
+  (reduce + 0 xs))
+
+(defn m35 [x]
+  (or (= 0 (mod x 3)) (= 0 (mod x 5))))
+
+(defn sum-numbers [n]
+  "Sum all multiples of 3 and 5 between 1 and n (inclusive)."
+  (let [xs (range 1 n)]
+    (let [ns (filter m35 xs)]
+      (sum ns))))
+
+(deftest test-sum-numbers-1
+         (is (= 23 (sum-numbers 10))))
+
+(deftest test-sum-numbers-2
+         (is (= 233168 (sum-numbers 1000))))
+
+(run-tests)
+
+(println)
+(println "Answer:" (sum-numbers 1000))

clojure/02-sum-fibonnaci.clj

+#!/usr/bin/env clj
+;
+;  02-sum-fibbonaci.clj
+;
+;  Sum all even elements of the fibonacci sequence whose values are less than
+;  4 million.
+;
+
+(ns euler
+  (:use clojure.test))
+
+(defn fibonacci-acc [n np t]
+  (let [npp (+ n np)]
+    (if (< npp t)
+      (cons npp (fibonacci-acc np npp t))
+      nil)))
+
+; NOTE: cons is not lazy in clojure
+(defn fibonacci [t]
+  (cons 1 (cons 2 (fibonacci-acc 1 2 t))))
+
+(defn fibonacci-sum [n]
+  (reduce + 0 (filter (fn [x] (= 0 (mod x 2)))
+                             (fibonacci n))))
+
+(deftest test-fibonacci-sum-1
+  (is (= 2 (fibonacci-sum 6))))
+
+(deftest test-fibonacci-sum-2
+  (is (= 4613732 (fibonacci-sum 4000000))))
+
+(run-tests)
+
+(println)
+(println "Answer:" (fibonacci-sum 4000000))

clojure/03-prime-factors.clj

+#!/usr/bin/env clj
+;
+;  03-prime-factors.clj
+;
+;  Calculate prime factors of a number.
+;
+
+(ns euler
+  (:use clojure.test))
+
+(defn get-factor
+  [x] (first (filter #(= 0 (mod x %)) (range 2 (+ 1 x)))))
+
+(defn get-factors-acc [x acc]
+  (if (= x 1)
+    acc
+    (let
+      [f (get-factor x)]
+      (recur (/ x f) (conj acc f)))))
+
+(defn get-factors [x]
+  (get-factors-acc x []))
+
+(deftest get-factors-1
+         (is (= [2 3 5] (get-factors 30))))
+
+(deftest get-factors-2
+         (is (= [2 2 2 2 2 3] (get-factors 96))))
+
+(deftest get-factors-solution
+         (is (= 6857 (reduce max (get-factors 600851475143)))))
+
+(run-tests)
+
+(println)
+(println "Answer:" (reduce max (get-factors 600851475143)))

clojure/04-palindrome.clj

+#!/usr/bin/env clj
+;
+;  04-palindrome.py
+;  code
+;
+;  Created by Lars Yencken on 2012-01-17.
+;  Copyright 2012 Lars Yencken. All rights reserved.
+;
+
+(ns euler
+  (:use clojure.contrib.combinatorics)
+  (:use clojure.test))
+
+(defn is-palindrome? [x]
+  (let [s (str x)]
+    (= s (apply str (reverse s)))))
+
+(deftest is-palindrome-1
+         (is (is-palindrome? 101)))
+
+(deftest is-palindrome-2
+         (is true (is-palindrome? 20)))
+
+(deftest is-palindrome-3
+         (is true (is-palindrome? 403304)))
+
+(run-tests)
+
+(println)
+(println
+  "Answer:"
+  (reduce max
+    (filter #(is-palindrome? %)
+            (map #(* (first %) (second %))
+                 (combinations (range 100 1000) 2)))))

clojure/05-divisible.clj

+#!/usr/bin/env clj
+;
+;  05-divisible.py
+;  Code
+;
+;  Created by Lars Yencken on 2012-01-29.
+;  Copyright 2012 Lars Yencken. All rights reserved.
+;
+
+; 2520 is the smallest number that can be divided by each of the numbers from
+; 1 to 10 without any remainder. What is the smallest positive number that is
+; evenly divisible by all of the numbers from 1 to 20?
+
+(ns euler
+  (:use clojure.test))
+
+(defn get-factor
+  [x] (first (filter #(= 0 (mod x %)) (range 2 (+ 1 x)))))
+
+(defn get-factors-acc [x acc]
+  (if (= x 1)
+    acc
+    (let
+      [f (get-factor x)]
+      (recur (/ x f) (conj acc f)))))
+
+(defn get-factors [x]
+  (get-factors-acc x []))
+
+(deftest test-get-factors-1
+         (is (= [2 3 5] (get-factors 30))))
+
+(deftest test-get-factors-2
+         (is (= [2 2 2 2 2 3] (get-factors 96))))
+
+(defn merge-dists [xs ys]
+  "Merge two frequency distributions taking the maximum count for each key."
+  (let [keys (list* (concat (keys xs) (keys ys)))]
+    (zipmap
+      keys
+      (map #(max (get xs % 0) (get ys % 0)) keys))))
+
+(defn pow [n i]
+  (reduce * (repeat i n)))
+
+(deftest test-pow-1
+         (is (= 8 (pow 2 3))))
+
+(deftest test-pow-2
+         (is (= 7 (pow 7 1))))
+
+(defn prod-dist [d]
+  "Calculate the product of the factor distribution."
+  (reduce * (map #(pow (% 0) (% 1)) (seq d))))
+
+(deftest test-prod-dist
+         (is (= 96 (prod-dist {2 5, 3 1}))))
+
+(defn smallest-divisible [n]
+  (prod-dist
+    (reduce
+      merge-dists
+      (map #(frequencies (get-factors %)) (range 2 (+ n 1))))))
+
+(deftest test-smallest-divisible-1
+         (is (= 2520 (smallest-divisible 10))))
+
+(run-tests)
+(println)
+(println "Answer:" (smallest-divisible 20))
+

clojure/06-sum-squares.clj

+#!/usr/bin/env clj
+;
+;  06-sum-squares.py
+;  Code
+;
+;  Created by Lars Yencken on 2012-02-17.
+;  Copyright 2012 Lars Yencken. All rights reserved.
+;
+
+(ns euler
+  (:use clojure.test))
+
+(defn sum-sq [xs]
+  (reduce + (map #(* % %) xs)))
+
+(deftest sum-sq-1
+  (is (= (sum-sq (range 1 4)) 14)))
+
+(defn sq-sum [xs]
+  (let [sum (reduce + xs)]
+    (* sum sum)))
+
+(deftest sq-sum-1
+  (is (= (sq-sum (range 1 4)) 36)))
+
+(deftest problem-test
+  (is (= (- (sq-sum (range 1 101)) (sum-sq (range 1 101))) 25164150)))
+
+(run-tests)
+(println)
+(println "Answer:"
+  (-
+    (sq-sum (range 1 101))
+    (sum-sq (range 1 101))))

clojure/07-numbered-prime.clj

+#!/usr/bin/env clj
+;
+;  07-numbered-prime.py
+;  code
+;
+;  Created by Lars Yencken on 2012-02-17.
+;  Copyright 2012 Lars Yencken All rights reserved.
+;
+
+(ns euler
+  (:use clojure.contrib.lazy-seqs))
+
+(println
+  "Answer:"
+  (nth primes 10000))

clojure/08-consecutive-digits.clj

+#!/usr/bin/env clj
+;
+;  08-consecutive-digits.py
+;  code
+;
+;  Created by Lars Yencken on 2012-02-17.
+;  Copyright 2012 Lars Yencken All rights reserved.
+;
+
+(ns euler
+  (:use clojure.test))
+
+(def x 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450)
+
+(def xs
+  (map #(read-string (str %)) (str x)))
+
+(println
+  "Answers:"
+  (reduce max
+    (map #(reduce * %) 
+      (map vector
+        xs
+        (drop 1 xs)
+        (drop 2 xs)
+        (drop 3 xs)
+        (drop 4 xs)))))

python/03-prime-factors.py

+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+#
+#  03-prime-factors.py
+#  code
+#
+#  Created by Lars Yencken on 2012-01-15.
+#  Copyright 2012 Lars Yencken. All rights reserved.
+#
+
+"""
+Calculate the largest prime factor of 600851475143.
+"""
+
+def factorize(x):
+    if x <= 1:
+        return set()
+
+    factors = set()
+    for i in xrange(2, x + 1):
+        if x % i == 0:
+            factors.add(i)
+            return factors.union(factorize(x / i))
+
+    return factors
+
+print max(factorize(600851475143))

python/04-palindrome.py

+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+#
+#  04-palindrome.py
+#  code
+#
+#  Created by Lars Yencken on 2012-01-24.
+#  Copyright 2012 Lars Yencken. All rights reserved.
+#
+
+"""
+Find the largest palindrome made from the product of two 3-digit numbers.
+"""
+
+def is_palindrome(x):
+    x = str(x)
+    return x == x[::-1]
+
+def iter_palindromes():
+    for i in xrange(100, 1000):
+        for j in xrange(100, 1000):
+            x = i * j
+            if is_palindrome(x):
+                yield x
+
+print max(iter_palindromes())

python/05-divisble.py

+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+#
+#  05-divisble.py
+#  Code
+#
+#  Created by Lars Yencken on 2012-02-11.
+#  Copyright 2012 99designs. All rights reserved.
+#
+
+"""
+2520 is the smallest number that can be divided by each of the numbers from
+1 to 10 without any remainder. What is the smallest positive number that is
+evenly divisible by all of the numbers from 1 to 20?
+"""
+
+def factorize(x):
+    factors = []
+
+    while x > 1:
+        for i in xrange(2, x + 1):
+            if x % i == 0:
+                factors.append(i)
+                x /= i
+                break
+
+    return factors
+