PROGRAM #3
Fall 2011
Due: October 28, 2011, 11:59pm on Angel
General Guidelines:
· All source code must be in C++. You can use Windows or Unix environments at your discretion.
· Each program project should be accompanied by a COVER SHEET (see details below). Assignments without cover page will NOT be graded.
·
For this programming
assignment, you have the option of either work as a TEAM if you prefer, or as
an individual. A TEAM should contain at
most 2 students including yourself.
·
In the rest of this
document, the term “YOU” is used either to refer to you (if you are working
individually) or your team (if you work as a team).
· The final material for submission should be entirely written by you. If you decide to consult with others or refer materials online, you MUST give due credits to these sources (people, books, webpages, etc.) by listing them on the cover sheet mentioned below. Note that no points will be deducted for referencing these sources. However, your discussion/consultation should be limited to the initial design level. Sharing or even showing your source code/assignment verbiage to anyone else in the class, or direct reproduction of source code/verbiage from online resources, will all be considered plagiarism, and therefore will be awarded ZERO points and subject to the WSU Academic Dishonesty policy. (Reproducing from the Weiss textbook is an exception to this rule, and such reproduction is encouraged wherever possible.)
· Grading will be based on correctness, coding style, implementation efficiency, exception handling, source code documentation, and the written report. Try to also follow the good coding practices discussed in class during the C++ review lecture.
·
If working as a team,
the same grade will be given to both members of a team.
·
If working as a team,
submit only one copy of your assignment into the Drop box and indicate
in the text box of the drop-box while submission, both names in the
project. If you specify only one name then only that person will get the grade
and the other will not. So please make sure you fill in both names.
·
If working as a team,
remember to include both your last names in the zip file of your submission.
· Angel DropBox submission:
Starting this programming assignment, we will use only DropBox.
All assignments with cover sheet should be zipped or tarred into one archive folder (named after your last name).
Instructions for DropBox submission: I have set up a have set up a new DropBox called
“Program project 3” inside Angel. The way to submit to the dropbox is as
follows:
1) Once you login to Angel, click on the "Lessons" tab.
2) You will see "Program project 3".
Click on that and you will see the submission website.
Under Title, just write your first and last name and say
Program 3 - e.g., "Ananth Kalyanaraman, Program 3".
If you are submitting as a team, type in both your names in
the textbox. Otherwise leave it empty.
Then click on the "Attachments" button and attach
your ZIP file there.
And then press the SUBMIT button.
PROBLEM A board game
For this assignment, you will be implementing a simple board game, as per the specifications stated below, using any (or more) of the data structures we have discussed in class so far (list, vector, balanced binary search trees (STL: set, map, multiset, multimap)) as appropriate.
Specifications:
A "board" is defined as a m * m square matrix, with each cell identified using a unique (x,y) coordinate. An example 10 * 10 board is shown in the figure below. In a game, a board has n players, where n ≤ m always. The figure shows an example for m=10 and n=8.
Your task is to implement the following specifications and functionalities:
- Write a Board class
that implements a board of size m *
m with n players. The value
of m is user specified (during class construction). At the start of the
game, all the m * m cells of the
board are empty (i.e., n=0). As
the game progresses n is allowed
to change.
Read the rest of the problem and understand the requirements before deciding on how to implement this class.
- Write a Player class
that implements each player. Each player object will have a unique,
positive integer ID, and at any given time the player will occupy a
unique (x,y) position on the
board. Care must be taken that the value of (x,y) position is always within bounds of the board at all
times. No two players are allowed to share the same cell.
- Implement an Insert
method in the Board class that will allow you to add a new player to the
board. The method should take as input the player ID to be inserted, along
with a desired (x,y) position
into which it is to be initially placed. For successful insertion, i) a
player with the same ID should not
already exist on the board; AND ii)
the specified insertion position on board should be currently
unoccupied. A third condition would be to ensure the total number of
players with this insertion (i.e., n) should not exceed m. If successful, the method should
update n and return true.
If insertion fails, the code should display an appropriate error message
and return false without
changing anything.
- Implement a Remove method
in the Board class that will allow you to remove a player from the board.
The method should take as input the player ID to be removed, and should
return true upon successful
removal and false otherwise
(i.e., player not found). The value of n
should also be accordingly updated. Note that upon successful
removal, the corresponding cell on the board should become available for
newer insertions.
- Implement a Find method
in the Board class that is given a player ID and returns true if the player is found and false otherwise.
- Implement a MoveTo method in the Board class that takes as input a player ID and a destination (x2,y2) cell position. The method should first locate the player, and move the player from its current position, say (x1,y1), to the new position (x2,y2) only if:
- (x2,y2) is within bounds, and
- the movement from (x1,y1) to (x2,y2) is always along the same row or same column or same diagonal in any direction (i.e., top-left -- right-bottom or top-right -- left-bottom).
Additional action is necessary if the destination cell (x2,y2) already has some other player, say Y. Then this function should first remove Y from the board before placing this player (ID) in its new position. Upon a successful move, the method should return true. If any player was removed in the process, the method should print a message to indicate which player was removed. If the move fails, the code should display an error message stating the reason of failure and return false.
Note: Any player(s) on the board along the path of moving from (x1,y1) to (x2,y2) is/are left unaffected by this move.
- Implement a PrintByID
method in the Board class that prints all the player IDs along with their (x,y) positions, in the increasing
order of their IDs. Again, the print should not display any unoccupied positions.
Design:
It is expected that you use balanced binary search trees for this project (set, map, multiset, multimap). However, you are free to pick other STL containers o appropriate. Your choice should be based on what is expected to give the “best” performance (both in terms of time and memory) assuming the following:
i) Although we will be testing for smaller values of n and m, your design should be optimized for the general use-case where the value of n is expected to be much smaller than the value of m. (For example, n=100, m=1,000,000). This simply implies that your code should not store the whole m*m board because it could run out of memory. Alternatively, think of storing only the occupied positions and the players.
ii) You can assume that the number of players sharing the same x-value is going to be a small constant.
iii) You can assume that for a given game, the value of m never changes. Of course the value of n could change dynamically as players are inserted and removed as the game progresses.
In trying to meet the above guidelines, you are permitted to maintain multiple data structures and/or copies of the same data in different containers as you deem necessary for design and efficiency. You are free to define new member functions not specified above to enhance code reuse and modularity.
Testing:
For testing, use the TestBoard.cpp code. This code is for the example board
shown above.
Save the output of your testing as a
text file and submit it as part of your report.
Written Report:
In a separate document (Word or PDF), compile the following sections:
· A: Problem statement. In a couple of sentences state the goal(s) of this exercise.
- B: Experimental setup. In this section, specify the machine architectural details where the testing was conducted. Also mention whether you used Windows or Unix or Mac OSX for your testing.
· C:Algorithm design (limit to 2 pages): Provide a design document for your code with the following information. State what data container(s) you used to support the different functions and why; what is the run-time complexity of each of the functions in your code; and what is the memory complexity for your implementation as a whole. Figures and illustrations can be used to show the design.
· D: Test results. Save the output of your testing using the TestBoard.cpp and attach it as a text file.
FINAL CHECKLIST FOR SUBMISSION:
___ Cover sheet
___ A separate folder containing all your sourcecode (including the main function you used for testing)
___ Report
___ Both the above zipped into another folder archivecalled Program3<YourLastName(s)>.zip