ECE 264 Spring 2010

Individual Programming Assignment 3

Treasure Hunting in a Maze

You were looking for hidden treasure in a lost civilization and went into a labyrinth.  After searching blindly for a while, you found yourself completely trapped in the maze.  The treasure must be somewhere in it, but you could see nothing but walls.  You realized that you must have a strategy to find it.  Unfortunately, no built-in Linux command would help you traverse a maze, you must write a C program to do this.

Purpose

To traverse a maze by using stack (data structure) and back track (algorithm) when reaching a dead end.

Sample Input and Output

Here are three sample mazes in a zip package.  The characters represent

• 'B': brick
• ' ': (space) corridor
• '$': treasure, i.e. the destination
• 'S': starting location of the player in the corridor

If you need more mazes, please use some tools to generate one, like this Online Maze Generator.  You may need to change the output a little to accomodate the assumptions.  Here is a brief tutorial:

• Change "Type of maze" to "Text"
• Change "Width of each cell" and "Height of each cell" to 2
• Click "Generate", then copy and paste the result into a text editor
• Use "Find and Replace" to substitute '-'s and '+'s with 'B'
• Enclose the maze and set starting and ending locations

If you want to see sample output or check your program's output, you can use this text-based IPA3 sample solution & checker.  Please remember that this program can run on ECN Intel-Linux computers only (such as ecelinux##).  After you download the file, please change the permission so that it is executable:

chmod u+x ipa3sc

Type "./ipa3sc --help" in a terminal for its usage.

If you discover that sample solution does not meet the requirements, please post the problem in Blackboard - Discussion.

Strategy

As you are thinking about how to find the treasure, you are searching for 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. You remember learning dynamic data structures (linked list, queue, stack, or binary tree) in ECE 264 and these structures can be expanded as needed. You decide to take the following strategy

1. Go as far as possible until reaching the exit or reaching a dead end.
2. When there is an intersection, you rely on your compass (GPS doesn't work but fortunately your compass still does).  You try different route at an intersection in the following order:
   North -> South -> West -> East
   Of course, you are smart enough to skip the direction that will lead you back to where you are from, unless you encounter a dead end.
3. After reaching a dead end, go back to the last intersection and take a different route, following the direction order listed above.
4. If all routes at an intersection reach to dead ends, go back to the previous intersection.

This strategy is called the depth-first-search with backtracking because you go as far as possible and backtrack when a route turns out to be a dead end.

Don't worry about getting out of the maze after you successfully grab the treasure.  (Somebody will come and rescue you ... hopefully)

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 non-zero return value.
• Your program will read the maze and keep track of all necessary information.
• Your algorithm must perfectly meet the strategy requirements in the [Strategy] section.
• For each step, print out a string "Move to (x,y)\n" where (x,y) is the coordinate of the new location.  The player can move only one step each time, i.e., from (x,y) you can only reach (x+/-1,y) or (x,y+/-1) as your next step.
  • the first step must be "Move to (x0,y0)\n" where (x0,y0) is the coordinate of the starting location 'S', and the last step must be "Move to (x1,y1)\n" where (x1,y1) is the coordinate of the treasure '$'.
• 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 'ipa3' (case-sensitive, no extension, not ipa3.exe).

Do not use graphical user interface (GUI). Instead, print the location of every step (in the same way as the sample solution). Your program will be graded based on the textual output.

Assumptions

• The top-left block of the maze has coordinate (0,0)
• The maximum width (number of columns) of a maze does not exceed 80.  A maze input file may contain an indefinite number of lines.
• Some mazes may not be of rectangular shape, meaning that some lines in the input file may be shorter or longer than others.
• The maze is always fully enclosed by bricks, i.e., it is impossible to escape from the maze.
• Starting location and treasure may appear anywhere in the mazes (e.g., at an intersection).
• Each maze has only one starting location and only one treasure.
• All passages (corridors) in mazes are 1-character wide.

Code

A project has been created for you with a sample structure.  Please check out the code by using the following command on a UNIX shell:

svn checkout http://purdue-wl-ece264-assignment.googlecode.com/svn/trunk/2010/IPA3 purdue-wl-ece264-assignment-read-only

Please read the file "Instruction" included to get started.

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.
• Makefile to create the executable. Name the executable as ipa3 (not ipa2, not IPA3, not pa3, not ipa3.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. You need to explain how you store the activities, how to remove activities and how to find the answer for each question. 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 input, or sample output.
• You may 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 make sure that the target executable of the Makefile is named "ipa3" (all lower-case).  You will receive zero if there is no executable named "ipa3" after running "make".

Late Policy

This assignment is due at 10:59AM on 4/06 (Section 1)  2/18 (Section 2).

• Before the deadline, you can submit and resubmit as many times as you wish. You will receive the grading result soon after submission. If you submit multiple times, your score is the highest among all submissions.
• The time is determined by the server's clock, not your watch.
• You must submit early. Sometimes the Internet can be slow. If you wait until a few minutes before the deadline, it is very likely that you will miss the deadline. Another common mistake is submitting wrong files when the deadline is too close.
• Do not send your assignment by email because it is late. Email submission is ignored.
• Every assignment has a no-penalty extension of 5 hours. The extension is not a new deadline. The extension is provided to accommodate unexpected problems, such as slow network. The extension should be sufficient for you to come to school and submit an assignment, if your home computer breaks.
• If Purdue cancels classes on a submission deadline, the deadline is extended to one day after classes resume.
• If the server is down within 12 hours of the deadline, the deadline will be extended by 24 hours.

Policy Handling Dishonest Behavior

You will receive F in this class if you cheat. Your case will always be reported to ECE main office. There is no exception. If you help a student cheat (such as giving your code), you will also receive F. If you want to help a classmate, tell the person to talk to the instructor or the teaching assistants.   You are responsible protecting your assignments. Do not leave a computer unattended. Do not throw away the printout of your programs.

Do not copy code from your classmates or from the Internet.

You are allowed to use the code given to you by the instructor or generated snippets using the tools approved by the instructor. You are not allowed to download code from the Internet and claim the code as yours. If you discover useful code, you must (1) announce the code in Blackboard Discussion so that everyone in the class is aware of the code or (2) request the instructor's written approval or (3) describe with sufficient details where the code comes from and how you use it in your README file. You must request the code owner's permission to use the code and you must cite the source in your submission. You are not allowed to purchase code from, for example, getacoder.com.

There were cases when students claimed they "accidentally" submitted code from the Internet because these students were "studying" the code. In all these cases, the students were considered cheating and received appropriate penalty.  It is not possible to "accidentally" submit the code that is not written by you.If it is your code, you must have spent many hours writing the code. You will treat the code with the greatest care. You will check, double check, and check again before submission. If you have spent so much time on an assignment, you will not accidentally submit wrong code.  "Accidentally submitting wrong code" is an invalid defense and you will receive F in this class.

You should know that advanced tools are available checking programs' similarities. These tools can detect programs of similar structures, even if you rename variables or change for to while (or many other techniques to disguise). These tools have successfully detected many cheating cases.  The very fact that you consider to cheat indicates your lack of programming skills. Hence, you do not have sufficient knowledge to defeat these similarity checkers. If you need help, please talk to the instructor or the teaching assistants, or post your questions in Blackboard Discussion. Do not ask your classmate or anyone that took this course to give code to you.  The submissions from multiple semesters will be checked.

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.

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 6 points.

• 0.5: read the maze from a file and print it on the screen (using printf). The input file may include empty or invalid lines (only the line with bricks are valid). Ignore (do not print) any line that has no brick.
• 2: can correctly traverse mazes which contain no intersection.
• 3.5: produce correct traversal sequence (i.e. visit correct locations) for general mazes (containing intersections).
• -2: Memory leak or unclosed files reported by valgrind memtest
  • For self-checking: You must receive "no leaks are possible" at the end of valgrind's report to pass this test.
• -0.5: each warning message reported by -Wall -Wshadow.

Congratulations!

You have got the priceless ancient treasure! After all, C programming isn't just writing code. It helps you make some money in your life. You are so happy that you study ECE 264 very hard and can apply the knowledge. You will lead an expedition team back to the maze and find the hidden treasure. You will also come back to tell younger ECE 264 students that the course has made you a millionaire.

Now all you have to do is to embrace your treasure pot and wait patiently for someone else to come and rescure you out.  Good luck.

Extension

This is not part of the assignment.

• Do you have an easy way to draw the shortest path between the start and destination after traversing the maze?
• What will your strategy be if there are multiple treasures hidden in the maze?
• The mazes used in this assignment have one common restriction: there is exactly one path between two points in each maze. We can easily create mazes in which there are multiple paths (by removing some bricks). How would your strategy be different?  Can you still find the shortest path in such situation?
• This assignment asks you to turn left first and right last. This strategy is not always the best. You may even pass the destination without knowing it. As a result, you have to travel farther than necessary. Can you propose a strategy that is smarter than the simple clockwise rule, meaning that on average the new strategy produces a shorter route than that produced by the given strategy in this specification?