I figuratively stubbed my toe on problem 58, engineering a rather complex solution when a simple loop would have sufficed.

My first idea was to write a higher-order function that would accept a lazy seq (of finite or infinite length), and return the fraction of the elements thus far that satisfied a particular predicate. Then, I could just start passing corner elements through that higher-order wrapper until the number of primes thins out to the desired (<10%) level.

The solution was pretty bulky, looking like this:

(use '[clojure.contrib.lazy-seqs :only (primes)])

(defn prime? [n]
  (and (< 1 n)
       (not-any? #(zero? (rem n %)) (take-while #(<= (* % %) n) primes)))) 

;; Basically same as problem 28
(defn diags-of-square [n]
  {:pre [(> n 0) (odd? n)]} ;; Must be odd to have diagonals
  (reverse (take 4 (iterate #(- % (dec n)) (* n n)))))

(def diags (lazy-cat [1] (flatten (map diags-of-square (iterate #(+ 2 %) 3)))))

(defn frac-satisfying-pred
  "Returns a lazy sequence of the running fraction of coll's elements that
  satisfy the predicate pred."
  [pred coll]
  (let [state (atom {:trues 0 :falses 0})
        getfrac (fn [n]
                  (do(if (pred n)
                        (swap! state #(assoc % :trues (inc (:trues %))))
                        (swap! state #(assoc % :falses (inc (:falses %)))))
                      (let [s @state]
                        (/ (:trues s) (+ (:trues s) (:falses s))))))]
    (map getfrac coll)))

(defn euler-58 []
  (let [fracs (take-while #(or (= % 0) ; Don't stop on 1st element
                               (> % 1/10)) 
                          (frac-satisfying-pred prime? diags))
        sides (lazy-cat [1] (flatten (map #(repeat 4 (+ 3 (* 2 %))) (range))))
        combined (map #(vector %1 %2) fracs sides)]
    (second (last combined))))

(time (euler-58)) ;; "Elapsed time: 5767.411147 msecs"

After writing that, I felt a little embarrassed about the extra work created by explicitly creating sides and then bundling it with the fractional values that are really important. Surely, an implicit solution would work just as well, and be a little more concise?

(defn euler-58 []
  (let [fracs (take-while #(or (= % 0)  ; Don't stop on 1st element
                               (> % 1/10)) 
                          (frac-satisfying-pred prime? diags))]
    (+ 3 (* (quot (count fracs) 4) 2))))

Hmmm…It’s shorter, but not really that much prettier. If anything, it’s probably harder to debug now with all those magic numbers floating around.

At this point, I wondered what would have happened if I had avoided theoretical elegance and instead taken the obvious, practical solution: use loop and avoid completely my frac-satisfying-pred higher-order function.

(use '[clojure.contrib.lazy-seqs :only (primes)])

(defn prime? [n]
  (and (< 1 n)
       (not-any? #(zero? (rem n %)) (take-while #(<= (* % %) n) primes))))

(defn euler-58-loop []
  (let [corners (fn [n] (take 4 (iterate #(- % (dec n)) (* n n))))]
    (loop [n 3
           trues 0
           falses 1]
      (let [c (count (filter prime? (corners n)))
            ts (+ trues c)
            fs (+ falses (- 4 c))]
        (if (> 1/10 (/ ts (+ ts fs)))
          n
          (recur (+ n 2) ts fs))))))

(time (euler-58-loop)) ;; "Elapsed time: 5774.851647 msecs"

I’m a little surprised that this didn’t perform dramatically faster than my original code because loop usually is quite performant when used properly. I guess the bottleneck is somewhere else.

Ciao for now!