Project 1 - Maze Solver

Updates

• Sep 22 Added ruby script goTest.rb to run public tests.

• Sep 13 Corrected "hello world" path coordinates at the end of the "Maze Data File Format" section: should have been (0,2), (0,1), (1,1), (1,2), ...

Introduction

As we saw in lecture, Ruby provides rich support for tasks that involve text processing. For this project, you'll write a Ruby program that processes text files containing maze data, and you will analyze that data to determine certain features of each maze. The goal of this project is to allow you to familiarize yourself with Ruby's built-in data structures and text processing capabilities.

Getting Started

• Your Ruby program - maze.rb
• Test inputs (sample maze data files)
  • maze1
  • maze2
  • maze3
  • maze4
• Test outputs (maze.rb output)
  • maze1.validate.out
  • maze1.closed.out
  • maze1.open.out
  • maze1.room.out
  • maze1.paths.out
  • maze1.print.out
  • maze1.solve.out
  • maze2.validate.out
  • maze2.paths.out
  • maze2.print.out
  • maze2.solve.out
  • maze3.validate.out
  • maze4.validate.out
• Submission scripts
  • submit.jar
  • .submit (Your OS may prevent you from seeing this file because it believes it is a system file)
  • submit.rb
• Test script
  • goTest.rb - script to run public tests

Maze Data File Format

The maze data files have a relatively simple structure. Here's an example:

  maze: 16 0:2 -> 13:11
  0,0: du 123.456,0.123456
  0,1: uldr 43.3,5894.2341,20.0,5896.904
  ...
  "path1:(0,2),u,r,d,...,l","path2:(0,2),d,r,l,...,r"

The first line in the file is the maze header. It has the form:

  maze: <size> <start_x>:<start_y> -> <end_x>:<end_y>

These fields indicate (respectively) the size of the maze and the (x,y) coordinates for the start and end points. Coordinates start in the upper left-hand corner of the maze and increase as they move down and right. For example, in a maze of size 16, (0,0) is the upper-left corner, and (15,15) is the lower-right corner. You should assume that all mazes are square. For example,

  16 5:9 -> 11:2

represents a maze with x and y dimensions of length 16; it starts at (5, 9) and ends at (11, 2).

Unlike common mazes that one might find on paper, the start and end points are arbitrary points inside the maze. A valid maze has no openings in the outer wall. The outer perimeter of the maze is a single, solid wall, so you needn't worry about accidentally walking through an open wall out into the space outside the maze.

Every line beyond the first can represent either a cell in the maze or a path through the maze.

Lines representing cells take the form:

<x>,<y>: <dirs (can be any combination of 'udlr')> <comma separated weights>

Following the coordinates is a colon, some optional whitespace, and a set of up four "open wall" characters, and a comma-separated list of floating point weights. For example,

  4,7: lur 1.3,5.6,8.2

indicates that the cell at coordinates (4,7) has open walls that lead up, left, and right from that cell. The characters can appear in any order, but may only include "udlr", and each letter may appear at most once. A wall is not open if its representative character is not in this list. Following the list of open walls is a list of weights for each wall. These appear in the same order as the open walls: in the example above, the left opening has weight 1.3, the up opening has weight 5.6, and the right opening has weight 8.2. We'll explain what these weights will be used for later.

Lines representing paths take the form:

  "path1_name:(<start x>,<start y>),<move 1>,<move 2>,...","path2_name:(<start x>,<start y>),..."

This "path line" contains a comma separated list of paths; each path is contained within a pair of quotation marks ("). Multiple paths can appear on the same line in the file. Each path consists of a name and a comma-separated list of coordinate values. Note that path names can contain any character except colon, and quotation marks in path names will be escaped (\"). Each path starts with its x/y start coordinate enclosed in parentheses. The start coordinate is followed by a single comma, after which begins a comma delimited list of directions (which we'll call "moves") that the path takes to reach its destination.

Maze files do not necessarily contain paths; some maze files will have paths, while others will not. There may be zero or more lines of paths in each maze file. In actual paths, the start coordinates must consist only of integers, and directions may only include the letters "u," "d," "l," and "r,"; the example below shows path data with each distinct path identified by labels (which will not appear in the data files):

  "path 1:(0,2),l,...","path \"2\":(0,2),d,..."
  [    first path    ] [   second path        ]

In the example

  "hello world:(0,2),u,r,d,...","\"goodbye world\":(0,2),d,r,..."

The first path (named "hello world") starts at (0,2), continuing to (0,1), (1,1), (1,2), and so on. The second path (named "\"goodbye world\"") also starts at (0,2), but instead moves to (0,3), (1,3) and so on.

For this assignment, coordinate (0, 0) is the upper-left corner of the maze and (<size - 1>, <size - 1>) is the lower-right corner. This means that moving down from a cell increases its y value, and moving right from a cell increases its x value. Thus going up from (5, 8) would take you to (5, 7), going down would take you to (5, 9); going left or right would respectively lead to (4, 8) and (6, 8).

Part 1: Validating Maze Data Files

The first part of this project is to write a "mode" for maze.rb that validates that an input file contains maze data and not, e.g., Aunt Bertha's secret apple pie recipe. We will invoke your program with

In response, your script should output exactly one line of text and then exit. That line should either contain the three letters yes followed by a newline if the file is valid, or the two letters no followed by a newline otherwise.

A valid file contains zero or more lines of text, each of which ends in a newline. (Hint: There are Ruby methods to read in a single line of text at a time.) The first line in the file must be in the header format, and each following line must be in either the cell or path format. Additionally, you must check the following:

• That all of the cells fall within the specified size of the maze. For example, if the maze is of size 16, a cell with coordinates (15, 5) would be within the maze, while one with coordinates (16, 2) would not (remember that cells are zero-indexed).
• That all openings between adjacent cells go in both directions. For example, if the cell line

    4,7: ulr ...

  is found in a file (... in this example means some weight values), then the line

    4,6: dr ...

  would be valid, but the line

    4,6: r ...

  would be invalid. This is because the cell at (4, 7) has an open wall that leads "up" to (4, 6), but (4, 6) has a closed downward wall, and so (4, 7) cannot be reached from there.
• That all of the perimeter cells (i.e. cells with x or y values of 0 or the size of the maze minus one) have closed outer walls. That is, all cells at the outermost edge of the maze should have walls that prevent you from wondering outside of the maze. A maze is invalid if one or more cells at the perimeter of the maze have open walls in directions that would allow you to go outside the bounds of the maze. In a maze of size 16, the line

    15,6: ul ...

  would be valid, but

    15,6: ulr ...

  would be invalid, since the (open) right wall is on the outer edge of the maze.
• That each cell line has exactly as many weight values as it does open walls. While you will need to ensure that walls are open in both directions, they do not need to have the same weight in both directions—you should only check that these weights are floating point numbers and that the correct number of weights exist. Note: floating point numbers can appear in exponential form (like 123.456789e+25 or 123.456789e-25) as well as the standard form (like 123.456).
• That each path contains only "legal" moves (for mazes that contain any paths at all). A "legal" move on a path is represented by one of "udlr" and passes through an open wall of the current cell. For example, if the cell line

   5,6: dr 1.2,3.4

  appears in the file, the move

   "example path:(5,6),r,..." 

  would be valid, since it represents a move from (5,6) to the cell to its right (6,6), and the right wall is open. However, the move

   "example path:(5,6),u,..." 

  is invalid since it moves through the closed upward wall.

We will test this part of the project by (a) making valid inputs and verifying that your program accepts them, and (b) making invalid inputs and verifying that your program rejects them.

Part 2: Maze Properties

Next, you're going to add a feature to your Ruby script to output some interesting attributes of the maze. In particular, there are three properties of a maze that your script needs to be able to find: the number of closed cells, the number of open walls in each direction, and the maximum "room size." You can assume for this and the remaining parts of the project that the input maze is valid.

First, if we invoke your script with the mode closed, your script should output one line listing exactly the number of closed cells in the maze, where a closed cell is one with no open walls. For example,

% ruby maze.rb closed maze1
2

Second, if we invoke your script with the open mode, your script should output the number of open walls in each direction, in the order u, d, l, r. They should be formatted exactly as appears below.

% ruby maze.rb open maze1
u: 8, d: 8, l: 7, r: 7

Finally, if we invoke your script with the room mode, your script should output the maximum "room" size in the maze. A room is defined as a block of adjacent cells with all walls open. The block of cells can be in any shape, but all cells in the block must have all four walls open.

% ruby maze.rb room maze1
2

Part 3: Which Path is Least Expensive?

As described in the introduction, some maze files will contain paths. These paths run from the start cell of the maze to its end cell. You will need to use the weights for each opening in the maze to calculate the cost of each path, and then sort the paths in order of cost from lowest to highest. For example, if the coordinates

  "example path:(0,1),d,r,d,u,..."

appear in a path, and the cell at (0,1) is defined as

 0,1: ldr 342.54,958.1,3.126

the cost of the first move in the path will be 958.1 (the weight for the "d" opening). The cost of a whole path is the sum of the weight of each opening through which it passes.

Your program should print a comma separated list of the name of each path in order of cost from lowest to highest. If a path name contains escaped quotes, you must unescape them: the name path \"3\" should be converted to path "3".

% ruby maze.rb paths maze5
path 1, path "3", path 0, path 2

This means that the path named "path 1" was the least expensive, the path named "path \"3\"" was the second least expensive, the path named "path 0" was the third least expensive, etc.

If a maze contains no paths, your program should simply print a blank line.

% ruby maze.rb paths maze6

The file maze6 contains no paths, and so only a blank line is printed.

Part 4: Maze Pretty-Printer

It is difficult to understand the layout of the mazes in this assignment thanks to their textual format. For this part of the assignment, you'll implement a "pretty-printing" function for mazes. Your pretty print format will use the following conventions:

• Each cell will be represented by either a space, the letter "s" (for the start cell), or the letter "e" (for the end cell).
• Left/right walls will be represented by a pipe character "|", up/down walls will be represented by a dash "-", and wall junctions will be represented with a plus "+".

Your program will print a maze in this format when executed with the "print" command.

For example:

ruby maze.rb print maze1
+-+-+-+-+
|s|   | |
+ + + +-+
|       |
+-+ + + +
|     | |
+ +-+ +-+
| | |  e|
+-+-+-+-+

In this example, the maze starts at (0,0) and ends at (3,3). Each cell is represented by " ", "s", or "e"; walls are represented by "|" or "-", and are joined by "+" characters.

Part 5: Can The Maze Be Solved?

Finally, we want to use your script to determine whether or not a maze can be solved. The way we recommend you do this is by actually finding a path from the start to the end (that is, by solving the maze!).

We recommend you do this by implementing breath-first or depth-first search for you maze representation. If, after exploring all cells that are reachable (through open walls) from the start cell, you have not reached the end cell, the maze cannot be solved. If you encounter the end cell while traversing the maze, there exists a path from start to finish, and the maze can be solved. There may be multiple paths from the start cell of a maze to its end cell, but your program need only find one.

Note that you do not need to return the length of the path from start to finish—your program will only need indicate whether a path exists by printing "true" when a maze can be solved and "false" otherwise.

% ruby maze.rb solve maze1
true

Project Submission

where <mode> describes what the tool should do (see below), and <file-name> names the file containing the maze data.

Be sure to follow the project description below exactly. Your solution will be graded automatically, and so any deviation from the specification will result in losing points. In particular, if you have any debugging output in your program, be sure to turn it off before you submit your program.

• Submit your maze.rb file directly to the submit server by clicking on the submit link in the column "web submission".

  

  Next, use the submit dialog to submit your maze.rb file directly.

  

  Select your file using the "Browse" button, then press the "Submit project!" button. You do not need to put it in a Jar or Zip file.

• Submit directly by executing a Java program on a computer with Java and network access. Included in p1.zip are the following files:
  • submit.jar
  • .submit (Your OS may prevent you from seeing this file because it believes it is a system file)
  • submit.rb

  The files should be in the directory containing your project. From there you can either execute submit.rb, or type the following command directly:

  java -jar submit.jar

  The first time you submit this way you will be asked to enter your linuxlab class account and password. All files in the directory (and its subdirectories) will then be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

  Successful submission # received for project 1

Hints and Tips

• This project is non-trivial, in part because you will probably be writing in Ruby for the first time, so be sure to start right away, and come to office hours if you get stuck.
• Follow good program development practices: Test each part of your program as you develop it. Start developing a simplified solution and then add features as you are sure that earlier parts work. Test early and often, and re-run your tests as you add new features to be sure you didn't break anything.
• Before you get too far, review the Ruby class reference, and look for classes and methods that might be helpful. For example, the Array and Hash classes will come in handy. Finding the right class might save you a lot of time and make your program easier to develop.
• If you write methods that should return a true or false value, remember that a Ruby 0 is not false.
• Ruby has an integrated debugger, which can be invoked by running Ruby with the -rdebug option. The debugger's p command may be helpful for viewing the values of variables and data structures. The var local command prints all of the local variables at the current point of exclusion. The chapter "When Trouble Strikes" of The Pragmatic Programmer's Guide discusses the debugger in more detail.
• To thoroughly debug your program, you will need to construct test cases of your own, based on the project description. If you need help with this, please come to TA office hours.
• Remember to save your work frequently---a power failure, network failure, or problem with a phone connection could cost many hours of lost work. For the same reason, submit your project often. You can retrieve previously-submitted versions of your program from the submit server should disaster strike.
• Be sure you have read and understand the project grading policies in the course syllabus. Do this well in advance of the project due date.

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.