Project Euler Problem 49

Ivar Thorson bio photo By Ivar Thorson

This problem was tricky. Although we get to reuse a significant amount of code for prime?, as-int, and choose-k, we still need to write two rather tricky functions to extract the special triples.

The solution I wrote actually is more general than may be needed because I wasn’t specifically looking for differences of 3330.

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

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

(defn as-int [coll] (Integer/parseInt (apply str coll)))

(defn choose-k
  "Returns all possible unique groups of size k in coll."
  [coll k]
  (let [n (count coll)]
    (if (<= k 1)
      (map vector coll)
      (reduce into []
              (for [i (range 1 (inc n))]
                (map #(into [(nth coll (dec i))] %)
                     (choose-k (drop i coll) (dec k))))))))

(defn has-special-triple? [coll]
  (let [fs (frequencies (map (fn [[a b]] (- b a)) (choose-k coll 2)))]
    (first (for [d (filter #(= 2 (fs %)) (keys fs))
                 a coll
                 :when (some #(= % (+ a d)) coll)
                 :when (some #(= % (+ a d d)) coll)]
             [a (+ a d) (+ a d d)]))))

(defn euler-49 []
  (let [ps (take-while #(> 10000 %) (drop-while #(> 1000 %) primes ))
        p2q (fn [p] (filter #(and (<= 1000 %) (prime? %))
                            (map as-int (distinct (permutations (str p))))))
        qs (distinct (map #(sort (p2q %)) ps))]
    (remove nil? (map has-special-triple? qs))))

Frankly, that may be one of the more incomprehensible things I have written so far. Here’s the breakdown: has-special-triple? checks to see that given a sorted list of numbers, there are three numbers that are spaced evenly apart. euler-49 generates primes in the right range, makes lists of permutations of each prime, makes sure the permutations are prime and four digits long (because a 0 in the leading position counts as 3 digits), and then returns all groups that satisfy the has-special-triple? property.

Got it? ;-)