CS35: Data Structures and Algorithms

Lab 5: Maze

Due on Wednesday, March 27 at 11:59 PM. This is a team lab. You and your assigned lab partner(s) will complete this lab together. Make sure that you are familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

We will be using Teammaker to form teams. You can log in to that site to indicate your preferred partner. Once you and your partner have specified each other, a GitHub repository will be created for your team. If you have any trouble using Teammaker, contact your instructor.

Overview

Maze1
Uncle Shuck's Farm
Source: By UncleShuck

This lab comes in two parts:

  1. An application that solves a maze using (at the user’s option) either breadth-first or depth-first search.
  2. Written answers to questions regarding algorithmic analysis.

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. There is however two weeks worth of work in this lab, and we do expect you to work on it this week. Plan accordingly.

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.:

$ cd ~/cs35
$ git clone git@github.swarthmore.edu:CS35-S18/lab05-user1-user2.git
$ cd lab05-user1-user2

You can also get the ssh git url from CS35 github org.

Part I: maze: A Maze Solver

The first part of this lab involves writing code for a program called maze. This program will solve provided mazes using the depth- and breadth-first search algorithms discussed in class. To implement these algorithms, you will first need to create implementations of the Stack and Queue ADTs.

Your Starting Code

When you clone your repository, you will see the following files. Files you may need to change appear in bold.

We can group these files into the major components of the maze lab, which we recommend implementing in the given order:

  1. ADTs and Data structures: you are provided with ADTs (List,Stack, Queues, OrderedCollection) in the adts folder and some implementations (STLList). You will implement LinkedQueue and LinkedStack in the corresponding files. You will thoroughly test your implementations using manualTests.cpp and testStackQueue.cpp.
  2. Helper methods specifically for the maze application. These are the Position class (provided, abstracts 2D locations in a grid), Maze class (you must implement) for representing the maze itself, and maze utilities for loading and drawing your mazes (provided). You will thoroughly test your implementations using manualTests.cpp and testMaze.cpp.
  3. Main application (main.cpp) which you will complete to bring all of the components together.

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, using the directory names as necessary (e.g. #include "adts/stlList.h). You are welcome to inspect these files, but recall that a feature of implementing ADTs is that you only need to know the interface. For the STLList, it has the exact same interface as your LinkedList implementation from last week:

/* ADTs */
#include <cs35/List.h>

/* Implementations */
#include <cs35/stlList.h>

int main(){
  List<int>* list = new STLList<int>;
  list->insertFirst(10);
}

Implementing LinkedQueue and LinkedStack

Type Hierarchy for Stacks and Queues

The LinkedQueue and LinkedStack classes appear in the like-named files in your starter code. As we discussed in lecture, these classes are easily implemented using a linked list; you can find a linked list implementation in the form of the STLList class in the file adts/stlList.h. You should proceed by implementing each of the methods in the files linkedQueue-inl.h and linkedStack-inl.h. These methods are not meant to be complex; they require very little code to complete. You do not need to throw your own exceptions from these objects’ methods since the underlying list will do so for you. For example, while pop() should raise an exception if it is called on an empty list, the STLList will throw this for you when you try to remove an element from an empty list.

This lab includes an OrderedCollection abstract class which describes the commonalities between queues and stacks (also as discussed in lecture). Note that e.g. LinkedQueue is a subclass of both Queue and OrderedCollection, so it will need not only enqueue and dequeue methods but also insert and remove methods. The insert and remove methods can be implemented simply by calling enqueue and dequeue; we will rely on this commonality later to reduce the amount of code you need to write!

Once you’ve completed your LinkedQueue and LinkedStack implementations, run the unit tests (make testStackQueue followed by ./testStackQueue) to see if they are working correctly. After these tests pass, proceed to the Maze part of the lab.

The Layout of a Maze

Example grid
Example Maze. Black positions are walls

Once you have completed your LinkedQueue and LinkedStack implementations, you are prepared to implement the search algorithms we discussed in lecture. We begin by considering how we will represent the mazes we intend to solve.

Each maze is a rectangular grid. Each spaces in the grid can connected to the orthogonally adjacent spaces. That is, from any location in the grid, you can move one space left, right, up, and down but not diagonally. The starting point of every maze is the upper left corner; the exit is in the bottom right.

The layout of a particular maze will be stored in a text data file with the extension .map; you can find several examples in your test_data directory. We have already written the code which loads files in this format for you; this explanation is just for reference. A map file contains the following:

For instance, the following is a valid map:

5 3
...##
.#...
...#.

And corresponds to the grid pictured.

The Position Class

We will represent a maze as a two-dimensional grid of Position objects. Each Position object contains relevant information for one place in the maze: the (X,Y) coordinates (where (0,0) is in 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 takes the X and Y coordinate values and initialize the other fields to suitable default values (like nullptr or false).

The Maze Class

Maze2
Star Wars Maze
Source: By The MAiZE Company

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 strategies. The two-dimensional grid that you create for your maze (in the Maze class) is a member field positions of type Position***: an array of arrays (2D array) of Position pointers; e.g. positions[0][0] will obtain the pointer (Position*) to the Position object in the upper-left corner. You’ll have to use nested for-loops to initialize positions properly.

This class has two public methods – solveBreadthFirst and solveDepthFirst – which will perform the appropriate search algorithm and return an answer. The answer is in the form of a List<Position*>*: a pointer to a new list of positions which constitute a correct path through the maze from start to finish. These two algorithms are very similar: they only differ in which data structure they use to perform the search! Regardless of whether we are using a stack (depth first) or a queue (breadth first), the search algorithm goes as follows:

At the end of the loop, you can determine whether you found a path by looking at the exit position; if that position has been visited, you just need to follow the previous position pointers backward adding each Position to the List you need to return, until you reach the start to describe the path to take. If the exit position has not been visited, then there is no possible path through the maze.

To avoid writing the same code twice, we can implement the above algorithm in the private method solve. This method takes an argument of type OrderedCollection<Position*> and uses that data structure during the search. Then, solveBreadthFirst and solveDepthFirst both call solve, each providing an appropriate data structure. Your solve method will return the list of positions that describe the correct path through the maze (or a nullptr in the event that no such path exists).

Testing the Maze Class

Make sure to run the provided unit tests on your code as you develop using make testMaze and ./testMaze; definitely test your code once you’ve finished the Maze class! It’ll be easier to find most bugs in your Maze implementation by direct testing than it will be by trying to find them by hand by running the maze program.

Some of the provided 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 in your getNeighbors method: up, left, right, and then down.

Implementing main

Example search solution
Example breadth-first solution.

The implementation for main relies mostly on the classes you have already completed and is thus relatively short for such a large lab assignment. The loadMap and renderAnswer functions have been written for you. loadMap will read a map file; it will return a Maze* if load is successful and will throw a runtime_error otherwise. renderAnswer will produce a string containing a solution, which looks like the map from the map file but contains @ characters on the path that you found. For instance, here is a possible execution of the program:

$ ./maze test_data/cycle.map breadth
@@###
#@@@#
#.#@#
#..@@
####@

Your program will take two command-line arguments:

If there is a solution to the provided map, your program should print the rendering of that solution. If there is no solution, your program should print a message to that effect.

Solutions to the provided test mazes are given in the .solution.txt files in the test_data directory:

$ cat cycl__breadth.solution.txt
@@###
#@@@#
#.#@#
#..@@
####@

if a map is unsolvable, then its solution file will be missing.

Invalid Inputs

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

Note that you are not permitted to allow your program to crash in these cases; you must catch exceptions and print messages accordingly, using syntax similar to the following:

try {
    ... // do stuff
} catch (runtime_error e) {
    ... // handle error
}

Memory

Your program is required to run without any memory errors. Use valgrind to determine if you have any memory errors; we will do so, and any errors reported by valgrind will result in lost points. You should also use valgrind as a debugging tool as you develop your program.

You are also required not to have any memory leaks, although memory leaks will be scored far more generously. You are encouraged to worry about memory leaks only after your program is working correctly. Once your program works, commit and push it and then consider making changes to solve leaks. It’s much better to have a correct, leaky program than it is to have a leak-free program that crashes.

Coding Style Requirements

You are required to observe good coding practices. Be sure to review our style guide from Lab 4.

Part II: Algorithmic Analysis

For this part of your assignment, you will give written answers much in the same way as you did in Lab 3. Your submission must be in a typeset PDF format according to that lab’s requirements; please see that link for instructions and see your Lab 3 template for instructions on how to use LaTeX. Your solution should appear in WrittenLab.pdf and we strongly recommend using the provided WrittenLab.tex as your starting point.

For this part of the lab, answer the following questions.

  1. Prove each of the following claims by induction.
    • The sum of the first \(n\) odd numbers is \(n^2\). That is, \(\sum\limits_{i=1}^{n} (2i-1) = n^2\).
    • \(\sum\limits_{i=1}^{n} \dfrac{1}{2^i} = 1 - \dfrac{1}{2^n}\)
  2. Recall the following function from Lab 3: 
     Function func(n)
   For i = 1...n
     For j = 1...i/2
       a = j
     End For
   End For
 End Function

    Provide the summation series and closed form run time (similar to the format of the induction claims in Problem 1). Prove your claim using induction.

  3. The function maxOdd, given below in pseudocode, takes as input an array \(A\) of size \(n\) of numbers and returns the largest odd number in the array. If no odd numbers appear in the array, it returns -∞ (negative infinity). Using induction, prove that the maxOdd function works perfectly. Clearly state your recursive invariant at the beginning of your proof.

    Function maxOdd(A,n)
  If n = 0 Then
    Return -infinity
  Else
    max <- maxOdd(A,n-1)
    If A[n-1] > max And A[n-1] is odd Then
      max <- A[n-1]
    EndIf
    Return max
  EndIf
EndFunction
  4. A palindrome is a sequence of letters which is the same when reversed; for instance, “civic” is a palindrome. We often ignore spaces in phrases to form palindromes; thus, we would view “taco cat” as “tacocat” and this is also a palindrome.
    • Write in pseudocode an algorithm which inputs a string containing only letters and determines the size of the largest palindrome that the string contains. For instance, given the string “purplehelper”, the substring “plehelp” is a palindrome of 7 characters. Or, given the string “zoom”, the substring “oo” is a palindrome of 2 characters. Your solution must run in \(O(n^2)\) time (where \(n\) is the length of the string).
    • Justify the runtime of your algorithm. That is, explain why it takes \(O(n^2)\) time and will not have a worse runtime for any input.

Summary of Requirements

When you are finished, you should have

When you are finished with your lab, please fill out the post-lab survey. You should do this independently of your partner.