$ cat /home/buntine/mind_melting_brilliance

Exercise 1.12 in SICP is proposed as follows:

My brain saw it as:

I spent about 30 minutes working on a solution that would actually return a structure containing all of the elements of Pascals Triangle up to a particular row/width. I was wondering the whole time how any non-experienced programmer could ever solve the problem at such an early stage of the book! D'oh!

Here is what I came up with:

(define (pascal width)
  (reverse (pascal-helper '((1)) width)))

(define (pascal-helper rows width)
  (if (= (length rows) width)
    rows
    (pascal-helper (cons (next-row (car rows))
                         rows)
                   width)))

(define (next-row previous)
  (let ((body (row-body '() previous)))
    (if (null? body)
      '(1 1)
      (cons 1 (append body '(1))))))

(define (row-body body previous)
  (if (null? (cdr previous))
    body
    (row-body (cons (+ (car previous) (cadr previous))
                    body)
              (cdr previous))))

And lets see it in action:

> (pascal 5)
> ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))

It works by building each row of the triangle in reverse order. Each row implements a linearly recursive process to build itself based on the contents of the previous row. We consume the previous row by taking it's cdr on each resursion. This means that the value of element y in row x is the sum of the first two elements in the previous row. This process is continued until the previous row has only one element left. At this point we throw a 1 on either side and we are done!

From now on I will be sure to pay more attention when interpreting the requirements for each exercise (although I secretly think this was much more fun)!