UMBC CMSC 201 Spring '05 CSEE | 201 | 201 S'05 | lectures | news | resources |discussion| help

CMSC 201
Programming Project Five

Out: Saturday, 30 April 2005
Due: Before Midnight, Tuesday 5/17/05

The design document for this project, design5.txt,
is due: Before Midnight, Friday 5/6/05

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 (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]

Playing Dominoes

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
  1. 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")
             [0 | 4] [4 | 5] [5 | 7] [7 | 3]
  2. 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")
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.

The Task

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. Print this menu
  7. 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.

Project Requirements

  1. Dominoes must be printed in the format [ x | y ].
  2. 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.
  3. Whenever a domino is added to the train (by either the user or the system), your program will print the new train.
  4. 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.
  5. The system will report the result of its turn to the user.
    1. Played domino [ x | y ] at the head (or tail) of the train
    2. Drew a domino from the boneyard
    3. Passing because the boneyard is empty
  6. Your program must enforce all game rules -- proper placing of dominoes, can't pass if boneyard is not empty, etc.

Programming Requirements

  1. Your program will accept two command line parameters, in this order
    1. 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.
    2. The number of dominoes each player selects to start the game ("N" in the description above)
  2. 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)
  3. 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)
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. You must guard your all of your header files (.h files).
  9. You must use top-down design. Your project will be graded for good design as in projects 2, 3 and 4
  10. 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
  1. The name of the file that contains the dominoes will be less than 50 characters.
  2. The data in the domino file is valid.
  3. As in previous projects, the graders will enter only a single character (or integer) for menu input.
  4. Graders will only input integers when specifying a domino.

Data Files

Several data files are available for you to use for testing. In Mrs. Evans' public directory
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.

Sample Output

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. 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 game himself.

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

Extra Credit

  • 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.

CSEE | 201 | 201 S'05 | lectures | news | resources | help |

Sunday, 15-May-2005 17:32:31 EDT