Data Structures and Algorithms

Lab 9: Labyrinth II: The Bees

Due on Sunday, April 10th 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.

Overview

For this lab, you will write a min-heap data structure for use as a priority queue. You will then write a labyrinth solver program which uses this priority queue to find the best path through a labyrinth which contains features (such as bees) which may cause a space to be less desirable to use. In the process, you will learn about the vector class, an array-list-like class from the C++ Standard Template Library.

Starting Code

Your starting code consists of the following files. Files that you will need to change are bolded below.

• Files to define a min-heap and use it as a priority queue.
  • priority_queue.h: The PriorityQueue interface.
  • array_min_heap.h/array_min_heap__definitions.h: The ArrayMinHeap class. You will need to add some private helper methods to the declaration and then define those methods as well as the public interface methods.
• A simple Pair data structure.
  • pair.h
• Files for implementing the labyrinth solver.
  • feature.h/feature.cpp: A couple utility functions pertaining to map features.
  • position.h/position.cpp: The Position class.
  • labyrinth2.h/labyrinth2.cpp: The Labyrinth2 class which implements the maze-solving algorithm.
• The main labyrinth-solving program.
  • labyrinth2_main.h/labyrinth2_main.cpp
  • program.cpp: The file in which the “real” main function is stored (which we keep separate for testing).
• A program for your tests.
  • test_utils.h/test_utils.cpp
  • tests.cpp

The C++ STL and the vector Class

The C++ Standard Template Library (STL) is a collection of templated definitions which are useful in developing C++ programs. In this course, we discuss how to create data structures and algorithms which operate over them. The STL is an existing implementation of many of these concepts (and more) and, rather than reinventing the metaphorical wheel, one would typically use these data structures (or others from a similar library) when writing C++ programs.

The vector class is one of the classes defined by the C++ STL. It provides functionality very similar to that of the ArrayList class (though it should be noted that it is not circular). For this lab, you should use the vector class when you need a list; this is mandated by several of the method signatures in the assignment. Here is a brief summary of the differences between using one of our List data types and the vector class from the STL:

There are several good resources for documentation on the vector class that can be found with a quick web search. For example, here’s one.

Copying

The vector variables in this lab contain only vector objects; they do not contain pointers. Conveniently, the vector class is implemented such that it may be returned, passed as an argument, or otherwise copied in the same way as basic C++ types (like int). So you can write

  vector<int> a;
  a.push_back(4);
  vector<int> b = a; // copies the contents of vector a into vector b
  a.pop_back();
  cout << b[0] << endl; // prints 4; does not crash

Copying vectors like this isn’t a good idea all of the time, of course; it could be quite inefficient depending on how big the list is. For this assignment, however, we copy only very small vectors (e.g. the vector of neighbors). Also, because the vectors can be statically allocated, you’ll have far fewer memory management problems to deal with!

Featured Labyrinths

The provided test data for this assignment includes labyrinth map files which have multiple kinds of non-wall spaces. Each non-wall space is associated with a cost that describes how much work it is to travel through that space.

• Open space (.): this is a normal open position in the labyrinth. Cost: 1.
• Mud (_): this space is covered in mud and difficult to walk through. Cost: 2.
• Water (~): this space is submerged and requires you to swim. Cost: 4.
• Bees (b): this space contains bees. They’re grumpy on account of being stuck in a labyrinth. Cost: 10.

As with the previous lab, the code to read these map files has been provided for you. You should familiarize yourself with the Labyrinth2 and Position classes in this new assignment to see how this information is stored. In particular, the feature.h file contains the declaration of an enum type called feature_type; this creates a new type that can be used in your code. There are only five values of type feature_type and they are stored in the variables space, wall, mud, and so on.

Your objective isn’t just to find any path through the labyrinth; you must find the one which takes the least effort. This is in contrast to the previous lab, where any valid solution was acceptable.

Dijkstra’s Algorithm

To solve a featured labyrinth, we’ll use a weighted version of the breadth-first search algorithm called Dijkstra’s Algorithm (named after its creator, Edsger Dijkstra). This algorithm is very similar to the generalized searching algorithm we used in the previous labyrinth-solving lab. It is presented below with the differing parts printed in bold:

• Add the start position to your PriorityQueue data structure
• Mark the start position as having zero cost
• While there are positions left in the data structure:
  • Take a position from the data structure; call it the current position.
  • If the current position is the exit, then you’re finished!
  • Otherwise, for each neighbor of the current position that isn’t a wall:
    • Calculate the new cost of the neighbor as the sum of its feature cost and the cost of the current position
    • If the current cost of the neighbor is greater than the new cost:
      • Set the neighbor’s cost to the newly calculated cost
      • Record the current position as previous to the neighbor
      • Add the neighbor to the data structure

Just like last time, you can determine whether you found a path by whether you ever visit the bottom right corner of the map. In building your solution vector, though, note that there’s no easy way to insert at the front of a vector. (It’s possible, but relies upon concepts we haven’t discussed in class.) Instead, you can just do this:

• Starting from the end, add each position in the solution to the end of the vector (producing a backwards solution)
• Loop over the vector and swap e.g. the first element with the last, the second element with the second-to-last, etc.

You’re not required to use the above approach if you’d prefer to get your solution into the correct order in some other way.

Testing

As usual, you have been provided RUN_MAIN and CHECK_FILES_EQUAL. You should write tests in tests.cpp for your ArrayMinHeap data structure as well as for your Labyrinth2 class. The labyrinth2_main function might be a convenient way for you to test Labyrinth2, as it allows you to use the files in test_data easily.

Memory

Your program is required to run without any memory leaks or errors; you must free up all of the memory that you allocate and you must only use memory that you have allocated and initialized. We will use valgrind to determine if you have done this correctly, so you should as well. You should also consider using valgrind to find bugs in your program as you proceed; it’s one of two very powerful C++ debugging tools that we’ve discussed.

Coding Style Requirements

You are required to observe some good coding practices:

• You should pick meaningful variable names.

  // Good
  int* pixels = new int[size];
  // Bad
  int* p = new int[size];
  

• You should use correct and consistent indentation. Lines of code within a block (that is, surrounded by { and }) should be indented four spaces further than the lines surrounding them.

  // Good
  if (condition) {
      cout << "Test" << endl;
  }
  // Bad
  if (condition) {
  cout << "Test" << endl;
      }
  

• You should use a block whenever possible, even if it’s not necessary. This helps you avoid subtle or messy bugs in the future.

  // Good
  if (condition) {
      cout << "Something" << endl;
  }
  // Bad
  if (condition)
      cout << "Something" << endl;
  

• Any new methods or fields in your header files should have comments explaining their purpose and behavior. You are permitted to omit documentation for methods that are inherited from other classes; that is, if your class has a foo method because its superclass has a foo method, you don’t need to document that method.

  // Good
  public:
      /**
       * Saves this image object to a file.
       * @param file The already-open stream into which this image should be written.
       * @return The number of pixels in the saved image.
       * @throws runtime_error If the image could not be saved due to an I/O error.
       */
      int save(ofstream& file);
  
  // Bad
  public:
      int save(ofstream& file);
  

  Your method/field documentation does not have to be in the format above, but you must describe the method’s behavior, its parameters, its return value, and any exceptions that it may throw. (If you’re indifferent, the above syntax is a good one to know; it’s a de facto standard used by Javadoc, Doxygen, and other tools that automatically process source code comments into other formats like searchable webpages.)

Peer Review

As this is a team assignment, you are required to complete a peer review of your lab partner or partners. You must do this even if everything is fine. You should complete this peer review after you have turned in your assignment. The peer review comes in the form of a simple Google Form and can be accessed here; in most cases, it will likely take less than a minute to complete. If you have trouble accessing this peer review, please make sure that you are logged into Google using your Swarthmore credentials.

Your peer review will be kept private; only course staff will have access to this information. You can also update your peer review after you have submitted it. However, if you do not submit a peer review, you will lose points on your lab. Please don’t forget!

Summary of Requirements

When you are finished, you should have

• A completed implementation of ArrayMinHeap
• A Labyrinth2 class which uses Dijkstra’s algorithm
• Appropriate tests
• No memory errors!
• Code which conforms to the style requirements above
• A completed peer review