Problem Set 6

Due date: 10/30

Purpose:

The original problem set 6 is due a week later than planned.
The goal of this problem set is to learn to choose a design strategy and to reinforce the lessons of structural design, design with generative recursion, and the use and introduction of abstraction. The problems rely on HtDP Parts I-V, though you should be reading Part VI in preparation of next week.

Drill:

All previously assigned drill problems count for this week's help sessions (i.e., problems assigned in weeks 2 through 6.)

Required Problems:

Note: You must annotate each function with the design strategy that you used. Specifically, you must annotate each function with a comment that looks roughly like one of those:

domain knowledge exclusively (algebra, physics, watching traffic lights)
function composition (one task, one function)
structural design, on the 6th argument
structural design, on the 4th and 6th argument (if you choose this option, also document which of the three situations you are working with)
structural design, supplemented with list abstractions (313)
structural design, via my own abstraction
generative design.

If you use a design "with accumulators", be sure to explain the connection between the local recursion argument, the accumulator, and the initial argument.

Your kid sister is desperate. Her tough, German-born math teacher has assigned a large number of problems involving "arithmetic evaluations." His idea is to get students to understand how calculations proceed. For example, given an expression such as

 ((2 * 5) + ((5 + 6) - 3))

he wishes to see the complete calculation:

 ((2 * 5) + ((5 + 6) - 3))
 = (10 + ((5 + 6) - 3))
 = (10 + (11 - 3))
 = (10 + 8)
 = 18

That's the bad news. The good news is that he is fond of fully parenthesizing expressions and wishes that his students use them, too. Better still, all of his homework problems involve only three arithmetical operations: addition, multiplication, and subtraction.

Build a "homework machine" for your kid sister. The homework machine accepts (representations of) arithmetic expressions and produces (representations of) complete calculations. (Believe it or not, your kid sister understands ISL (with lambda) and is capable of translating her teacher's homework problems into data representations, provided you give precise instructions on how to create those. So that solves the part of your problem for which you can't design a solution yet; the best you'd be able to do is guess-and-try-and-fail kind of programming.)

Design the function hangman. The function consumes a string and creates a "hangman world", producing true as the answer. A player can then enter a character via the keyboard. The world program checks whether the character occurs in the chosen word and where. If so, the occurrences of the character are revealed. Otherwise, the hangman world program draws another limb of a hangman. Here is how I did with (hangman "hello"):

You are free to design the details of the hangman; you may even display the words instead of drawing it, but your program must allow for at least seven incorrect guesses.

Design the following three functions on strings:

prefix, which consumes two strings and computes their longest common prefix;
below, which consumes two strings and determines whether the first is "below" the second string;
A string s is below string t if (and only if) for any position i in s, t contains the same character as s or #\_.
contains, which consumes two strings and determines whether the second is contained in the first. If so it produces the 0-based index of the first such occurrence; otherwise, it produces false.

This exercise exposes the compound nature of strings. Read up on the BSL/ISL library to find out which functions turn strings into compound data structures that you understand.