A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which, $$ a^2 + b^2 = c^2 $$ For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which $a + b + c = 1000$. Find the product $abc$.
For this one, we could go ahead and dive into properties of Pythagorean triplets, of which there are many. You can read the Wikipedia page about them and get many hints on how to do this problem more efficiently than what I'm going to show you, and in fact in later articles we'll want to take advantage of these.
However as we say in software engineering: if the sub-optimal solution is good enough and more clear than more efficient solutions, then consider just using the sub-optimal solution. In this case, we can just use Clojure's for comprehension to give us an answer quickly:
(defn find-triplet [s]
(first
(for [a (range 1 s)
b (range (+ a 1) (- s a))
:let [c (- s a b)]
:when (== (* c c)
(+ (* a a) (* b b)))]
(list a b c))))
(println (reduce * (find-triplet 1000)))
This runs fast enough (remember that the JVM takes about 1.5s to start up on my machine):$ time clj 9.clj 31875000 real 0m1.635s user 0m3.341s sys 0m0.084s
No comments:
Post a Comment