Lab #4 (AY2007/8 Semester 1)

Date of release: 18 September 2007, Tuesday, 23:59.

Submission deadline: 3 October 2007, Wednesday, 23:59.

School of Computing, National University of Singapore

This lab contains three exercises. You are to submit only the first two exercises. Exercise 3 is for your own practice and it will not be graded.

You are advised to review the material covered in chapters 1 through 6 and read Programming Style, Design and Marking Guidelines before attempting this lab assignment. You should not use syntax or constructs not covered in lectures; you shouldn't need to and may even be penalized for doing so (if the objective of the assignment is undermined).

A word of advice: **Code incrementally**. This is even more important
now than before as your program gets longer. Don't try to finish all parts of
a program then compile it. Write your program in bits and pieces and
compile frequently. Try to maintain a compilable program even while you are
working on it. Submitting a compilable program that partially works is
better than submitting an un-compilable one. This last point especially
applies to the programming exams. Seriously, code incrementally.

The following topics have not been covered and hence you should not use them (if you are in doubt whether you can use certain features not mentioned below and are not yet covered in class, please consult your discussion leader or lecturer first):

- Arrays
- Exceptions
- Recursion
- Inheritance and polymorphism

You may assume that **all input data are correct**.

You should use `Scanner` class on `System.in` for
input and `System.out` for output in your programs,
unless otherwise stated.

Your last output statement should be a `println` and
not `print`.

**Test your programs thoroughly with your own input data before you
submit to CourseMarker.** Do not use CourseMarker as a debugging tool.
For this lab, the number of submissions is set to **10**.
Only your last submission will be graded.

**Make good use of the 1-week recess for revision.**

In general, the expected time to complete a lab
assignment (including all graded exercises) is
between **3 to 5 hours**. You should aim not to spend
more than 5 hours. It might be difficult at first, but
it should get easier as you gain experience. Make that your
target.

- Selection and repetition statements
- Solving a simple mathematical puzzle

This question appears in a Primary 5 Mathematics paper:

There is a number less than 100, where

- Dividing it by 3 yields remainder 1
- Dividing it by 4 yields remainder 2
- Dividing it by 5 yields remainder 3
- Dividing it by 6 yields remainder 4
What is the number?

For this exercise, you are going to write a program `Remainder.java`
to read in two positive integers *m* and *n* (*m* < *n*),
and find the number of values in the range [*m*,*n*] that satisfy
the above 4 criteria. For example, between 100 and 1000 inclusive, there
are 15 values that satisfy the above 4 criteria: 118, 178, 238, 298, 358,
418, 478, 538, 598, 658, 718, 778, 838, 898 and 958. So the answer your
program should produce is 15.

Sample run using interactive input (user's input shown in
blue; output shown in
**bold purple**):

$ javac Remainder.java $ java Remainder Enter m and n: 1 500

Another sample run:

$ java Remainder Enter m and n: 100 100015

Submit your program `Remainder.java` through CourseMarker.

- You should have a method
`solvePuzzle(int, int)`which computes the answer and returns it to the caller.

- This is a very simple exercise and we hope that every student
is able to complete it within half an hour.

- Selection and repetition statements.
- Floating-point numbers.
- DecimalFormat class.

Numerical analysis
is an important area in computing.
One simple numerical method we shall study here is the
**Bisection method**, which computes the root of a continuous function.
The **root**, *r*, of a function *f* is a value such that
*f(r)* = 0.

How does bisection method work? It is best explained with an example.
Given this polynomial
*p*(*x*) = *x*^{3} + 2*x*^{2} + 5,
we need to first provide two endpoints *a* and *b* such that
the signs of *p*(*a*) and *p*(*b*) are **different**.
For example, let *a*=-3 (hence *p*(*a*)=-4) and
*b*=0 (hence *p*(*b*)=5).

The principle is that, the root of the polynomial (that is, the
value *r* where *p*(*r*) = 0) must lie somewhere
between *a* and *b*. So for the above polynomial, the
root *r* must be somewhere between -3 and 0.

This is achieved as follows.
The bisection method finds the midpoint *m* of the two
endpoints *a* and *b*, and depending on the sign of
*p*(*m*) (the function value at *m*), it replaces one of
the two endpoints with
*m*, and repeats the process, until the difference
between the two endpoints falls within a threshold, that is, when they
become very close to each other, or, when the midpoint is the root
itself. For the former case, we shall set the threshold
to **0.0001** for this exercise.

Figure 1 below shows the two endpoints *a* (-3) and *b* (0),
their midpoint *m* (-1.5), and the function values at these 3 points:
*p(a)* = -4, *p(b)* = 5, *p(m)* = 6.125.

Figure 1. Graph of *p*(*x*)
= *x*^{3} + 2*x*^{2} + 5

The following table illustrates the iterations in the process. The end-point that is replaced by the mid-point value computed in the previous iteration is highlighted in pink background.

iteration | endpoint a |
endpoint b |
midpoint m |
function value p(a) |
function value p(b) |
function value p(m) |

1 | -3.000000 | 0.000000 | -1.500000 | -4.000000 | 5.000000 | 6.125000 |

2 | -3.000000 | -1.500000 | -2.250000 | -4.000000 | 6.125000 | 3.734375 |

3 | -3.000000 | -2.250000 | -2.625000 | -4.000000 | 3.734375 | 0.693359 |

4 | -3.000000 | -2.625000 | -2.812500 | -4.000000 | 0.693359 | -1.427002 |

5 | -2.812500 | -2.625000 | -2.718750 | -1.427002 | 0.693359 | -0.312714 |

6 | -2.718750 | -2.625000 | -2.671875 | -0.312714 | 0.693359 | 0.203541 |

7 | -2.718750 | -2.671875 | -2.695312 | -0.312714 | 0.203541 | -0.051243 |

8 | -2.695312 | -2.671875 | -2.683594 | -0.051243 | 0.203541 | 0.076980 |

9 | -2.695312 | -2.683594 | -2.689453 | -0.051243 | 0.076980 | 0.013077 |

10 | -2.695312 | -2.689453 | -2.692383 | -0.051243 | 0.013077 | -0.019031 |

11 | -2.692383 | -2.689453 | -2.690918 | -0.019031 | 0.013077 | -0.002964 |

12 | -2.690918 | -2.689453 | -2.690186 | -0.002964 | 0.013077 | 0.005059 |

13 | -2.690918 | -2.690186 | -2.690552 | -0.002964 | 0.005059 | 0.001048 |

14 | -2.690918 | -2.690552 | -2.690735 | -0.002964 | 0.001048 | -0.000958 |

15 | -2.690735 | -2.690552 | -2.690643 | -0.000958 | 0.001048 | 0.000045 |

16 | -2.690735 | -2.690643 | -2.690689 | -0.000958 | 0.000045 | -0.000456 |

Hence the root of the above polynomial is **-2.690689**
(because the difference between *a* and *b* in
the last iteration is smaller than the threshold 0.0001), and
the function value at that point is **-0.000456**, close enough to
zero.

(Some animations on the bisection method can be found on this website: Bisection method. Look at the first one.)

Write a program `Bisection.java` that asks the user to enter
the integer coefficients
(*c3*, *c2*, *c1*, *c0*)
for a polynomial of degree 3:
*c3*×*x*^{3} +
*c2*×*x*^{2} +
*c1*×*x* +
*c0*.
It then asks for the two endpoints, which are real numbers.
You may assume that the user enters a continuous function with a real
root. You may use the `double` data types for real numbers.
To simplify matters,
you may also assume that the two endpoints the user entered have
function values that are opposite in signs.

Real numbers are to be displayed accurate to 6 decimal digits (see output in sample runs below).

Sample run using interactive input (user's input shown in
blue; output shown in
**bold purple**).
**Only the last 2 lines shown in
bold purple
are what your program needs to produce. The iterations are shown
here for your
own checking only.**

The sample run below shows the output for the above example. Note that the iterations end when the difference of the two endpoints is less than 0.0001, and the result (root) is the midpoint of these two endpoints.

$ javac Bisection.java $ java Bisection Enter coefficients (c3,c2,c1,c0) of polynomials:1 2 0 5Enter endpoints a and b:-3 0#1: a = -3.000000; b = 0.000000; m = -1.500000 p(a) = -4.000000; p(b) = 5.000000; p(m) = 6.125000 #2: a = -3.000000; b = -1.500000; m = -2.250000 p(a) = -4.000000; p(b) = 6.125000; p(m) = 3.734375 #3: a = -3.000000; b = -2.250000; m = -2.625000 p(a) = -4.000000; p(b) = 3.734375; p(m) = 0.693359 #4: a = -3.000000; b = -2.625000; m = -2.812500 p(a) = -4.000000; p(b) = 0.693359; p(m) = -1.427002 #5: a = -2.812500; b = -2.625000; m = -2.718750 p(a) = -1.427002; p(b) = 0.693359; p(m) = -0.312714 (... omitted for brevity ...) #15: a = -2.690735; b = -2.690552; m = -2.690643 p(a) = -0.000958; p(b) = 0.001048; p(m) = 0.000045 #16: a = -2.690735; b = -2.690643; m = -2.690689 p(a) = -0.000958; p(b) = 0.000045; p(m) = -0.000456root = -2.690689 p(root) = -0.000456

The second sample run below shows how to find the square root of 5. For polynomial where there are more than one real root, only one root needs to be reported.

$ java Bisection Enter coefficients (c3,c2,c1,c0) of polynomials:0 1 0 -5Enter endpoints a and b:1 3#1: a = 1.000000; b = 3.000000; m = 2.000000 p(a) = -4.000000; p(b) = 4.000000; p(m) = -1.000000 #2: a = 2.000000; b = 3.000000; m = 2.500000 p(a) = -1.000000; p(b) = 4.000000; p(m) = 1.250000 (... omitted for brevity ...) #16: a = 2.236023; b = 2.236084; m = 2.236053 p(a) = -0.000201; p(b) = 0.000072; p(m) = -0.000065root = 2.236053 p(root) = -0.000065

Submit your program `Bisection.java` through CourseMarker.

- Array is strictly disallowed for this exercise.

- You are reminded that only two lines of output (those shown
in
**bold purple**in the sample runs above) are the required output. Your program is not to display the iterations in your output.

- Note that your program will be tested with a number of test data.

- Creating some Java classes
- Instantiating objects
- Constructor, accessor and mutator methods
- Overriding method toString
- Selection and repetition statements
- Developing a game

You are given these 2 codes:

- Peg.java (full code;
**not**to be modified) - FourPegs.java (partial code)

In the game of **MasterMind**®, a secret code of 4 pegs are
hidden from the player's view. Pegs are in six different colours:
Red (`'R'`),
Green (`'G'`),
Blue (`'B'`),
Yellow (`'Y'`),
Cyan (`'C'`), and
Magenta (`'M'`). The program `Peg.java` defines the
`Peg` class, which implements the colours by using a character
to represent each colour
(`'R'`, `'G'`, `'B'`,
`'Y'`, `'C'`, and `'M'`).

The player tries to break the secret code by making guesses, where
each guess consists of 4 pegs. The player is awarded 'sinks' and
'hits' points as follows. A **sink** point is awarded if a peg in the
guess matches the colour of the corresponding peg in the same position
in the secret code. A **hit** is awarded if a peg in the guess
matches only the colour of some peg in the secret code, but not
the position. A sink takes precedence over a hit; that is, if a
peg has already contributed to a sink point, it should not be
used to compare for a hit.

The game ends when the player gets 4 sinks, or when he/she has made the maximum number of attempts.

There are two versions of the game. In one version, the secret code may contain two or more pegs of the same colour. In another version, no duplicate colour is allowed. We shall implement the first version here.

Refer to the sample runs below for some examples. Note that the secret code is deliberately displayed for you to check the correctness of sinks and hits awarded.

Please take note of the following:

- The file
`Peg.java`is given to you. It is**not**to be modified. You may not need to use all the methods in the`Peg`class in your other programs.

- You are to complete and submit
`FourPegs.java`. The partial code is given to you.

- You should not modify the methods that have been
completed for you: the 3 constructors,
`setColour`and`getColour`.

- You are to complete the
`toString`,`countSinks`and`countHits`methods. You may change the signatures of`countSinks`and`countHits`to your liking.

- You may add other methods deemed necessary.

- You should not modify the methods that have been
completed for you: the 3 constructors,
- You are to write and submit
`MasterMind.java`that implements the MasterMind game. Note that:

- The maximum number of attempts for the player to make guesses
is 10.

- This program may call any method in the
`FourPegs`class, but it may**not**call any method in the`Peg`class.

- You may add other methods deemed necessary.

- You are to read a string of 4 characters from the player.
If the string has length other than 4, you should
ask the player to re-enter, as shown in the second sample
run below.

- You may assume that the characters in the string
entered by the player are valid characters that
represent the colours. A FourPeg object representing
the player's guess should be created from the data in the
string.

- The String method
`charAt(int)`might be handy. You may refer to the API Specification for`charAt(int)`.

- Hint: In generating the secret code, you may use an
appropriate method in the
`Random`class to generate 4 integers each in the range [0, 5], and map each number to a corresponding colour. You may refer to the API Specification for`Random`class.

(You may choose not to follow the hint and do it your own way.)

- The maximum number of attempts for the player to make guesses
is 10.

Sample run using interactive input (user's input shown in
blue; output shown in
**bold purple**):

$ javac Peg.java $ javac FourPegs.java $ javac MasterMind.java $ java MasterMindSecret code: G R R CEnter your guess: BGRMGuess #01: B G R M Sinks = 1; Hits = 1Enter your guess: YCCYGuess #02: Y C C Y Sinks = 0; Hits = 1Enter your guess: RRCCGuess #03: R R C C Sinks = 2; Hits = 1Enter your guess: BBMYGuess #04: B B M Y Sinks = 0; Hits = 0Enter your guess: CGCGGuess #05: C G C G Sinks = 0; Hits = 2Enter your guess: CCCGGuess #06: C C C G Sinks = 0; Hits = 2Enter your guess: CGRRGuess #07: C G R R Sinks = 1; Hits = 3Enter your guess: RRCGGuess #08: R R C G Sinks = 1; Hits = 3Enter your guess: RGCRGuess #09: R G C R Sinks = 0; Hits = 4Enter your guess: CRRGGuess #10: C R R G Sinks = 2; Hits = 2Sorry you didn't get it. The secret code is G R R C. Hope you have enjoyed the game. Bye!

Another sample run:

$ java MasterMindSecret code: B M Y REnter your guess: GG Enter your guess: GGRRR Enter your guess: GGRRGuess #01: G G R R Sinks = 1; Hits = 0Enter your guess: MMMYGuess #02: M M M Y Sinks = 1; Hits = 1Enter your guess: BMBYGuess #03: B M B Y Sinks = 2; Hits = 1Enter your guess: BMYCGuess #04: B M Y C Sinks = 3; Hits = 0Enter your guess: BMYRGuess #05: B M Y R Sinks = 4; Hits = 0Congratulations! Hope you have enjoyed the game. Bye!

You do not need to submit this exercise.

- Ensure that the outputs of your program comform to the format of
the sample outputs given.

- As the topic on arrays has not been covered, we suggest that you
do not use array in this assignment. Although as a result some
parts of the code will be repetitive and long, it is still bearable,
since the number of pegs is only 4. You could treat the array version
as an enhancement later, and write it on your own.

However, if some of you insist on using array, we will allow you to do so, without extra credit. But you might need to modify certain part of the program`FourPegs.java`that is given to you.

- You may further enhance your MasterMind program by adding
graphics to it. Since students always tell us that doing
assignments for grading takes away the fun, we shall let you
work on this enhancement for your own pleasure and at
your own leisure. :) ☺

The deadline for handing in all programs is **3 October 2007, Wednesday,
23:59**. (Yes, you are given more than two weeks for this lab assignment
- thanks to the 1-week recess!) Late submissions will NOT be accepted.

**Start early**. Do not wait till the eleventh hour and
rush to meet the deadline.

- 0 Introduction

- 1 Exercise 1: Remainder (20%)

- 2 Exercise 2: Bisection Method (80%)

- 3 Exercise 3: MasterMind (0%)

- 4 Deadline

tantc@comp.nus.edu.sg

Wed Sep 5 10:43:46 SGT 2007