HtDP Solution Set

Section 14



Problem 1 (Solution):
#|
An ft-node is one of
empty or
child
 
A child is a structure
(make-child ft-node ft-node symbol number symbol)
 
A list-of-symbol is one of
empty or
(cons symbol list-of-symbol)
|#
 
(define-struct child (father mother name birthyear eyes))
 
 
(define gms (make-child empty empty 'erma 1880 'blue))
(define gps (make-child empty empty 'john 1876 'blue))
(define gmh (make-child empty empty 'mary 1856 'blue))
(define gph (make-child empty empty 'reuben 1840 'green))
(define ph (make-child gph gmh 'charles 1903 'blue))
(define mh (make-child gps gms 'betty 1902 'brown))
(define mom (make-child ph mh 'stacy 1952 'brown))
(define mr (make-child empty empty 'margaret 1902 'green))
(define pr (make-child empty empty 'james 1900 'brown))
(define dad (make-child pr mr 'jim 1946 'brown))
(define me (make-child dad mom 'jamie 1970 'brown))
 
;mothers-names : ft-node -> list-of-symbol
(define (mothers-names atree)
(cond
[(empty? atree) empty]
[(child? atree) (append (mother-s-name atree)
(mothers-names (child-mother atree))
(mothers-names (child-father atree)))]))
 
; mother-s-name : child -> list-of-symbol
(define (mother-s-name achild)
(cond
[(empty? (child-mother achild)) empty]
[else (cons (child-name (child-mother achild)) empty)]))
 
 
#| Tests |#
(mothers-names empty)
"should be" empty
(mothers-names dad)
"should be" (cons 'margaret empty)
(mothers-names me)
"should be" (cons 'stacy (cons 'betty (cons 'erma (cons 'mary (cons 'margaret empty)))))
 
 


Problem 2 (Solution):
;born-after : number ft-node -> list-of-symbol
; produce list of name of people born after given year
(define (born-after ayear atree)
(cond
[(empty? atree) empty]
[(child? atree)
(append (check-child-year ayear atree)
(born-after ayear (child-father atree))
(born-after ayear (child-mother atree)))]))
 
;check-child-year : number child -> list-of-symbol
; return list of name if birth year is less than given year
(define (check-child-year ayear achild)
(cond
[(> (child-birthyear achild) ayear) (cons (child-name achild) empty)]
[else empty]))
 
#| Tests |#
(check-child-year 1910 me) "should be" (cons 'jamie empty)
(check-child-year 1986 me) "should be" empty
 
(born-after 2002 empty) "should be" empty
(born-after 2002 me) "should be" empty
(born-after 1900 me)
"should be"
(cons 'jamie
(cons 'jim
(cons 'margaret
(cons 'stacy
(cons 'charles
(cons 'betty empty))))))
 


Problem 3 (Solution):
#|
A Web-page (shor: WP) is one of:
1. empty
2. (cons symbol WP)
3. (cons WP WP)
|#
 
; remove-wp : WP -> WP
(define (remove-wp awp)
(cond
[(empty? awp) empty]
[(symbol? (first awp)) (cond
[(symbol=? (first awp) '%remove) empty]
[else (cons (first awp) (remove-wp (rest awp)))])]
[else (cons (remove-wp (first awp)) (remove-wp (rest awp)))]))
 
#| Tests |#
(remove-wp empty)
"should be" empty
 
(remove-wp
(cons 'TeachScheme
(cons 'Webpage
(cons (cons '%remove (cons 'Lecture (cons 'Notes (cons 'for (cons 'Teachers empty)))))
(cons (cons 'DrScheme empty)
empty)))))
"should be"
(cons 'TeachScheme (cons 'Webpage (cons empty (cons (cons 'DrScheme empty) empty))))
 


Problem 4 (Solution):
#|
A File is a structure
(make-file symbol string)
|#
 
(define-struct file (name contents))
 
#|
A P2P-Network is one of
- empty
- (make-node number list-of-file P2P-Network)
 
A list-of-file is one of
- empty or
- (cons File list-of-file)
|#
 
(define-struct node (address files neighbor))
 
;p2p-search : symbol P2P-Network -> number or false
; return address of node containing item or false if not in network
(define (p2p-search item net)
(cond
[(empty? net) false]
[else (cond
[(in-node? item (node-files net)) (node-address net)]
[else (p2p-search item (node-neighbor net))])]))
 
;in-node? : symbol list-of-file -> boolean
; looks for item in node's list of files
(define (in-node? item files)
(cond
[(empty? files) false]
[else (or (symbol=? item (file-name (first files)))
(in-node? item (rest files)))]))
 
;p2p-search-all : symbol P2P-Network -> list-of-number
; produce addresses of all nodes hosting file
(define (p2p-search-all item net)
(cond
[(empty? net) empty]
[else
(cond
[(in-node? item (node-files net))
(cons (node-address net)
(p2p-search-all item (node-neighbor net)))]
[else (p2p-search-all item (node-neighbor net))])]))
 
#| Tests |#
(define f1 (make-file 'earth "the earth is great"))
(define f2 (make-file 'rain "i like rain too"))
(define f3 (make-file 'fire "burn fire burn"))
(define n1 (make-node 1001 empty empty))
(define n2 (make-node 1002 (cons f2 empty) n1))
(define n3 (make-node 1003 (cons f3 (cons f2 (cons f1 empty))) n2))
 
(in-node? 'rain empty) "should be" false
(in-node? 'rain (cons f1 (cons f2 empty))) "should be" true
 
(p2p-search 'rain n1) "should be" false
(p2p-search 'rain n2) "should be" 1002
(p2p-search 'rain n3) "should be" 1003
 
(p2p-search-all 'rain n1) "should be" empty
(p2p-search-all 'rain n3) "should be" (cons 1003 (cons 1002 empty))
 


Problem 5 (Solution):
;p2p-get : symbol number P2P-Network -> string
; return contents of file from a particular node or false
(define (p2p-get item address net)
(cond
[(empty? net) (error 'pgp-get "can't happen")]
[else (cond
[(= (node-address net) address)
(get-file-contents item (node-files net))]
[else (p2p-get item address (node-neighbor net))])]))
 
;get-file-contents : symbol list-of-file -> string or false
(define (get-file-contents item files)
(cond
[(empty? files) false]
[else (cond
[(symbol=? item (file-name (first files)))
(file-contents (first files))]
[else (get-file-contents item (rest files))])]))
 
#| Tests |#
(get-file-contents 'rain empty) "should be" false
(get-file-contents 'rain (cons f1 (cons f2 (cons f3 empty)))) "should be" "i like rain too"
 
(p2p-get 'rain 1002 n2) "should be" "i like rain too"
(p2p-get 'fire 1003 n3) "should be" "burn fire burn"



Jamie Raymond
Matthias Felleisen
 

23 september 2002