Project Euler Problem 14 in Clojure

This one was fun. I also learned a good lesson the hard way about lazy sequences. When I was playing with the code in the REPL everything worked fine, but I got confused when I hooked everything up and started getting empty lists out of functions. It looked like functions were returning the values pointed to by the atoms before I modified them. I'd read about how lazy sequences don't get evaluated until they are required, but it didn't occur to me that "for" would return immediately, without evaluating anything. In the REPL this doesn't happen of course.

Was also my first look at maps, and the loop macro.

Solves in about 40sec

(defn- next-int [n]
  (if (even? n)
    (/ n 2)
    (+ (* n 3) 1)))

(defn- grow [start-num]
  (let [sequence (atom (list start-num))]
    (loop [head (first @sequence)]
      (let [next (next-int head)]
        (swap! sequence conj next)
        (if (= 1 next)
          @sequence
          (recur next))))))

(defn- measure-sequences []
  (let [counts (atom {})]
    (doall
      (for [start-num (range 1 1000000)]
        (let [sequence (grow start-num)]
          (swap! counts assoc start-num (count sequence)))))
    @counts))

(defn max-map-entry [map]
  (first (sort (comparator #(> (val %1) (val %2))) (seq map))))

(defn solve []
  (first (max-map-entry (measure-sequences))))

Project Euler Problem 13 in Clojure

Really not very interesting

;; defining big list of numbers elided

(defn solve[]
(.substring (str (apply + numbers)) 0 10))

Project Euler Problem 9 in Clojure

Solves in about 16sec. I quite liked the solution though of course the forum posts on the Project Euler site show some much cleverer solutions.

(defn pythagorean-triplet? [a b c]
  (and
    (< a b)
    (< b c)
    (= (+ (* a a) (* b b)) (* c c))))

(defn solve []
  (first
    (for [a (range 1 1000) b (range a 1000) c (range b 1000)
      :when (and
        (pythagorean-triplet? a b c)
        (= 1000 (+ a b c)))]
    (* a b c))))

Project Euler Problem 8 in Clojure

Not very interesting solution, since I use int/string conversions. As a clojure newcomer it feels a bit weird using the Java String API, just because you know its there. Writing functions to wrap the Java String API is probably not idiomatic Clojure, but I think it might be nice to wrap them in macros one day, to make the substring calls look a bit more Clojure-ish.

Solves in about 20msec.

(def bignumber "73167176531330624919......") ;; elided

(defn- calc-offsets []
  (range 0 (- 1000 5)))

(defn- five-digit-list [bigstring offset]
  (let [substr (.substring bigstring offset (+ 5 offset))]
    (map #(Integer/parseInt (str %)) substr)))

(defn- five-digit-lists [bigstring]
  (map #(five-digit-list bigstring %) (calc-offsets)))

(defn solve []
  (apply max (map #(apply * %) (five-digit-lists bignumber))))

Project Euler Problem 7 in Clojure

Another idea stolen from Ed. This defines a lazy sequence of primes, and holds on to the head, so whichever primes have been realised are memoised, and so are cached for future access.

Takes about 45 seconds to run.

(def primes
  (let [known-primes (atom (list))]
    (for [n (iterate inc 2)
      :when (or
        (= 2 n)
        (not-any? #(zero? (mod n %)) @known-primes))]
    (do
      (swap! known-primes conj n)
      n))))

(defn solve []
  (nth primes 10000))

Project Euler Problem 6 in Clojure

Wrote a square function so that the result wasn't cast to Double, so I didn't have to mess about with the formatting of the answer.

(defn square [num]
  (* num num))

(defn sum-squares [max]
  (reduce + (map #(square %) (range 1 max))))

(defn square-sum [max]
  (square (apply + (range 1 max))))

(defn solve []
  (- (square-sum 101) (sum-squares 101)))

Project Euler Problem 5 in Clojure

Not very impressive performance, this brute-force method takes about 30 seconds to run. Could probably be a lot quicker if factors were chosen more intelligently.

(def factors (into () (range 20 3 -1)))

(defn- all-factors [number]
  (if (every? #(zero? (mod number %)) factors)
    number
    (recur (inc number))))

(defn solve[]
  (all-factors 1))

Project Euler Problem 4 in Clojure

Most of my time was spent playing with for, trying to work out if it was best to do it all in the list comprehension. In the end I thought it was more readable to pull the creation of the products out into its own function.

(defn palindrome? [str]
  (if (= (first str) (last str))
    (if (<= 2 (count str))
      (recur (rest (butlast str)))
      true)
    false))

(defn three-digit-numbers []
  (range 100 1000))

(defn- products []
  (distinct
    (for [n1 (three-digit-numbers) n2 (three-digit-numbers)]
      (* n1 n2))))

(defn solve []
  (apply max (filter #(palindrome? (str %)) (products))))

Project Euler Problem 3 in Clojure - part 2

So the solution in part 1 was no good - it took half an hour to run. I spent a while trying and failing to make a lazy, purely functional version but after talking to Ed about his solution I came up with this, which runs in about 500msec :

(defn factor? [big small]
  (zero? (mod big small)))

(defn prime? [n]
  (not-any? #(factor? n %) (range 2 n)))

(defn primes []
  (filter #(prime? %) (iterate inc 2)))

(defn prime-factors [n]
  (let [factors (atom ())]
    (last
     (for [candidate (primes) :while (< (apply * @factors) n)]
       (if (factor? n candidate)
      (swap! factors conj candidate))))))

(defn solve []
  (first (prime-factors 600851475143)))

Project Euler Problem 3 in Clojure - part 1

This one is proving a bit tougher. First you need a list of prime numbers. I'm using the Euler's Sieve to produce primes.

First I wrote this function:

(defn sieve-numbers [position numbers]
  (if (>= position (count numbers))
  numbers
    (let [prime (nth numbers position)]
      (let [products (map #(* prime %) numbers)]
        (let [filtered (remove #(some #{%} products) numbers)]
          (recur (inc position) filtered))))))

which worked but was dog-slow:

;; (dotimes [_ 5] (time (sieve-euler 1000)))
;; "Elapsed time: 484.981564 msecs"
;; "Elapsed time: 459.624835 msecs"
;; "Elapsed time: 462.771112 msecs"
;; "Elapsed time: 460.312279 msecs"
;; "Elapsed time: 462.203786 msecs"
;; nil

To solve the problem we need to primes up to ceil(sqrt(N)) which is 775147 so that first method would take days.

To speed up the filtering I rewrote to use a SortedSet:

(defn sieve-numbers [primes candidates]
  (if (empty? candidates)
  primes
  (let [prime (first candidates)]
    (let [products (map #(* prime %) candidates)]
      (let [filtered (difference candidates products #{prime})]
        (recur (conj primes prime) filtered))))))

which is about 32 times faster:

;; (dotimes [_ 5] (time (sieve-euler 1000)))

;; "Elapsed time: 13.061787 msecs"
;; "Elapsed time: 12.994529 msecs"
;; "Elapsed time: 13.716897 msecs"
;; "Elapsed time: 13.237088 msecs"
;; "Elapsed time: 14.33136 msecs"

Still not good enough though. I need a faster sieve before I can even attempt to factor the large(ish) number and solve problem 3 inside a minute. I think my next step will be to pre-filter some of the non-primes with a Wheel Factorisation. This method wont remove all the non-primes, but it might be fun to implement.

I'm leaving the current sieve chugging away tonight to see how long it takes anyway, for comparison.

Project Euler Problem 2 in Clojure

;; lazy fibo stolen from programming clojure p137
(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [1 2])))

(defn solve []
(reduce + (filter even? (take-while #(> 4000000 %) (fibo)))))

Project Euler Problem 1 in Clojure

I'm trying to solve Project Euler using Clojure as an exercise to learn the language. My aim is to favour readability over performance, but still execute each problem inside a minute.


(defn is-multiple [number factor]
(zero? (mod number factor)))

(defn is-multiple-3-or-5 [number]
(or (is-multiple number 3)
(is-multiple number 5)))

(defn solve []
(reduce + (filter is-multiple-3-or-5 (range 1 1000))))