Chris Pollett>Old Classes>PIC 15, Fall 1999>Hw2>HW2 Solution

;2.8 Problem was to write a function which produces the interval that results
; from subtracting two intervals I1 I2. 
; i.e., the output should be the range of values such that given
; x\in I1 and y \in I2 then x-y \in I1-I2
;
:

;Name: make-interval
;=====
;Purpose: 
;========
;given two number produces the interval from the lower number to the higher one.
;i.e., given xl and xu produces (xl xu) 
;
;Known Bugs:
;===========
;none

(define (make-interval a b) (cons a b))

;Name: upper-bound
;=====
;Purpose:
;========
;projects the upper bound of an interval x
; i.e., on input x:=(xl xu) returns xu
;
;Known Bugs:
;===========
;none
(define (upper-bound x) (cdr x))

;Name: lower-bound
;=====
;Purpose:
;========
;projects the lower bound of an interval x
; i.e., on input x:=(xl xu) returns xl
;
;Known Bugs:
;===========
;none
(define (lower-bound x) (car x))

;Here's the solution to the hw problem:
;
;Name: sub-interval
;=====
;Purpose:
;========
;subtracts the interval x from the interval y
; if x=(xl xu) and y=(yl yu) then returns (xl-yu xu-yl) 
;
;Known Bugs:
;===========
;none

(define (sub-interval x y)
  (let (( new-lower (- (lower-bound x) (upper-bound y)))
        ( new-upper (- (upper-bound x) (lower-bound y)))
        )
    (make-interval new-lower new-upper)
    )
  )

;
; Here is some code to test sub-interval:
;
(define test-interval (make-interval 5 6))
(define test-interval2 (make-interval 3 4))
(sub-interval test-interval test-interval2 )

;2.34 The problem was to complete the code in the book for
; evaluating polynomials using Horner's rule. Here's the sol'n.

;Name: horner-eval
;=====
;Purpose:
;========
;evaluate at the point x the polynomial whose coefficients
; are represented by coefficient-sequence
;
; i.e., if x = 3 and coefficient-sequence (1 1 1)
; outputs f(3)=13 where f(x)=1+x+x^2
;
;Known Bugs:
;===========
;none


(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) (+ (* higher-terms x)
                                                   this-coeff)
                )
              0
              coefficient-sequence)
  )

;
; Here's a test where we compute f(2)
; where f(x)= 1+3x+0x^2+5x^3+0x^4+x^5
;
(horner-eval 2 (list 1 3 0 5 0 1))

;2.42 The problem was to complete the code from the book for the
; n-queens problem. this involved figuring out what representation
; one should use for a bound and then writing empty-board (representation of
; of the empty board), safe? (which checks if a newly added position was safe)
; and adjoin-position (which given a row and a partial board
; outputs a new board with the row added). Here's the sol'n.

; Since we are only putting one piece (and that being a queen) in
; each row we can represent a board as a list of column number
; where queens are stored.
;
; Ex:
; (4 2 5 3 1)
; Says in the last row there is a queen in column 4.
; In the next to last row there is a queen in column 2.
; In the next to next to last row there is a queen in column 5, etc.


;Name: empty-board
;=====
;Purpose:
;========
;This is just a constant for the board with no pieces on it.
;In our representation described above this will be just the empty-list.
;
;Known Bugs:
;===========
;none
(define empty-board ())

;Name: adjoin-position
;=====
;Purpose:
;========
;Produces the board that would result when we add the row called "row" onto 
;the current board called "queens". In our representation we ignore the
;parameter k.
;
;To implement this in our representation we simply cons the column 
;position of "row" onto "queens"
;
;Known Bugs:
;===========
;none

(define (adjoin-position row k queens)
  (cons row queens)
  )

;Name: safe?
;=====
;Purpose:
;========
;This predicate outputs true iff the first member of positions
;(i.e., the last row added) doesn't threaten any queen in the
;remainder of positions.
;
;To implement this we use an auxiliary function safe-list?
;which checks to see if there is a queen in the same column
;or on a diagonal from the row we need to-check.
;
;Known Bugs:
;===========
;none

(define (safe? k positions)
  (define (safe-list? to-check correct cnt)
    (if (null? correct)
        #t
        (let ((pos (car correct)))      
        (if (or (= to-check pos) (= to-check (- pos cnt))
                (= to-check (+ pos cnt)))
            #f
            (safe-list? to-check (cdr correct) (+ cnt 1)))
          )   
    )
   ) ;end def of safe-list?
  
  (let ((to-check-pos (car positions))
        (correct-pos  (cdr positions))
        )
    (safe-list? to-check-pos correct-pos 1)
  )
 )