Project Euler Problem 33

Ivar Thorson bio photo By Ivar Thorson

Project Euler Problem 33 asks us to find a particular pattern of fraction which satisfies several characteristics:

  1. It is less than one.
  2. It has two digits in both numerator and denominator.
  3. You can simplify the fraction correctly by canceling a single digit from both numerator and denominator.
  4. It is not a trivial fraction like (30/50).

My first attempt had the right idea, but the implementation has flaws because I tried to manage the numerator and denominator separately.

(defn as-digits [num]
  (map #(Character/getNumericValue %) (str num)))

(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))
(defn lcm [a b] (/ (* a b) (gcd a b)))

(defn curious-frac? [num den]
  (let [n (as-digits num)
        d (as-digits den)]
  (and (= (second n) (first d))
       (not (zero? (first n)))
       (not (zero? (second d)))
       (= (/ (first n) (second d))
          (/ num den))
       (< (/ num den) 1))))

(defn reduce-fraction [[n d]]
  (let [g (gcd n d)]
    [(/ n g) (/ d g)]))

(defn euler-33 []
  (let [fracs (for [num (range 10 100)
                    den (range num 100)
                    :when (curious-frac? num den)]
                [num den])]
    (reduce-fraction [(reduce * (map first fracs))
                      (reduce * (map second fracs))])))

(time (euler-33)) 

Compare this to bibi’s nice solution from clojure-euler:

(defn non-trivial?[n d]
  (let [x (quot n 10)
        y (rem n 10)
        u (quot d 10)
        v (rem d 10)]
     (zero? v) false
     (and (= y u) (= (/ x v) (/ n d))) true
     :else false)))
(defn euler-33-bibi []
  (let [fracs (for [n (range 10 99)
                    d (range (inc n) 100)
                    :when (non-trivial? n d)]
                (/ n d))]
    (.denominator (reduce * fracs))))

Lesson learned: don’t ignore the built-in data types like I did! Follow bibi’s example and let clojure manage your fractions automatically for you!