CMSC 201
Programming Project Five
Dominoes
Out: Monday, November 26, 2007
Due: Before Midnight, Sunday 12/9/07
The design document for this project,
design5.txt,
is due: Before Midnight, Sunday 12/2/07
The Objective
The objective of this assignment is to give you practice using command line
arguments, guarding header files, and working with linked lists.
The Background
A domino is a small, rectangular piece of ivory (now plastic, but to be
historically correct, we'll say ivory). A groove is carved into each domino
to divide it into two halves. Small circular indentations are carved into
each half of the domino. The number of circular indentations in each half
represent the value of that half of the domino. (If no indentations are
carved, the value is zero.) The domino [4 | 3] is
shown below.
Sets of dominoes are created by specifying the the maximum value on
a domino. The set contains all dominoes which can be made from a unqiue
combination of two values between 0 and the maximum value, inclusive.
For example, if we specified that the maximum value is 4,
then the set contains the following dominoes:
[0 | 0] [0 | 1] [0 | 2] [0 | 3] [0 | 4]
[1 | 0] [1 | 1] [1 | 2] [1 | 3] [1 | 4]
[2 | 0] [2 | 1] [2 | 2] [2 | 3] [2 | 4]
[3 | 0] [3 | 1] [3 | 2] [3 | 3] [3 | 4]
[4 | 0] [4 | 1] [4 | 2] [4 | 3] [4 | 4]
Our simplified version of Dominoes is a game played by two players
(the user and the system).
When play begins, each player selects N dominoes from the set of
dominoes provided (known as the "bone yard").
A single domino is selected from the bone yard and placed on the table as
the start of the "train".
At each turn the player tries to add to the train by placing one of his
dominoes with a matching value at the head (left hand side)
or the tail (right hand side) of the train.
Note that it may be necessary to "flip" a domino so that
it may be added to the train.
For example, if the train is
[4 | 5] [5 | 7] [7 | 3]
then the player may either
- place a domino that has a 4 on one half (such as
[4 | 6] or [0 | 4]) at the head
of the train, creating for example
[6 | 4] [4 | 5] [5 | 7] [7 | 3] (Note that [4 | 6] was "flipped")
OR
[0 | 4] [4 | 5] [5 | 7] [7 | 3]
- place a domino with 3 on one half (such as [3 | 0]
or [2 | 3]) at the tail of the train, creating for
example
[4 | 5] [5 | 7] [7 | 3] [3 | 0]
OR
[4 | 5] [5 | 7] [7 | 3] [3 | 2] (Note that [2 | 3] was "flipped")
If the player cannot add one of his dominoes to the train,
he chooses a domino from the remaining dominoes in the bone yard and adds it
to his dominoes. If the boneyard is empty, the player simply passes his turn.
The next player then takes his turn.
The game is over when a player uses all of his dominoes.
Your task is to write a program that plays the simplified
version of dominoes described above. The user will be one player and your
program will be the other player. The user will play first.
Your program will first print the requisite greeting and
instructions.
When it is the user's turn to play, you will present the user
with the following menu. Your program may use integer or character input for
the menu.
- Print user's dominoes -- this choice prints all
of the user's dominoes in the format shown in the example above. See the
sample output below.
- Add a domino to the head of the train -- the user specifies
the domino by entering the domino's 2 values (on the same line,
separated by a space). The values may be entered in either order.
If the specified domino does not belong to the user, an error is produced
and the user must choose from the menu again. If the domino does belong
to the user, it is added to the head of the train (being automatically
flipped if necessary) and removed from the user's set of dominoes.
This choice ends the user's turn.
- Add a domino to the tail of the train -- same as adding a
domino to the head of the train, but the domino is added to the tail.
This choice ends the user's turn.
- Draw a domino from the bone yard -- the first domino in the
boneyard is removed from the boneyard and added to the user's set of dominoes.
If the boneyard is empty, an appropriate message will be displayed and the
user will choose another option from the menu. This choice will end the
user's turn.
- Pass this turn -- It's now the system's turn to play. It is an
error for the user to pass his turn if the boneyard is not empty.
This choice ends the user's turn.
- Print this menu
- Quit -- The program terminates with a message.
When it is the system's turn to play, your program will search its
dominoes and play the first domino it finds that can be added to either the
head or the tail of the train. In accordance with the rules described
above, if your program cannot find a domino to
play, it will take the first domino from the bone yard
and add it to the system's dominoes. If the boneyard is empty,
the sytsem simply passes it's turn. It is then the user's turn.
When one player (user or system) uses all of his dominoes, he is declared
the winner and the game terminates with a friendly message.
- Dominoes must be printed in the format
[x | y].
- A set of dominoes (i.e. the train or the user's dominoes) are printed with 4 dominoes printed on the first line and 5 dominoes per line on subsequent lines. See the
sample output below.
- Whenever a domino is added to the
train (by either the user or the system), your program will print the new
train.
- When a player (user or system) chooses a domino to add to the train,
your program will automatically "flip" the domino if necessary.
See the example in the description above.
- The system will report the result of its turn to the user.
- Played domino [x | y] at the head (or tail)
of the train
- Drew a domino from the boneyard
- Passing because the boneyard is empty
- Your program must enforce all game rules -- proper placing of
dominoes, can't pass if boneyard is not empty, etc.
- Your program will accept two command line parameters, in this order
- The name of the file that contains the set of dominoes to use
when playing the game.
Each domino in the file is represented as 2 integers. There is
one pair of integers per line.
- The number of dominoes each player selects to start the game
("N" in the description above)
- You must use linked lists to represent each set of dominoes
(the train, the bone yard, the user's dominoes and the sytstem's dominoes)
- You must use the following structures. You may not change these
structures in any way. You may create other typedefs if you wish.
/* a domino */
typedef struct domino
{
int left; /* the value of the left half of the domino */
int right; /* the value of the right halof of the domino */
} DOMINO;
/* a node in the linked list */
typedef struct node
{
DOMINO data; /* the data */
struct node *next; /* pointer to next node in the list */
} NODE;
/* the linked list */
typedef struct linkedList
{
int nrNodes; /* how many nodes in the linked list */
NODE *head; /* points to first node or NULL */
NODE *tail; /* points to last node or NULL */
} LIST;
Note -- The number of nodes in the linked lists
("nrNodes") is used for display purposes only.
You MAY NOT use nrNodes to
traverse the lists. (I.e no 'for' loops -- 'while' loops only)
- The number of dominoes in a set (in the file) is NOT at the top
of the file. Dynamic memory allocation using malloc() or calloc() for each
linked list node is required, i.e. CreateNode().
You MAY NOT
declare a huge array in which to store the dominoes.
- Since you are allocating the space for each node, when you are
finished with a node, its memory should be free()d. You MUST write
a function called DestroyList(), that will take a list as one of its
arguments and free all of its nodes. This function should also reset
head and tail so that the list is empty after all of the nodes have
been free()d.
- You must perform all necessary error checking, responding with
appropriate error messages and (if possible) continuing the game.
For example, you may not exit() if the user makes an invalid menu choice.
- Your header file(s) must act as a user interface, meaning
each function prototype must have a full function header
comment above it. Function header comments are also
required above the function definitions themselves.
- You must guard your all of your header files (.h files).
- You must use top-down design. Your project will be graded for good
design as in projects 2, 3 and 4
- Since you must use separate compilation for this project, you
will have several files that must be submitted for this
project. The source file that contains main() MUST be
called proj5.c, you will need other .c and .h files. You may name them
as you wish just use names that fit your design.
Assumptions
Your program may make the following assumptions
- The name of the file that contains the dominoes will be less
than 50 characters.
- The data in the domino file is valid.
- As in previous projects, the graders will enter only a single
character (or integer) for menu input.
- Graders will only input integers when specifying a domino.
Data Files
Several data files are available for you to use for testing. In my
pub directory
/afs/umbc.edu/users/b/o/bogar/pub/
you will find files named
- set3.dat - this contains the set of dominoes from
[0 | 0] to [3 | 3]
- set4.dat - this contains the set of dominoes from
[0 | 0] to [4 | 4]
- set5.dat - this contains the set of dominoes from
[0 | 0] to [5 | 5]
Each file contains a set of dominoes in random order. A domino is
represented as a pair of integers, one pair of ints per line. The number
of dominoes in the file is not specified. Copy them into your directory using the Unix 'cp' command.
Because there are several ways to code this program and many choices
to be made by the user, it is unlikely that your output will
exactly match any of the
sample outputs provided. Use these as a guide to reasonable output formats
a reminder of possible error conditions and project requirements. You have
some flexibility in the output, but you must satisfy all
project requirements and all
programming requirements.
Three sample outputs are provided
- set3.out shows a sample game won by the user
using set3.dat and starting with 2 dominoes each.
- set4.out shows a sample game won by the user
using set4.dat and starting with 3 dominoes each.
- set5.out shows a sample using set5.dat and
starting with 4 dominoes each. This game is won by the computer.
The system is not "smart". It places dominoes by playing the first domino it
can from its list (see above). It uses no strategy in its playing.
Try experimenting with these files with different numbers of starting dominoes.
Don't forget that the system can win too!
Submitting the Program
To submit your project, type the following at the Unix prompt.
Note that the project name starts with uppercase 'P'.
submit cs201 Proj5 proj5.c (followed by your other .c & .h files)
Do NOT forget to submit your .h files.
Your program will NOT compile without them.
To verify that your project was submitted, you can execute the
following command at the Unix prompt. It will show all files that
you submitted in a format similar to the Unix 'ls' command.
submitls cs201 Proj5