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))
                           state)))]
    (fn [item]
      (get-in (if (< item (first (:unknown @state)))
                @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"
nil

(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!