Skip to content

Instantly share code, notes, and snippets.

Created August 8, 2022 03:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ericnormand/8698a9a60fcfebb3e6cf8953d710700f to your computer and use it in GitHub Desktop.
Save ericnormand/8698a9a60fcfebb3e6cf8953d710700f to your computer and use it in GitHub Desktop.
473 Eric Normand Newsletter

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.


;; 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:

Copy link

nbardiuk commented Aug 8, 2022

(defn gcd [a b]
    (= 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)]))

Copy link

fredokun commented Aug 8, 2022

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

Copy link

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

Copy link

Using clojure ratios:

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

Copy link

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

Copy link

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))))

Copy link

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)]
      (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)))

Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment