Lab Assignment Objectives

1. Be able to recognize a situation in which a subtask is a simpler version of the larger problem and design a recursive solution to solve this problem.
2. Safeguard against infinite recursion by defining a valid variant expression and threshold on a problem solution.

Understand the Application

Suppose that you have a friend, Ann Ohlone, that has a maze in her backyard. One day, Ann discloses the following two key facts about the maze:

1. Somewhere within the maze is a magic tapestry that contains the secret of happiness.
2. The finder of the tapestry gets to enjoy this secret of happiness provided that they can return to the maze's entrance after entry. (Aside: So far, unfortunately, many a seeker of happiness have entered, but none have returned successfully).

The maze is built on a rectangular grid. At each point of the grid, there are four directions to move: north, east, south, or west. Some directions, however, may be blocked by an impenetrable wall.

Your task is to accept the challenge of providing a program that will guide a user to enter the maze, find the treasure and back out to successfully return to the maze's entrance. In short, you will write a recursive function that can be executed on a laptop that your friend can carry through the maze. The function will give directions and ask the person traversing the maze questions to take them to the magic tapestry and back out to the entrance.

The Program Specification

Write an interactive program to lead the user into a maze and back out again while searching for a magic tapestry. User input will dictate search options available.

Traversing a Maze

In order to traverse the maze, your program needs to detect either a dead end condition (i.e. user facing wall) or an unpursued path (i.e. name is amiss on an unexplored option).

Implementation Subtasks

The dead_end() function will return a boolean value to indicate whether or not the direction directly ahead can or cannot contain the tapestry.

The traverse_maze() recursive function will return a boolean value. A function that returns a value can be recursive in a situation such as this where the answer to a small problem will help to solve the complete problem. In this case, searching part of the maze can help determine whether the tapestry is present or not in the entire maze.

bool dead_end(); // Postcondition:The return value is true if the direction directly in front // is a deadend (i.e., a direction that cannot contain the tapestry). bool traverse_maze(); // Precondition: The user of the program is facing an unblocked spot in the // maze which has not previously been visited by the user. // Postcondition: The function has asked a series of questions and provided // various directions to the user. The questions and directions have led the // user through the maze and back to the exact same position that the user // started at. The return value of the function is a true/false value // indicating whether or not the user found a magic tapestry in the maze.

The Program Design

Since this is our first lab assignment for this course, I will walk you through the design.

traverse_maze

When this function starts, all that is known is that "Ann", the user of the program, is facing some spot in the maze that has not been previously visited. This function needs to take Ann into the maze, eventually heading her back to the exact starting spot. The crown jewel is for her to find the magic tapestry along the way.

Thinking recursively

Always ask Ann to take a step onto an unvisited spot, writing her name on the ground to tag whether or not she has been to a spot before. Once these two recordings are in place, ask Ann whether she has found the tapestry at this new spot; record her answer.

Cases to consider:

• Tapestry is found at this first spot, Ann can pick up the tapestry, step back backward to her starting spot. This is the stopping case.
• Tapestry is not found at this first spot. In this case, there are 3 uncharted possible directions for Ann to explore: forward, left or right. Note: Sometimes, not all 3 directions need be explored (i.e. the direction is a dead end if either a wall is blocking that direction or Ann's already been there).

Remember, anytime that Ann has found the tapestry not to explore new directions.

Steps (Ann has not found tapestry):

1. Designate left as first direction to explore.

2. for each of the 3 possible directions

{

(Test if the tapestry is found and test that the direction being faced is not a dead end).

{

Explore direction selected returning to this spot and setting found to true if the tapestry is found.

}

Have Ann turn 90 degrees to the right (next direction).

}

3. Ann is now facing the direction she came from, so ask her to step forward and turn around (so that she is facing this spot, as she was before this function was called).

Implementation

To implement your solution write the functions to carry out subtasks:

bool dead_end(): This function determines whether the direction in front of the user is a dead end. Dead ends are caused by a wall or a direction that the user has already explored. The function returns true (for a dead end) or false (for no dead end).

bool traverse_maze(): This function explores the three directions available at a given spot in the maze. The function returns true (tapestry found) or false (tapestry not found).

main(): This function provides the test driver to traverse the maze and report whether or not the tapestry is found.

Include the provided library tools:

bool inquire(const char query[ ]): This function reads characters from standard input until a newline character is encountered.

bool inquire(const char query[ ]): This function asks the user a yeso question; it returns true if the user answers "yes", and returns false if the user answers "no".

The Program Design

Write a complete C++ program implementing the functions dead_end(), traverse_maze() and main().

Testing Requirements

Use the provided files to eliminate the need to validate user input.

• auxa1.cpp

• auxa1.h

Provide a commented out copy of your program test run after the source statements in your a1.cpp test driver file.

Example Test Run

Your program display should look something like these sample runs (although the values will differ for each student):

$ ./a1 Step forward & write your name on the ground. Have you found the tapestry? [Yes or No] Yes Pick up the tapestry and take a step backward. You found it! $ ./a1 Have you found the tapestry? [Yes or No] No Please turn left 90 degrees. Are you facing a wall? [Yes or No] No Is your name written in front of you? [Yes or No] No Step forward & write your name on the ground. Have you found the tapestry? [Yes or No] No Please turn left 90 degrees. Are you facing a wall? [Yes or No] Yes Please turn right 90 degrees. Are you facing a wall? [Yes or No] No Is your name written in front of you? [Yes or No] No Step forward & write your name on the ground. Have you found the tapestry? [Yes or No] Yes Pick up the tapestry and take a step backward. Please turn right 90 degrees. Please turn right 90 degrees. Please step forward, then turn 180 degrees. Please turn right 90 degrees. Please turn right 90 degrees. Please turn right 90 degrees. Please step forward, then turn 180 degrees. You found it! 

What to Turn In

Hand in 5 files:

• auxa1.h
• auxa1.cpp - provides eat_line(), inquire()
• maze.h
• maze.cpp - provides dead_end(), traverse_maze()
• a1.cpp - provides main test driver

auxa1.cpp Download auxa1.cpp (712 Bytes) ZOOM + // CS 124-03 // FILE: auxa1.cpp // IMPLEMENTS: A toolkit of functions for lab 1. #include // Provides toupper #include // Provides cout, cin, get #include "auxa1.h" using namespace std; void eat_line) // Library facilities used: iostream { char next; do cin.get(next); while (next != ' '); } bool inquire(const char query[ ]) // Library facilities used: ctype.h, iostream { char answer; do { cout > answer; toupper(answer); eat_line(); } while ((answer != 'Y') && (answer != 'N')); return (answer 'Y'); } answer = auxa1.h Download auxa1.h (846 Bytes) ZOOM + // CS124-03 // FILE: auxa1.h // PROVIDES: A toolkit of useful functions for lab 1. // FUNCTIONS in this toolkit: void eat_line) Postcondition: Up to next newline has been read and discarded from cin. bool inquire(const char query[ ]) Precondition: query is a null-terminated string of characters. Postcondition: query has been printed, and a one-line response read from the user. The function returns true if the user's response begins with 'Y' or 'y', and returns false if the user's response begins with 'N' or 'n'. (If the response begins with some other letter, then the query is repeated.) #ifndef AUXA1_H// Prevent duplicate definition #define AUXA1_H void eat_line(); bool inquire(const char query[ ]); #endif auxa1.cpp Download auxa1.cpp (712 Bytes) ZOOM + // CS 124-03 // FILE: auxa1.cpp // IMPLEMENTS: A toolkit of functions for lab 1. #include // Provides toupper #include // Provides cout, cin, get #include "auxa1.h" using namespace std; void eat_line) // Library facilities used: iostream { char next; do cin.get(next); while (next != ' '); } bool inquire(const char query[ ]) // Library facilities used: ctype.h, iostream { char answer; do { cout > answer; toupper(answer); eat_line(); } while ((answer != 'Y') && (answer != 'N')); return (answer 'Y'); } answer = auxa1.h Download auxa1.h (846 Bytes) ZOOM + // CS124-03 // FILE: auxa1.h // PROVIDES: A toolkit of useful functions for lab 1. // FUNCTIONS in this toolkit: void eat_line) Postcondition: Up to next newline has been read and discarded from cin. bool inquire(const char query[ ]) Precondition: query is a null-terminated string of characters. Postcondition: query has been printed, and a one-line response read from the user. The function returns true if the user's response begins with 'Y' or 'y', and returns false if the user's response begins with 'N' or 'n'. (If the response begins with some other letter, then the query is repeated.) #ifndef AUXA1_H// Prevent duplicate definition #define AUXA1_H void eat_line(); bool inquire(const char query[ ]); #endif