Preliminary Material

Project 3 is worth 8% of your grade.

In order to pass this course, you must submit this project. The last possible date for submission is May 5, 2004. See the syllabus for details.

In the previous project, you coded the first level for the game ,EENVG, "Extremely Exciting Non_ Violent Game" (pronounced N-VIG). This project stores the possible moves of the Robot in a binary search tree (BST) instead of in a circular doubly linked list. The Stalker does not change.

The game also becomes more interesting by including another level to the board. If on the first board, the Robot has accumulated enough points (points >= the number in primary.input) she advances to a new board.

In addition to the previous rules, we must add:

• If the Robot accumulates the specified number of points, she begins play on the 2nd board.
• the Robot is placed in the same position as her last position on the previous board; if she was at [0,2] when the first game ended, she will be placed in cell [0,2] on the second board (even if the board size changes.)
• the Stalker is placed in the same position as its last position on the previous board; if he was at [1,2] when the first game ended, he will be placed in cell [1,2] on the second board (even if the board size changes.)
• On board2, the Robot's initial points are her previous point count. If she earned 17 points on board1, she begins with 17 points on board2 and adds to this count.
• primary.input contains the number of points the game will be played to for board1 and board2. They are respectively 10 and 20 for purposes of submitting your project.
• The size of board2 may be different from the size of board1. If so, it will be larger.
• The Robot may not land on the Stalker
• The game ends if the BST has moves, but none are valid. See FAQ.
• Old rules:
• The Robot is represented by the number 9
• The Stalker is represented by the number 8
• The Stalker moves AFTER the Robot
• In each round of play, the Robot moves and then the Stalker moves.
• The Robot should always make the "best" move - the cell with the most points that it can reach (based upon Pairs in the BST). The sooner the Robot accumulates enough points and ends the game, the better. If there are more than 1 move with the same number of "most" points, the first movewith the "most" points encountered in an inorder traversal of the BST is selected as the Robot's move.
• If the Robot lands upon a cell with negative points, it loses those points. These are stumbling blocks. The positive values on the board are treasures.
• The game is over when
• the Robot's points equal or exceed the value in primary.input.
• the Robot lands on the Stalker (Robot's points will be 0)
• the Stalker lands on the Robot (Robot's points will be 0)
• the Robot runs out of moves - there may be moves in the BST but none are reachable from the Robot's current position.
• The game continues if the Stalker runs out of moves. In this case, the Stalker remains on the last cell it moved to before running out of moves.
• After the Robot leaves a cell, the points in that cell are set to 0 (zero)
• After the Stalker leaves a cell, the points in that cell are set to 0 (zero) unless they were negative before the Stalker landed there. In this case, the original negative value is restored to that cell when the Stalker moves on.

Purpose

This project implements the STL vector class as well as a binary search tree. The goals of this project are to:

1. Understand and implement a binary search tree.
2. Understand templates.
3. Manipulate interacting classes Board, Robot and Stalker.
4. Understand and implement a logic puzzle

Academic Integrity Statement

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Style Guide

Students are expected to write "clear and legible" code. Please review the following Style Guide which specifies how students in CMSC 214 are expected to lay out their code:

http://www.cs.umd.edu/class/spring2003/cmsc214/Projects/styleguide.txt

FAQ

Answers to "frequently asked questions" will be posted via the main projects page. Prior to asking a question or submitting a project you should check the FAQ to see if any important information has been covered there. In addition to answers to FAQ's any important information pertaining to a project will be posted on it's FAQ.

E-mailing Questions

DON'T email questions. We cannot keep up with the numerous emails about a project. GO SEE A TA or an instructor during office hours. We will generally NOT respond to email questions about the project.

Project Overview

For this project you will be required, among other things, to write the code for 1 new class and modify several classes already written:

class 1: Bst

• This class replaces the Moves class
• This class is templatized on Pair because Node is templatized on Pair.
• The binary seach tree stores the Pairs of moves
• The moves for board1 will be in "moves.dat"
• The moves for board2 will be in "moves2.dat"
• The BST will have more moves than are needed.
• Your implementation of erase() must be one of the following:
• easy right pullup
• easy left pullup
• right subtree successor
• left subtree predecessor
• You must implement preorder, inorder and postorder traversals but the printing of the list will use an inorder traversal.

class 2: Robot

• Robot is templatized on Pair (the type in Bst)
• Robot is contained in the Board class
• Robot now contains Bst<T> move instead of Moves<T> move
• The Robot's moves are now contained in a BST
• the Moves.h and Moves.cpp are not needed in the project.
• the moves are in Bst.h and Bst.cpp
• Robot's initial position on the board is in "robot.dat"

class 3: Stalker

• moves about the board sucking up treasures (+ points)
• it leaves stumbling blocks (- points) unchanged when it moves off of a cell with a negative value
• its moves are stored in a vector
• all moves for the Stalker will be valid moves on the board.
• Stalker's initial position on the board is in "stalker.dat"
• Stalker's moves are in "smoves.dat" (board1) and in "smoves2.dat" (board2)

class 4: Mpair

• a pair of integers indicating the coordinates of a board cell
• for coordinate [r,c], r indicates the row position and c indicaties the column position
• each row and column begins at 0
• has changed from project 2

class 5: Board

• Board is templatized on the contents of the board ("int" in this case) and the Robot's generic type (Pair)
• Has changed from project 2
• input to the board will be in "board.dat" for board1 and "board2.dat" for board2

class 6: Except

• exceptions that occur in the above classes
• 2 are provided, do not change these
• 3 were written by you for project 1
• 3 were written by you for project 2
• write 3 other exceptions that could occur in your classes
• you may leave the exceptions (if any) that you wrote for Moves
• you need a total of 11 exceptions
• Note: exceptions must be thrown in the function in which they occur, but they are NOT caught there. They are caught in main or in the function which calls the function containing the exception.

class 7: Node

• Node is templatized on Pair
• has changed from project 2

class 8: Pair

• has changed from project 2

In the class posting accounts (~bt214001) you can find the header
files, data files, and main.cpp for the classes. The following rules
MUST be adhered to:

• No public functions or (public, protected, or private data members) may be added to the header files.
• Your output must match our output, an example of which is provided in primary.output
• You may not change the input - as provided in primary.input
• Projects submitted after 2 days late but prior to May 5, 2004 at 11PM will receive a grade of 10 out of 100 points.

After copying the header files into your account you should create the corresponding Pair.cpp, Node.cpp, Bst.cpp, Mpair.cpp, Board.cpp, Except.cpp, Robot.cpp and Stalker.cpp files. You will write the code that implements the member functions for these classes.

Note: you may NOT change the public methods in the header files but may add private methods as needed. You may NOT add private, public or protected data members to any class other than Except.h.

You must add public methods to Except.h only. However, do not change the public methods provided to you. You will add 3 more exceptions to Except.h and Except.cpp.

In each header file you will find the class with it's data member(s) and member function(s). There is a comment before/around each member function describing what it should do. You are to implement (i.e. write the code for) the member functions ABOVE the line

    // YOU MAY PUT ANY PRIVATE METHODS HERE

so that it does what the comment states that it should do and nothing more.

Next you should write 7 unit test files to test each of your classes:

• testBoard.cpp
• testBst.cpp
• testMpair.cpp
• testNode.cpp
• testPair.cpp
• testRobot.cpp
• testStalker.cpp

A unit test file should be a main() for a particular class that calls and tests each public method. It also tests the private methods which are called from public methods. Note that when developing/writing code you should do so in parts/modules and test each as you create it (keeping backup copies!). So for example, when writing Node, you also write a testNode.cpp that is the main() for Node.cpp. It should call all public functions and include appropriate output to test that all Node.cpp code works correctly.

And finally you should test your project with the main provided:

main.cpp

Add your own catch clauses to this file. We will run your main but it must diff down to and including the 2 catch clauses that were written for you for exceptions we provided.

It is expected that your output will match our primary.output exactly

Assumptions

You may assume that

• All input will be read from a file. For example, moves.dat will hold the allowable Robot's moves for board1. It will contain more moves than you will/can use.
moves2.dat will hold the allowable Robot's moves for board2. It will contain more moves than you will/can use. board.dat will hold the dimensions and values for the cells in board1. board2.dat will hold the dimensions and values for the cells in board2. smoves.dat will hold the moves for the Stalker for board1, all of which will be valid moves. smoves2.dat will hold the moves for the Stalker for board2, all of which will be valid moves.
• There may be multiple lines in any file.
• The input will not be empty. Each non-empty line will be followed by a newline (carriage return).
• Your program may be tested using an empty file.
• Each file will contain an EOF marker on the last line.
• "moves.dat" and "moves2.dat" may contain upper/lower case letters and white space, as well as digits.
• all other input files, including primary.input will contain integers only
• for purposes of submitting your program, sizes of boards 1 and 2 will be as specified in "board.dat" and "board2.dat"
• the size of the board may change in subsequent tests for project 3
• the board will always be a perfect square (nXn)

Hints

As soon as the test files are posted for Project 2, go back over project 2 and correct code that failed our tests or was inefficient or incomplete.

Start immediately. A binary search tree is a more complex data structure than your last one (cdll). The erase() function will take some time to code and test. You also have another level of play.

Although Node.h might look the same as in Project 2, it has some subtle differences. Copy the new version and see what has changed.

It might be to your advantage to get the BST working before you change Robot and the other classes that depend upon it.

You should get board1 working before you tackle board2.

If you work on your class account, tar up your files every day and email them to your wam account. You can always work on the project on the g++ compiler on wam if the detective cluster goes down or is slow.

Sample I/O

You may assume:

• There are no blank lines in the input file.
• Each line terminates with a carriage return.
• The last line contains an EOF marker.

A primary input file and a primary output file are provided in the class posting accounts (in the appropriate directory). You should review these files. They will be named primary.input and primary.output respectively.

Your project will successfully submit if it passes the primary.input.

Your program should generate the corresponding output similar to
primary.output. Additionally, we will test several methods from your code.

When your main program is compiled and run with input redirected so that it gets the contents of the primary input file (primary.input) as input, it should generate output that matches the primary output file. When we test your program we will diff your output (using diff -bwi) with that of the primary output and if it does not match, your program will be considered to not meet the minimum running standards and you will be unable to submit it.

Passing primary does not guarantee a passing grade (70 or above) for your project. Testing your program thoroughly helps.

How to Submit

Provide a makefile that creates an executable file named p3 when the command make p3 is run.

Tar up all necessary files, such as source code, including:

• all .cpp files
• all .h files
• your makefile

submit p3.tar 3

Submit will start accepting project 2 submissions on or about 03/27/04.

See the class syllabus for policies concerning email Last Modified: March 8, 2004

Web Accessibility