HtDP Solution Set

Section 12



Problem 1 (Solution):
#|
An auction-record is a structure
(make-auction String Number Number)
|#
 
(define-struct auction (item id bid))
 
#|
A list-of-auction-records is one of:
empty
(cons auction-record list-of-auction-records)
|#
 
;sort-auction-records-by-bid : list-of-auction-records -> list-of-auction-records
; sort list of auction records by decreasing bid amount
(define (sort-auction-records-by-bid aloar)
(cond
[(empty? aloar) empty]
[else (insert-auction (first aloar)
(sort-auction-records-by-bid (rest aloar)))]))
 
;insert-auction-record : auction-record list-of-auction-recort
; -> list-of-auction-records
; insert auction into a sorted list of records in the right decreasing bid spot
(define (insert-auction ar aloar)
(cond
[(empty? aloar) (cons ar empty)]
[else
(cond
[(>-auction-record ar (first aloar)) (cons ar aloar)]
[else (cons (first aloar) (insert-auction ar (rest aloar)))])]))
 
; >-auction-record : auction-record auction-record -> Boolean
; compare two auction records
(define (>-auction-record ar1 ar2)
(> (auction-bid ar1) (auction-bid ar2)))
 
#| Tests |#
 
(>-auction-record (make-auction 'lamp 4 4) (make-auction 'chair 1 1))
"should be" true
 
(insert-auction (make-auction 'chair 1 1) empty)
"should be" (cons (make-auction 'chair 1 1) empty)
(insert-auction (make-auction 'bed 3 3)
(cons (make-auction 'lamp 4 4)
(cons (make-auction 'chair 1 1) empty)))
"should be"
(cons (make-auction 'lamp 4 4)
(cons (make-auction 'bed 3 3)
(cons (make-auction 'chair 1 1) empty)))
 
(sort-auction-records-by-bid empty)
"should be" empty
(sort-auction-records-by-bid (cons (make-auction 'chair 1 1) empty))
"should be" (cons (make-auction 'chair 1 1) empty)
(sort-auction-records-by-bid
(cons (make-auction 'dvd 1 1) (cons (make-auction 'chair 2 2) empty)))
"should be"
(cons (make-auction 'chair 2 2) (cons (make-auction 'dvd 1 1) empty))
 


Problem 2 (Solution):
#| A list-of-number is one of
empty, or
(cons number list-of-number)
|#
 
;cancel-sum : list-of-number -> list-of-number
; add number to end of list that when summed with others produces zero
(define (cancel-sum alon)
(add-at-end (* -1 (sum-list alon)) alon))
 
;sum-list : list-of-number -> list-of-number
; sum up the numbers in a list
(define (sum-list alon)
(cond
[(empty? alon) 0]
[else (+ (first alon) (sum-list (rest alon)))]))
 
;add-at-end : number list-of-number -> list-of-number
; add number to end of list
(define (add-at-end n alon)
(cond
[(empty? alon) (cons n empty)]
[else (cons (first alon) (add-at-end n (rest alon)))]))
 
 
#| Tests |#
(add-at-end 3 empty)
"should be" (cons 3 empty)
(add-at-end 3 (cons 2 empty))
"should be" (cons 2 (cons 3 empty))
 
(sum-list empty)
"should be" 0
(sum-list (cons 1 empty))
"should be" 1
(sum-list (cons 1 (cons -3 empty)))
"should be" -2
 
(cancel-sum empty)
"should be " (cons 0 empty)
(cancel-sum (cons 1 empty))
"should be " (cons 1 (cons -1 empty))
(cancel-sum (cons 1 (cons 2 empty)))
"should be " (cons 1 (cons 2 (cons -3 empty)))
 
 


Problem 3 (Solution):
#| 
A list-of-list-of-symbol is one of
empty or
(cons list-of-symbol list-of-list-of-symbol)
 
A list-of-symbol is one of
empty or
(cons symbol list-of-symbol)
|#
 
;search-lolos : symbol list-of-list-of-symbol -> boolean
; look for symbol within a list of list of symbols
(define (search-lolos s alolos)
(cond
[(empty? alolos) false]
[else (or (search-los s (first alolos)) (search-lolos s (rest alolos)))]))
 
;search-los : list-of-symbol symbol -> boolean
; look for symbol with a list of symbols
(define (search-los s alos)
(cond
[(empty? alos) false]
[else (or (symbol=? s (first alos)) (search-los s (rest alos)))]))
 
#| Tests |#
(search-los 'a empty)
"should be" false
(search-los 'f (cons 'a (cons 'f empty)))
"should be" true
 
(search-lolos 'f empty)
"should be" false
(search-lolos 'g (cons empty (cons (cons 'a (cons 'f empty)) empty)))
"should be" false
(search-lolos 'f (cons (cons 'g empty) (cons (cons 'a (cons 'f empty)) empty)))
"should be" true
 


Problem 4 (Solution):
 
;expand-lon : list-of-number -> list-of-number
; produce new list with each original number repeated its number of times
(define (expand-lon alon)
(cond
[(empty? alon) empty]
[else (expand-num (first alon) (first alon) (expand-lon (rest alon)))]))
 
;expand-num : number number list-of-number -> list-of-number
; cons the first number of copies of the second number onto a list
 
(define (expand-num num onum alon)
(cond
[(zero? num) alon]
[else (cons onum (expand-num (sub1 num) onum alon))]))
 
(expand-num 2 2 empty)
"should be" (cons 2 (cons 2 empty))
 
(expand-lon empty)
"should be" empty
(expand-lon (cons 2 empty))
"should be" (cons 2 (cons 2 empty))
(expand-lon (cons 2 (cons 3 empty)))
"should be" (cons 2 (cons 2 (cons 3 (cons 3 (cons 3 empty)))))
 
 
 


Problem 5 (Solution):
#| A list-of-posn is one of
empty or
(cons posn list-of-posn)
|#
 
;complete-polygon : list-of-posn symbol -> boolean
; draw lines from each posn to every other posn in list
(define (complete-polygon lops color)
(cond
[(empty? (rest lops)) true]
[else (and (draw-lines (first lops) (rest lops) color)
(complete-polygon (rest lops) color))]))
 
;draw-lines : posn list-of-posn symbol -> boolean
; draw lines from posn to every posn in list
(define (draw-lines p lops color)
(cond
[(empty? lops) true]
[else (and (draw-solid-line p (first lops) color)
(draw-lines p (rest lops) color))]))
 
#| Tests |#
(start 100 100)
 
(define *mysq*
(cons (make-posn 10 10)
(cons (make-posn 90 10)
(cons (make-posn 10 90)
(cons (make-posn 90 90)
empty)))))
 
(define *mytri*
(cons (make-posn 10 50)
(cons (make-posn 50 10)
(cons (make-posn 90 50)
empty))))
 
(define *myhex*
(cons (make-posn 30 0)
(cons (make-posn 60 0)
(cons (make-posn 0 45)
(cons (make-posn 90 45)
(cons (make-posn 30 90)
(cons (make-posn 60 90)
empty)))))))
 
(complete-polygon *mytri* 'red)
"should be" true
(complete-polygon *mysq* 'green)
"should be" true
(complete-polygon *myhex* 'blue)
"should be" true
 



Jamie Raymond
Matthias Felleisen
 

23 september 2002