Pascal’s Triangle

Tagged as LISP, Programming, Self-Learning, SICP

Written on 2008-02-07 03:25:28

A little over two weeks ago I came up against Exercise 1.12 in the venerable Structure and Interpretation of Computer Programs.

The exercise wants you to write a recursive program to compute elements of Pascal's Triangle.

This exercise has pretty much infuriated me and it's all my own fault. Upon first hearing the problem statement I got it in my head that the function should look something like "(define (pas n)...)". I always think of number series being described in terms of a single argument (i.e. the 12th element) so it seemed natural to me that the pascal's triangle function should be computed in this way even though it is not, in some sense, a traditional series.

After a while, I cracked and read the precursor text (but not the code) to Eli Bendersky's solution and noticing that he defined the function with two arguments (for columns and rows) arrived fairly quickly with that insight at what seems to be the more or less standard solution. I have had this much completed for a week but gotten stalled trying to figure out the problem of a pascal function that takes one argument.

As of today I've solved the problem though and hoped to share my results here. First, the throwaway code that ended up being good for nothing!

(define (is-one? element)
  (define (is-one-iter ones count flag)
    (cond ((< element 5) #t)
	  ((= ones element) #t)
	  ((> ones element) #f)
	  ((= flag 1) (is-one-iter (+ ones 1) count (- flag 1)))
	  (else (is-one-iter (+ ones count) (+ count 1) (+ flag 1)))))
  (is-one-iter 4 2 0))
;Value: is-one?

That code tests to see whether a given element equals one and it does take a single argument which is nice. I couldn't figure out a way to use it to compute the actual elements though.

After a little bit of experimenting I stumbled on this number sequence (OEIS #A080956) which when put in the following procedure would allow me to compute n from a given column and row.

EDIT: Corrected dyslexic mistake in my code (I'd replaced all instances of col with row and vice versa). See comments.

(define (n-from-rowcol row col)
  (define (f x)
    (- (/ (* (+ x 1) (- 2 x)) 2)))
  (+ row col (f (- row 1))))
;Value: n-from-rowcol

Now all I had to do was find a way to reverse the function to give me the inputs if I gave it the output. I actually stumbled upon another number sequence (OEIS #A000124, also known as the Lazy Caterer's Sequence) which when put into the following procedure returns the correct column and row for a given element. At last, working code:

(define (pascal n)
  (define (pas col row)
    (cond ((= col 1) 1)
	  ((= row 1) 1)
	  ((= col row) 1)
	  (else (+ (pas (- col 1) row)
		   (pas (- col 1) (- row 1))))))
  (define (colrow-from-n)
    (define (col-iter count)
      (define (f x)
	(- (/ (+ (square x) x 2) 2) x))
      (cond ((> (f count) n) (pas (- count 1) (- n (- (f (- count 1)) 1))))
	    ((= (f count) n) (pas (f count) 1))
	    (else (col-iter (+ count 1)))))
    (col-iter 1))
(colrow-from-n))
;Value: pascal

Any insights into cleaner code, better algorithms, or comparisons between the two number series are welcomed.

• ← Previous
• Next →