School of Engineering and Applied Science
Department of Computer Science
CSci 133 -- Algorithms and Data Structures I
http://www.seas.gwu.edu/~csci133/spring05
Prof. Michael B. Feldman
mfeldman@gwu.edu

Project #1

Due Date: beginning of class, Friday, Jan. 28, 2005
This project depends on Lewis/Loftus, especially Section 6.3

The purpose of this project is to refresh your memories of programming since you took CSci 53, and to give students who took different introductory courses a chance to get up to speed with Java. Start working on this now, so you have a chance to ask questions about anything you don't understand!

Before Starting:

You must complete the first laboratory exercise before starting work on this project, because in that lab you will set up the necessary directory structure to gain access to all the files and develop your own programs for this course.

The Project:

In this project you'll develop a program to do the data management for an adaptation of a very simple 1-person game called Stratagem. The original Stratagem was invented recently by Kristin Heckman, a GW graduate student who just completed her doctoral program and used this game as part of her dissertation in Artificial Intelligence.

Stratagem is played on a board with four rows and four columns. The rows and columns are number 0-3. There are thus 16 cells. At the start of the game, 15 cells are occupied by game pieces (like checkers); the empty cell is chosen randomly and can be any one of the 16. A typical initial game might look like this:


The Moves:

The player makes a valid move by moving a piece from an occupied cell to an empty one, subject to these constraints:
  1. The move can be horizontal (along a row) or vertical (along a column).
  2. Diagonal moves are not allowed.
  3. Each move must jump over one occupied cell; the piece in that cell is then removed from the board.
The goal of the game is to continue until no more valid moves are possible, and to remove as many pieces as possible.

Examples:

Let's specify a move by a pair of (row, column) coordinates that give the starting and jumped cells. Starting with the initial board above, ((2,0),(2,1)) is a valid move that lands on (2,1). The resulting board is (the piece that moved is indicated in a lighter shading):

Now which possible moves are valid? ((0,0),(1,0)) is one. So are ((0,1),(1,1)) and ((2,3),(2,2)). After ((0,1),(1,1)), the board is:


One more example: if (0,1) is initially unoccupied:


then the moves ((2,1),(1,1)) and then ((2,3), (2,2)) go as follows:

Representing the Game:

In this course we try not to get distracted by graphics issues, so we can focus on more fundamental subjects. So we'll represent Strategem using a simple text display, using the Screen class to position the cursor. The symbol ** means "occupied at the start of the game", the symbol -- means "vacant", and a number k means that a piece jumped there on move k. For the first move in the first example above, here's what the board looks like.

          0   1   2   3  

     0   **  **  **  ** 

     1   **  **  **  ** 

     2   --  --   1  ** 
    
     3   **  **  **  ** 


Move number 1:
From position (row first, then column) >2 0
Over position (row first, then column) >2 1

Valid and Invalid Moves:

In any good program, input data must be validated. In this game, an attempted move is invalid if:
A move is valid if it is not invalid!

Your Program:

Your program will read and process moves from the human user at the keyboard, continuing until the user presses Control-C. The main logic of the program is expressed in this pseudocode:

initialize game board
loop forever
{
  read a move from the keyboard
  if the move is invalid
  {
    write an error message
  }
  else
  {
    execute the move
  }
}

The file programs133/Stratagem.java contains a partial solution, that reads one move and executes it, using the mbf.Screen class to put the board in the center of the screen and display the moves. This is 161 lines long. Copy and compile this file and  use it as a starting point for your project. In your program, use the bottom few lines of the screen for data input and program messages.

Note that this partial program doesn't validate its inputs; your solution must do so. HINT: the most straightforward approach is to expand the "if" in the pseudocode into a series of "else if" blocks that test the invalidity conditions, like

if (move fails first condition)
{
  write message
}
else if (move fails second condition)
{
  write message
}
else if (move fails second condition)
{
  write message
}
. . .
else
{
  move is valid; execute it
}

You can run Prof. Feldman's solution by copying programs133/MBFStratagem.class into your csci133 directory and then executing it. You'll need to compile Screen first. Obviously Feldman's source code is not provided!

Feldman's program adds about 60 lines to Stratagem.java. Your added code is important but not long, so there is absolutely no reason why you can't deliver it by the deadline!

What to submit:

This first project doesn't require a full CSci 53 or 133 submission; it's just to get you started in the course. Accordingly, submit
  1. a printed listing (.txt) file of your program
  2. an e-mail message to Prof. Feldman and to Mohamed, containing your source code for the program, in case we wish to compile and run it. Do NOT send an attachment--instead, paste the source code into the text of the message. The e-mail must be sent before class on the due date; late submissions will be subject to the usual 20%-per-week "late fee".

Grading:

Grading for this first project will be 0-20 points: program correctness, 0-16; code style and layout, 0-4.