Problem Set 9h

This is the honors version of Problem Set 9.

Purpose This problem set concerns the use of existing abstractions, simultaneous processing of inputs, and trees.

Finger Exercises HtDP/2e: 264, 265, 266, 267, 268, 276, 279, 282, 321, 323

More Sequences!

The following problems deal with Sequences as defined on last week’s problem set. Refer to Problem Set 8h for data definitions of [Sequence X] and [Equality X].

Problem 1 : Equality of Sequences

1. Design a function sequence=?, that consumes two [Sequence X] and an [Equality X] and determines if they are equal.

2. Design a function sequence-number=?, that consumes two [Sequence Number] and determines if they are equal. Note that sequence-number=? is an [Equality [Sequence Number]]. Note that both 3 and '(2 1 0) are examples of [Sequence Number] and they happen to be equal.

Both of these functions will be helpful for writing tests.

Problem 2 : Growing, Shrinking, and Combining Sequences

1. Design a function sequence-length that outputs the length of a sequence. Use sequence-foldr.

2. We have sequence-empty?, sequence-first, and sequence-rest. What are we missing? sequence-cons, of course!

   Design a function sequence-cons which puts an element at the start of a sequence. Note that you have no idea what data structure the sequence is given in, and that your function should act independently of that. Hint: can sequence-foldr help?

3. Design a function sequence-remover which, given a [Sequence X] and an [Equality X], will output a function that, given an X, will return the sequence with the first instance of that x removed.

4. Design a function sequence-append that will append two sequences together.

5. Design a function sequence-append-all that will flatten a sequence of sequences into one sequence.

6. Design a function sequence-sequence=?, which given an [Equality X] will output an [Equality [Sequence [Sequence X]]].

Problem 3 : Sequence Cartesian Product

We want you to design sequence-cartesian-product, which takes a [Sequence [Sequence X]] and returns a [Sequence [Sequence X]]. Let’s make clear what it has to do.

((sequence-sequence=? =) (sequence-cartesian-product '((0 1 2)  (3 4)))

'((0 3) (0 4) (1 3) (1 4) (2 3) (2 4)))

The above code should return true. Given the sequence '(0 1 2) and '(3 4), it outputs a [Sequence [Sequence Number]], each element of which contains two elements, where the first element came from the first sequence and the second came from the second seqeunce. It was also in an order such that everything beginning with 0 came first, and everything ending with 3 came before all that ended with 4, provided the first element was equal. Now, for a more formal specification...

The cartesian product of Sequences S-1, S-2... S-n is defined as a sequence of sequences of size n, where the kth element of a, a sequence in the output sequence, is from S-k. It is ordered in such a way that, if S-1 is the sequence x-1, x-2, x-3...x-y, all sequences beginning with x-1 appear before x-2, appear before x-3, etc. Then, within all sequences that begin with x-1, the ordering is defined the same way, except with S-2 taking the part of S-1, and so on.

Here’s another example to illustrate:

((sequence-sequence=? symbol=?)

(sequence-cartesian-product '((a b) (red green blue) (hutt putt)))

`((a red hutt)

(a red putt)

(a green hutt)

(a green putt)

(a blue hutt)

(a blue putt)

(b red hutt)

(b red putt)

(b green hutt)

(b green putt)

(b blue hutt)

(b blue putt)))

1. When tackling such problems, it’s always a good idea to have many ways to test our functions. We already have sequence-sequence=?, but let’s have another one for good measure. Design a function sequence-cartesian-product-length, that given a sequence of sequences will predict the length of sequence-cartesian-product applied to that sequence of sequences.

2. Design sequence-cartesian-product. Warning: use of helpers will prevent you from getting lost! Here are some hints:

   • Use the magic of recursion and sequence-foldr to create the cartesian product of all sequences except the first one.

   • Write a helper that will sequence-cons one element onto every sequence in a sequence of sequences.

   • Do that to all of the elements in the first sequence and sequence-append-all of them together.

   Advice: If you find yourself stuck on this problem, complete the rest of the problem set first.

Legos!

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

Problem 5 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 6 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 7 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.

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