5 Jul 2012
4clojure problem 100 - calculate the Least Common Multiple (LCM) of two or more numbers.
Here’s how I worked it out in the REPL, warts and all….
I first thought about using the meaning of LCM to solve this (as given in Wikipedia), ie for two numbers a and b (eg 4 and 6), find all the multiples of a (an infinite sequence), find all the multiples of b (an infinite sequence), and find the first match. But I was impatient and didn’t want to work out how to find the first match between lists, so I decided to use the GCD definition:
From there it was just a matter of balancing parentheses (thanks paredit) by breaking up the problem into stages, starting with calculating the GCD of two numbers:
(defn gcd [a b]
(cond
(= b 0) a
(= a 0) b
(> a b) (gcd b (mod a b))
(> b a) (gcd a (mod b a))))
(gcd 15 5)
==> 5
Now get LCM working for two arguments:
(defn lcm [x y]
(/ (* x y) (gcd x y)))
(lcm 4 6)
==> 12
Now get LCM working for more than two arguments. I remembered seeing multiple arities used to solve other 4clojure problems, so I thought I’d use the Arity-Reduce “pattern” (well I’m using apply, same idea):
(defn lcm2
([x y] (/ (* x y) (gcd x y)))
([x y & rest] (apply lcm2 (lcm2 x y) rest)))
(lcm2 5 3 7)
==> 105
4clojure doesn’t allow defn, so I then used letfn to nest my definition of GCD inside LCM:
(fn lcm3
([x y]
(letfn [(gcd2 [a b]
(cond
(= b 0) a
(> a b) (gcd2 b (mod a b))
(> b a) (gcd2 a (mod b a))))]
(/ (* x y) (gcd2 x y))))
([x y & rest] (apply lcm3 (lcm3 x y) rest)))
(lcm3 5 3 7)
==> 105
So my solution worked, but it wasn’t very elegant - Dacquiri wins the prize for that, again :-)
comments powered by Disqus