Problem Set 8

Purpose This problem set concerns binary trees. Lots of binary trees.

Finger Exercises HtDP/2e: 221, 222, 223, 225

Problem 1 Implement a function leaf : Number -> [BinaryTree ArithOp] that produces a valid [BinaryTree ArithOp] that always evaluates to the given number. (This should be a very short function...)

(Note: If you try to write a straightforward check-expect for leaf, DrRacket will complain that you cannot compare functions for equality. We discussed in class why this was so. In order to test leaf, you’ll need to write a test of it and eval together.)

Problem 2 Implement the function eval which takes an ArithExp and produces a number (the result of the evaluation). Note that since the ArithExp definition makes use of the same structure as the [BinaryTree X] definition, we can—and should!—use our fold-tree function. For example the ArithExp (make-bt + (make-bt - (leaf 4) (leaf 3)) (leaf 2)) should produce 3 when evaluated. Make use of tree-fold in your answer.

Problem 3 In a comment, explain whether implementing eval using tree-fold actually evaluates its arithmetic expression in the correct order, namely the left-to-right, innermost-first order that Racket uses, and why.

Hint: Design a function that consumes a natural number n, and creates (a list of) all leafy binary trees of height equal or less than n.

Note: this is not about abstraction; it’s a kind of puzzle that will exercise your ability to think recursively. (We hope you) Have fun...

Problem 5 Design a function count-leafy-trees which consumes a natural number n and returns the number of distinct leafy binary trees of height n.

Problem 6 : Legos Let’s build some lego buildings out of lego bricks. Here are data definitions for lego bricks and lego buildings:

; A Lego is a (make-lego  String Color Number)

; where the String is a label

; the Color is the color of the lego brick

; and the Number is the width of the brick, in pixels

(define-struct lego (label color width))

; A LegoBuilding (LB) is one of:

; - Lego

; - (make-bigger Lego LB LB)

(define-struct bigger (lego left right))

; Where (make-bigger a b c) makes a lego building

; by putting a lego brick a on top of two lego

; buildings b and c.

Problem 7 Design a function, count-bricks, that takes a lego building and produces the total number of lego bricks in that building.

Problem 8 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 9 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 10 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. 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. NOTE: You will need another data definition to write the signature for this function.

Problem 11 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-lego "6" 'orange 60))

Problem 12 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 string "m" and lb is labeled with the string "n", then the lego we get by merging them is labeled with the string "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))