Programming Project Five
Out: Saturday, 30 April 2005
Due: Before Midnight, Tuesday 5/17/05
The design document for this project,
is due: Before Midnight, Friday 5/6/05
The objective of this assignment is to give you practice using command line
arguments, guarding header files, and working with linked lists.
A domino is a small, rectangular piece of ivory (or fake ivory for those
on a limited budget). 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
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.
- place a domino that has a 4 on
one half (such as [4 | 6] or [0 | 4]) at the head of the train, creating
[6 | 4] [4 | 5] [5 | 7] [7 | 3] (Note that [4|6] was "flipped")
[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]
[4 | 5] [5 | 7] [7 | 3] [3 | 2] (Note that [2|3] was "flipped")
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
- 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
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
- 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 */
/* a node in the linked list */
typedef struct node
DOMINO data; /* the data */
struct node *next; /* pointer to next node in the list */
/* 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 */
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
- 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.
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.
Several data files are available for you to use for testing. In Mrs. Evans'
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
Three sample outputs are provided
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. Since
the system is not smart, the user (not your program) must recognize the
condition that the boneyard is empty and neither player can play and quit the
- 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.
Try experimenting with these files with different number 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
- You MUST first submit a normal project 5 with all its necessary
files into the Proj5 directory that works as specified. You may then choose
to work on a "smart" version of this project.
- Smart versions must be submitted into the Smart directory using:
submit cs201 Smart smart.c (followed by your other .c & .h files)
- The smart version should have the system choose the best domino to
play, if more than one domino is a possible choice. The system should
try to "set itself up" for future plays, like a human player does.
- Keep in mind that you could possibly keep track of all the remaining
unplayed dominoes in the set being used.
- The smart version should also end the game if the boneyard is empty
and neither player can play on the current train.
- No help will be given for the extra credit work.
- The smart version of the project can earn you a maximum of 10 extra
points on your project 5 score. These points are variable and based
on the judgement of your grader.