Read the FAQ for updates/corrections. Items that have changed from the previous version will be marked in red to make it easier to spot changes.

Project #1 Updates

You are expected to read updates on a daily basis.

Updates

Project #1 FAQ

Some of your questions may be answered here. Read it to see before sending email.

You are expected to read FAQ on a daily basis.

Project #1 FAQ

Your Responsibility

The project should be posted in its entirety very soon. However, there may be clarifications/corrections to the project. So, don't (repeat: DON'T) just print it out and ignore the webpage until you submit. You should frequently check the webpage to make sure you have the latest updates. We will try to make as few updates as possible, and correct any errors as soon as possible.

We suggest you look at the webpage sometime in the evening to see if any updates have occurred. Common student errors and their solutions are often posted in the FAQ (this will be up soon, once some questions are available). Contact your TA for questions, and they can forward it to the instructors if necessary.

Purpose

1. To learn when and when not to implement: copy constructor, assignment operator, and destructor.
2. To understand what an abstract data type is, in particular, a Sorted List.
3. To develop container classes: ItemSortedList and ItemArrayList using sorted doubly linked lists and dynamic arrays, respectively.
4. To write test drivers to test the classes you implement.
5. To learn how to write preconditions, postconditions, class invariants.
6. To learn how to plan/design classes.
7. To write classes with good programming and commenting style.
8. To write documentation for classes.

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

Checklist

Click here before submitting.

Project 1 Checklist

Overview

This project has many parts. Start on it soon.

Some students see the objective of programming as "get the project to work", and believe that getting it to work means writing as much code as possible. Planning code, testing code, and documenting code is seen as a hassle, something that is unimportant. Unfortunately, nothing could be further from the truth.

If you program for a living, you will eventually have to work in teams, and the code you write must be well thought out, otherwise, it will be hard to maintain, contain bugs, etc. Documentation is important because other people need to know what your code does, and you need to know what other people's code does. So, even if you believe it's "busy work", it serves a useful purpose.

This project consists of several exercises, which will be listed as tasks.

• Task 1 Style Exercise

  In previous courses, you have been told to write your code "with good style". You were told penalties would be assessed if you didn't write with good style. However, some people still have poorly indented code, inconsistent style, that not only makes code look unprofessional, but also hard to read and debug.

• Task 2 String Tokenizer

  You will implement a class called Tokenizer. You are provided a file called Tokenizer.h. Implement the methods.

  All methods in this file are static.

• Task 3 Queue

  You will implment a queue class called MovieQueue. You are provided a file called MovieQueue.h, Movie.h and Movie.cpp. The Movie class should be implemented for you.

  You will also implement a unit testing class called MovieQueueUnit to test MovieQueue. The queue is implemented as a linked list. You may wish to read the text on queues, if you are unfamiliar with them.

  The purpose of this task is twofold: first, to get you practice writing a queue (this is a good warmup for writing a linked list). Second, to learn how to write test code prior to implementing the class. This idea is used in XP (extreme programming). Read the full description by clicking on the link above.

• Task 4 Documentation

  You should document the following files: ItemArrayList and ItemSortedList. The documentation is specified in the links above.

  (9/18) You do not need to write documentation for classes in Tasks 1, 2, 3. Notice that documentation and commenting code are NOT the same. Documentation appears in .dcmt files and are just plain text. Commenting appears in your .cpp files.

  Here's another useful link that pertains to documenation:

  • Preconditions, Postconditions, Design by Contract

  Read the next task before starting this one.

• Task 5 Specifications

  You need to implement the following classes: Item, ItemArrayList, ItemSortedList, plus any nested classes. The specifications are above.

  The following link is a review of singly linked lists (SLL).

  • Review of SLL

  The following link to nested classes is NOW READY.

  • Nested Classes

  The following link for converting numbers to strings might be useful to you. (NEW: 9/21)

  • Converting Numbers to Strings

  (9/18) You should implement ItemSortedListUnit as well (the unit testing class for ItemSortedList). Implement at least 5 test methods. It's optional to write this for other classes, but consider it, if you find the idea useful.

• Task 6 Main project

  This is an live version of Task 6. This means it has been looked over some more, and is pretty much the way it's going to be (short of overlooked bugs). You may begin to email clarifications and/or bugs in the description.

Files Provided

In addition to the primary input and primary output, the following files are in the posting account under Projects/P1.

• Movie.h
• Tokenizer.h
• Item.h
• ItemArrayList.h
• ItemSortedList.h
• MovieQueue.h
• MovieQueueUnit.h
• StyleExercise.cpp

The following are secondary files. You do NOT implement these (they are used for Task 3).

• Assert.h
• AssertException.h
• TestCase.h
• TestSuite.h

Files Submitted

(9/26) Please read the Checklist instead.

Project Description

You will implement a variation on the game called Sokoban (do a "google" search, and you can see how to play this game). Here are the rules of the game.

1. The game is played on a 10x10 board.
2. The coordinates of the board are written as (row,col). Thus, (2, 3) is row 2 and column 3.
3. (0,0) is the northwest corner. (9,9) is the southeast corner.
4. There is one player on the board.
5. Each position on the board consists of exactly one of the following:
   • a box
   • a food item (doughnut, coffee, pickle, etc.)
   • the player
   • a wall
   • empty
   Each of these are located at some valid coordinate on the board.
6. Each food item has a name. The name consists of alphanumeric characters, and may have upper or lowercase characters, possibly in combination.
7. Initially, your program will read in information (through input redirection). The following information will be provided in the redirected input.
   • the coordinate of each box You may assume these are in valid coordinates, and that no two boxes are placed in the same coordinates)
   • the coordinate and name of each food item You may assume these are in valid locations, not occupied by a box, and that no two food items are located at the same coordinate).
   • the coordinate of walls (think of walls as boxes that can't be moved). Again, the walls are at valid coordinates and do not overlap food items, nor boxes.
   • the coordinate of the player You may assume the player is at a valid coordinate, which is not occupied by a box, wall, or food item.
   • a list of commands The commands will be described below.

8. There are two kinds of walls: interior walls which are the ones provided in the input to your program, and outer walls which is the wall surrounding the 10 by 10 grid (immediately to its north, west, south, and east). The outer walls are NOT inside the 10 by 10 grid. They are not part of the input file, and are always there, regardless of the input file.
9. A player can "push" a box. For example, suppose the player is located at (4,0) and a box is located at (3,0). If a player moves north 1 unit, then the player pushes a box (since the box is located at a position where the player wishes to move). After the move, the player is at coordinate (3,0), while the box has been moved to (2,0).
10. To push a box, the player must be adjacent to the box and walking in that direction. Thus, a player moving north can only push a box that is one unit north of the player. If a player is at (4,0) and the box is at (2,0), and the player moves north 1 unit, then the box isn't pushed (the player successfully moves to (3,0)).
11. The box can only move in the direction the player is moving.
12. The player can only move: north, east, west, south. The player can not move diagonally.
13. There are restrictions to moving boxes. The player can not move two boxes in a row. For example, if there is a box at (2,0) and (3,0) and the player is at (4,0), and attempts to move north, nothing will happen. Normally, the box at (3,0) can be moved north to (2,0) but another box is already located there.
14. A box can not be moved off the playing board (there's a wall around the entire 10x10 board, not represented in the input file).
15. A box can't not be moved through a wall. Thus, if there is a box at (3,0) and a wall at (2,0) and the player is at (4,0) trying to move north one unit, it will be unsuccessful. The wall blocks the box.
16. If a player is moving a box, and there is a food item in the way, the box will crush the food item, and the food item no longer exists. Thus, if there is a box at (3,0) and a doughnut (which is a food item) at (2,0) and the player is at (4,0) trying to move north one unit, the move is successful The box will move to (2,0) and crush the doughnut. The player will be at (3,0).
17. Once a food item is crushed, it is no longer on the board.
18. If a player walks over a food item, the player automatically picks up the food item, and the item is no longer on the board.
19. Unlike the real "Sokoban", there is no "target coordinate". Normally, the game is played by attempting to move boxes to a target coordinate. The game is completed when all boxes are successfully on some target coordinate. However, this is a multi-part project, so you may wish to think about how you will incorporate this feature for the next project.

Commands

The following are a list of commands you must implement. These commands will appear as part of the input to your program.

For each command, you should print out the command as follows:

 <out> := "(" <count> ") [" <cmmd> "]" <endl>
  <count> := <udigits>

where <cmmd> is any one of the commands listed in the next section, and <count> is the count of the command number, which begins numbering at 1.

This will be called the command echo.

You may assume:

• Each complete command lies on one line.
• All commands are valid.
• There may be blank lines (lines consisting of 0 or more blanks ending in a newline) without any commands.. They should be ignored, and NOT count as a command.

However,

• The spacing on the command may be arbitrary.
• The commands may be in upper or lowercase (or a combination of upper and lower case).
• When you print the command out, they should have only one blank separating each "word" even if the original had multiple blanks.
• There should be NO blanks immediately after the "[" or immediately before the "]"
  (e.g., it should look like "[MOVE N 3])". Notice no blanks appear between the left bracket and the command, MOVE, nor between the 3 and the right bracket.
• You should preserve the same capitalization as read in from the input. So, if the input were "MoVE n 3", you should print [MoVE n 3].

List of Commands

• MOVE

  This is the BNF (where % is short for zero or more blanks and %% is short for one or more blanks). Read the EBNF on the tutorial webpage for more information.

  <cmmd1> := % MOVE %% <direction> %% <units> % <endl>
    <direction> := [ "N" | "W" | "S" | "E" | "n" | "w" | "s" | "e" ]
    <unit> := <udigits>
  

  You can move in one of four directions, "N" is north, "W" is west, "E" is east, "S" is south. The units are integer values. You can assume that they number is positive. The directions can be in lower-case too.

  There are a variety of messages that can occur once the move is complete.

  • Case 1: Player successfully moves and encounters no obstacles

    After printing the command echo, print:

       <out1> := "Player successfully moves " <units> " units " 
                    [ "EAST" | "WEST" | "NORTH" | "SOUTH" ] <endl>
                    "Player is currently at " <coord> <endl>
      <coord> := "("  <udigits> "," udigits> ")"
    

    Note: <coord> will be used often in later BNF.

  • Case 2: Player successfully moves, and moves either a box and/or picks up food items and/or crushes food item.

    The output is printed in the following order, AFTER the player has completed the move in a particular direction.

    • Prints player has successfully moved.
    • Prints the location of the box (starting and ending coordinate).
    • Prints any items picked up. (One output line per item, in the order the item(s) was/were picked up).
    • Prints any items crushed. (One output line per item, in the order the item(s) was/were crushed).
    • Prints coordinate of the player after the move.

    Here's the BNF.

       <out1> := "Player successfully moves " <units> " units "
                 [ "EAST" | "WEST" | "NORTH" | "SOUTH" ] <endl>
                 [ "Box is moved from " <coord> " to "
                    <coord> <endl> ]?
                 [ "Player picks up [" <name-of-item> "] at "
                    <coord> <endl> ]*
                 [ "Box crushed [" <name-of-item> "] at "
                    <coord> <endl> ]*
                 "Player is currently at " <coord> <endl>
       <name-of-item> := <word>
    

    Some notes:

    • If there is no box, then don't print messages related to boxes.
    • If no items are picked up, then don't print messages related to picking up items.
    • If no items are crushed, then don't print messages related to items being crushed.
    • If there's more than one item, print one line per item picked up.
    • If there's more than one item crushed, print one line per item crushed.

  • Case 3: Player unsuccessfully moves the entire distance.

    Suppose a player is attempting to move NORTH 8 units. This may not completely succeed. A player may only successfully move part of the distance.

    There are several reasons this may happen:

    • Player is (eventually) blocked by a wall.
    • Player is pushing a box that is (eventually) blocked by another box.
    • Player is pushing a box that is (eventually) blocked by a wall.

    In the process, the player may pick up or crush items.

    The output is printed in the following order.

    • Prints how far player has moved.
    • Print why player has unsuccessfully moved (one of the three reasons above).
    • Prints the location of the box (starting and ending coordinate).
    • Prints any items picked up. (One output line per item, in the order the item was picked up).
    • Prints any items crushed. (One output line per item, in the order the item was crushed).
    • Prints coordinate of the player.

     <out1a> := "Player ONLY moves " <units> " of " <units> " units "
                     [ "EAST" | "WEST" | "NORTH" | "SOUTH" ] <endl>
                 [ "Player is blocked by " 
                    [ "outer wall" | "wall at " <coord> ] <endl> |
                    "Box at " <coord> " is blocked by box at "
                       <coord> <endl> |
                    "Box at " <coord> " is blocked by "
                       [ "outer wall" | "wall at " <coord> ] <endl> ]
                 [ "Box is moved from " <coord> " to " <coord> <endl> ]?
                 [ "Player picks up [" <name-of-item> "] at " <coord> <endl> ]*
                 [ "Box crushed [" <name-of-item> "] at " <coord> <endl> ]*
                 "Player is currently at " <coord> <endl>
    

    Some notes:
    • The first error message indicate that the player is being blocked from further movement by a wall. If it's an outer wall, do not print the coordinates. If it's an interior wall, print the coordinates of the part of the wall that's blocking the player (the player will be one unit away from this coordinate).
    • The second error message indicates where the last valid coordinate of the box that was moved, followed by the coordinate of the box which prevented the first box from continuing its movement.
    • The third error message is printed if the box being moved is blocked by a wall (either an outer wall or an interior wall). As before, print the coordinates only if it's an interior wall.
    Only one of the three errors should print (if an error has occurred).

• DISPLAY

  This takes no arguments. After printing the command echo, you should print the current configuration of the board. The board should be printed using the following symbols.

  • A period (".") if the location is blank.
  • A "P" to indicate the player.
  • A "@" to indicate a box.
  • A "#" to indicate a wall.
  • A lowercase alphabetic letter to represent the item. 'a' should represent the item that is first in the ItemSortedList, 'b' should represent the item that's second, 'c' for the third, and so forth. (You can therefore assume there are no more than 26 food items).

  You should print a blank space between each pair of symbols. Thus, there should be 20 characters per line (10 characters to represent the items on the board, plus 9 blanks, plus a newline to signify the end of line).

  This is the BNF.

     <display> := [ <line> ]{10,10} <endl> [ <more> ]?
     <line> := <char> [ <blank> <char> ]{9,9} <endl>
     <char> := "." | "P" | "#" | "@" | <lower>
  

  If there are food items on the board

  After you print the board, if there are items on the board, print a blank line, then, print out the "Legend". This prints what each item is. This is the BNF for that. Notice there are 6 dashes (same number of characters as "Legend").

     <more> := "Legend" <endl> "------" <endl> 
                 <list-items>
     <list-items> := [ <one-item> ]+
     <one-item>   := "(" <lower> ") [" <name-of-item> "] " 
                       <udigits> " pts"  <endl>
  

  So, print the letter of the item in parentheses (starting with "a", "b", "c", etc.), followed by a space, followed by a left bracket, then the item name, then a close bracket, then the number of points the item is worth, then "pts", and finally a newline.

  The list should print out in alphabetical order. This should be case-insensitive. You may assume the items have one word names that may be written in any combination of upper or lowercase letters and digits.

  If there are NO food items on the board

  Print the map, but don't print the legend.

  Use iterators

  Use iterators to print the list forward through an ItemSortedList.

• DISPLAY_BACKWARD

  Similar to DISPLAY. Print the board as before, but this time, print the legend backwards. Thus, if there were five food items on the board, you should label them (e), (d), (c), (b), (a).

  Use iterators in the reverse direction to print backwards.

• SHOW_FOOD

  This displays the food items that the player has picked up so far. This MUST be displayed in the order that the player picked up the food item. Recall that as the player walks over a coordinate with a food item, it is picked up by the player (there is no command to pick items, so this is done when player does MOVE over a food item), and the player stores that information.

  After printing the command echo, print the following:

     <show-food> := "Food items" <endl>
                        "----*----*"  <endl>
                         [ <food-list> | <no-food> ]
                         <endl> <total-points>
     <no-food>    := "Player is not carrying any food items" <endl>
     <food-items> := [ <food> ]+
     <food>       := "(" <udigits> ") [" <name-of-item> "]" <udigits> " pts" <endl>
     <total-points> := "The player has (" <udigits> ") total pts"
  

  Note: there are 4 dashes and a star, followed by 4 dashes and a star.

  If the player is not carrying any food items, then print the <no-food> message. If the player is carrying food items, then print out the number (starting at 1), in parentheses, followed by a space, followed by a left bracket, the food item, followed by a right bracket, then a newline.

  After the list of food items, print the total points of all food items (sum them up) that the player is carrying.

  Note: the food items must be printed in the order they were picked up.

• QUIT

  This command has no arguments.

  After printing the command echo, you should print the following:

    <quit> := "Exiting program.  Thanks for playing!" <endl>
  

  You should not accept any further commands (i.e., ignore the rest of the input).

Input file format

The format of the input file looks like:

<all> := <boxes> <walls> <food-list> <player> <cmmds> 

<boxes> :=  % "<box>" % <endl>
              [ % <coord> [ %% <coord> ]* % <endl> ]*
              % "</box>" % <endl>

<walls> :=  % "<wall>" % <endl>
              [ % <coord> [ %% <coord> ]* % <endl> ]*
              % "</wall>" % <endl>

<food-list> :=  % "<food>" % <endl>
                 [ % <one-food-item> ]*
                 % "</food>" % <endl>
<one-food-item> := % <food-name> %% <points> %% <coord> % <endl>
<food-name> := <word>
<points>    := <udigits>

<player> :=  % "<player>" % <endl>
             % <coord> % <endl>
             % "</player>" % <endl>

<cmmds> :=  % "<command>" % <endl>
                [ % "MOVE" %% <dir> %% <udigits> % <endl> |
                  % "DISPLAY" % <endl> |
                  % "DISPLAY_BACKWARD" % <endl> |
                  % "SHOW_FOOD" % <endl> |
                  % "QUIT" % <endl> ]*
            % "</command>" % <endl>

The BNF doesn't clearly show the following, but they do apply.

• There may be blank lines in the input, which should be ignored. Blank lines are defined as 0 or more spaces ending in a newline.
• The commands and name of the food items can be a mix of upper and lower case (plus, possibly digits). You should handle this by being case-INSENSITIVE.

Assumptions

• You may assume boxes, the player, food items, and walls are on valid locations on the board.
• You may assume the player will move in non-negative units.
• You may assume the commands are valid, i.e., they have the correct name, number of arguments, and type.
• You may assume there is a QUIT command somewhere in the list of commands.
• (9/28) Food items appear with unique names. No two food items will have the same name (even when you ignore case).

Requirements/Restrictions

• You must use ItemArrayList to hold the food items picked up by a player. (REQ1)
• You must use ItemSortedList to hold the food items on the board. (REQ2)
• You must use iterators to print the food items, in the ItemSortedList. (REQ3)
• ItemSortedList must be a doubly linked list. (REQ4)
• ItemArrayList must be a dynamic array. (REQ5)
• You may not use STL vectors, etc. to substitute for ItemSortedList or ItemArrayList.
• You must write at least ONE class that's not specified.

For each of the REQ, put a comment in the code and/or header file where you have met these requirements. For example, you would write // REQ1. This way, the graders can easily find where you have met the requirements. If these are missing, we may deduct points, even if you have met the requirements.

Writing Classes

This project may require that you write your own classes. You should pick sensible classes, and you can write as many or as few as you want.

Here are some requirements/restrictions:

• Each file must use the following naming convention. <name>.mine.cpp where <name> is the name of the class. Thus, if you create a class called Foo, you should name the file Foo.mine.cpp and Foo.mine.h.

• Each file must have documentation, e.g. Foo.mine.dcmt. You can leave out preconditions, postconditions, efficiency, etc. The description can be fairly brief per method. Ideally, someone reading your documentation can tell what the code does.

  At the top of the file, after your name, etc. Explain why you felt you needed this class.

• If you wish to submit a Unit test class, you can do so. Label it something like: FooUnit.mine.cpp and FooUnit.mine.h. You won't be graded on it, however. (It might earn a little extra credit, but no guarantees).

• No public data members. They must be private.

• No global variables.

• Try using const whenever possible.

• Write copy constructors/destructor/assignment operator only if you have to (i.e. implicit versions are inadequate).

• The classes should be SENSIBLE. The purpose of writing a class is NOT to just get the whole project to work, but to write a reasonable class that someone, in principle, could reuse. Even if they couldn't, an experienced person would say "That's a well-designed class" rather than "you just wrote the bare minimum, because you were trying to get the project done".

• Keep in mind that the project continues on, and while it may not be obvious you need a class now, you may need classes later on. So, decide if you would rather spend that time now.

• Do not create your own template classes nor use inheritance.

• Do not alter methods in ItemArrayList, ItemSortedList to complete the project. In reality, if you had someone else's classes, you would have to deal with whatever problems it had.

You may feel free to use whatever string methods or vector methods you can find in the book, etc., unless it is not in the spirit of the project (e.g., don't use vectors, when you are asked to use a ItemSortedList).

Where We Might Be Headed

Two things to think about. Board size and target squares for boxes (to make it behave more like Sokoban).

How to Submit Your Project

In order to successfully submit your project, it must pass the primary input and produce the primary output. The primary input will be sent to your project using input redirection.

   p1 < primary.input

Your program MUST produce the executable p1, EXACTLY, when the command "make" is run with no arguments. Thus, you must use a makefile named exactly "Makefile".

We will use "diff -bwi" to test your code. This ignores case, treats N blanks as 1 blank, treats N blank lines as 1 blank line. We will also strip all blank lines from your input when matching to ours. However, diff is sensitive to punctuation, number of dashes, etc. so you should attempt to make your output match ours as closely as possible otherwise you may not be able to submit your program. If this is the case (that your program does not submit) you must fix your code until the output it produces matches that of the primary output. Note: "hardcoding" output is a violation of the University's Code of Academic Integrity.

To submit your project you must first combine the following files (and only these files) into a single tar file using the Unix tar command:

You may name your tarfile anything you want, but p1.tar is the suggested name.

NOTE! You should make a backup copy of all your files BEFORE attempting to create your tarfile!!!! You have been warned.

After creating the tar file you should submit that one file using the following command:

submit p1.tar 1

where p1.tar can be replaced by whichever tar file you have created, and 1 refers to the current project,

See the class syllabus for policies concerning email Last Modified: Tue Feb 12 19:48:57 EST 2002