CS35 Lab 05: A-maze-ing Race

Due 11:59pm Sunday, March 19 2017

This is a two-part lab:

  1. An application that solves a maze using either breadth-first or depth-first search.
  2. Written answers to questions regarding algorithmic analysis, induction, and invariants.
The main goals of this lab are to use data structures to implement algorithms and to gain practice using induction. Concepts you will be familiar with after this lab include:

Note: This is a two-part, two-week lab assignment. However, the lab is due in three weeks because of spring break. This lab is not designed to make you work over spring break, nor are you expected to. We do expect you to work on it this week though, and the coding part of this lab should be especially good practice for the quiz. Plan accordingly.

As with most assignments for the rest of the semester, you will be working with a partner. Both partners should be present and working on the code together. You will both be responsible for understanding all concepts, so dividing and conquering is not an option. The academic integrity policy applies to the entire pair; you cannot work or share code with anyone outside your partner.

You and your lab partner will share the same git repository, which is named lab05-<user1>-<user2>.git. Please access your lab by cloning the appropriate git repository, e.g.:

$ git clone git@github.swarthmore.edu:CS35-s17/lab05-jbrody1-adanner1.git

Part I: The A-Maze-ing Race

Images taken from UncleShuck's farm, Dawsonville, GA, and from The MAiZE Company.

In this lab, you will implement two search algorithms—depth-first search and breadth-first search—for finding a path through a maze.

Search Algorithms

In class last week, you saw the following search algorithm:
Algorithm MazeSearch:
  mark start as visited
  add start to data structure
  while (data structure is not empty):
    current = remove location from data structure
    if (current == destination): // found a path!
      return path found
    else for each neighbor of current:
      if neighbor not visited:
        mark neighbor visited
        add neighbor to data structure
  return no path exists
The way this algorithm traverses through locations depends on which data structure is used to store visited locations. When we use a stack, the algorithm is called Depth-First Search (DFS). When a queue is used, it is commonly called Breadth-First Search (BFS).

In this lab you will implement both DFS and BFS, use them to find paths through a 2-D maze, and explore how the two search algorithms produce different paths.

Starting Code

Below is an overview of the files required for submitting this lab. Those highlighted in blue will require implementation on your part. Those highlighted in black are complete and should not be modified except for comments.

ADT Implementations

For this and future labs, you will occasionally be provided with implementations of the ADTs we discussed in class. These implementations make use of the C++ Standard Template Library (STL) and are written as classes named e.g. STLList. To use these classes, simply #include the header the same way you normally would.

Programming Requirements

The Maze Layout

Each maze is a rectangular grid. Each space in the grid is assumed to be connected to the adjacent spaces (left, right, up, and down, but not the diagonally adjacent spaces. The starting point of each maze is the upper left corner; the exit is in the bottom right corner.

The layout of a particular maze will be stored in a file with the extension .map; you can find several examples in your test_data directory. A map file contains the following information:

For instance, the following is a valid map:
5 3
.#.#.
.#...
...#.
We have given you the code which loads files in this format; this explanation is just for reference.

The Position Class

We will represent a maze as a two-dimensional grid of pointers to Position objects. Each Position object contains relevant information for one place in the maze: the (X,Y) coordinates (where (0,0) is the upper-left), whether that position is a wall, and some fields which will be used during the search to construct an appropriate path through the maze. The constructor of the Position class should take the X and Y coordinate values and initialize the other fields to suitable default values (like NULL or false).

The 2-D grid that you create for your maze should take the form of a data member positions of type Position***. This is an array of arrays of Position pointers. This way, you can write e.g. positions[0][0] to get the Position* which points to the Position object in the upper-left corner. You'll have to use nested for-loops to initialize positions correctly.

The Maze Class

A maze object represents our knowledge of a particular maze. We can use this information to find a path through the maze using various search algorithms. You will write two methods---solveDepthFirstSearch and solveBreadthFirstSearch---which are very similar. These methods will return a List*: a pointer to a list of Position pointers, which constitute a correct path through the maze from the start to the finish. If no such path exists, the method should return NULL.

You have been given the declaration of the maze class. You only need to implement each of the methods. The real magic of making the program work happens in these methods, which find a path through the maze using the search algorithm given above.

At the end of the loop, you can determine whether a path has been found by looking at the exit position and seeing if it has been visited. If so, you just need to follow the previous position pointers backward until you reach the start. This gives you the path to take (in reverse order). If the exit position has not been visited, then there is no possible path through the maze.

Testing the Maze class

Make sure to run the unit tests we've provided on your code as you develop. Definitely test your code once you've finished the Maze class! It will be easier to find bugs in your Maze implementation by direct testing than it will be by trying to find them by hand running the maze program.

Some of the map files in test_data have multiple possible solutions. As a result, your output may differ from the provided solutions depending on how you explore the maze. To get the same results as the provided solutions, you should explore neighboring spaces in the following order: up, left, right, and then down.

Implementing Main

The implementation of main should be less work than the Maze class. It just involves something assembling the pieces you've constructed above. The loadMap and renderAnswer functions have been written for you. loadMap will read a map file and return a Maze* if loading was successful. Otherwise, it will throw a runtime_error. renderAnswer should produce a string containing a solution, which looks like the map from the input file, but contains \@ characters on the path you found. For example, here is a possible execution of the program:

$ ./maze
Welcome to CS35 lab 05: The A-Maze-ing Race.
where is your maze file? test_data/cycle.map
Which search algorithm to use (BFS or DFS)? DFS
@@###
#@@@#
#.#@#
#..@@
####@

Invalid Inputs: Your maze program should gracefully handle the following cases of invalid input:

Memory Management

Your program should run without any memory errors. It's OK if your destructor(s) do not clean everything up, but you should at least make a reasonable attempt, and in any case, you should avoid dereferencing uninitialized memory.

Part II: Algorithmic Analysis, Induction, Invariants
For this part of your assignment, you will give written answers much in the same way as you did in Lab 03. Your submission must be in either PDF or .tex format. To get you started with LaTeX, we've given you a WrittenLab.tex which contains the problems below. For further details about LaTeX, see the file LearningLaTeX.tex.
  1. Prove each of the following claims by induction:
    • Claim 1: The sum of the first $n$ odd numbers is $n^2$; i.e. $$\sum_{k=1}^n (2k-1) = n^2\ .$$
    • Claim 2: $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$.
    • Claim 3: $\sum_{k=1}^n \frac{1}{2^k} = 1-\frac{1}{2^n}$.
  2. The function maxEven, given below in pseudocode, takes as input an array $A$ of $n$ integers and returns the largest even integer in the array. If no such integers appear in the array, it returns $-\infty$ (minus infinity). Using induction and loop invariants, prove that the maxEven function works correctly. (Hint: you should use the loop invariant "S(k): at the beginning of the loop iteration with $i == k$, max is equal to the largest even integer in the first $k$ elements of the array, or $-\infty$ if no such numbers exist.")
    function maxEven(A,n):
      max = -infinity
      for i = 0..n-1:
        if A[i] > max and A[i] is even then:
          max = A[i]
        end if
      end for
      return max
    end function
  3. The Horserace. You are in charge of organizing a large horse race. There are 25 horses, and you must determine the three fastest horses (Win, Place, and Show) by placing them into races. Unfortunately, your track only has space for five horses, and you have no timing equipment. You're able to race five horses at a time, and have decided to run multiple races to determine the three fastest horses. You can race each horse any number of times. However, you can only race five horses at a time, and you cannot directly compare results from two different races (since you don't keep track of exact times).

    Give a method to determine the three fastest horses. What is the minimum number of races you need to arrange?


Commenting and Coding Style Requirements
For this and future labs, graders will assign minor penalties for poor commenting and coding style. Here are some style tips for this lab:

Extra Challenges

These additional features are optional -- we'll look at them, but they won't be for credit. Make sure you complete and push both parts of the main lab before starting any extra challenge, and note in your README file that you've done extra challenges so the graders know which version of your lab to grade. (There's a chance your added features will break our grading scripts; we'll grade the base version of your lab to ensure you don't get penalized in the off-chance your extra features break our grading scripts)

Survey
When you have completed your lab, answer a few short survey questions in the file README.md.

Summary

To summarize the requirements of this lab:

Submit

Once you are satisfied with your code, hand it in using git. Remember the add, commit, push development cycle. You can push as many times as you like, but only the most recent submission will be graded. You may want to run git status to confirm all modifications have been pushed.