Project Euler Problem 42

Ivar Thorson bio photo By Ivar Thorson

For our 42nd problem in Project Euler, we need to find how many words have wordscores that are also triangle numbers. Triangle numbers are generated by the equation 1/2 * n * (n-1).

This problem was very similar to problem 22. However, since I learned about zipmap since then, I was able avoid using interleave this time. It would be difficult to imagine a shorter definition for letter-val or word-score.

def letter-val (zipmap "ABCDEFGHIJKLMNOPQRSTUVWXYZ" (range 1 27)))

(defn word-score [word] (reduce + (map letter-val word)))

(def triangle-nums (map #(* (/ 1 2) % (dec %)) (iterate inc 2)))

(defn triangular? [n] (= n (first (drop-while #(< % n) triangle-nums))))

(defn euler-42 [file]
  (count (filter #(triangular? (word-score %)) (re-seq #"\w+" (rp file)))))

(euler-42 "/path/to/words.txt")

The obvious ugly part of this code is the definition of triangular. Though concise, it is a really terrible algorithm. An obvious enhancement I see for triangular? would be to push values into a map instead of the drop-while idiom. Actually, that might be a useful idiom to have, so let’s take a moment to write it (with help from stack overflow):

(defn make-lazy-predicate [coll]
  (let [state        (atom {:mem #{} :unknown coll})
        update-state (fn [{:keys [mem unknown] :as state} item]
                       (let [[just-checked remainder]
                             (split-with #(<= % item) unknown)]
                         (if (seq just-checked)
                           (-> state
                             (assoc :mem (apply conj mem just-checked))
                             (assoc :unknown remainder))
    (fn [item]
      (get-in (if (< item (first (:unknown @state)))
                (swap! state update-state item))
              [:mem item]))))

(def triangular-mapped? (make-lazy-predicate triangle-nums))

Spend some time studying that, it’s a nice bit of code that uses a closed-over atom to lazily memoize the infinite seq. Also, I learned about the existence of get-in through this function.

In the end, it’s probably simpler just to use the mathematical properties of triangular numbers:

(defn natural? [n] (= n (int n))) 

(defn triangular-math? [n]
  (let [m (Math/sqrt (+ 1 (* 8 n)))]
    (and (> n 0) (natural? m))))

The performance of the lazy predicate version is actually only about 4 times slower than the mathematical definition in a simple benchmark, suggesting it might be a useful technique for lazy, ordered sequences whose mathematical properties aren’t well understood enough to analyze.

(dotimes [_ 5] (time (reduce + (filter triangular? (range 100000)))))
"Elapsed time: 2998.309655 msecs"
"Elapsed time: 2997.313831 msecs"
"Elapsed time: 2997.213703 msecs"
"Elapsed time: 2996.954904 msecs"
"Elapsed time: 3005.674668 msecs"

(dotimes [_ 5] (time (reduce + (filter triangular-math? (range 100000)))))
"Elapsed time: 16.292261 msecs"
"Elapsed time: 16.250659 msecs"
"Elapsed time: 16.274408 msecs"
"Elapsed time: 16.261641 msecs"
"Elapsed time: 16.327551 msecs"

(dotimes [_ 5] (time (reduce + (filter triangular-mapped? (range 100000)))))
"Elapsed time: 109.244218 msecs"
"Elapsed time: 57.835461 msecs"
"Elapsed time: 57.654765 msecs"
"Elapsed time: 57.738389 msecs"
"Elapsed time: 57.532498 msecs"

Ciao for now!