Imagine that you are an intrepid adventurer that goes looking for hidden treasure in the far-off caves of lost civilization. As part of this quest, you become trapped in an underground maze. You are convinced that the treasure is somewhere in the maze, but you can see nothing but walls. You realize that you must have a strategy and a computer program to find the treasure. Unfortunately, no built-in Unix command would help you traverse a maze, so you must write a C program to do this.
In the example maze in the figure above, the red square is the exit of the maze (leading to the hidden treasure). The blue circle is the current location. The green circles mark the visited intersections. The yellow circles mark the visited locations.
Purpose
To exhaustively traverse a maze to find the exit and back tracking (algorithm) whenever reaching a dead end.
Sample Input and Output
You can download these sample inputs to test your program. Four examples are shown here. You are encouraged to post your answers to these test cases and compare your results with those of your classmates. The characters represent
'*': brick
' ': (space) corridor
'E': exit, i.e. the destination
's': your starting location (notice: lower case 's', not upper case)
Please be aware that these test cases are not the cases to be used in grading. Passing all tests cases here does not guarantee a full score. You are responsible for creating test cases that meet the specification but are not included here.
If you need more mazes, please please use some tools to generate one, like this Online Maze Generator. You may need to change the output a little to satisfy the assumptions.
Demonstration
Strategy
As you are thinking about how to find the exit, you are thinking about the courses that have taught you problem-solving skills. You need to remember where you have been and to avoid visiting the same place twice. Every time you encounter an intersection, you have to remember the decision made at this intersection. You do not know the size of the maze so you have to store data of an unknown size. Fortunately, you have developed a survival strategy:
Go as far as possible until reaching the exit or a dead end.
Whenever you encounter an intersection, you rely on your compass (GPS doesn't work underground but fortunately your compass still does). You try different routes at an intersection in the following order:
East -> South -> West -> North
You should not take a direction that would lead you back to where you have been, unless you encounter a dead end.
After reaching a dead end, go back to the last intersection and take a different route, following the direction order listed above.
If all routes at an intersection reach to dead ends, go back to the previous intersection.
This strategy is called depth-first-search with backtracking because you go as far as possible and backtrack when a route turns out to be a dead end. If you follow this strategy, it is possible to show that you will eventually always find the exit (if there exists a path from the starting point to the exit in the first place, that is).
Requirements
The program takes one input argument as the maze file. If this input file name is not provided, the program prints an error message and terminates with return value EXIT_FAILURE. If the file cannot be opened, it also prints an error message and return EXIT_FAILURE. This constant is defined in stdlib.h and your program needs to include that header file.
Your program will read the maze file and keep track of all necessary information in memory.
Your algorithm must meet the strategy requirements in the [Strategy] section. It is very important that your solution follows the order: East -> South -> West -> North. If your program takes a different order, the output will be different and you will receive zero points on the assignment.
For each step, print out a string "Move to (row,col)\n" where (row,col) is the coordinate of the new location. The player can move only one step each time, i.e., from (row,col) you can only reach (row+/-1,col) or (row,col+/-1) as your next step. Here, row corresponds to the vertical (y) coordinate and col corresponds to the horizontal (x) coordinate.
The first step must be "Move to (row0,col0)\n" where (row0,col0) is the coordinate of the starting location 's', and the last step must be "Move to (row1,col1)\n" where (row1,col1) is the coordinate of the exit 'E'.
You must include a Makefile in your submission. Your program will be compiled and built using your Makefile. If there is no Makefile, your submission will not be graded. The name of the executable file must be 'ipa1' (case-sensitive, no extension, not ipa1.exe).
Your code needs to follow the coding standards specifiedhere. We will manually check this and you can lose up to 1 point if standards are not followed.
Do not use a graphical user interface (GUI). Instead, print the location of every step to the console using standard C functions. Your program will be graded based on the textual output. You can print the maze and the current location for debugging. Please remember to remove all debugging information when you submit the program for grading.
If you want to learn GUI, you can try GTK or Qt. Both need some understanding about C++. You can take ECE 462 after 264.
Assumptions
The top-left block of the maze has coordinate (0,0). This is the convention in computers.
The maximum width (number of columns) of a maze does not exceed 80. For part 1, you can assume the maximum height (number of rows) also does not exceed 80. For parts 2 and 3, a maze input file may contain many lines. Therefore, your program should allocate memory only after it knows the number of lines in the file. Your program can read the same file twice: the first time to find the number of rows so that you know the amount of memory to allocate, the second time to store the maze in a piece of memory allocated by your program. You can use fseek to return to the beginning of the file before reading the second time.
The maze is always fully enclosed by bricks, i.e., it is impossible to escape from the maze other than through the exit. Be aware that a valid maze does not have to be rectangular.
The starting location may appear anywhere in the maze, even at an intersection.
Each maze has at most one starting location and one exit. It is possible for a file to contain an invalid maze that has no starting location, no exit, or neither.
All passages (corridors) in mazes are 1-character wide.
There is one and only one path between two points in the maze.
What to submit?
The source code (including all .c and .h needed to generate the final executable). You must use at least three files (one .h header file and two .c source files.) You will receive zero if everything is in a single file. Of course, you cannot submit three files and two of them are empty. You can have more files if necessary.
Upload the files as a zip package containing the necessary files (source files, header files and Makefile). You can name the source files, header files and the zip package arbitrarily, but the names should have no spaces. Make sure that the target executable of the Makefile is named "ipa1-1", "ipa1-2", or "ipa1-3" depending on which assignment you are submitting (all lower-case). You will receive zero if there is no executable named "ipa1-1", "ipa1-2", or "ipa1-3" depending on which assignment you are submitting after running "make".
Makefile to create the executable. Name the executable as ipa1-1 (not ipa1, not IPA1-1, not pa1-1, not ipa1-1.exe, or anything else). You will receive zero if your submission has no Makefile. The file name must be Makefile (this is a widely accepted convention); any other names will be rejected.
README to explain what you have done and how you do it. It is a text file readable You need to explain how you store the locations. The file name must be README, not readme, not Readme, not README.txt, not README.pdf, nor README.doc.
Do not include object files, executable files, sample inputs, or outputs.
You should never have a space or symbol (other than .) in a file name. Some operating systems can accept file names with spaces or symbols but some operating systems cannot. To make sure your programs work, do not take a chance.
Part 1
This may be the most complex program you have ever written. To help you manage the assignment, this assignment is divided into three parts. In the first part, your program needs to read the maze file and print the following information:
The size of the maze: the height (number of rows) and the width (number of columns).
The location of the exit.
The location of the starting point.
Please use the following code so that your output has the same format as expected by the grading program
printf("height=%4d, width=%4d\n", height, width);
printf("exit at (%4d, %4d)\n", exitRow, exitColumn);
printf("start at (%4d, %4d)\n", startRow, startColumn);
You can use different names for the variables: width, height,
Please use the following code for the error message if a maze does not have a starting/ending point.
printf("Maze is invalid due to a missing starting/exit point\n");
Your program should still exit normally, i.e. return EXIT_SUCCESS, if this happens.
Please use the following code if the number of command line arguments does not equal 2.
printf("Usage: ipa1-1 <maze file>\n");
Please use the following code for error message if a file cannot be opened.
printf("Error opening file! Exiting Program!\n");
You should return a value of EXIT_FAILURE for both errors.
Output Code
You can download the output code from here. The file contains the following functions
PrintError - Contains all of the possible message errors for the assignment
PrintResults - Contains the format for printing your solution for ipa1-1.
Examples
You can find example mazes and their solutions here.
Part 2
The second part requires that your program prints the location of every step from the starting point to the exit. There will be NO intersections here.
We will check whether your program initializes all pointers to NULL. For example,
int * ptr = NULL; /* initialized to NULL, required */
You can do the following. It is the same.
int * ptr;
ptr = NULL; /* immediately after declaring ptr */
This is another allowed way to use a pointer.
int * ptr = malloc(numberElement * sizeof(int));
If you write the following code without initialization, you will lose 0.2 point.
int * ptr; /* uninitialized pointer. NOT ALLOWED */
Why do we check this? Uninitializing pointers make a program's behavior unpredictable.
(You are also allowed to declare and allocate memory for a pointer immediately using malloc().)
Please use the following code if the number of command line arguments does not equal 2.
printf("Usage: ipa1-2 <maze file>\n");
Please use the following code for error message if a file cannot be opened.
printf("Error opening file! Exiting Program!\n");
You should return a value of EXIT_FAILURE for both errors.
Please use the following code for the error message if a maze does not have a starting/ending point.
printf("Maze is invalid due to a missing starting/exit point\n");
Your program should still exit normally, i.e. return EXIT_SUCCESS, if this happens.
You need to use structure for this part. A Maze structure should include relevant information about the maze, such as the location of the exit, the current location, the cells, and so on.
Output Code
You can download the output code from here. The file contains the following functions
PrintError - Contains all of the possible message errors for the assignment
PrintResults - Contains the format for printing your solution for ipa1-2.
Examples
You can find example mazes and their solutions here.
Part 3
The third part also requires that your program prints the location of every step from the starting point to the exit. This time, however, there WILL be intersections! (If you coded your program so that it can handle intersections already for Part 2, you will not have to change anything for this part).
We will check whether your program initializes all pointers to NULL. For example,
int * ptr = NULL; /* initialized to NULL, required */
You can do the following. It is the same.
int * ptr;
ptr = NULL; /* immediately after declaring ptr */
This is another allowed way to use a pointer.
int * ptr = malloc(numberElement * sizeof(int));
If you write the following code without initialization, you will lose 0.2 point.
int * ptr; /* uninitialized pointer. NOT ALLOWED */
Why do we check this? Uninitializing pointers make a program's behavior unpredictable.
(You are also allowed to declare and allocate memory for a pointer immediately using malloc().)
Please use the following code if the number of command line arguments does not equal 2.
printf("Usage: ipa1-3 <maze file>\n");
Please use the following code for error message if a file cannot be opened.
printf("Error opening file! Exiting Program!\n");
You should return a value of EXIT_FAILURE for both errors.
Please use the following code for the error message if a maze does not have a starting/ending point.
printf("Maze is invalid due to a missing starting/exit point\n");
Your program should still exit normally, i.e. return EXIT_SUCCESS, if this happens.
You need to use structure for this part. A Maze structure should include relevant information about the maze, such as the location of the exit, the current location, the cells, and so on.
Output Code
You can download the output code from here. The file contains the following functions
PrintError - Contains all of the possible message errors for the assignment
PrintResults - Contains the format for printing your solution for ipa1-3.
Examples
You can find example mazes and their solutions here.
Performance
The score of your program is not determined by its performance. However, your program has to be "reasonably fast" so that it can be graded. If your program takes longer than 100 times of the sample solution, your program will fail certain tests.
Your program is graded by another program. Nobody will sit in front of a computer to enter anything from the keyboard. Do not use scanf or anything that requires inputs from keyboard. This will cause your program to hang up and eventually time out while your program is being graded and you will likely receive zero.
Grading
The full score of this assignment is 15 points, divided into three parts.
Part 1 (5 points)
0.5: return -1 if no file name is given
0.5: return -1 if the file cannot be open
0.5: print the size correctly
0.5: print the locations of the exit and the starting point
-0.25: Memory leak or unclosed files reported by valgrind. For self-checking: You must receive "no leaks are possible" at the end of valgrind's report to pass this test.
-0.2: each warning message reported by -Wall -Wshadow. Pay special attention to the variables that are defined but never used.
Details about grading for Parts 2 and 3 to be announced!
Programming style:
You will lose most points if the program leaks memory. You will lose 0.2 point for each warning message.
The minimum score is zero. You will not receive a negative score.
Memory Management
Memory management (allocation and release) is an important part of ECE 264. You have to allocate enough memory to make your program work. You have to allocate and release memory as needed. You are not allowed to allocate a large piece of memory regardless of the input size. We will restrict stack size to prevent that. You will receve heavy penalty (50%) if your program does not release all memory (i.e. memory leak). We will use valgrind to check for memory leaks.
Submission Procedure
You must submit through this web site. This is the only way to submit your exercises and programming assignments.
You need to provide a user name and a password through Blackboard before submission. The user name and the password are different from your Purdue career account.
Return Message
The following files will now be return to you.
Testcases used to check your code. These files are named testmaze** where ** is the corresponding testcase number.
The expected output. These files are named solution** where ** is the corresponding testcase number.
The output from your code. These files are named yoursolution** where ** is the corresponding testcase number.
Congratulations!
You have found the priceless ancient treasure! After all, C programming isn't just about writing code. It saves your life. You are so happy that you study ECE 264 very hard and apply the knowledge in the future. You will lead an expedition team back to the maze and find the hidden treasure. You will also come back to tell future ECE 264 students that the course is very helpful.
Bonus Points
If you have done additional work and deserve bonus points, please contact the instructor before March 21, 2012. When you submit the assignment, turn off the bonus features because the grading programs do not handle bonus features.
Single Path
1 points: After finding the exit, print the path without the mistakes. Make the correct decision at every intersection.
2 points: For a w x h maze, what is the longest distance you may possibly need to go through before finding the exit? Write down your answer as a function of w and h.
Multiple Path
2 points: Handle multiple paths. The mazes used in this assignment have one common restriction: there is exactly one path between two points. We can easily create mazes in which there are multiple paths (by removing some bricks). How would your strategy be different?
1 points: Print the shortest path in a maze with mutliple path. Make the correct decision at every intersection.
