CS 5 Fall 2009
Lab Assignment #1
Due Wednesday, October 14
The purpose of this assignment is to consolidate your knowledge of
basic Java statements and control structures and to allow you to
create a couple of useful classes. It also provides an opportunity to
analyze a somewhat more complex problem and to use methods effectively
in the problem decomposition. Finally, it gives you practice in
developing a good user interface for a program.
Although we call this a lab assignment, you are not obligated to sit
in a computer lab to do it. The term "lab assignment" distinguishes
this type of assignment from short assignments. This lab assignment
is much more complex than a short assignment. It requires more
thinking, design, and creativity. And you have a full week to do it.
For reasons that escape me, every year several CS 5 students miss
important points of this assignment. At the end of this web page is a
recap of things you should make sure you have
done before handing in this assignment.
The Game of Chips
Write a Java program that enables two people to play the following
game. Read the description of the game carefully.
We start with a pile of chips. Let's say—for the
moment—that there are 99 chips. (But your game will allow for
numbers other than 99.) We get the names of the two players. The
first player removes between 1 and 49 chips from the pile. From then
on the players alternate turns, removing chips from the pile until it
is empty. Each player removes at least one chip in each turn, but
- never more than twice the number of chips last removed by the
other player, and
- never more than the number of chips remaining in the pile.
Once the pile becomes empty, the game is over. Since the total number
of chips is odd, one player will have an even number of chips and the
other player will have an odd number of chips. The winner of the game
is the player with an even number of chips.
When a game is over, your program should ask whether to play another
game. If the answer begins with y, it should play
another game; otherwise the program ends. This prompt should occur
after each game.
Your program should allow the initial number of chips to be
any odd number, not just 99; this number should be entered at
the beginning of each game, rather than being fixed. (Think about why
we can't allow an even number of chips to start with.) The initial
number of chips should be at least 3, however, since the game is not
terribly interesting with only one chip. The first move of the game
must leave at least half of the initial number of chips in the pile.
The remaining moves do not have this restriction.
Note that it is two humans who are playing the game. The
computer is merely serving as a referee. In other words, you
don't have to worry about determining a strategy for winning the game,
nor do you have to worry about programming such a strategy.
Begin by analyzing the game. What are the inputs and outputs? What
information makes up the state of the game, i.e., what needs to be
saved from turn to turn? You should create a separate class that
keeps this information in instance variables that are private to the
class; for the sake of discussion, we'll call this class
Referee, but you are free to use any name you like, as
long as it's descriptive. Your main program will create a single
object of this class that will represent the current state of the
game. Your main program will call methods using this object's name.
You should also create a class that keeps track of information for
each player. (I called mine—ready for this clever
name?—Player.) I would expect that, at a minimum,
each object of this class has the player's name and how many chips the
player currently has. In my implementation, the Referee
class maintains references to two Player objects.
What are the various tasks that are needed to let the main program
interact with the information saved in the instance variables and
update it as necessary? (Note that the instance variables are
private, and so the only way that the main program can affect them is
via method calls.) For example, you will need to set up the game to
start with, make a move, print out information about the current state
of the game, decide who won, etc. Concentrate on organizing your
program so that its structure reflects the structure of the game. The
methods that you add to your Referee class (or whatever
you decide to call yours) should make the main program short and easy
to write. The program GuessingGame.java that we will develop in class
should serve as a good reference for you.
Historically, several CS 5 students have submitted programs that have
one method for the first player's turn and a different method for the
second player's turn, and a main game loop in which each iteration
calls one method for the first player's turn and then the other method
for the second player's turn. Do not design your program this way;
you will lose major points if you do. (Remember that it is not enough
to write a program that works; your program must be well designed and
well written.) In addition to being a crufty design, it also can make
one player take a turn even when the other player has just taken the
last chip. It is much cleaner to design methods that work for either
player's turn, knowing whose turn it is. One way to do so is by using
two separate variables (references to Player in my
implementation) to keep track of the player whose turn it currently is
and the other player. You would swap these references after each
move.
As an aside, the easiest way to swap the values of two
variables—no matter what their types, and no matter whether they
are primitive types or references to objects—is to use a
temporary variable. Let's suppose we want to swap the values of
variables x and y, both of type
T. (Here, T stands for any type at all,
including a reference to objects of some class.) The easy way is
<![CDATA[
T temp = x;
x = y;
y = temp;
]]>
An important part of your program should be the user interface. It
should prompt the players tastefully. It should check inputs to make
sure they make sense and are legal moves. (You may assume that what
players enter into the program are of the right type. In other words,
you shouldn't worry about a player typing in Z or 3.14 in response to
how many chips to take. Assume that you will read an integer. But
you should check that the integer number of chips entered is legal.)
And it should provide just enough information to keep the game moving
without getting in the way.
At the start of each game, your program should ask for the players'
names. It should make sure that the two players have different names.
(Differences in upper/lower case don't count: consider Bozo and BoZo
to be the same name. The String method
equalsIgnoreCase helps here.) Your program should ask
how many chips there are. It should accept only legal answers to this
question, reprompting if illegal answers are given. Upon each turn,
your program should announce whose move it is, how many chips each
player has, and how many are left. It should ask for a move and check
to see whether the move is legal. If the move is not legal, your
program should tell the player so and give the player another chance
to move legally. Your program should determine when the game is over,
and when that happens, it should announce the winner.
A Sample Run
Here is a sample run. You need not reproduce the prompts and the
presentation of the information exactly as I have done.
<![CDATA[
What is the name of the first player? Nancy
What is the name of the second player? nancy
Both players cannot be named nancy. Enter a different name: Tom
How many chips does the initial pile contain? 1
You have to start with at least 3 chips. Choose another number: 22
You have to start with an odd number of chips. Choose another number: 23
Nancy has 0 chips.
Tom has 0 chips.
It is your turn, Nancy.
There are 23 chips remaining.
You may take any number of chips from 1 to 11. How many will you take, Nancy? 7
Tom has 0 chips.
Nancy has 7 chips.
It is your turn, Tom.
There are 16 chips remaining.
You may take any number of chips from 1 to 14. How many will you take, Tom? 0
Illegal move: you must take at least one chip.
How many will you take, Tom? 16
Illegal move: you may not take more than 14 chips.
How many will you take, Tom? 11
Nancy has 7 chips.
Tom has 11 chips.
It is your turn, Nancy.
There are 5 chips remaining.
You may take any number of chips from 1 to 5. How many will you take, Nancy? 5
* * * * * * * * * * * * * * * * * * * * * * * * * * *
Tom has 11 chips.
Nancy has 12 chips.
Nancy wins!
Play another game? (y/n) y
What is the name of the first player? Tom
What is the name of the second player? Chase
How many chips does the initial pile contain? 57
Tom has 0 chips.
Chase has 0 chips.
It is your turn, Tom.
There are 57 chips remaining.
You may take any number of chips from 1 to 28. How many will you take, Tom? 56
Illegal move: you may not take more than 28 chips.
How many will you take, Tom? -1
Illegal move: you must take at least one chip.
How many will you take, Tom? 28
Chase has 0 chips.
Tom has 28 chips.
It is your turn, Chase.
There are 29 chips remaining.
You may take any number of chips from 1 to 29. How many will you take, Chase? 28
Tom has 28 chips.
Chase has 28 chips.
It is your turn, Tom.
There is 1 chip remaining.
You may take any number of chips from 1 to 1. How many will you take, Tom? 1
* * * * * * * * * * * * * * * * * * * * * * * * * * *
Chase has 28 chips.
Tom has 29 chips.
Chase wins!
Play another game? (y/n) n
]]>
How to proceed
Familiarize yourself with the game. Discuss it with classmates. Play
the game with a friend, or with someone you'd like to be a friend.
Think about how you would organize the program in terms of
- what information needs to be saved from turn to turn, and
- what methods are needed to make use of and update this
information as the game progresses.
Your section leader will discuss the assignment during your recitation
section this week.
DO NOT LEAVE THIS ASSIGNMENT FOR
THE LAST MINUTE.
There will come a time when you will eat assignments like this for
breakfast. That time, however, is in the future. We have covered in
class everything you need to know to start on this program right now.
Your section leader will help you get going. Get a jump on this
program so that you can focus on a clean design and an aesthetic
implementation.
Extra Credit
CS 5 lab assignments offer you the chance to submit extra credit.
Extra credit counts separately; getting 35 on the basic part
of the assignment plus 5 points of extra credit is not the
same as getting a 40. Do not skimp on the basic part of the
assignment for the sake of extra credit. In other words, a 40
with no extra credit is better than a 35 with 5 points of extra
credit.
Also, please note that when you choose to do extra-credit work, you do
it on your own. We are always happy to help you with the basic part
of the assignment, but we will not give help for extra credit.
Exasperated referee
As in the guessing game program, have the computer keep track of how
many times in a row a player attempts to make an illegal move. Have
the prompts get progressively crabbier and eventually declare the
other player the winner.
If you do this extra credit part, (exasperated referee) you
should just turn it in as part of your regular program, but indicate
clearly in a comment near the beginning that you've done this extra
credit.
Alternate winning criteria
There are a number of other possible criteria for winning. One is
that the player who takes the last chip wins. Another is that the
player who takes the last chip loses. Still another is the one who
takes the most chips wins. Note that for some of these criteria, the
requirements for the initial pile of chips may be different. It may
not matter that the initial number of chips is odd, and for
last-chip-wins you only have to require that the first player leave
one chip. In your design, is it possible to only replace your
Referee class with a different Referee
class, or must you rewrite other parts of your program?
Implement one or more of these options (or others that you invent).
Still better, let the players choose between three or four winning
criteria at the start of a game.
If you go for this extra-credit option but do not allow the
user to chose among the criteria at the start of the game, hand in
separate versions of the game for the different winning conditions.
If you do allow the user to choose, make sure that the original
winning condition (even-number-of-chips wins) is one of the choices,
and just hand in a single program.
Chips for Three
When I play Chips with my wife, my mother-in-law always wants to get
into the act, too. (Surely you're having no trouble envisioning this
scene as we sit by the woodstove on a cold winter evening.) So we
devised a version of Chips with three players. Start with an odd
number of chips that is equal to 3n+1 for some even integer
n; again, this value should be entered when you run the
program, and your program should check that it equals 3n+1 for
some even integer n > 1. Players take turns under the same
rules as the two-player version, except of course the turns rotate
among three players. Once all the chips have been taken, either one
player has an odd number of chips and the other two have an even
number, or all three players have an odd number of chips. If one
player has an odd number of chips and the other two have an even
number, then the player with an odd number is the winner. If instead
all three players have an odd number of chips, then determine the
remainders when you divide the number of chips each player has by 3.
It will turn out that two players have the same remainder and one
player will have a different remainder. (If you know a little math,
you can prove this, but you are not required to.) The player with the
different remainder is the winner. It's a great game—it drives
my mother-in-law nuts. (I'm kidding. My mother-in-law is wonderful.)
If you do this extra credit part (Chips for Three), keep it as
separate files from the basic program. In this case, you will turn in
two separate programs and listings.
Chips with dialog boxes
Have your program communicate with the players by means of popup
dialog boxes, rather than the console interface. You can read about
dialog boxes on pp. 267–270 of Lewis & Loftus, and you can
read in detail about the JOptionPane class that you would
use by finding it in the listing of all classes
available in Java.
Take care when constructing the dialog boxes. Think about creating
messages that are on multiple lines, rather than creating one very
long line. The newline character, \n, is your friend!
Your dialog boxes will require actual answers. If instead of
supplying an answer, the user were to press the "Cancel" button in a
dialog box, it would be OK for your program to throw an exception that
caused the program to terminate.
If you use dialog boxes, you will need to convert strings (as returned
by, say, the method JOptionPane.showInputDialog, which
returns a reference to a String) to integers. The
Integer class contains a method parseInt
that does this for you. For example, after executing the lines
<![CDATA[
String digits = "37";
int x = Integer.parseInt(digits);
]]>
the int variable x has the value 37. More
to the point, let's suppose you execute the following:
<![CDATA[
int x = Integer.parseInt(JOptionPane.showInputDialog("Give me a number, Clyde"));
]]>
Then x will get whatever number is typed into the dialog
box. If the String referenced by
JOptionPane.showInputDialog's return value contains
characters that do not form an integer, then an exception occurs.
Again, that's OK.
As with Chips for Three, if you do this extra credit part
(Chips with Dialog Boxes), keep it in as separate files from the basic
program, and turn in a separate program. You cannot turn in a listing
with dialog boxes, and so your section leader will determine
correctness only by running your program.
Other extra credit
If you come up with a different idea for extra credit, please discuss
it with me or with your section leader. We encourage creativity, but
only for extra credit. Make sure that you turn in the basic
version of the program, even if you do extra credit. (But if
you implement the exasperated referee and no other extra credit, you
can just turn in the one version.)
General directions for turning in your lab assignments
Please read these directions carefully. Despite
assurances from the Dean of Admissions about the intelligence of
students admitted to Dartmouth, it is positively astounding how many
CS 5 students do not turn in the lab assignments correctly.
For each program you should
- Turn in a clean listing (i.e., a printout of your
source code) of your program.
- Turn in a run (or runs) that shows off what your
program can do. Make sure that the runs you submit
come from the program that you submit. If you make even the
smallest change to your program, redo your runs! Remember
that if the runs you turn in do not come from the program you
submit, you have violated the Academic Honor
Principle.
- We have created a special computer account for your section
leader. It is to be used only for you to submit your
lab assignments. Don't use it for anything else, including
asking for help or submitting short assignments.
Send a Blitz to the special account for your section
leader containing your Java files.
- The special account is of the form
cs5-xxxxxx@cs.dartmouth.edu, where xxxxxx is replaced by
your section leader's first name. If you look up your
section on the Recitation Sections part of Blackboard,
you'll see the account for your section. Or you can use
this handy list:
Please be careful to enter the correct email address
when you Blitz your lab assignment. For example, if
your section leader is Bertha, you should Blitz to
cs5-bertha@cs.dartmouth.edu:
- not to cs5@cs.dartmouth.edu
(don't forget the -bertha part),
- not to bertha@cs.dartmouth.edu
(don't forget the cs5- part),
- not to cs5-bertha@dartmouth.edu
(don't forget the cs. part).
I know you can get this right.
- The "Subject:" line of your Blitz should be
CS 5 Lab Assignment #1
- The Blitz you send should have the .java files that you
wrote, sent as enclosures. Do not
copy-and-paste or cut-and-paste them into the message.
Send them as enclosures.
- Please send just one message, with all your
.java files as enclosures. In other words, do not send
a different message for each .java file.
- Enclose only .java files. Please do not send .class
files or anything else. Do not email some
representation of the output of your program. Just the
.java files that make up your program. Nothing more,
nothing less.
- The Blitz that you send will automatically contain a
timestamp, so that we'll know whether you sent it on
time.
- The cs5-xxxxxx@cs.dartmouth.edu accounts are set up so
that as soon as we receive a Blitz from you, you will
get an automated reply saying
Your blitz with Subject: "YYYYYY" has been received
by the cs5-xxxxxx account.
where YYYYYY is replaced by the "Subject:" line of your
Blitz, and xxxxxx is your section leader's name.
- It may come to pass that you Blitz your files and then
realize that you need to submit updated versions. No
problem! Just Blitz the new versions to the same
account, and use the "Subject:" line
CS 5
Lab Assignment #1 v2
The "v2" will indicate
that it's the second version. And if you need to go to
a third version, use v3. And if you need to go to a
fourth version, then you're sending too many versions,
and you need to think more carefully before Blitzing!
Note that we have set up the automated reply system so
that it will not send an automatic reply twice within
any 10-minute span. We do that because Dartmouth
students have a habit of setting up their Blitzmail
accounts to have an automatic reply giving some crucial
information, such as when the next frat party is, when
they're next going to be in a play, or just some Deep
Thought. If the cs5-xxxxxx account were to autoreply
immediately, then it might autoreply to your autoreply,
and then your autoreply will autoreply to the cs5-xxxxxx
autoreply, and then the cs5-xxxxxx autoreply will
autoreply to your autoreply, and then ... you get the
picture. By disabling autoreplies within a 10-minute
window, we break such "autoreply loops."
- If the timestamp on your Blitz is after 1:45 PM on Wednesday,
October 14, there will be an automatic 16-point deduction. If
the timestamp is after 5:00 PM on Thursday, October 15, we will
not accept your assignment and you will get a 0.
- Package the runs and listings together, all clearly marked and
containing your name. Put them in an envelope that is at least
8.5 x 11 inches, and don't forget to put your name and your
section leader's name on the outside of that envelope as well.
We will not accept your assignment if it is not in an envelope.
If you cannot afford an envelope, please see me or a TA, and we
will get you one. Put the envelope in your section leader's HW
HANDIN box by the start of class on October 14. If you hand it
in after the start of class on October 14, you will need to get
it directly to your section leader. If you Blitz your
electronic version on time but your envelope is late, there
will be a 1-point deduction if we get it by 5:00 on Wednesday,
or a 2-point deduction if we get it by 5:00 on Thursday. After
5:00 on Thursday, we will not accept it, and there will a
6-point deduction. Note also that if you do not submit
hardcopy at all, then you won't have demonstrated that you
tested your program, and in addition to the 6-point deduction
for missing hardcopy, you will also lose the 6 points for
testing.
Grading
Your section leader will run your program and grade this assignment
according to the following breakdown of points:
- Correctness: 8 points
Does the program work? Are there any bugs?
- Decomposition: 8 points
Good use of classes, methods, and parameters?
- Problem Structure: 8 points
Was game state clearly identified? Is it the right amount of
state? Were special cases avoided?
- Testing: 6 points
Did the tests exercise all of the code?
- Style: 10 points
Comments and indentation? Use of final variables?
Input/output is correct, descriptive, and accurate?
- Extra Credit Options:
Alternate winning criteria: up to 8 points
Exasperated referee: up to 6 points
Chips for Three: up to 10 points
Chips with dialog boxes: up to 15 points
Other neat stuff: up to 15 points
- Penalties:
Late electronic submission: -16 points
Late hardcopy submission: -1 or -2 points
Missing hardcopy: -6 points
Features of the game
- Does it ask for the player names? Does it make sure that the
two names are different?
- Does it allow you to enter the initial number of chips? Does
it check that this number is odd and at least 3?
- Does it alternate turns between the two players?
- Upon each turn, does it announce whose move it is, how many
chips each player has, and how many chips are left? Does it
prompt for a move?
- Does it check that the number of chips removed in the first
move is at least 1 and that it leaves at least half of the
initial number of chips?
- Does it check that the number of chips removed in each move
after the first is at least 1, at most twice the number removed
in the previous move, and at most the number remaining in the
pile?
- Does it end a game when the pile is empty?
- Does it announce the winner according to which player has an
even number of chips?
- Does is ask whether to play another game and do so if the
response begins with
y?
Handing it in
- Have you printed out a listing of the source code of your
program? Does it match the electronic version that you are
going to Blitz to your section leader's
cs5-xxxxxx@cs.dartmouth.edu special account?
- Have you printed out test runs that show off what your program
can do? Do they come from the very program that you are
submitting and not some similar, but not exactly the same,
version? Do these test runs demonstrate all of your program's
capabilities? For example, do they demonstrate that the
initial number of chips must be odd and at least 3? Do they
demonstrate that when asking for a move, the program will not
accept a number of chips less than 1 or greater than the number
allowed? (Note that this is not an exhaustive list of the
capabilities that you must demonstrate, but rather a sample to
give you an idea of the extent of testing that we expect.)
- Have you Blitzed your .java files, as enclosures, to your
section leader's cs5-xxxxxx@cs.dartmouth.edu account by 1:45 PM
on October 14? Did you make sure that you Blitzed
only .java files, and not, say, your .class files?
- Have you put your printouts in an envelope that is at least 8.5
x 11 inches? Is your name on the outside of the envelope?
Have you put this envelope in your section leader's HW HANDIN
box by the start of class on October 14?
Back to Lab Assignments
Thomas H. Cormen <thc@cs.dartmouth.edu>
Last modified: Sun Oct 4 19:12:20 2009