Wellesley College, Summer 2003

Problem Set 3

Due: Tuesday, June 24 by 10 am

Reading

About this Problem Set

This problem set is intended to help you practice reading, writing, and understanding methods. You should think carefully about what patterns should be abstracted into methods and which patterns should be named as variables.

Task 1 is an independent problem in which you will create a BuggleWorld design. Because it is an independent problem, you may not consult with anyone else about this particular problem. Task 2 is a pencil-and-paper problem in which you draw an invocation tree, while Tasks 3 and 4 require writing some PictureWorld methods. You may collaborate with other students on Tasks 2, 3, and 4, but as usual can communicate with them only in English, not in Java code.

To get the code for Tasks 1, 3 and 4, connect to cs.wellesley.edu via Fetch. Use the cs111d account and the password given in class and download the ps3_programs folder.

How to turn in this Problem Set

You are required to turn in both a hardcopy and a softcopy. For general guidelines on problem set submission, including how to submit a softcopy and how to check if you softcopy submission was successful, click here. Please make sure to keep a copy of your work, either on a zip disk, or in your private directory (or, to play it safe, both).

Hardcopy Submission

Your hardcopy packet should consist of:

The cover page;
Your modified RugBuggle.java file from Task 1;
Your invocation tree diagram from Task 2;
Your modified KnitWorld.java file from Task 3;
Your modified QuiltWorld.java file from Task 4.

Staple these together, and place the packet into the CS111 box in the back of room 257.

Softcopy Submission

Save you modified RugBuggle.java, KnitWorld.java, and QuiltWorld.java files in their respective folders within ps3_programs. Submit the entire ps3_programs folder to your drop folder on the cs111 server.

Task 1: Rug Buggles (Independent Problem)

Task 1 is an independent problem (which is effectively a mini take-home exam). You may not consult with anyone else about this problem. (If you have any questions, you may of course ask Lyn or Elena; but we cannot help you to solve the problem.)

Reggy is an artistic buggle that works for the Buggle Bagel Ruggle Company. He has created the following rug design that is parameterized over three colors:

reggy.rug(Color.yellow, Color.magenta, Color.blue)

reggy.rug(Color.cyan, Color.green, Color.yellow);

A skeleton implementation of the rug method can be found in the file RugBuggle.java within the BuggleRug folder. Your task is to flesh out the body rug method so that Reggy draws the patterns shown above.

Notes:

You should define several auxiliary methods that capture common patterns that appear in the rug design.
Strive to make your program as clear as possible. Use meaningful method and variable names, and use comments where appropriate (particularly to specify what your auxiliary methods do).
Invoking the rug method should not change the state of the buggle. In particular, Reggy's color after invoking rug should be the same as his color before the invocation.
Suggestion: it might be a good strategy first to solve the problem without preserving the color of the buggle, and then to add code for saving and restoring the color.
There are two test files, Test1.java and Test2.java, that produce the two rug patterns shown above. To pick one of these, move the associated .html file to the top of the file list in the Link Order window of the BuggleRug project.

Task 2: PictureWorld Invocation Tree

As discussed in class, an invocation tree is an abbreviated version of a Java Execution Model. It contains a node for each method called during the execution of a program. Each node contains the receiver of the method invocation, the name of the method, the values of its parameters, and (where applicable) its result. There is an edge connecting each "parent" node to the "children" nodes for the method invocations encountered directly within the body of the parent. The children nodes are all shown at the same vertical level, arranged from left to right in the order of their execution.

For example, consider the invocation tree for fourSame(greenWedge), where greenWedge denotes a green triangle with coordinates (0,0), (1,0), and (1,0.5), and fourSame is defined as follows:

	public Picture fourSame (Picture p) {
		return fourPics(p, p, p, p);
	}

	public Picture fourPics (Picture p1, Picture p2, Picture p3, Picture p4) {
		return above(beside(p1,p2), beside(p3,p4));
	}

Below is an invocation tree for the invocation SPW.fourSame(P1), where SPW symbolizes the SimplePictureWorld object that receives the method invocation and P1 denotes the greenWedge Picture object. Each node contains the value of the receiver, followed by the method name, followed by the actual parameters enclosed in parentheses. The result of invoking the method is then shown after a colon. Note that the nodes at the same level are drawn from top to bottom in the order that the methods are invoked.

EXECUTION LAND

The Objects referenced in the invocation tree are shown below:

OBJECT LAND

In this problem, you will draw an invocation tree for the invocation of a method that creates a design by combining various rotated copies of a given picture. This method, called "rots()", is defined as follows:

public Picture rots (Picture p) {
  return rotations2(rotations2(p));
}
	
public Picture rotations2 (Picture p) {
  return fourPics(p, clockwise90(p), clockwise180(p), clockwise270(p));
}	
	
public Picture fourPics (Picture p1, Picture p2, Picture p3, Picture p4) {
  return above(beside(p1,p2), beside(p3,p4));
}

For this problem, you are to draw a complete invocation tree for the invocation rots(P1), where P1 represents the green wedge shown in the example above. To represent each Picture object, you should sketch the picture represented by that object below your invocation tree. Show the unit square in a dotted line around the picture object, as shown above. Give your sketch of the picture a label, such as P1, P2, P1a, etc., and use that label to reference the object in the invocation tree, as shown in the diagram above. You should label the part of your drawing that contains the invocation tree "EXECUTION LAND", and the part of the drawing that shows the Picture objects "OBJECT LAND" as in the example above. In your invocation tree, all children of the same parent should appear at the same vertical level. (You may need to turn your paper sideways, and perhaps tape two pieces of paper together to fit all the nodes).

Task 3: Knit Picking

Escher's Knitting Patterns

Dutch artist M. C. Escher is renowned for creating artwork based on interlocking patterns and visual playfulness. Here we will experiment with "knitting patterns" that Escher himself experimented with in 1943. (For more details on Escher's artwork, see M.C. Escher: Visions of Symmetry by Doris Schattschneider, W.H. Freeman and Company, 1990).

Escher's knitting patterns were based on the following two primitive patterns that he designed:

Pattern A

Pattern B

We will call these patterns A and B. We can make many variants of A an B by rotating them, flipping them, and painting their stripes different colors. These variants of A and B can be combined to form an amazing number of patterns that resemble the weave patterns of knitted yarn. For example, study the following four knitting patterns, all of whose basic squares are versions of A and B that have been rotated, flipped, and colored in various ways.

Playing with Knitting Patterns in PictureWorld

PictureWorld is a perfect tool for experimenting with Escher's knitting patterns. The file KnitWorld.java within the ps3_programs folder contains several methods that aid in this experimentation. Colored versions of the A and B patterns are created by the following two black-box methods in KnitWorld.

public Picture A(Color c1, Color c2, Color c3, Color c4, Color c5);
public Picture B(Color c1, Color c2, Color c3, Color c4, Color c5);

The five color arguments of A and B paint the patterns in the way indicated by the following examples:

A(Color.red, Color.blue,
Color.green, Color.yellow, Color.magenta);

B(Color.red, Color.blue,
Color.green, Color.yellow, Color.magenta);

The tileKnit method is useful for constructing many simple knitting patterns:

public Picture tileKnit (Picture p1, Picture p2, Picture p3, Picture p4) {
    return fourSame(fourSame(fourPics(p1, p2, p3, p4)));
}

The fourSame and fourPics methods are the same as those presented in lecture:

public Picture fourSame (Picture p) {
    return fourPics(p, p, p, p);
}
 	
public Picture fourPics (Picture p1, Picture p2, Picture p3, Picture p4) {
    return above(beside(p1,p2), beside(p3,p4));
}

Using the above methods, plus the usual picture combinators of PictureWorld, it is possible to make pictures for all four knitting patterns shown above. Here is a knit1() method, parameterized over two colors, that generates the knit1 pattern shown above:

public Picture knit1(Color c1, Color c2) {
    Picture A1 = A(c1, c2, c1, c1, c2);
    Picture B1 = B(c2, c1, c2 ,c2, c1);
    return tileKnit(A1,B1,A1,B1);
}

The knit2() method is similiar in structure to knit1(), but uses different colorings, flips, and rotations:

public Picture knit2(Color c1, Color c2) {
    Picture A1 = A(c1, c2, c1, c2, c1);
    Picture B1 = B(c2, c1, c2 ,c1, c2);
    return tileKnit(flipHorizontally(B1),
                           flipHorizontally(A1),
                           clockwise180(B1),
                           clockwise180(A1));
}

The knit3() method is parameterized over three colors rather than four:

public Picture knit3(Color c1, Color c2, Color c3) {
    return tileKnit(B(c1,c2,c1,c3,c1),
                           clockwise90(B(c1,c3,c2,c2,c1)),
                           flipVertically(B(c1,c3,c1,c2,c1)),
                          flipVertically(clockwise90(A(c1,c2,c3,c3,c1))));

The knit4 pattern has a more complex repetition pattern that cannot be expressed via tileKnit(). The following knit4() method captures this pattern:

public Picture knit4(Color c1, Color c2) {
    Picture tile1 = fourPics(B(c1,c2,c1,c2,c1),
                             clockwise270(A(c1,c2,c1,c1,c2)),
                             flipVertically(B(c1,c2,c1,c2,c1)),
                             clockwise90(flipVertically(B(c2,c1,c2,c2,c1))));
    Picture tile2 = fourPics(A(c2,c1,c2,c1,c2),
                             clockwise270(B(c2,c1,c2,c2,c1)),
                             flipVertically(A(c2,c1,c2,c1,c2)),
                             clockwise90(flipVertically(A(c1,c2,c1,c1,c2))));
    return fourSame(fourPics(tile1, tile2, tile1, tile2));
}

Your Task

In this problem, you will define methods that draw the following two knitting patterns: knit5 (shown in the LEFT column) and knit6 (shown in the RIGHT column). knit5() is parameterized over four colors, while knit6() is parameterized over two colors. The particular knit5 patterns shown below are created by the invocation that you can read in the top of the KnitWorld picture (in the yellow bar at the top of the image). For example, the top left knit5 pattern in created by this invocation: knit5(Color.red, Color.magenta, Color.blue, Color.green).

The file KnitWorld.java contains the skeletons of two methods that you should flesh out :

public Picture knit5(Color c1, Color c2, Color c3, Color c4) {
    // Put your definition here.
}
 	
public Picture knit6(Color c1, Color c2) {
    // Put your definition here.
}

To begin this problem, first study the knit1() through knit4() methods above and convince yourself that they do in fact draw the four knitting patterns shown in the previous section. Your solutions to knit5() and knit6() will be similar to the knit1() through knit4(). Next, you should carefully study the knit5 and knit6 patterns to determine which rotations, flips, and colorings of the basic patterns A and B are employed. The final step is to encode your findings in Java code in the method bodies of knit5() and knit6(). You may find it helpful to define your own auxiliary methods in addition to defining knit5() and knit6().

Testing your program

To make testing a little easier, we have included a folder Test which contains working examples of the patterns you need to make so that you can compare your work with the examples (but, alas, no Java code!). To see the examples, open the folder Test in ps3_programs that you have downloaded and double-click on test.mcp icon. You can choose knit5 and knit6 from the menu. The test project will be especially helpful for the second part of the assignment.

Note: If you are running the test project in addition to your own project, it is easy to get confused in switching from one to the other (for instance, you may be running the test applet thinking that you are running your own). To avoid confusion, make sure to close applets that you no longer need and to double-check the name of the project which you are compiling (it appears on the title bar of the project window).

Task 4: QuiltWorld

Bertha Buggle, co-founder of the Buggle Bagel Ruggle Company, has been looking for new ways to expand her company's product line. Although the bagel rugs marketed by the company are popular, they are difficult to manufacture because of the labor costs (each rug is hand-drawn by a Buggle) and and raw material costs (bagels cost more than you think!). Bertha thinks the company should diversify to produce other products with interesting designs, such as quilts,wallpaper, and sweaters. Bertha is currently experimenting with the picture drawing software presented in CS111 to design quilts. Here is an example of one of Bertha's quilt designs, which we will call quilt1. It is the result of calling a quilt method on six color parameters:

quilt1 is the result of the invocation
quilt(red, blue, green, black, cyan, magenta)

(In this and the following examples, we assume that red is a local variable containing the same value as Color.red, blue is a local variable containing the same value as Color.blue, and so on.)

You and several other CS111 students have been hired as interns at the Buggle Bagel Ruggle Company to help Bertha design quilts. Your project is to use PictureWorld to generate the quilt design shown above. The quilt displayed above is just one sample of the quilt design that can be produced by invoking the quilt method. Your code will contain methods that take color parameters, and thus will be able to generate lots of different quilts, in the same pattern as above, but with color variation. This description of the assignment will use the above quilt as an example, but keep in mind that your code must be generic and able to handle different color variations of the above pattern.

There is a file named QuiltWorld.java in the QuiltWorld subfolder of the ps3_programs folder. All the methods that you will define for this problem will be in the QuiltWorld class in this file. Your goal is to flesh out the skeleton of the quilt method so that it returns a picture corresponding to the quilt shown above. This picture is ultimately generated by combining primitive pictures generated by the following two black-box methods with which you are provided.:

public Picture patch (Color c)
Returns a rectangular patch of color c with a black border that fills a given picture frame.

patch(red);

public Picture triangles(Color c1, Color c2)
Returns a picture that consists of two triangles filling the given picture frame: a black-bordered triangle of color c1 in the lower left corner of the frame; and a black-bordered triangle of color c2 in the upper right corner of the frame.

triangles(red, blue);

Divide, Conquer, and Glue

The key to solving the problem of defining quilt is to note that the picture can be decomposed into smaller pictures that are used more than once in the larger picture. For example, the upper right quadrant is a picture generated by a method that that we'll call quarter:

quarter(red, blue, green, black, cyan, magenta)

The whole picture can be decomposed into four copies of quarter that have different rotations. Once we figure out how to define the quarter picture, we can combine four rotated copies of the picture to form the desired quilt picture. This is an excellent illustration of the divide, conquer, and glue problem solving strategy we will use throughout this course:

Divide the problem into subproblems. Here there is one subproblem: defining the quarter method.
Conquer the subproblems by solving them. In this case, the solution to the subproblem is the result of invoking the quarter method.
Glue the solutions to the subproblems together to form the solution to the whole problem. Here, we combine four rotated versions of the picture returned by invoking quarter to construct the quilt.

But how do we solve the problem of defining the quarter method? By applying the divide, conquer, and glue strategy again! In this case, quarter naturally decomposes into four quadrants:

quadrant2(green,blue,black,cyan,magenta)

quadrant3(magenta,black)

quadrant1(red,blue,green,black,cyan)

quadrant2(green,blue,black,cyan,magenta)

We give the names quadrant1, quadrant2, and quadrant3 to the methods that draw these patterns. Notice that the picture created by quadrant2 is used twice in the corner method! We can continue to use divide, conquer, and glue to decompose each quadrant above into smaller and smaller pictures. When does the process stop? When we get to pictures so small that they are trivial to solve! In this case the trivial pictures are those generated by the patch() and triangles() methods.

Auxiliary Methods

A general principle of computer science is "never write any piece of code more than once". If you find yourself writing the same or similar code more than once in your program, you should instead write methods that capture the patterns of the repeated code and invoke the methods instead.

The divide, conquer, and glue process of defining quilt1() naturally exposes the need for numerous auxiliary methods. As part of working on this assignment, you should define and use the following methods. Skeletons for all of these methods can be found in QuiltWorld.java.

public Picture patch_2x2 (Color c)
Returns a picture consisting of four rectangular patches of color c with black lines between the patches. (Remember that patch(c) returns a picture with a black border.)

patch_2x2(red);

public Picture triangles_2x2 (Color c1, Color c2)
Returns a picture similar to triangles(c1, c2) except that each large triangle is composed out of four smaller fragments (two triangles and two rectangles).

triangles_2x2(red, blue);

public Picture LL (Picture p)
Returns a picture which divides the picture space into four quadrants and places the given picture in the lower left corner.

LL(triangles(red, blue));

public Picture LLNest (Picture p1, Picture p2)
Returns a picture which places picture p2 over the lower left corner of picture p1.

LLNest(patch(red), triangles(red, blue));

Completing the Assignment

All of the methods in the PictureWorld and QuiltWorld contracts are available to you. At a minimum, you should have methods that correspond to each pattern described above. The QuiltWorld.java file contains skeletons for methods that you must define. You should define any additional methods that capture any other repeated patterns that you see. It is also helpful to define local variables within your methods to give names to pictures that you generate as part of your solution. In particular, rather than invoking a method more than once on the same actual parameters, you should name the picture that results from a single invocation, and refer to that name more than once.

The quadrant3 pattern is made up of invocations of LLNest and triangles. You do not need anything else.

Testing your Program

The QuiltWorld folder contains a Test folder with a project that contains several pictures you can compare to your own.

Your Final Task.

Oh no! Bertha has just designed this new quilt shown below, using the same pattern as above, but with different colors. She forgot how she actually created this one. She hires you to figure out which Color parameters were used in what order to create the pattern below. To solve this problem, write a new method called quilt2 that produces the quilt shown below. Your quilt2 method should invoke the quilt method on appropriate arguments.


 

 quilt2()

quadrant2(green,blue,black,cyan,magenta)	quadrant3(magenta,black)

quadrant1(red,blue,green,black,cyan)	quadrant2(green,blue,black,cyan,magenta)