473 Eric Normand Newsletter

00 Simplifying fractions.md

Simplifying fractions

A harder one for this week.

Fractions are often represented in simplified form, where the numerator and denominator share only the factor 1. Write a function simplify that takes two integers (representing the numerator and denominator) and simplifies the fraction they represent, returning the two numbers.

Examples

;; the fraction 10/10
(simplify 10 10) ;=> [1 1]
;; the fraction 1/3
(simplify 1 3) ;=> [1 3]
(simplify 2 4) ;=> [1 2]
(simplify 100 40) ;=> [5 2]

Thanks to this site for the problem idea, where it is rated Very Hard in Swift. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://ericnormand.me/newsletter

(defn gcd [a b]
  (cond
    (= 0 b) a
    (< a b) (gcd b a)
    :else   (gcd b (mod a b))))

(defn simplify [a b]
  (let [d (gcd a b)]
    [(/ a d) (/ b d)]))

Almost perfect solution above, although gcd is tail-rec I would just use recur instead of explicit calls

(defn simplify [n d]  (mapv #(long (/ % (.gcd (biginteger n) (biginteger d)))) [n d]))

Using clojure ratios:

(defn simplify
  [n d]
  (let [r (/ n d)]
    (if (ratio? r)
      [(numerator r) (denominator r)]
      [r 1])))

(defn simplify [a b]
  (loop [x a
         y b]
    (if (zero? y)
      [(/ a x) (/ b x)]
      (recur y (mod x y)))))

Since others have already used gcd and ratio functions, here's an ugly hack just for fun.

(defn simplify [n d]
  (let [rr (/ n d)
        ss (mapv read-string (str/split (str rr) #"/"))]
    (if (ratio? rr) ss (conj ss 1))))

I thought I'd weigh in with a naïve implementation testing factors counting up from 2. It also showcases the seemingly little used but ever useful reduced.

(defn next-fraction [fraction factor]
  (let [simplified (mapv #(/ % factor) fraction)]
    (cond
      (every? int? simplified)      (recur simplified factor)
      (some #(> factor %) fraction) (reduced fraction)
      :else                         fraction)))

(defn simplify [n d]
  (reduce next-fraction [n d] (iterate inc 2)))

(defn simplify
  ([num den] (simplify 2 num den))
  ([cand num den]
   (cond (or (> cand num)
             (> cand den))            [num den]
         (and (zero? (mod num cand))
              (zero? (mod den cand))) (simplify cand (/ num cand) (/ den cand))
         :else                        (simplify (inc cand) num den))))