Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Created August 8, 2022 03:00
Show Gist options
  • 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.

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

@nbardiuk
Copy link

nbardiuk commented Aug 8, 2022

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

@fredokun
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

@RedPenguin101
Copy link

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

@lonnelars
Copy link

Using clojure ratios:

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

@jonasseglare
Copy link

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

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

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

@JonathanHarford
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