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:
(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)
[(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)
[(empty? aloar) (cons ar empty)]
[(>-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)
(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)
[(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)
[(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)
[(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)
[(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)
[(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)
[(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)
[(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)
[(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)
(define *mytri*
(cons (make-posn 10 50)
(cons (make-posn 50 10)
(cons (make-posn 90 50)
(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)
(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