Slick Savy, the world’s stealthiest super-villain, is planning to take over the world. The plans Slick needs for this scheme are in an ultra secure safe deep within a Swiss bank. Evil mastermind that he is, Slick has already disabled the bank’s security, made his way to the safe, and retrieved the plans. Clever as he is, Slick somehow (conveniently) forgot to plan his escape! Luckily for Slick, there are two possible exits that he can use to leave the bank now that he has broken into his safe. One of them is a loading dock that opens into the bank’s parking garage. The other is Slick's private helipad. You need to help Slick by finding a suitable route from his safe’s current location to one of these two exit points. You will develop a number of algorithms that lead Slick from his safe out of the building.
The bank has a simple rectangular prism shape with square floors. A description of it will be provided by an input file using a 3-D coordinate system and special characters. The special characters and what they represent include:
Because Slick is stuck at the safe, you will begin your path from the safe.
You can travel north, south, east or west on each bank floor. You may also travel on stairways going up ('^') one floor, and on stairways going down ('v') one floor. Note that taking a stairway up leads directly to the same relative (row, col) location on the floor above. Similarly, taking a stairway down leads directly to the same relative (row,col) location on the floor below. This does not necessarily mean that a corresponding stairway of the opposite type exists at the same relative (row,col) location (although one could). That is, taking an “up” stairway from location (3,5) on the first floor always leads directly to location (3,5) on second floor. However, there may or may not be a corresponding down stairway at location (3,5) on the second floor even though there is an up stairway in location (3,5) on floor one.
You may not travel diagonally in the building, and you may not travel through walls. Some buildings may not be enclosed by walls and may have stairways leading beyond the top floor or below the bottom floor; you are to treat building edges and other ‘passages to nowhere’ (as well as walls) as impassable terrain.
Ultimately, your task will be to indicate Slick’s exit route from the safe using directional indicators ('n' for north, 'e' for east, 's' for south, 'w' for west, 'u' for up stairs, and 'd' for down stairs). More details on this are provided below.
The program gets its description of the building from a file that will be read from standard input. This input file is a simple text file specifying the layout of the building. We require that you make your program compatible with two input modes: map (M) and coordinate list (C).
Unlike output (see more below), the input file’s format is not specified on your command line when running your program. Instead, the first line of every input file should be a single character specifying the input mode, ‘M’ or ‘C’. For both input modes, the second line should be a single integer N, indicating the size of each (and every) floor of the building (each floor is N x N in size and all floors are the same size). On the third line (again, for both input modes), a single integer F should be listed indicating the number of floors in the building.
Comments may also be included in an input file.
Comment lines begin with a # and they are allowed anywhere in the file after the first three lines that specify the input mode and building size. When developing your test cases, it is good practice to place a comment on line 4 identifying what kind of test this building is designed for. Any floors with noteworthy characteristics for testing purposes should also be commented. By convention, a comment line identifying the floor number is placed before the map for that floor. Comments are allowed in either input mode.
Map input mode (M):
For this input mode, the file should contain a map of each floor, in order. The floors are specified beginning with the highest floor and working down. The lowest floor is floor 0; that is to say, the floors are 0-indexed.
A valid (M) mode input example file for a building that has three 8x8 floors:
M
8
3
# sample M mode input file, three 8x8 floors
#floor 2
WWWWWWWW
W......H
W..W.WWW
W.W..W.W
W..WW..W
W......W
W......W
WWW.vWWW
#floor 1
WWWWWWWW
W......W
W..W.WWW
W.W..W.W
W..WW..W
W......W
W^....SW
WWW.vWWW
#floor 0
WWWWWWWW
W..W.^WW
W....WWW
W..W...W
P..W...W
W...W..W
W...W..W
WWW...WW
Coordinate list input mode (C):
The file should (after the first three lines) contain a list of coordinates for at least all non-floor space coordinates in the building. Only one coordinate should appear on a given line. We do not require that the coordinates appear in any particular order. A coordinate is specified in precisely the following form: (row,col,floor,character). The x and y positions range from 0 to N-1, where N is the value specified at the top of the file; specifically: there is no row, or column ‘N’ (but there is a row and column ‘N-1’). By default, all unspecified coordinates within the building are of type ‘.’ (floor space); however, it is not invalid to redundantly specify them to be so.
Valid coordinates (for a building with three 4x4 floors):
(0,1,0,W)
(2,2,2,H)
(1,3,1,.) -- while it is valid to specify floor space, it is redundant!
Invalid coordinates (for a building with three 4x4 floors):
(1,2,-1,W) -- Floor -1 does not exist!
(1,2,3,.) -- Floor 3 does not exist!
(4,3,2,W) -- Row of index 4 does not exist!
(2, 3, 0, W) -- No spaces or other extra characters allowed!
3,1,2,W -- Parenthesis are required!
(2 3 2 W) -- The components of the coordinate must be separated by a comma!
A valid (C) mode input example file for a building that has three 8x8 floors:
C
8
3
#sample C mode input file, three 8x8 floors
(3,0,0,P)
(1,5,0,^)
(7,0,0,W)
(1,7,2,H)
(0,0,2,W)
(0,0,1,W)
(7,4,2,v)
(6,1,1,^)
(7,1,1,W)
(7,7,1,W)
(6,6,1,S)
(7,4,1,v)
You are to develop two routing schemes to get from the safe to an exit:
One of these routing schemes must (and will) lead you out of the building via the shortest path.
In the queue-based routing scheme, use a queue of locations within the building. Place the start location in the queue, and do the following:
In the stack-based routing scheme, proceed with the above steps; however, you will push and pop the locations rather than enqueuing and dequeuing them. You will need to expand on the above algorithms, but follow this basic outline for the queue and stack-based routing.
The program must run to completion within 30 seconds of total CPU time (user + system). Note, in most cases 30 seconds is more time than you should need. See the time manpage for more information. We may test the program on very large buildings (up to several million locations in the building). Be sure you are able to solve a large building within 30 seconds. Smaller buildings should run MUCH faster.
You are allowed and encouraged to use all parts of the C++ STL and the other standard header files for this project. You are not allowed to use other libraries (eg: boost).
The program will write its output to standard output. Similar to input, we require that you implement two possible output formats. Unlike input, however, the output format will be specified through a command- line argument ‘--output’, or ‘-o’, which may be followed by an argument of M or C (M for map output and C for coordinate list output). See the section on command line arguments below for more details.
For both output formats, you will show the path you took from start to finish. In both cases you should first print the number of rows/cols N and then the number of floors F of the bank.
For map (M) output mode, you should print the map of the rooms, replacing existing characters as needed to show the path you took. Beginning at the starting location, overwrite the characters in your path with ‘n’, ‘e’, ‘s’, ‘w’, ‘u’, or ‘d’ to indicate which space you moved to next. Do not overwrite the 'H' or 'P' at the end of the path (but do overwrite the 'S' at the beginning). For all spaces that are not a part of the path, simply reprint the original building space. You should discard all existing comments from the input file for the output file. However, do create comments to indicate the floor numbers and format them as shown below:
Thus, for the sample input file specified earlier, using the queue-based routing scheme and map (M) style output, you should produce the following output:
8
3
#floor 2
WWWWWWWW
W......H
W..W.WWW
W.W..W.W
W..WW..W
W......W
W......W
WWW.vWWW
#floor 1
WWWWWWWW
W......W
W..W.WWW
W.W..W.W
W..WW..W
W......W
W^..swwW
WWW.dWWW
#floor 0
WWWWWWWW
W..W.^WW
W....WWW
W..W...W
PwwW...W
W.nwW..W
W..nW..W
WWWnw.WW
Using the same input file but with the stack-based routing scheme, you should produce the following output:
8
3
#floor 2
WWWWWWWW
W.eeeeeH
WenW.WWW
WnW..W.W
WnwWW..W
W.n....W
Wen....W
WWW.vWWW
#floor 1
WWWWWWWW
W......W
W..W.WWW
W.W..W.W
W..WW..W
W......W
WuwwwwwW
WWW.vWWW
#floor 0
WWWWWWWW
W..W.^WW
W....WWW
W..W...W
P..W...W
W...W..W
W...W..W
WWW...WW
For (C) coordinate list output mode, you should print only the coordinates that make up the path you traveled. You should print them in order, from (and including) the starting position to the ‘H’ or ‘P’ (but you should not print the coordinate for ‘H’ or ‘P’). The coordinates should be printed in the same format as they are specified in coordinate list input mode (the (row,col,floor,character) format). The character of the coordinate should be ‘n’, ‘e’, ‘s’, ‘w’, ‘u’, or ‘d’ to indicate spatially which space is moved to next. You should discard all comments from the input file, but you should add one comment on line 3, just before you list the coordinates of the path that says “#path taken”.
The following are examples of correct output format in (C) coordinate list mode that reflect the same solution as the Map output format above:
For the queue solution:
8
3
#path taken
(6,6,1,w)
(6,5,1,w)
(6,4,1,s)
(7,4,1,d)
(7,4,0,w)
(7,3,0,n)
(6,3,0,n)
(5,3,0,w)
(5,2,0,n)
(4,2,0,w)
(4,1,0,w)
For Stack solution:
8
3
#path taken
(6,6,1,w)
(6,5,1,w)
(6,4,1,w)
(6,3,1,w)
(6,2,1,w)
(6,1,1,u)
(6,1,2,e)
(6,2,2,n)
(5,2,2,n)
(4,2,2,w)
(4,1,2,n)
(3,1,2,n)
(2,1,2,e)
(2,2,2,n)
(1,2,2,e)
(1,5,2,e)
(1,6,2,e)
There is only one acceptable solution per routing scheme for each map of the bank. If no valid route exists, the program should simply reprint the building with no route shown for Map output mode, and should have no coordinates listed after the “#path taken” comment in Coordinate list output mode.
Please note that the mode of input and output can vary. That is, the input mode may be Coordinate mode, but the output may be requested in Map mode and vise-versa. They may also be, but are not guaranteed to be, the same. Also note that unlike input, the output file’s format is specified through the command line.
Your program should take the following case-sensitive command line options (when we say a switch is "set", it means that it appears on the command line when you call the program):
Legal command line arguments must include exactly one of --stack or --queue (or their abbreviations -s or -q). If none are specified or more than one is specified, the program should print an informative message to standard error and exit(1).
Examples of legal command lines:
Examples of illegal command lines:
It is extremely frustrating to turn in code that you are 'certain' is functional and then receive half credit. We will be grading for correctness primarily by running your program on a number of test cases. If you have a single silly bug that causes most of the test cases to fail, you will get a very low score on that part of the project even though you completed 95% of the work. Most of your grade will come from correctness testing. Therefore, it is imperative that you test your code thoroughly. To help you do this we will require that you write and submit a suite of test cases that thoroughly test your project.
Your test cases will be used to test a suite of buggy solutions to the project. Part of your grade will be based on how many of the bugs are exposed by your test cases. (We say a bug is exposed by a test case if the test case causes the buggy solution to produce different output from a correct solution.)
Each test case should be an input file that describes a bank in either map (M) or coordinate list (C) format. Each test case file should be named test-n.txt where 0 < n <= 30 for each test case. All test cases will be run in both queue mode and stack mode. Test cases may have no more than 8 floors, and the size of a floor may not exceed 8x8. You may submit up to 30 test cases (though it is possible to get full credit with far fewer test cases). Note that the tests the autograder runs on your solution are NOT limited to 8x8x8; your solution should not impose any size limits (as long as sufficient system memory is available).
A small portion of your grade will be based on error checking. You must check for the following errors:
In all these cases, print an informative error message to standard error and exit(1).