Homework 9

Due Date: Monday November 16, 6pm.

Purpose: Practice working with tree data, and using lambdas and local definitions.

Expectations

• You and your partner must submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept no email submissions.

• You must use the language specified at the top of this page.

• Your code must conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses, so revisit it before submitting each assignment. (You can resubmit as many times as you like until the due date without penalty.)

• Unless otherwise stated, every function and data definition that you design, including helper functions, must follow all steps of the design recipe.

Finger Exercises HtDP/2e: 282, 283, 285, 288, 289

Matrices

Exercise 1 Design a function scalar-matrix, which, for given numbers n and k, produces an n×n matrix (a list of lists of numbers), where the diagonal entries (first of the first row, second of the second row, etc.) are k and all other entries are 0. For example, (scalar-matrix 3 2) should produce a representation of the following matrix

2 0 0

0 2 0

0 0 2

Exercise 2 Design a function diagonal-matrix, which, given a number n and a function f, produces a diagonal matrix, that is, an n×n matrix where all diagonal entries are generated by f as follows:

(f 0) 0     0     0

0     (f 1) 0     0

0     0     (f 2) 0

0     0     0     (f 3)

Write at least 3 check-expects using lambda.

Exercise 3 Design a function scalar-matrix/v2 using diagonal-matrix.

Exercise 4 Design a function matrix->string, which converts a given matrix into a string representation, where each row occupies a separate line. For example (matrix->string (scalar-matrix 4 1)) should return a string containing

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

You must use list abstractions to solve this problem. Trailing spaces and newlines are fine. You can assume that each entry in the given matrix is a single digit.

Family trees

Exercise 7 Design the function valid-ft? which validates the given family tree. That is, it should return #true if the given FamilyTree is valid and #false otherwise. A FamilyTree is valid if and only if every person in the tree is younger than their parents.

Legos!

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

(define-struct lego (label color width))

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

; Interpretation: (make-lego l c w) is a lego brick

; with a 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).

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

Exercise 9 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).

Exercise 10 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.

Exercise 11 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.

Here is the data definition for the type of data this function returns:

; 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.

Exercise 12 Design a function, lb->image, that takes a lego building and produces an image of the building.

Here are some examples:

> (lb->image (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))))

> (lb->image (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)))