About this Problem Set

The purpose of this problem set is to give you with lists of lists, iteration (tail recursion, while loops, and for loops), and Java graphics. In Task 1, you will use list of lists to determine all the different ways to make change for a given amount of money. In Task 2, you will use iteration to manipulate lists. In Task 3, you will use Java graphics to draw simple cartoon faces.

There are also an optional open-ended extra-credit opportunity for you to use Java Graphics to draw any picture(s) of your own design.

All code for this assignment is available in the ps8_programs folder in the cs111d download directory on the cs file server.

How to turn in this Problem Set

Hardcopy Submission

1. The cover page;
2. Your modified ChangeMaker.java file from Task 1.
3. Your iteration table from Task 2a;
4. Your modified Partition.java file from Tasks 2b, 2c, 2d, and 2e;
5. The final version of Faces.java from Task 3.
6. The final version of MyPicture.java from (optional) Extra Credit Challenge 1.

Softcopy Submission

• The ChangeMaker subfolder should contain your final version of ChangeMaker.java.
• The Partition subfolder should contain your final version of Partition.java.
• The Faces subfolder should contain your final version of Faces.java.
• The MyPicture subfolder should contain your final version of MyPicture.java (if you did the first extra credit challenge).

Task 1: Making Change

Lists of lists are useful data structures for holding lists of possibilities. We can use them to hold the list of all subsets of a set of numbers like we saw in lecture. We could also use them to hold a list of all permutations of a list of numbers, using an approach similar to computation of string permutations considered in the previous problem set. In this problem, we will use lists of lists to represent all the possible ways of making change for a given amount of money given an unlimited number of coins with certain denominations. Some examples are given below (assume all values are in cents).

Amount to change	Denominations	Ways to Make Change
5	[5,1]	[[5], // 1 nickel [1, 1, 1, 1, 1] // 5 pennies ]
16	[10,5,1]	[[10, 5, 1], // 1 dime, 1 nickel, and 1 penny [10, 1, 1, 1, 1, 1, 1], // 1 dime and 10 pennies [5, 5, 5, 1], // 3 nickels and 1 penny [5, 5, 1, 1, 1, 1, 1, 1], // 2 nickels and 6 pennies [5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], // 1 nickel and 11 pennies [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] // 16 pennies. ]

Your goal is to formulate a strategy that will list all the possible ways to make change for a given amount of money with a list of possible coin denominations provided in descending order of value. You will be completing the method makeChange of the ChangeMaker class. The skeleton for the method is provided below:

public static IntListList makeChange (int amount, IntList coins)
Returns a list of possible ways to make change for amount using the coin denominations in the list coins. Assume the integers in coins are in descending order of value.

Complete this problem by fleshing out the definition of makeChange in the ChangeMaker.java file within the ChangeMaker folder.

Notes

• The ChangeMaker.mcp project is configured so that it tests makeChange on a number of test cases when you run the project. The correct output for the test cases is provided at the end of this problem description. You need to get the same number of ways to make change and the same ways to make change as listed, but you may list the ways to make change in any order and may list the coins in any order.
• The ChangeMaker class has been configured so that you can use the IL. prefix for IntList methods, and the ILL. prefix for IntListList methods.

  IntList Methods (IL)	IntListList Methods (ILL)
  IL.empty IL.prepend IL.head IL.tail IL.isEmpty IL.toString IL.fromString IL.length IL.append IL.postpend	ILL.empty ILL.prepend ILL.head ILL.tail ILL.isEmpty ILL.toString ILL.fromString ILL.length ILL.append ILL.postpend ILL.mapPrepend

  Note that the IntListList operations include the mapPrepend method discussed in lecture. It is defined as:

      public static IntListList mapPrepend (int n, IntListList L) {
  	if (ILL.isEmpty(L)) {
  	    return L;
  	} else {
  	    return ILL.prepend (IL.prepend(n, ILL.head(L)), 
  			        mapPrepend(n, ILL.tail(L)));
  	}
      }
  

• Here's a hint for how to approach this problem. Given an amount for which to make change and a list of coin denominations, there are two ways to make the problem smaller:
  1. You can decide to use the largest coin denomination (if it's not too large) to make change for the amount. This gives a subproblem where you have a smaller amount and the same list of coin denominations.
  2. You can decide not to use the largest coin denomination to make change for the amount. This gives a subproblem where you have the same amount and a smaller list of coin denominations.
  If you combine the results of these two subproblems, then you will have all ways to make change for the given amount and coin denominations.
• It may help you to carefully study the test case answers below to figure out how to divide the change making problem into two subproblems and how to combine the results of those two subproblems.
• The base cases for this problem require careful thought. It may help to think of examples involving the smallest instances of the general case to determine what should happen in the base cases.
• This is a challenging problem. If you get stuck, move on to the rest of the assignment and then come back to this problem later.

Correct Test Case Answers

----------------------------------------------------
There are 1 ways to make change for 5 cents using [5]:
[[5]
 ]
----------------------------------------------------
There are 1 ways to make change for 5 cents using [10, 5]:
[[5]
 ]
----------------------------------------------------
There are 1 ways to make change for 10 cents using [5]:
[[5, 5]
 ]
----------------------------------------------------
There are 2 ways to make change for 10 cents using [10, 5]:
[[10],
 [5, 5]
 ]
----------------------------------------------------
There are 1 ways to make change for 15 cents using [5]:
[[5, 5, 5]
 ]
----------------------------------------------------
There are 2 ways to make change for 15 cents using [10, 5]:
[[10, 5],
 [5, 5, 5]
 ]
----------------------------------------------------
There are 0 ways to make change for 16 cents using [10, 5]:
[]
----------------------------------------------------
There are 2 ways to make change for 5 cents using [5, 1]:
[[5],
 [1, 1, 1, 1, 1]
 ]
----------------------------------------------------
There are 3 ways to make change for 10 cents using [5, 1]:
[[5, 5],
 [5, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 ]
----------------------------------------------------
There are 4 ways to make change for 10 cents using [10, 5, 1]:
[[10],
 [5, 5],
 [5, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 ]
----------------------------------------------------
There are 4 ways to make change for 15 cents using [5, 1]:
[[5, 5, 5],
 [5, 5, 1, 1, 1, 1, 1],
 [5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 ]
----------------------------------------------------
There are 6 ways to make change for 15 cents using [10, 5, 1]:
[[10, 5],
 [10, 1, 1, 1, 1, 1],
 [5, 5, 5],
 [5, 5, 1, 1, 1, 1, 1],
 [5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 ]
----------------------------------------------------
There are 6 ways to make change for 16 cents using [10, 5, 1]:
[[10, 5, 1],
 [10, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 1],
 [5, 5, 1, 1, 1, 1, 1, 1],
 [5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 ]
----------------------------------------------------
There are 13 ways to make change for 26 cents using [25, 10, 5, 1]:
[[25, 1],
 [10, 10, 5, 1],
 [10, 10, 1, 1, 1, 1, 1, 1],
 [10, 5, 5, 5, 1],
 [10, 5, 5, 1, 1, 1, 1, 1, 1],
 [10, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 5, 1],
 [5, 5, 5, 5, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 ]
----------------------------------------------------
There are 60 ways to make change for 56 cents using [25, 10, 5, 1]:
[[25, 25, 5, 1],
 [25, 25, 1, 1, 1, 1, 1, 1],
 [25, 10, 10, 10, 1],
 [25, 10, 10, 5, 5, 1],
 [25, 10, 10, 5, 1, 1, 1, 1, 1, 1],
 [25, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [25, 10, 5, 5, 5, 5, 1],
 [25, 10, 5, 5, 5, 1, 1, 1, 1, 1, 1],
 [25, 10, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [25, 10, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [25, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [25, 5, 5, 5, 5, 5, 5, 1],
 [25, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1],
 [25, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [25, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [25, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [25, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 10, 10, 5, 1],
 [10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 10, 5, 5, 5, 1],
 [10, 10, 10, 10, 5, 5, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 10, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 5, 5, 5, 5, 5, 1],
 [10, 10, 10, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 5, 5, 5, 5, 5, 5, 5, 1],
 [10, 10, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1],
 [10, 10, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1],
 [10, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1],
 [10, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1],
 [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 ]

Task 2: List Partitioning

The following partitionIter method takes an integer named pivot and a list of integers named L and partitions the list into two lists:

1. All the elements in L less than pivot.
2. All the elements in L greater than or equal to pivot.

The two resulting lists are returned in a two-element IntListList -- i.e., a list of two integer lists.

    public static IntListList partitionIter (int pivot, IntList L) {
      return partitionTail(pivot, L, IL.empty(), IL.empty());
    }

    public static IntListList partitionTail (int pivot, IntList list, 
                                             IntList lesses, IntList greaters) {
      if (IL.isEmpty(list)) {
        return twoLists(lesses, greaters);
      } else if (IL.head(list) < pivot) {
        return partitionTail(pivot, IL.tail(list), 
                             IL.prepend(IL.head(list), lesses), greaters);
      } else {
        return partitionTail(pivot, IL.tail(list), 
                             lesses, IL.prepend(IL.head(list), greaters));
      }
    }

Because the program manipulates both IntList and IntListList objects, it is necessary to distinguish the list operations for these different kinds of lists. As in Task 1, we will use IL. to prefix IntList operations and ILL. to prefix IntListList operations. To make the code more readable, we use the following helper method:

    public static IntListList twoLists (IntList L1, IntList L2) {
      return ILL.prepend(L1, ILL.prepend(L2, ILL.empty()));
    }

Task 2a: Iteration Table

Suppose that the list A has the printed representation [7,2,3,5,8,6,1]. Fill in the above table to show the parameters passed to successive calls to partitionTail in the computation that begins with the invocation partitionIter(5, A). There are more rows shown here than you need, so you should draw only as many rows as you need to in your table.

Part 2b: partitionWhile

public static IntListList partitionWhile (int pivot, IntList L) {
  // Replace this stub
  return ILL.empty();
}

Notes:

• You should flesh out the skeleton of the partitionWhile method in the file Partition.java within the Partition folder.
• As in Task 1, it is necessary to distinguish IntList operations from IntListList operations. The prefix IL. will be used for the former and ILL. for the latter.
• Recall that a Java while loop has the syntax

  while (test-expression) {
    body-statements
  }

• You should use exactly one while loop to implement the iteration implied by the iteration table. The body of this loop may contain any Java statements, including conditionals, but should not contain other while loops.
• Executing the Partition.mcp project invokes the main method of the Partition class, which will run the methods of this task on various test cases. You should study the results of the test cases in the Java console window to verify that the results are what you expect.

Task 2c: partitionFor

public static IntListList partitionFor (int pivot, IntList L) {
  // Replace this stub
  return ILL.empty();
}

Recall that a Java while loop has the syntax

for (init-statement; test-expression; update-statement) {
  body-statements
}

The above for loop is equivalent to the following while loop:

init-statement;
while (test-expression) {
  body-statements;
  update-statement;
}

Task 2d: partitionRec

Suppose that we want the resulting lists to have the same relative order as in the original list. If we are provided with an IntList reversal method IL.reverse, we can easily accomplish this by reversing the two lists before gluing them together. That is, we can change the line

	return twoLists(lesses, greaters);

	return twoLists(IL.reverse(lesses), IL.reverse(greaters));

An alternative to using IL.reverse to achieve this behavior is to define a non-tail-recursive version of partitionIter that we will call partitionRec. Flesh out the following skeleton of partitionRec, which partitions the elements of a list about the pivot but maintains the relative order of the elements in the resulting lists:

 
    public static IntListList partitionRec (int pivot, IntList L) { 
      if (IL.isEmpty(L)) { 
        return twoLists(IL.empty(), IL.empty()); 
      } else { 
        IntListList subresult = partitionRec(pivot, IL.tail(L)); 
        // replace the following stub:
        return ILL.empty(); 
      } 
    } 

Notes:

• partitionRec should be a self-contained non-tail-recursive method that should not invoke any of the other partitioning methods mentioned in this problem. The "Rec" in the name "partitionRec" stands for "Recursive", and is intended to suggest a non-tail-recursive method.
• The partitionRec method is tested by the main method of the Partition class.

Task 2e: quicksort

To sort the elements of a list, partition the elements of the tail of the list around its head into result lists that we'll call lesses and greaters. Then result of sorting the whole list can be obtained by appending the result of sorting lesses to the result of prepending the head of the list to the result of sorting greaters.

For example, if the initial list is [5, 2, 8, 3, 6, 7, 1, 4], then partitioning the tail of the list around the head (5) yields:

	lesses = [4, 1, 3, 2]
	greaters = [7, 6, 8]

By wishful thinking, sorting lesses will yield [1, 2, 3, 4] and sorting greaters will yield [6, 7, 8]. The result of sorting the original list is the result of appending [1, 2, 3, 4] to the result of prepending 5 to [6, 7, 8].

Flesh out a method with header public static IntList quicksort (IntList L) that uses this idea to sort the elements of a list. You may use IL.append to append two lists and any of the above partitioning methods to partition a list. The quicksort method is tested by the main method of the Partition class.

It turns out that quicksort, true to its name, is one of the fastest algorithms for sorting a list. If you take CS230 and CS231, you will learn (among other things) much more about various sorting algorithms and how to compare them in terms of efficiency.

Task 3: Faces

In this problem, we will model simple cartoon faces like those shown below:

Each face is characterized by the following features:

• Its color.
• Its happiness, which is a floating point number that should be between 0.0 (mouth closed) and 1.0 (mouth wide open). A face with happiness value h between 0.0 and 1.0 has its mouth open by a fraction h.
• Its sleepiness, which is a floating point number that should be between 0.0 (eyes wide open) and 1.0 (eyes shut). A face with sleepiness value s between 0.0 and 1.0 has its eyelids closed by a fraction s.

For example, the following table shows the values for the color (r = red, g = green, and b = blue), happiness (h) and sleepiness (s) of each face in the corresponding position in the figure above:

In the following parts, you will be implementing in stages the following drawFace class method within the Face class:

public static void drawFace (Graphics g, Rectangle r, Color c, double h, double s)
Using graphics context g, draws a face with color c, happiness h, and sleepiness s in the specified rectangle r.

Task 3a: Put on a Happy Face

Below is a diagram of a happy face inscribed in the unit square indicating the placement of the eyes, nose, and mouth. You should draw the happy face exactly as depicted in this diagram.

Notes:

• In order to draw the face, you will need to use various drawing methods of the Graphics class presented in lecture and lab. As part of doing this problem, you should consult the contract for the Graphics class. You will also need to use the contracts for the Rectangle and Polygon classes.
• For examples of each of the kinds of shapes out of which a face is composed, study the following graphics demos from Lecture 19:
  • GraphicsDemo.java
  • Circles.java
  • Ovals.java
• The drawing methods in the Graphics class expect integers as arguments. The java compiler will complain if you pass a floating point number rather than an integer as an argument to one of these methods. For instance, if g denotes a Graphics instance and r denotes a Rectangle instance, then the following is incorrect:

  g.drawLine(r.x + (0.1 * r.width), 
             r.y + (0.3 * r.height),
             r.x + (0.7 * r.width),
             r.y + (0.6 * r.height));
  

  This problem can be fixed by using an integer cast expression (int) E to convert the result of a floating point expression E to an integer. A corrected version of the above example is:

  g.drawLine(r.x + (int) (0.1 * r.width), 
             r.y + (int) (0.3 * r.height),  
             r.x + (int) (0.7 * r.width),
             r.y + (int) (0.6 * r.height));
  

• You can view a large version of a happy face by running the OneFace.html applet. You can do this by moving OneFace.html before ManyFaces.html in the LinkOrder tab of the Face.mcp project file. Here is the window produce by this applet:
  

Task 3b: Sleepy Faces

A face with sleepiness factor s (between 0.0 and 1.0) should have "eyelids" covering a fraction s of the height of the eyes from the top to the bottom. This effect can be achieved as follows:

• Draw the normal "alert" eyes as filled black ovals.
• Draw a filled rectangle with the color of the face that covers the appropriate fraction of the eyes.
• Draw unfilled black ovals around the eyes.

Note that, according to its contract, the drawOval() method covers an area that is width + 1 pixels wide and height + 1 pixels tall. In contrast, the the fillOval() method covers an area that is width pixels wide and height pixels tall. Because of this discrepency, to get your picture to "look right" you may need to subtract 1 from the width and height arguments of drawOval().

Task 3c: Drawing Happiness

For example, here are faces whose happiness value changes from left to right:

Here is the specification for the mouth that you should implement:

• The mouth should have a width that is 0.6 times the width of the face.
• The mouth should be horizontally centered in the face.
• The height of the mouth should be the happiness value times 0.3 times the height of the face, but should never be smaller than 1. The "never smaller than" effect can be achieved using the Math.max() method, which returns the maximum of two integers.
• The mouth should be vertically centered about a horizontal line that is 0.75 the way down the face.

The above specification can be implemented via a single invocation of the fillArc() method that handles all happiness values between 0.0 and 1.0. The key to getting this to work is to determine the coordinates of the rectangle in which the arc is inscribed as a function of the happiness value. Do not attempt to do this by trial and error! Instead, determine the correct formula on a sheet of paper before you attempt to implement this part!

Extra Credit Challenge: Create Your Own Picture [up to 5 points]

This is a completely optional problem. You should only attempt it after completing the rest of the assignment.

You can use Java graphics as a tool to create fascinating pictures. Here is a chance to be artistically creative and earn some extra credit points at the same time.

For this challenge, flesh out the paint() method in the MyPicture class within the MyPicture folder to draw whatever picture you imagine. If you like, you can draw more than one by making copies of MyPicture.java where the files (and the contained class) have different names.

Notes:

• The extra credit challenges are the only problems on this problem set in which you may collaborate with others in the class. Feel free to collaborate with as many people as you want.
• All extra credit pictures submitted will be posted on an "exhibition page" so that you can share your designs with the rest of the world.
• If you need help to do something fancy, please talk to the instructors.
• The amount of extra credit awarded on this problem will be proportion to the creativity and artistry in your designs, as well as the level of technical challenge. You can earn up to 5 problem set points in extra credit on this challenge.