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.

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