CS 106 Winter 2017

Assignment 06: Recursion and Randomness


Question 1 The P-Reptile

A reptile is a single shape that can be divided up into smaller copies of itself. Each of those copies can then be divided up, and so on. If you keep doing this, you can fill as large a region (e.g., a bathroom floor) as you want with copies of the original shape, usually in an irregular pattern.

One example of a reptile is the "P pentomino": a shape made by gluing five squares together. The resulting shape is easy to describe using beginShape(), vertex(), and endShape(), with the coordinates given as follows:

You will complete a sketch that carries out the substitutions in the P pentomino reptile to any desired number of recursive levels, as in the pictures above.

  1. In the starter code, open the PReptile sketch. The sketch contains the usual features of a recursive drawing: a global levels variable, a recursive function (drawP() in this case), and a keyPressed() hook to control the number of levels. The number of levels is initially set to zero, which will case a single large P pentominmo to be drawn in the sketch window.

  2. Your job is to complete the recursive case for the drawP() function (marked by a TODO comment). You'll need about 25 lines of code, broken into four blocks. Each block will set up a geometric context in order to map the entire shape down into one of the recursive versions at the next level (as demonstrated by the relationship between the initial shape and the first level of replacement in the six drawings above). The pentomino is divided into four copies of itself, hence four recursive calls.

The easiest way to approach this task is incrementally and experimentally. Find the line drawP( levels ) in the draw() function and replace it by these two lines:

drawP( 0 );
drawP( 1 );

Those lines will allow you to see the four level-1 tiles superimposed on the single level-0 tile. You must manipulate the four recursive calls so that the two pictures match up exactly, with the four smaller tiles exactly covering the large original. If you get that working, you can change the code in draw() back to drawP( levels ) and use the arrow keys to explore deeper levels of recursion.

Save your work in a sketch titled PReptile.

Question 2 Smith-Truchet tiles

In the early 1700s, SĂ©bastienm Truchet first talked about the range of geometric designs possible with two very simple square tiles with triangular motifs; today we call these Truchet Tiles. Later, Smith introduced a variation based on tiles inscribed with quarter circles. We can carry this variation one step further by colouring the tiles in black and white.

In the starter code, open the SmithTruchet sketch. The sketch comes equipped with a helper function called drawTile() that takes two boolean parameters. By considering all four combinations of true and false for those parameters, you can get the four possible coloured Smith-Truchet tiles:

You will create a Processing sketch that draws a random arrangement of these four tiles, very much in the spirit of the 10 Print examples discussed in class. As with those examples, you will use ControlP5 to add a "bias" slider that allows you to control the weighting between two types of tiles in each grid cell.

  1. The four tiles drawn in the draw() function in the starter code are not needed in the final sketch. That code is just there to demonstrate the drawing of the four types of tiles. You can delete the code, or comment it out for now.

  2. Add code to draw() to draw a 10×10 grid of tiles, all of the same time (for now). Use a geometric context to translate each tile to its final position in the grid, and then call drawTile() inside that context.

  3. Now try drawing a random tile in every grid cell, by choosing the boolean values for drawTile() via two simulated coin flips.

  4. The previous step will cause two problems. The first problem is that the pattern will change wildly every frame, because the coin flips change each time. Solve this problem by setting a random seed at the start of draw().

  5. The second problem above is that the pattern will be "discontinuous"—there will be places where there's a sudden, sharp transition from a white region in a tile to a black region in a neighbouring tile, and vice versa. Looking at the diagram above, we see that in fact, not all pairs of tiles can legally be adjacent to each other. In particular, note that the (false,false) and (true,true) tiles are white in their top-left corners (we'll call these "white-cornered tiles"), and the other two are black in their top-left corners ("black-cornered tiles"). In order to preserve continuity, a white-cornered tile must be adjacent to four black-cornered tiles, and vice-versa.

    Modify your code to produce continuous patterns. The trick is that your grid must alternate between white-cornered and black-cornered tiles in a checkerboard. Each cell in the checkerboard must choose one of two random tiles (not four). There's a nice way to check which type you need in each cell. Let x be a loop counter for the current column in the grid, a number from 0 to 9. Let y be a loop counter for the current row. Then you can use code a bit like this:

    if( (x+y) % 2 == 0 ) {
      // Draw a white-cornered tileelse {
      // Draw a black-cornered tile
    }
    

  6. Use ControlP5 to add a single "bias" slider that runs from 0 to 1. It turns all coin flips used while drawing from fair (50/50) to biased, allowing you to control the ratio of one kind of tile to the other kind. The technique is similar to the TenPrintRandomSeed sample sketch, and the result should look something like the demonstration video above.

  7. Finally, add code (as in TenPrintRandomSeed that responds to key presses, so that when the user presses the space bar it changes the random seed, resulting in a different, random arrangement of tiles. (In the last part of the video above, the pattern is changing because the user is pressing the space bar.)

Save your work in a sketch called SmithTruchet, inside the A06 folder.

Question 3 What's the Secret Word?

We want to make sure that you have a look at your marked exam on Crowdmark and carefully try to understand where you might have lost marks. Don't ignore the marked exam just because it wasn't handed back to you on paper.

To encourage you to look at your exam, we placed a six-letter "secret word" in a comment somewhere in your exam. Find this secret word. Create a sketch with a single line of code that declares a global variable to be your word, as follows:

String word = "your secret word here";

Replace the text your secret word here with the six-letter word you find in your exam and nothing else. Save your work as a sketch titled SecretWord inside the A06 folder.

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 A06.zip containing the entire A06 folder and all its subfolders.

  5. Upload A06.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.