Question 1 Singles

1. Consider the following function:

   // Requires: b >= 0.
   int mystery( int a, int b )
   {
     if( b == 0 ) {
       return a;
     } else {
       return 1 + mystery( a, b - 1 );
     }
   }

   What does this function do (in a weird, roundabout way)? What does it return when b is 0? When b is 1? If you're stuck, try dropping the code into a sketch and trying a few examples in setup().

   (You don't have to write a function for this problem; just understand the one that's given.)

2. Rewrite the function repeat(), as described in Lab 01, using recursion. The function should still take two arguments: a String and an int, and it should be recursive on the int (that is, any recursive call will use the same string argument and an integer that's one smaller). It should still return a String. It should follow the general layout of the mystery() function above, with string operations substituted for arithmetic.

3. Write a new function repeatArray() that takes two arguments: an array of integers and a single integer saying how many times to repeat it. It should behave similarly to repeat(), but with arrays instead of strings. That is, if arr is the array {3, 1, 4} then repeat( arr, 0 ) should be {} (an array of length zero), repeat( arr, 2 ) should be {3, 1, 4, 3, 1, 4}, repeat( arr, 4 ) should be {3, 1, 4, 3, 1, 4, 3, 1, 4, 3, 1, 4}, and so on. Once again, use recursion, just with array operations (particularly concat()).

Question 2 Towers of Hanoi

The Towers of Hanoi is a classic puzzle. You have three pegs, which we'll arrange in a row and label 0, 1, and 2 from left to right. The puzzle starts with a stack of n discs on Peg 0. The largest disc is on the bottom, and they get strictly smaller towards the top. The goal is to move all the discs from Peg 0 to Peg 2, under the following restrictions:

• A move consists of lifting the topmost disc off of one peg, and dropping it onto a different peg.
• No disc is ever allowed to sit on top of a disc that's smaller than it is.

You can see that all the moves in the video above obey these two rules. The puzzle be solved for any number of discs if we use a third peg as a kind of "storage area". For example, the following sequence shows the initial state of a puzzle with three discs, followed by the seven moves required to solve the puzzle (click for a PDF). To the right of every step is a description of the move in text form. For example, the first move, 0 → 2, tells us to move a disc from Peg 0 to Peg 2.

In the provided starter code, open the Hanoi sketch and run it. You'll see a simple Towers of Hanoi visualization with three discs. Pressing the space bar will walk through the move sequence above to solve the puzzle for you.

You should ignore the Hanoi tab. It contains a lot of code to manage the visualization of the game, but you don't need to change anything in it. Instead, go straight to the Moves tab. Read the comments. You'll see two global variables you can use to control the sketch, and an empty function called hanoiMoves(). The only thing you have to do is complete this function. This function will turn out to be recursive: the body of hanoiMoves() will contain calls to hanoiMoves(). It will also use a provided helper function called move() to express a single move of a disc from one peg to another.

The logic behind solving Towers of Hanoi is quite elegant. Think about the general problem of moving n discs from Peg p_f to Peg p_t, using Peg p_s as the storage peg. Here, n is an integer that's at least 1, and p_f, p_t, and p_s are the numbers 0, 1 and 2 in some order. The base case is when n is 1; in that case, we simply move a single disc from p_f to p_t, and we're done. Otherwise, n is more than 1, so we break the solution into three phases:

1. Move n-1 discs from p_f to p_s.

2. Move the largest disc, which has now been exposed, from p_f to p_t.

3. Move n-1 discs from p_s to p_t.

You can translate these steps more-or-less directly into code. And while the description is somewhat detailed, the solution is very simple: you will need around seven short lines of code in hanoiMoves() to complete this question.

Save your work in a sketch titled Hanoi

Question 3 Cantor's Comb

Imagine starting with a strip of paper and removing its middle third. You'd end up with two smaller strips, each a third the length of the original, separated by a gap of the same length. Now remove the middle third of each of those strips to get four even smaller strips. Remove the middle third of each of those four. Repeat this process as many times as you like. Theoretically, if you continued this process forever, you'd end up with a mysterious mathematical object called the Cantor Set. Of course, we don't need to continue the process forever, and the intermediate stages can be visually interesting. If you stack them up vertically, you get a weird-looking comb like the drawing above. Think of the comb as consisting of horizontal "slabs", where each slab shows the construction carried out to a different number of levels.

We can think of drawing each slab as a recursive function that takes three values as arguments: the start and end x coordinates of the slab, and the number of levels of removal to perform. If the number of levels is zero, that's a base case: we just draw the entire slab connecting the start and end x coordinates. If the number of levels is greater than zero, we need to proceed recursively:

1. Draw a slab with one fewer levels, extending across the first third of the slab you were asked to draw.

2. Draw a slab with one fewer levels, extending across the last third of the slab you were asked to draw.

In the provided starter code, open the sketch Cantor. The sketch attempts to draw the comb image above, by calling a recursive helper function cantor() with different numbers of levels of removal. Your job is to fill in the cantor() function according to the logic above. In the base case, use rect() to draw a rectangle. The x coordinate and width of the rectangle are the recursive part; the rectangle should always start at y=0 and have height 40. In the recursive case, make two recursive calls as described above. The provided setup() function will use geometric contexts to draw six slabs stacked vertically.

As with Hanoi, the description of what to do is much, much longer than the code you need to write. You'll need something like 6–8 lines of code to solve this question. You may find the built-in lerp() function useful.

Submit you work in a sketch titled Cantor.

Submission

When you are ready to submit, please follow these steps.

1. If necessary, review the Code Style Guide and use Processing's built-in auto format tool. You do not need to use the precise coding style outlined in the guide, but whatever style you use, your code must be clear, concise, consistent, and commented.

2. If necessary, review the How To Submit document for a reminder on how to submit to LEARN.

3. Make sure to include a comment at the top of all source files containing your name and student ID number.

4. Create a zip file called L06.zip containing the entire L06 folder and its subfolders Hanoi and Cantor.

5. Upload L06.zip to LEARN. Remember that you can (and should!) submit as many times as you like. That way, if there's a catastrophe, you and the course staff will still have access to a recent version of your code.

6. If LEARN isn't working, and only if LEARN isn't working, please email your ZIP file to the course account (see the course home page for the address). In this case, you must mail your ZIP file before the deadline. Please use this only for emergencies, not "just in case". Submissions received after the deadline may receive feedback, but their marks will not count.