Problem Set 9h
DUE DATE: 6pm, Friday, November 8
This is the honors version of Problem Set 9; if you’re looking for the normal version, click here.
Purpose This problem set concerns trees and the design of functions on XML-like data.
Do all problems on Problem Set 9, as well as the following problems.
Legos!
(define-struct lego (label color width)) ; A Lego is a structure: ; (make-lego Number Symbol Number) ; interpretation: (make-lego l c w) is the lego brick ; with label l, color c, and width w (in pixels). (define-struct bigger (lego left right)) ; A LegoBldg (lego building) is one of: ; - Lego ; - (make-bigger Lego LegoBldg LegoBldg) ; interpretation: (make-bigger l lft rgt) makes a bigger ; lego building by putting a lego brick l on top of two lego ; buildings lft (left) and rgt (right).
Problem 1h Design a function, count-bricks, that takes a lego building and produces the total number of lego bricks in that building.
Problem 2h Each lego brick is 10 pixels tall. Design a function, how-high, that takes a lego building and produces the total height of the lego building (in pixels).
Problem 3h Design a function, contains-colored-brick?, that takes a lego building and a color, and determines whether the building contains a lego brick of the given color.
Problem 4h Design a function, find-colored-brick?, that takes a lego building and a color and finds any lego with the given color in the building, or returns false if there are no such legos.
; A MaybeLego is one of: ; - false ; - Lego
Your function should not use contains-colored-brick?, it should not traverse/examine parts of the building more than once, and it should stop searching once any brick of the given color is found.
Problem 5h Design a function, lb->image, that takes a lego building and produces an image of the building.
Hints: You may want to look up above and beside/align in Help Desk. Also, you may want to design a helper function, lego->image, that takes a lego and produces an image of the lego. All legos are rectangular and 10 pixels tall.
(make-bigger (make-lego 4 'purple 80) (make-bigger (make-lego 2 'blue 60) (make-lego 1 'yellow 40) (make-lego 3 'red 40)) (make-bigger (make-lego 6 'orange 60) (make-lego 5 'green 40) (make-lego 7 'red 40)))
(make-bigger (make-lego 4 'purple 80) (make-bigger (make-lego 2 'blue 60) (make-lego 1 'yellow 40) (make-lego 3 'red 40)) (make-lego 6 'orange 60))
Problem 6h Design a function, merge-lb, that takes two lego buildings and merges them into a new lego building. Two buildings can be merged if corresponding bricks (starting with the brick at the top) are of the same color. If the buildings cannot be merged, the function should produce an error: merge-lb: Colors don’t match. The two buildings need not have the same number of bricks; the bricks in each building that don’t correspond to bricks in the other building should be discarded.
Here’s how two legos la and lb are merged (assuming their colors match):
If la is labeled with the number m and lb is labeled with the number n, then the lego we get by merging them is labeled with the number m.n.
The legos la, lb, and the merged lego piece all have the same color.
The widths of la and lb are added together to get the width of the merged piece.
Here are some examples to illustrate:
(merge-lb (make-bigger (make-lego 2 'blue 60) (make-lego 1 'yellow 40) (make-lego 3 'red 40)) (make-bigger (make-lego 2 'blue 60) (make-lego 1 'yellow 40) (make-lego 11 'red 20))) ---> (make-bigger (make-lego 2.2 'blue 120) (make-lego 1.1 'yellow 80) (make-lego 3.11 'red 60)) (merge-lb (make-bigger (make-lego 4 'purple 80) (make-bigger (make-lego 2 'blue 60) (make-lego 1 'yellow 40) (make-lego 3 'red 40)) (make-lego 6 'orange 60)) (make-bigger (make-lego 4 'purple 80) (make-lego 2 'blue 60) (make-bigger (make-lego 6 'orange 60) (make-lego 5 'green 40) (make-lego 7 'red 40)))) ---> (make-bigger (make-lego 4.4 'purple 160) (make-lego 2.2 'blue 120) (make-lego 6.6 'orange 120))
Orderly Legos
Let’s build a different kind of lego building where all legos in the building must have distinct labels and brick labels appear in a certain order in the building.
; An OrdLegoBldg (ordered lego building) is one of: ; - 'none ; - Lego ; - (make-bigger Lego OrdLegoBldg OrdLegoBldg) ; where each lego brick in the building has a unique label and ; where each (make-bigger l lft rgt) has the property that ; – the label of l is bigger than all the labels in lft ; – the label of l is smaller than all the labels in rgt
All functions that you design below must exploit/maintain the distinct-label and label-ordering properties of OrdLegoBldgs.
Problem 7h Design a function, ord-lb-contains?, that takes an ordered lego building and a label and determines whether the building contains a lego with that label.
Problem 8h Design a function, colors-in-order, that takes an ordered lego building and produces a list of colors. The output list must be ordered so that it starts with the color of the lego with the smallest label in the building and ends with the color of the lego with the highest label.
You may use append to concatenate lists of colors. Your function should not traverse/examine parts of the building more than once.
Problem 9h Design a function, grow-ord-lb, that takes an ordered lego building and a lego brick and adds the brick to the building. If the new brick’s label is the same as the label of a brick already in the building, return an error: Label already in building. The new building must be an OrdLegoBldg that is, it must satisfy the distinct-label and label-ordering properties of OrdLegoBldg.
Problem 10h Design a function, build-ord-lb, that takes a list of legos and produces an ordered lego building built using these legos. The building must be an OrdLegoBldg (i.e., it must satisfy the distinct-label and label-ordering properties of OrdLegoBldg). If the input list contains multiple legos with the same label, report an error.