CPS 6 - Assignment 5 - Summer

CPS 6 Summer_I 2002: Assignment #5

Due: Monday, 24 Jun by 9am

20 points

Setup

Assignments are to be your own work. You may consult with other CPS 6 students or me if you get stuck, but the final writeup is to be yours.

See the CPS 6 web page about the late policy for programming assignments. If a program is late there is a penalty, however it is usually better to keep working on it and turn it in late and correct, then on time and not working..

In your cps006 directory, you should create an assign5 directory to work in. You'll then copy files into this directory to help you get started. That is, type the following unix commands from your account after you login (don't forget the trailing dot on the last line).

   cd cps006
   mkdir assign5
   cd assign5
   cp ~abd5/cps006/assign5/*  .

If you did these commands correctly, typing pwd should show that you are in your assign5 directory, and typing ls should show the files

Note that 20% of your program grade is based on the readability of your program. This includes things like style, comments, and the naming of variables and functions. Make sure you include a comment at the top of each program with your name, course and purpose of the program specified.

// Name: YOUR NAME HERE // // Course: CPS 6 // // Date: // // Purpose: purpose of program here //

Problem: Dots

For this assignment you'll write some of the classes used to play a game of dots. Other classes are written for you and you'll use them in implementing the classes Box and DotsModel.

The game of dots allows each of two (or more) players to draw an edge between two dots. The players alternate drawing edges. When four edges form a box, the player who just completed the box gets to "claim" it with his/her initial and gets to make another edge. When all edges are taken, and all boxes outlined, the player with the most boxes wins.

Here's part of a game as played by a complete version of the program you're writing. This version uses players named Andy and Herb on a 2 x 2 board.

(user entered input in italics).

prompt> dodots

    0      1      2      
  0 +......+......+
    .      .      .
    .      .      .
    .      .      .
  1 +......+......+
    .      .      .
    .      .      .
    .      .      .
  2 +......+......+
    0      1      2      
Herb enter point 1> 0 0
Herb enter point 2> 1 0

    0      1      2      
  0 +------+......+
    .      .      .
    .      .      .
    .      .      .
  1 +......+......+
    .      .      .
    .      .      .
    .      .      .
  2 +......+......+
    0      1      2      
Andy enter point 1> 1 0
Andy enter point 2> 1 1

    0      1      2      
  0 +------+......+
    .      |      .
    .      |      .
    .      |      .
  1 +......+......+
    .      .      .
    .      .      .
    .      .      .
  2 +......+......+
    0      1      2

Note that the origin here is in the upper-left corner, that x-coordinates increase to the left and y-coordinates increase downward. The first coordinate of a point entered by the user is the x-coordinate as the example run above shows.

If the user picks an edge that's not on the board, or already taken, the program prints an error message.

Andy enter point 1> 0 1
Andy enter point 2> 2 1
that edge is illegal, try again
    0      1      2      
  0 +------+......+
    .      |      .
    .      |      .
    .      |      .
  1 +......+......+
    .      .      .
    .      .      .
    .      .      .
  2 +......+......+
    0      1      2      
Andy enter point 1> 0 0
Andy enter point 2> 1 0
that edge is used, try again
    0      1      2      
  0 +------+......+
    .      |      .
    .      |      .
    .      |      .
  1 +......+......+
    .      .      .
    .      .      .
    .      .      .
  2 +......+......+
    0      1      2      
Andy enter point 1> 0 1
Andy enter point 2> 1 1
    0      1      2      
  0 +------+......+
    .      |      .
    .      |      .
    .      |      .
  1 +------+......+
    .      .      .
    .      .      .
    .      .      .
  2 +......+......+
    0      1      2

If a player completes a box, he/she gets another turn:


    0      1      2      
  0 +------+......+
    .      |      .
    .      |      .
    .      |      .
  1 +------+......+
    .      .      .
    .      .      .
    .      .      .
  2 +......+......+
    0      1      2      
Andy enter point 1> 0 0
Andy enter point 2> 0 1

    0      1      2      
  0 +------+......+
    |      |      .
    |   O  |      .
    |      |      .
  1 +------+......+
    .      .      .
    .      .      .
    .      .      .
  2 +......+......+
    0      1      2      

Andy enter point 1>

When all edges/boxes are taken the game is over and the player with the most boxes wins.

Classes and The Design of Dots

You'll need to implement most of the classes Box and DotsModel. You shouldn't need to modify any other classes. You will need to add some code to dodots.cpp to tell which player has won the game. You should not modify classes other than those you're asked to modify.

Complete Classes You Start With---Do Not Modify These

Point and Edge

You're given .h and .cpp files complete for the classes Point and Edge. These are both declared in edge.h and implemented in edge.cpp. Documentation for these classes, and for other classes, can be found in the .h files for the classes. You whould be sure to read this documentation to understand the program structure. These classes are mostly support classes for the class Box.

The class Point represents an ordered pair (x,y). Points can be compared for equality using operator ==, printed using operator <<, constructed, and translated. Translation means changing the x- and y-coordinate by some amount. See the header file edge.h for more details.
The class Edge is defined by two points. In the dots game these points will be adjacent either horizontally or vertically. Edges can be compared for equality and the edge (p,q) is considered equal to the edge (q,p) where p and q are points. Edges can be printed too, see the header file for more details.

Player

The class Player in its current version simply stores a player's name. It's possible we'll provide a version of this class so that the computer can play a game of dots with a person (a so-called AI, or Artificial Intelligence, player). See player.h for details.

DotsViewer

The class DotsViewer shows a model---that is the current state of the boxes/game. This is a text view of the model, you can study the code to see how the classes Box and Edge are used in printing the board the players see. See dotsviewer.h and dotsviewer.cpp for details.

Implenting the class Box

The class Box, declared in box.h is a collection of edges; the collection represents a box on a dots board. The Box member functions are described in the box.h header file and in this write-up. You must implement most of the class Box.

You need to implement several of the of the Box member functions. To help you determine if you've implemented the functions correctly you're given a test program in testbox.cpp.

Your goal is to run this program, have it do all the tests, and have it print nothing. When you copy it and run it initially, it will print error messages indicating that some tests have failed. You should implement the corresponding Box member functions, run the tests, then when the tests pass (there's no output), you'll run the other test functions from testbox.cpp

Summary of running testbox.cpp

Compile and run,

  prompt> make testbox
  prompt> testbox

Initially the program runs the test function testBadEdges which tests member functions Box::isUsed and Box::isFree. You'll need to implement these functions and the private function Box::init (and perhaps others) to pass the tests. After your code passes tests, when there's no output from running testbox.cpp, you'll uncomment one of the commented-out test function calls from main, e.g., testEdges.

Looking at the test code, you'll implement more Box member functions until the tests pass. Then you'll uncomment the last commented-out function call from main, pass these tests, and be confident your Box class is correct.

run testbox, make it pass the tests in testBadEdges
uncomment the call to testEdges and pass those tests
uncomment the call to testAdding and pass those tests

Do not proceed to the next step until your code passes the tests.

Implementing the class DotsModel

The class DotsModel, declared in dotsmodel.h stores the state of a dots game. This means it stores how many boxes there are and other game information. The boxes store edge and other information so that most of the DotsModel code consists of finding the right Box and interacting with that Box.

In the version you're writing, the Boxes are stored in a vector of Boxes. For example, on a 2x3 dots board a DotsModel object will need to store 6 Boxes. On a 4x5 dots board 20 Boxes will be stored in the private vector myBoxes. Your implementation can store the boxes in any order, but you must store all the boxes for a game. Note that client programs like DotsViewer request all the boxes from a model one at a time. The order in which your code returns the boxes doesn't matter, so you can store boxes in any order. However, the function DotsModel::initialize constructs the boxes.

If you run the dodots executable, you'll find which functions from DotsModel aren't implemented. Using the game program dodots as a testing program, you should implement all the member functions of DotsModel so that a game is played between two players.

Anatomy of addEdge

The header for DotsModel::addEdge is shown below. Pseudo-code for the implementation is given to help you understand the relationship between the DotsModel class and the vector of Boxes that store most of the game state. bool DotsModel:: addEdge(const Edge& e, const Player& p) // pre: isOk(e), i.e., e is in model, not used // post: e added to model, returns true if adding e completes // the box to which it's added and returns false otherwise // note: returns false if e not added to model { initialize boxFilled to false; foreach of the k Boxes in myBoxes { if possible, add e to the k-th box if the k-th box can have e added to it then mark the k-th box as complete occupy the k-th box with player's name set boxFilled to true since at least one box filled endif } return boxFilled; }

Final changes to DotsModel

The current Model class doesn't keep track of how many boxes are occupied by each player. For full credit on this assignment, you should design a solution so that the DotsModel class keeps track of how many boxes each player using the model has "captured". You can add any state you want to the private section of the DotsModel class, and you can add new public/private member functions to the class.

You must implement a member function that can be used in client programs like dodots.cpp as follows to find how many boxes Player p has captured.

    
   int pCount = model.getFilledCount(p);

Submit

When your program compiles and produces the correct output, create a file named README (please use all capital letters in naming the file). In the file include your name, section number, the date, and an estimate of how long you worked on the assignment . You must also include a list of names of all those people with whom you consulted on the assignment. See the CPS 6 web page for the meaning of consult.

To submit your program electronically you must be in your code directory and type

submit_cps006 assign5 *.cpp *.h README

You should receive a message telling you that the programs were submitted correctly.

To see that the programs were submitted correctly, type

    submit_cps006 assign5

with no arguments and a list of the files submitted will be shown. PLEASE RUN THIS COMMAND to make sure your programs were submitted correctly.

The submit command with *.cpp submits all of your .cpp programs in your current directory at the same time. You can resubmit again if you realize you made a mistake and want to change something. If you submit more than once, we grade the last submission. If the first submission is on time and the last one is late, then the programs are late. All programs must be turned in together. You cannot submit one program early and the rest late.