Project 1: The A-maze-ing Recursive Labyrinth Solver

Due Date:

Midnight Monday, 25 September 2000. Note that this means before 23:59:59 on Monday evening. The standard late policy applies.

Objectives

The objectives of this project are:

The Problem

Mazes (sometimes called Labyrinths) are path-finding puzzles. Over a history that spans 3200 years, the modern maze has developed as a pattern with one or more paths that reach from one end to the other and one or more paths which end somewhere in the middle of the maze (sometimes called a "dead" end; a name that might come from the not unusual idea that something horrible is chasing you through this pattern.)

Your task is to write a program that reads in a maze description from a file and finds a path from one end of the maze to the other. Your program should take the maze name from the command line and produce output that includes:

  1. The dimensions (size) of the maze,
  2. A picture of the maze and the path through it,
  3. The length of the path that it found, or a failure message if none could be found,
  4. and the total number of steps it took to get there.
A sample run of your program should look like this: [irix1] proj1> proj1 Mazes/test.maze -- CMSC 202 Maze Solver v1.0 -- - The file "Mazes/test.maze" holds a maze that is 7 rows x 10 columns. - Passages make up 38% (27/70 squares) of the total area of the maze. - After trying 27 steps, I found a solution 19 steps long. #.######## #........# ##### ##.# # #..# # #####.## # #.....## ###.###### [irix1] proj1> proj1 Mazes/foo.maze Fatal Error: I couldn't open "Mazes/foo.maze". [irix1] proj1> proj1 Mazes/unsolveable.maze -- CMSC 202 Maze Solver v1.0 -- - The file "Mazes/unsolveable.maze" holds a maze that is 7 rows x 10 columns. - Passages make up 37% (26/70 squares) of the total area of the maze. - The maze cannot be solved. # ######## # # ##### ## # # # # # ##### ## # # ## ########## [irix1] proj1>

The Importance of Procedural Abstraction

When programming, one of the tricks we use to keep from losing our minds in the face of all this complication is to break the problem that we're solving into manageable subproblems. This is called problem decomposition. The mechanism we have for this in C/C++ is called a function. The idea is that once we have a function to take care of a subproblem, we don't need to worry about how it's done anymore; we know that calling this function will take care of it. In that sense the use of functions in programming is declarative; it tells what will be done when the function is called. Function implementations are procedural; they describe how this particular subproblem will be solved. The trick to picking what should go into a particular function is thinking ahead to the way in which we plan on using the function. At one extreme the entire program is just one function (the problem is broken up into just one subproblem that happens to be the same as the original problem). At the other extreme we have subproblems for every line of code that we write. The difference between a good problem decomposition and a bad one is often the difference between success and failure in programming.

The key is to decompose the problem into fairly large subproblems. Once you have your first level of subproblems, you can treat each of these separate subproblems as a problem of its own and break each of these problems down into its own subproblems. Notice that in this way, the problem decomposition that we're talking about is actually a recursive process.

So What?
In general there are many successful decompositions to any reasonably large problem. To help you practice this skill we're going to add a twist to project 1: For this project, you may not use any of the following three keywords in your project: for, while, and goto. As a general rule you shouldn't be using any gotos anyway, but it's extra-explicit for this program. By this I mean you are not allowed to use any builtin looping constructs in your program.

Ouch.

Before you panic, think about what we just discussed: procedural abstraction. If you can break your program into reasonable subproblems (functions), your use of those functions will be the same whether they were written iteratively or recursively. Remember, when we use functions all we care is what they do; not how they manage to accomplish that task. If you break your problem into good logical subproblems and make sure you solve them correctly, your program should work like a charm.

Requirements

Your program must:
  1. Handle the command line arguments correctly
  2. Use no explicit loops in the source code that you hand in
  3. Print the maze as shown
  4. Go from one end of the maze to the other (this means you must be able to find an entrance to start by)
  5. Exit gracefully if the file cannot be opened
  6. If the maze cannot be solved, say so.
Similarly, you may assume:
  1. If the file can be opened, it is a correct maze file. This means it will have the right number of pixels, all either '#' or ' '.
  2. The two numbers at the top of each input file are the number of rows and the number of columns respectively.

Sample Program

A sample executable (and sample input mazes) is available in the directory /afs/umbc.edu/users/j/k/jkukla1/pub/cs202/fall00/Project1/ on the irix.gl.umbc.edu systems. Please use it to help understand how the program should behave under certain conditions. When in doubt, make it behave like the sample program!

Note: The program is an executable file compiled for irix, so the odds are fairly high that it won't run as is on your home machine.

Coding Standards

For this project you must follow the class coding standards. Remember, you must document your .C and .H files. All functions must have a header comment as described in the coding standards. Comments inside of functions should be on their own lines and should not share lines with actual code.

For this project, you may write your program in C or C++. You may use whatever non-looping language features that you like from either language.

Using Code You Didn't Write

Claiming authorship of code that you didn't write is plagiarism and will be dealt with as academic dishonesty. You should not use code that you didn't write; it defeats the learning experience of the project. If you do use outside code on your project, you must site the source. If a significant portion of the project comes from an outside source, your grade may be reduced.

Testing Your Program

Remember, your program must compile and run using the CC compiler on the IRIX machines (irix.gl.umbc.edu (or irix1 and irix2)). If your program does not compile or does not generate the correct output, you will not receive full credit for this project.

Many systems come with a utility called "make" which helps simplify project compilation. For this class you will be required to use make for each project. The way this is done is by using a "makefile" that tells make what to do when compiling your program.

You may use this sample makefile for this project. This makefile is extensively documented and should serve as a primer on make itself. You should make sure that you have a makefile named either makefile or Makefile and that when you type make your program compiles to an executable called proj1. Failure to follow these simple directions will result in a reduced grade.

Grading

The grade for this project will be broken down as follows: 50% Correctness This tests that your program behaves the same way that the sample does. 30% Design and Style You should follow the coding standards and make sure your coding style is consistent. 20% Documentation Commenting source code inline as well as header files. A breadown that the graders will receive when they go to grade your project is provided here.

What to Turn In

You should submit your Makefile and any files needed to build your program.

Submitting Your Project

When you have finished and tested your project you can submit it electronically using submit. The project name for this assignment is proj1. As an example, to submit your files, you would type: submit cs202 proj1 Makefile file.1 file.2 ... file.n More complete documentation for submit and related commands can be found here. You should replace all of the file.x's above with your real file names.

Last modified: 10 September 2000