CS 211: C and Systems, Spring 2019 Programming Assignment 2: Maze Traversal
1 Introduction
Your assignment is to write a maze traverser. The input will be the parameters of a rectangular maze followed by a character representation of the maze itself. The output of your program will be the maze with a path from entry point to exit point.
You can design your own class for the maze and any other classes you may need.
2 Program Specification
Your maze traverser will accept parameters and a rectangular maze through standard input. The first two parameters will be the number of rows and columns in the maze. The next two parameters will be the row and column of the entry point. The last two parameters will be the row and column of the exit point. The parameters will be followed by the character representation of the maze. Your program will draw a path from entry point to exit point.
The maze will be a rectangular grid of blocks and floor panels. A block will be a (hashtag), a floor panel will be a blank. The walls of the maze will be constructed from blocks and the floor from floor panels. Your traverser can move freely from floor panel to adjacent floor panel, but it will not be possible to walk through the walls.
You can drop a marker on any floor panel to show a step in you path. A marker can be any character except a block or a floor panel. You can also pick up a marker and replace it with a floor panel.
You can touch the walls, but you cannot alter the walls, so don’t even think about it. The walls are too high to jump over, so that option is out as well. No digging under the walls, as there are giant carnivorous moles down there.
3 Maze Traverser
In a real-life maze, you could enter the maze, put one hand on the wall (left or right) and start walking. As long as you never stop touching the wall with that hand, you will make your way to the exit.
Your algorithmic maze traverser can be right- or left-handed. The right-handed traverser always wants to turn to the right, the left-handed traverser always wants to turn to the left.
It would be good to decide on a convention for directions in the maze. I went with North, South, East and West for a rectangular maze. You traverser will have to know the row and column of its current location as well as the direction the traverser is facing/going.
1
The maze traverser can change direction as needed. A right-handed traverser facing north would turn to the east. A left-handed traverser facing north would turn to the west. The sequence of turns for a right-handed traverser would be a circular sequence of north, east, south, west and then back to north. For a left-handed traverser, the sequence would be north, west, south, east and then back to north.
4 Maze Traversal Algorithm
Your traverser would start at the entry point coordinates. Based on the entry point coordinates, the traverser would have to determine its initial direction of travel. A traverser entering through a west wall would be traveling east. (What rule would you infer here?) The traverser then takes a step in that direction. At the new location, the traverser tries to determine the next step. A left-handed traverser facing east will reach to the north.
If there is no wall to the north, the traverser turns to the north and takes a step to the north. If there is a wall to the north, the left-handed traverser then turns to the right and tries the wall to the east. The traverser keeps turning until it finds a location it can step to next. (What behavior would you infer for a right-handed traverser?)
The traverser builds a path by putting down some sort of marker on each floor panel the traverser steps on. Of course, the never-take-your-hand-off-the-wall approach means that the traverser will retrace some of its steps. Before putting down a marker, the traverser should look at the floor panel. If there is no marker there, go ahead and put a marker down. If there is a marker there already, the traverser should pick it up. The traverser gets a five-cent deposit on all returned markers.
Maze traversal ends when the traverser reaches the exit point coordinates.
5 Extra Credit
Calculate the number of steps on the final path from entry to exit. You can also print out the maze as colored blocks. See the resource on printing stuff in color. Another option would be to print the maze after every step. If you use the escape sequence TBA to put the cursor back at the top left corner of the screen. Print the sequence before every maze reprint to get an interesting effect.
6 Submission
You have to e-submit the assignment using Sakai. Your submission should be a tar file named pa2.tar that can be extracted using the command:
tar xf pa2.tar
Your tar file must contain:
• readme.pdf: this file should describe your design and implementation of the traverse pro- gram. In particular, it should detail your design, any design/implementation challenges that you ran into, and an analysis (e.g., big-O analysis) of the space and time performance of your program.
2
• source code: All C source code and necessary for building your traverse executable. These should at least include traverse and any other files necessary for your program.
• A makefile that can build all the necessary executable files.
You can build your pa2.tar file in the following steps:
1. Put all the files you want to hand in in a subdirectory called pa2. 2. In the parent directory that contains pa2, invoke tar:
tar cvf pa2.tar pa2
The arguments to tar are cvf. The c tells tar to create a new archive file. The f tells tar that the next command line argument is the name of the output file. The v just makes tar list the files it’s putting into the archive.
We will compile and test your program on the clamshell machine so you should make sure that your program compiles and runs correctly on these machines.
7 Grading Guidelines 7.1 Functionality
The most significant part of your grade will be based on programmatic checking of your program. We will test your code for correct functionality against a set of inputs, some of which may be quite large. Thus:
• You should test your code as thoroughly as you can. In particular, your code should be adept at handling exceptional cases.
Be careful to follow all instructions. If something doesn’t seem right, ask.
7.2 Design
Having said the above about functionality, design is a critical part of any programming exercise. In particular, we expect you to write reasonably efficient code based on reasonably performing algorithms and data structures. More importantly, you need to understand the performance (time & space) implications of the algorithms and data structures you chose to use. Thus, the explanation of your design and analyses in the readme.pdf will comprise a non-trivial part of your grade. Give careful thoughts to your writing of this file, rather than writing whatever comes to your mind in the last few minutes before the assignment is due.
7.3 Coding Style
Finally, it is important that you write “good” code. Unfortunately, we won’t be able to look at your code as closely as we would like to give you good feedback. Nevertheless, a part of your grade will depend on the quality of your code. Here are some guidelines for what we consider to be good:
3
• Your code is modularized. That is, your code is split into pieces that make sense, where the pieces are neither too small nor too big.
• Your code is well documented with comments. This does not mean that you should comment every line of code. Common practice is to document each function (the parameters it takes as input, the results produced, any side-effects, and the function’s functionality) and add comments in the code where it will help another programmer figure out what is going on.
• You use variable names that have some meaning (rather than cryptic names like i). Further, you should observe the following protocols to make it easier for us to look at your code:
• Error and warning messages should be printed to stderr.
4