Overview

Suppose we are trying to find a way to navigate a maze, one of Dan’s devious puzzles. There is a designated starting chamber, where one must find (if it exists) a path from the start chamber to the exit (end chamber).  Each chamber is either solid or not (a wall).  For example, in the maze pictured below, the start chamber is coloured green and the end chamber is coloured yellow, walls (solid areas we cannot travel) are black and chambers we can enter are white, where on the right a path is shown to escape the maze. Can we help somebody from the clutches of Dan’s dastardly plot, the capturing of us all in overly simplistically designed mazes?

This is where you come in, unfortunately, we need a data structure for exploring this maze. To find the exit (if it exists) in the maze, we will use a stack. You will in C++:

❼ Program a linked-list implementation of a stack.

❼ Use your stack to solve maze puzzles you can design!

The specifications of the assignment start on Page 2.  You are provided several classes and eventually a program for solving mazes, that will be used to partially grade your assignment.

Learning Objectives

❼ Implement an ADT, from an interface in C++ (abstract class).

❼ Implement a stack in C++, from a specification.

❼ Understanding code provided, where student code is part of a larger program.

Classes to Implement, Other Details

In this assignment you must implement two classes, TileNode and LinkedStack, your code will be contained in files you will create called TileNode.cpp and LinkedStack.cpp, respectively. You will be provided header files for all classes, including those you must implement. You must write all the code for the two classes yourself.  Our LinkedStack class is implementing StackADT (an interface for a stack that consists of Tile pointers which will be used to navigate the maze). In addition to implementing the two classes, you will design two custom mazes, based on your understanding of the maze solving program.

I will expect you to know how to compile C++ programs and understand C++. Please compile your code using g++. Presume input data being fed to the program indeed matches the parameters of methods.

The next three sections outline how to carry out the three goals.

Class TileNode

You will be implementing a node for our linked-list based stack (which underlying it is a linked list), as per the specifications given in TileNode.h.  The instance variables of class TileNode are a pointer to a Tile object (, as it is a pointer, it may be null✯.), data, and a pointer to the next TileNode in the underlying linked list, next.  You are not to modify the code of TileNode.h. Nodes will have the following private attributes (as given by TileNode.h):

The constructor for your class should take the provided Tile pointer variable and set it to data (which is provided as input to the constructor), and set the next attribute of the TileNode to null. Then this class, you must also implement all the following public methods:

1. Tile* TileNode::getData(): Return the data attribute in the node.

2. TileNode* TileNode::getNext()): Return the next node of the linked list.

3. void TileNode::setData(Tile* newData): Update the data attribute in the node to newData.

4. void TileNode::setNext(TileNode* newNext): Update the next attribute to newNext.

Class LinkedStack

The next class you will be implementing is the linked-list based stack itself, it is similar to the implementation we described in class.   This class is implementing the interface provided called StackADT. The elements in our linked list are pointers to Tile objects. To maintain the stack, each push will insert a new node containing the element at the start/beginning of the linked list (the head of the linked list, at top), and each pop operation will remove the node at the head of the linked list, returning its data. The LinkedStack has two private attributes:

❼ TileNode* top – A pointer to the head of the linked list, the top of the stack. ❼  int  count – The number of elements in the stack.

You are not to modify the code of LinkedStack.h. For the LinkedStack class, you must implement all the following public methods:

1. LinkedStack::LinkedStack(): A default constructor, here you will initialize the head node called top to null and the number of elements, count, is set to zero.

2. LinkedStack::∼LinkedStack(): The deconstructor for the linked list, which is responsible for de-allocating for memory dynamically allocated using the new keyword. Create a pointer variable  (TileNode*) that is assigned top, then traverse the linked list, from top to the end of the linked list, deleting each successive node using the delete keyword. You are not responsible for deleting the Tile pointed to by the data attribute, it will be assumed that upon removing data from the stack, those elements will be deleted by the user.

3. void LinkedStack::push(Tile*  elem):  Create a new TileNode whose data is a Tile* named elem (the input) and insert this node at the head of the linked list (i.e. the beginning of the linked list).  Make sure to update the number of elements in the stack appropriately, and when you update the linked list that the insertion is performed correctly.

4. Tile* LinkedStack::pop(): Remove and return element at the top of the stack. As this is a linked list, this means performing a removal of a node at the head of the linked list. If the stack is empty, return null.  Make sure to update the number of elements in the stack, and to delete the node (, only the node itself, not any of the data its contents are pointing to,) removed from the linked list (, and the linked list is correctly updated).

5. Tile* LinkedStack::peek():  Return the element at the top of the stack.  Do not remove this element (or its node) from the linked list. If the stack is empty, return null.

6.  int LinkedStack::size(): Return the size of the stack, the number of elements it contains.

7. bool LinkedStack::isEmpty():  Are there any elements in our stack?   False if yes, true otherwise.

Make sure to #include any header files of classes used in LinkedStack.cpp so that compiles.

Custom Mazes!

You will be tasked with designing a couple custom mazes for that dastardly Dan! You are provided six mazes, some will have a solution, others may not.  For each maze file, it has a specific format (that must be followed, the MazeSolver program does not handle exceptions for File I/O). Each maze is created as a text file (.txt), and has two parts:

1. A dimension for the maze d, the maze is a d × d grid of chambers/tiles. Provide a number on the first line of your file.

2. Then, the design of the maze puzzle is provided (which will be d symbols on each line, for d lines). The following symbols are used to encode the maze:

❼ O - empty tile, one can freely move on an empty tile (it is a capital O, not zero).  Note

that empty tiles can be placed on the outermost perimeter of the maze, they do not need to be enclosed.

❼ X - solid/wall tile, we cannot enter/leave such chambers/tiles.

❼ S - start tile, this is where the explorer of the maze begins (there is only one such tile, it

should exist).

❼ E - end tile, this is the exit/end of the maze (there is only one such tile, if it exists).

For example, below is maze1.txt:

11

XXXXXXSXXXX

XOXOOOOXOOX

XOOOXXOOOXX

XOXOOOXOXOX

XOXXXOXOOOX

XOOOXOXOXOX

XXXXXOXOXXX

XOOOOXXOOOX

XXOXOXXXXOX

EOOXOOOOOOX

XXXXXXXXXXX

Study the MazeSolver program, in particular the main function which contains the maze solving algorithm. Take note, for example, how it never revisits tiles/chambers upon being pushed into the stack (by marking them), and investigates always in a specific order neighbours (Up, Down, Left, Right are the possible directions).  A stack is used here to solve the maze, if there is a solution. Design two custom mazes (each, saved in its own file as named exactly below, as per the format above):

1.  (customMaze1.txt) Provide a 3 ×3 maze with as many steps (defined below) as possible, that has no solution.

2.  (customMaze2.txt) Provide a 5 × 5 maze, where its solution to the maze has the longest possible path (not the number of moves/steps) when the algorithm computes a solution among all possible 5 × 5 mazes.

Note, every time the main-loop iterates and the end tile/chamber is not yet reached, counts as a step/move. The length of the path, if it exists, is simply the number of tiles in the path less one.

Files Provided

Classes:

❼ Tile.cpp, Tile.h

❼ TileNode.h

❼ LinkedStack.h

❼ StackADT.h

❼ MazeSolver.cpp

Text files (mazes):

❼ maze1.txt, maze2.txt, maze3.txt, maze4.txt, maze5.txt, maze6.txt

Download all these files from the course website.  The code given to you is written with the assumption your TileNode class and LinkedStack class are both implemented.

Testing Your Program

We will perform tests on your implementation of the linked-list based stack and also run the maze solving program given some mazes. To get full marks for testing, your code must compile where all provided files are all in the same directory and pass these tests.  You are encouraged to test your LinkedStack class by creating an instance of it and trying to push/pop tiles/chambers as they are created to see how it works and that all other member functions are working as expected; study the Tile class to see how they work! For example, here is a snippet of code that one can use to test a sequence of push operations then a sequence of pop operations...

LinkedStack✯ newStack = new LinkedStack();

std :: cout<<”Pushing tiles with IDs 0,1,2,...,9 onto stack”<

for(int  i=0;i<10;i++){

Tile ✯ newTile = new Tile();

newTile❂ >setID(i);//a tile has an ID , you can use this!

newStack ❂ >push(newTile);

std :: cout<<”Pushed a tile with ID: ” << newStack❂ >peek()❂ >getID() << ” , number of tiles in stack:” << newStack❂ >size()<

std :: cout<<”Removing all the tiles from the stack”<

while(!newStack ❂ >isEmpty()){

Tile ✯ returnedEntry = newStack ❂ >pop();

std :: cout<<”Popped a tile , its ID:” << returnedEntry ❂ >getID() << ” , number of tiles in stack:” << newStack❂ >size()<

}

delete  newStack;

Ensure that all the methods required by the LinkedStack class are present (which rely on the TileNode class).

Please compile your program (consisting of all the files) using g++. Ensure all the required .cpp and .h files are in the same directory. Your program must be able to compile using:

g++  *.cpp  -o MazeSolver

The program MazeSolver, takes one command line argument, namely the file for the maze (e.g. maze1.txt). If you fail to provide this file, the program will not continue to execute and willl ask for this command line argument.  For example, to execute MazeSolver with maze1.txt can be performed (where the manner the program is called may vary by operating system):

.\MazeSolver maze1.txt

You can use any of the provided mazes (maze1.txt  -- maze6.txt) or create your own too!          Give yourself plenty of time to debug your code. Do not submit your own test programs.

Coding Style

Your mark will be based partly on your coding style:

❼ Variable and method/member function names should be meaningful and they must reflect

their purpose in the program.

❼ Comments, indents, and white spaces should be used to improve readability.

❼ Make sure at the top of your  .cpp file you include a brief summary of your class, including

your name as author of that class.

❼ No variable declarations should appear outside methods/member functions in your .cpp files.

Variables which are needed only inside methods should be declared inside those methods.

Marking

Your mark will be computed as follows:

❼ Program compiles, produces meaningful/correct output for mazes: 2 marks. ❼ LinkedStack tests pass: 6 marks.

❼ Coding style: 2 marks.

❼ TileNode implementation: 2 marks.

❼ LinkedStack implementation: 6 marks.

❼ Custom mazes provided, as per specifications: 2 marks.

If the program, as compiled by the graders, fails to compile, you will only receive at most 12 marks out of 20 marks.  So please, do not modify any of the files provided to you.  Make sure you include any header files necessary for your classes to compile, wherever necessary.  So, do not omit any required methods for the classes, as some files may require those for successful compilation, should you not finish all the methods.