4clojure 97 Pascal’s Triangle

4clojure problem 97 Pascal’s Triangle – calculate the nth row:

Pascal's Triangle

My solution:

(defn pascal [n]
  (if (= n 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


4 Responses to 4clojure 97 Pascal’s Triangle

  1. 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.

      • Merlyn Albery-Speyer

        I think this is that Haskell code translated into Clojure:
        (iterate (zip + (concat [0N] %1) (concat %1 [0N])) [1])

  2. Merlyn Albery-Speyer

    Oops. That should be:

    (iterate (map + (concat [0N] %1) (concat %1 [0N])) [1])

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>