4clojure 97 Pascal’s Triangle
| 04-Jun-2012 | Posted by Sonia Hamilton under Clojure |
4clojure problem 97 Pascal’s Triangle – calculate the nth row:
My solution:
(defn pascal [n]
(if (= n 1)
[1]
(map #(apply + %)
(partition 2 1
(concat [0] (pascal (- n 1)) [0])))))
(pascal 5)
user=> (1 4 6 4 1)
A negative – my solution doesn’t use tail recursion; on my laptop it works up to about n = 760:
(pascal 10e4) user=> java.lang.StackOverflowError (NO_SOURCE_FILE:0)
Share This
There is a lovely solution here for haskell. It is representing the recursiveness of the problem directly in the solution, and relying on lazy evaluation to deal with the fact that the triangle is infinite. I translated this to clojure as:
(defn next-row [coll]
(map + (lazy-cat [0N] coll) (lazy-cat coll [0N])))
(def triangle (iterate next-row '(1N)))
(defn pascal [n]
(nth triangle n))
I am using big ints, because integers overflow otherwise, and it runs ok for about 1500, but at some point above that it blows the JVM heap. I’m sure that can be solved…
Hey that’s a cool solution :-) A mate at work is studying Haskell, I asked him to do Pascal’s triangle this morning, I might show him that solution when he’s done.