Instantly share code, notes, and snippets.

# ericnormand/00 Simplifying fractions.md

Created August 8, 2022 03:00
Show Gist options
• Save ericnormand/8698a9a60fcfebb3e6cf8953d710700f to your computer and use it in GitHub Desktop.

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.

### 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 commented Aug 8, 2022

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

### RedPenguin101 commented Aug 8, 2022

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

### lonnelars commented Aug 8, 2022

Using clojure ratios:

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

### jonasseglare commented Aug 8, 2022

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

### mchampine commented Aug 8, 2022

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 commented Aug 9, 2022

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 commented Aug 9, 2022

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