sicp-ex-1.12



<< Previous exercise (1.11) | sicp-solutions | Next exercise (1.13) >>


  
 ;; ex 1.12 
  
 (define (pascal r c) 
   (if (or (= c 1) (= c r)) 
       1 
       (+ (pascal (- r 1) (- c 1)) (pascal (- r 1) c)))) 
  
 ;; Testing 
 (pascal 1 1) 
 (pascal 2 2) 
 (pascal 3 2) 
 (pascal 4 2) 
 (pascal 5 2) 
 (pascal 5 3) 
  

Computes an entry in the Pascal triangle given the row and column. Rows start from 1, counting from above; columns start from 1 too, counting from left to right.

  
 ;; ex 1.12 
  
 (define (pascal-triangle row col) 
   (cond ((> col row) 0) 
         ((< col 0) 0) 
         ((= col 1) 1) 
         ((+ (pascal-triangle (- row 1) (- col 1)) 
             (pascal-triangle (- row 1) col))))) 
  
 ;; Testing 
 (pascal-triangle 1 1) 
 (pascal-triangle 2 2) 
 (pascal-triangle 3 2) 
 (pascal-triangle 4 2) 
 (pascal-triangle 5 2) 
 (pascal-triangle 5 3) 
  

I find this one easier to grok, it allows only values though:

 (define (pascal row col) 
   (cond ((or (< row col)  
              (< col 1)) 0 ) 
         ((or (= col 1) 
              (= col row)) 1) 
         (else (+ (pascal (- row 1) (- col 1)) 
                  (pascal (- row 1) col ))))) 
  

Not having to worry about zero values makes it clearer to me:

 ;; rows / elements numbered starting at 1 
 ;; first / last elements in a row = 1 
 (define (ptcell r e) 
     (cond ((= e 1) 1) 
           ((= e r) 1) 
           (else (+ (ptcell (- r 1) (- e 1)) 
                    (ptcell (- r 1) e))))) 

Off on a tangent having misread the question & skipping ahead a few chapters:

;;; calculates nth row of pascal's triangle as a list
(define (pascal n)
  (define (p-row prev)
    (cond ((null? (cdr prev)) (list 1))
          ((= 1 (car prev)) (cons 1 (cons (+ (car prev) (cadr prev)) (p-row (cdr prev)))))
          (else (cons (+ (car prev) (cadr prev)) (p-row (cdr prev))))))
  (cond ((< n 1) (display "error: one or more rows"))
        ((= n 1) 1)
        ((= n 2) (list 1 1))
        (else (p-row (pascal (- n 1))))))

If you don't consider out of bounds cases, like negative numbers and other places outside the triangle, you can get a pretty simple solution. Push the triangle so it's left aligned with the 0th column, and you will see that if the column is 0 (in a 0-based world it's the left most of any depth) or if the col equals the depth (the last valid entry in that depth for the triangle), you will get 1. Otherwise, the value of the triangle is the number directly above it added to the number above and to the left.

 ;;;Left-aligned triangle, assuming the top most is at (col=0, depth=0) 
 ;;;1 
 ;;;1  1 
 ;;;1  2  1 
 ;;;1  3  3  1 
 ;;;1  4  6  4  1 
 ;;;1  5  10 10 5  1 
  
 (define (pascal col depth) 
   (cond  
     ((= col 0) 1) 
     ((= col depth) 1) 
     (else (+ (pascal (- col 1) (- depth 1))  
              (pascal col ( - depth 1)))))) 
 ; Left-aligned triangale with start at row=0 and col=0 
 ; 1 
 ; 1  5 
 ; 1  4 10 
 ; 1  3  6 10 
 ; 1  2  3  4  5 
 ; 1  1  1  1  1  1 
 (define (pascal row col) 
   (if (or (= row 0) (= col 0)) 
     1 
     (+ (pascal (- row 1) col) (pascal row (- col 1))))) 
 ;; This is wrong. One error is (pascal row (- col 1)) because it means 
 ;; using an element of the same row, which is not what the construction rule 
 ;; says. Another error is not handling out-of-bounds as zero and instead 
 ;; yielding one. This procedure only works for row=0, col=0. 
  
 ;; This is not wrong! It is an elegant and efficient way from a different perspective. 
 ;; The starting point is at bottom left (0 0), which yields 1 (the root) 
 ;; Every value can be calculated by reading it this way. for example: (pascal 2 2) yields 6 
 ;; If it is a problem that no out-of-bounds are handled, 
 ;; the second row can easily be modified like this: 
 ;; (if (or (< row 1) (< col 1)) 

Defining pas-n, where:

(pas-n 1) evaluates (pas 1 1)

(pas-n 2) evaluates (pas 2 1)

(pas-n 5) evaluates (pas 3 2)

and so on

 ;; firstly we define (pas x y) the same way as other solutions before 
 (define (pas x y) 
   (if (or (= y 1) (= y x)) 
       1 
       (+ (pas (- x 1) (- y 1)) 
          (pas (- x 1) y)))) 
  
 ;;now defining pas-n 
 (define (pas-n n) 
   (define (iter x y counter) 
     (cond ((= counter 1) (pas x y)) 
           ((= x y) (iter (+ x 1) 1 (- counter 1))) 
           (else (iter x (+ y 1) (- counter 1))))) 
   (iter 1 1 n)) 

A solution following the Wikipedia formula

 (define (pascal n k) ; entry in the nth row and kth column of Pascal's triangle 
     (cond ((or (< n 0) ; for any non-negative integer n 
                (or (< k 0) (> k n))) ; and any integer k between 0 and n, inclusive 
           0) ; treating blank entries as 0 
           ((and (= n 0) (= k 0)) 1) ; unique nonzero entry 
           (else (+ (pascal (- n 1) (- k 1)) ; adding the number above and to the left 
                    (pascal (- n 1) k))))) ; with the number above and to the right 

Here's one with binomial coefficient and tail recursion:

 (define (pascals-triangle number row) 
   (define (factorial n) 
     (define (iter n acc) 
       (if (< n 2) acc 
                   (iter (- n 1) (* n acc)))) 
     (iter n 1)) 
   (/ (factorial (- row 1)) (* (factorial (- number 1)) (factorial (- (- row 1) (- number 1)))))) 
  
 (pascals-triangle 1000 2000) 

This solution includes some input checks, and errors out if the input is invalid (rather than returning 0 for invalid input, as some solutions above do). It also starts the row and column numbering with zero, as suggested in a course video:

 (define (pascal row col)  
   (cond ((or (= 0 col) (and (= col row) (> col 0))) 1) ; first and last columns 
         ((or (< col 0) (< row 0) (> col row)) (raise "bad input")) ; rudimentary input check 
         (else  
               (+ (pascal (- row 1) (- col 1))  
                  (pascal (- row 1) col)))))