Back to the Ship!
Due Thursday, January 26, 2023 at 11:59 PM
Overview
You have just broken out of the detention level of a large and strangely moon-like space station. You need to find your way back to your old spacecraft of questionable space-worthiness to escape. Your adorable robot friend has hacked into the elevator system of the space station to assist you in your escape.
Learning Objectives
These are the skills and concepts encountered in this project:
3D Maze: read, store, access, and write
Breadth first search (BFS w/ queue)
Depth first search (DFS w/ stack)
Map and coordinate list mode input
Map and coordinate list mode output
Use getopt_long() to handle command line arguments
Command Line Options
ship should take the following (optional) command line options:
--stack, -s
The search container will be used like a stack and the routing scheme will perform a depth first search (DFS). The stack option may be invoked by calling the program with either --stack or -s, it accepts no arguments.
--queue, -q
The search container will be used like a queue and the routing scheme will perform a breadth first search (BFS). The queue option may be invoked by calling the program with either --queue or -q, it accepts no arguments.
--output (M|L), -o (M|L)
Indicates the output file format by the required argument, M (map format) or L (coordinate list format). If this option is not provided when running the program, the default output format is map format. If specified, this option requires that an argument be provided, and the autograder will only use valid arguments.
--help, -h
This causes the program to print a helpful message about how to use the program and then immediately exit(0).
Legal command lines must include exactly one of --stack or --queue (or their respective short forms -s or -q). If none are specified or more than one is specified, the program should print an informative message to standard error (cerr) and exit(1).
Using getopt_long() will make this much easier. See Project 0 and the man page for getopt, for more information.
Legal Command Lines
$ ./ship --stack < infile > outfile
This will run the program using a stack and map output mode.
$ ./ship --queue --output M < infile > outfile
This will run the program using a queue and map output mode.
$ ./ship --stack --output L < infile > outfile
This will run the program using a stack and coordinate list output mode.
These examples use the shell redirection operators < and > to redirect standard input (cin) and standard output (cout). This is a convenient way to read input from a file and write output to a file, without having to write any code to open and close files. The operating system “connects” cin to read the input file, and print statements to cout to the output file.
Illegal Command Lines
$ ./ship --queue -s < infile > outfile
Contradictory choice of routing, both stack and queue are specified.
$ ./ship < infile > outfile
You must specify one of stack or queue options.
$ ./ship -o < infile > outfile
Output option requires an argument describing the output mode.
Space Station Layout
A space station is composed of up to 10 square levels with elevators to travel between levels. The description of a space station will be provided by an input file using a 3-D coordinate system and special characters.
The special characters and what they represent:
’.’ floor space
’#’ walls (the only character that cannot be walked on/through)
‘S’ your starting location at the detention level
‘H’ the hangar of the spacecraft location (the goal)
‘E’ corresponds to elevators that transport you from that location to the same row and column of the levels that have an elevator on the same location
You may discover new locations north, east, south or west from any floor space (.) as well as the starting location (S); no discoveries may be made diagonally. Elevators allow discovery and travel between levels, when an elevator (E) is located in the same row and column on different levels, and are the only way to change levels. Your path planning program must check that it does not move off of the map or onto walls (#).
Levels are implicitly enclosed by walls that are not included in input files; you are to treat both level edges and walls as impassable terrain.
Ultimately, your task will be to indicate your route to the hangar tile from your starting location using directional indicators (‘n’ for north, ‘e’ for east, ‘s’ for south, ‘w’ for west, and 0-9 to indicate where you got off the elevator). More details on this are provided below.
Input File Formats
The program gets its description of the space station from a file that will be read from standard input (cin). This input file is a simple text file specifying the layout of the space station. We require that you make your program compatible with two input modes: Map Mode (M) and coordinate list mode (L).
The reason for having two input modes is that a large percentage of the runtime of your program will be spent on reading input or writing output. Coordinate list mode exists so that we can express very large graphs with relatively few lines of a file, map input mode exists to express dense graphs (ones for which most of the tiles are not just floor space) in the smallest number of lines. You should use std::ios::sync_with_stdio(false) - this makes a very significant runtime difference.
The first three lines of any input file are called the “file header” and they will be formatted as follows:
The first line of every input file will be a single character specifying the input mode, M or L. Input file format is given in the file, unlike the output mode, which can only be given as a command line option.
The second line will be a single, positive integer 1≤l≤10, indicating the number of levels in the space station.
The third line will be a single, positive integer n≥2, indicating the size of every level of the space station. Each level is n×n in size.
Comments may also be included in any input file. Comment lines begin with // and they are allowed anywhere in any file, after the file header. When developing your test files, it is good practice to place a comment on line 4 describing the nature of the space station in the test file. Any levels with noteworthy characteristics for testing purposes should also be commented. By convention, a comment line identifying the level number is placed before the map of that level, but this is not required and the format is not guaranteed.
After the file header, the input file will contain the space station layout in one of the two modes listed above and described below.
Additionally, there may be extra blank/empty lines at the end of any input file - your program should ignore them. If you see a blank line in the file, you may assume that you have hit the end (but do not have to check for this).
Map Input Mode
For this input mode, the file header will start with an ‘M’ and contain a 2D map of characters defining each level, starting with level 0 and ending with level l−1.
A map input mode example file for a space station that has two 4x4 levels:
p1-back-to-the-ship/spec-m.txt
M
2
4
//sample M mode input file with two 4x4 levels
//level 0
.H..
....
E..S
#..#
//level 1
....
#...
E#..
#...
Coordinate List Input Mode
For this input mode, the file header will start with an ‘L’ and contain a list of coordinates for at least all non-floor space characters in the space station. A coordinate is specified in precisely the following form: (level,row,column,character). The level values will be in the range [0,l), and the row and column values will be in the range [0,n). Only one coordinate will appear on each line, and there is no guarantee that the coordinates will be grouped by floor or ordered in any way. By default, all unspecified coordinates within the space station are of type ‘.’ (floor space); however, it is not invalid to redundantly specify them to be so.
Valid coordinates (for a space station with three 4x4 levels):
(0,0,1,#)
(2,2,2,H)
(1,1,3,.) -- Unnecessary, but valid
Invalid coordinates (for a space station with three 4x4 levels):
(9,1,2,#) -- level 9 does not exist
(3,4,2,.) -- row 4 does not exist
(2,1,5,#) -- column 5 does not exist
(0,0,1,F) -- 'F' is an invalid map character
A coordinate list input mode example file with two 4x4 levels, equivalent to the example above:
p1-back-to-the-ship/spec-l.txt
L
2
4
//sample L mode input file, two 4x4 levels
(1,1,0,#)
(1,2,1,#)
(1,3,0,#)
(0,0,1,H)
(0,2,0,E)
(1,2,0,E)
(0,2,3,S)
(0,3,0,#)
(0,3,3,#)
Routing schemes
You are to develop two routing schemes to get from the starting location to the hangar location tile:
A routing scheme that uses a queue as the search container
A routing scheme that uses a stack as the search container
Both of these routing schemes will always lead you to the hangar (if a path exists). Whether you’re supposed to be using stack or queue based, the algorithm is basically the same. Read the “Project 1 the STL and You” file, it will tell you (among many other useful things) how to use a single data structure, a deque, and allow you to write one version of the code for both routing schemes.
We’re going to use a few terms here, and try to be consistent about them in the project specification, office hours, Piazza, etc.
Search container (the deque) is where you add things to help you find the hangar. Think of this as the places that might help you get to the hangar, but haven’t had a chance to investigate yet.
Discovered means that this square has been added to the search container. You can never discover the same location twice (this prevents infinite loops and other problems). You must keep track of what has been discovered and what has not.
Investigate is when a location comes out of the deque, and you start to determine what other locations it helps you to discover. There is no need to track what has or has not been investigated.
Create a search container. Before you start looping, add the starting location to the search container, and mark it as discovered. As long as the search container is not empty, do the following:
1.Take the “next location” from the search container; we will refer to this as the current location. Remove it from the search container.
2.Investigate the current location, which means discover all of the locations that are reachable from the current location. For each one, if it is off the edge, a wall, or already discovered before, ignore it. Otherwise, add it to the search container and mark it as discovered. Check in this order: N, E, S, W. If the current location is an elevator (floor tile ‘E’), you should also discover elevators on every other level at the same row and column. Starting from the lowest level (0) to the highest level (l−1). If any other levels have an ‘E’ in the same row/column, and they are not discovered, each should be added to the search container and marked as discovered.
3.As soon as you find the hangar tile H, you should stop searching. If you don’t stop, loop back to step 1.
The only difference between an elevator and a non-elevator tile is what positions you are allowed to discover. You still have to check that you haven’t discovered a location before discovering it.
One important point to remember: when we talk about the routing scheme, adding things to the search container, etc.: you (the person) are not moving yet! Until your trusty robot companion uses this program to find the route that will get you to the hangar, you stay put. If you start asking questions like “how did I teleport from level 0, row 1, column 2 to level 3, row 5, column 4?”, remember that YOU didn’t move yet. The program investigated a different location that just happened to be far away from the last location it investigated. Once your robot is done running the program, it will produce output (a map or list of directions) for you to follow, and that set of directions will make sense for you: you’ll go north, go east, take an elevator to level 2, go south, etc.
The program must run to completion within 35 seconds of total CPU time (user time). In most cases 35 seconds is more time than you should need. See the time manpage for more information (this can be done by entering “man time” to the command line). We may test your program on very large space stations (up to several million locations). Be sure you are able to navigate to the hangar tile in large space stations within 35 seconds. Smaller space stations should run MUCH faster.
Output file format
The program will write its output to standard output (cout). 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 option –output, or -o, which will be followed by an argument of M or L (M for map output and L 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.
Map output mode (M):
For this output mode, you should print the map of the levels, 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’, or ‘0-9’ (where you got off the elevator) to indicate which tile you moved to next. Elevator tiles that you use in your final path should be overwritten with the number of the level where you exited the elevator. Do not overwrite the ‘H’ 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 space station space. You should discard all existing comments from the input file for the output file. However, do create comments to indicate the level numbers and format them as shown below. Before any other output, state the starting location, so that the map is easier to follow.
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:
Start in level 0, row 2, column 3
//level 0
.Hww
...n
E..n
#..#
//level 1
....
#...
E#..
#...
Using the same input file but with the stack-based routing scheme, you should produce the following output:
Start in level 0, row 2, column 3
//level 0
eH..
n...
nwww
#..#
//level 1
....
#...
E#..
#...
Coordinate list output mode (L):
For this output mode, you should print only the coordinates that make up the path you traveled. Print [each step of] your path from the start to the hangar and omit the hangar itself. The coordinates should be printed in the same format as they are specified in coordinate list input mode (the (level,row,column,character) format). The character of the coordinate should be ‘n’, ‘e’, ‘s’, ‘w’, or ‘0-9’ (where you got off the elevator) to indicate spatially which tile is moved to next. You should discard all comments from the input file, but you should add one comment on line 1, just before you list the coordinates of the path that says “//path taken”. There’s no need to state the starting location in this mode, since it would be the first line after the “//path taken”.
The following are examples of correct output format in (L) coordinate list mode that reflect the same solution as the Map output format above:
For the queue solution:
//path taken
(0,2,3,n)
(0,1,3,n)
(0,0,3,w)
(0,0,2,w)
For the stack solution:
//path taken
(0,2,3,w)
(0,2,2,w)
(0,2,1,w)
(0,2,0,n)
(0,1,0,n)
(0,0,0,e)
There is only one acceptable solution per routing scheme for each map of the space station. If no valid route exists, the program should simply reprint the space station with no route shown for Map output mode, and should have no coordinates listed after the “//path taken” comment in List output mode.
The mode of input and output can differ. That is, the input mode may be List mode, but the output may be requested in Map mode and vise-versa. They may also be the same (but are not guaranteed to be).
Test files
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 files. If you have a single silly bug that causes most of the test cases on the autograder 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 files that thoroughly test your project.
Your test files 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 files. (We say a bug is exposed by a test file if the test file causes the buggy solution to produce different output from a correct solution.)
Each test file should be an input file that describes a space station in either map (M) or coordinate list (L) format. Each test file file should be named test-n-flags.txt where 0 < n <= 15 for each test file. The “flags” portion should include a combination of letters of flags to enable. Valid letters in the flags portion of the filename are:
s: Run stack mode
q: Run queue mode
m: Produce map mode output
l: Produce list mode output
The flags that you specify as part of your test filename should allow us to produce a valid command line. For instance, don’t include both s and q, but include one of them; include m or l, but if you leave it off, we’ll run in map output mode. For example, a valid test file might be named test-1-sl.txt (stack mode, list output). Given this test file name, we would run your program with a command line similar to the following (we might use long or short options, such as –output instead of -o):
./ship -s --output L < test-1-sl.txt > test-1-output.txt
Test files may have no more than 10 levels, and the size of a level may not exceed 8x8. You may submit up to 15 test files (though it is possible to get full credit with fewer test files). The tests the autograder runs on your solution are NOT limited to 10x8x8; your solution should not impose any size limits smaller than 65,535 (as long as sufficient system memory is available).
Errors you must check for
A small portion of your grade will be based on error checking. You must check for the following errors:
Input errors: illegal map characters, such as F. Check this for both map/list input modes.
For coordinate list input mode, you must check that the row, column, and level numbers of each coordinate are all valid.
More or less than one –stack or –queue (or -s or -q) on the command line.
You may assume the command line will otherwise be correct (this also means that we will not give you characters other than ‘M’ or ‘L’ following –output or -o).
In all of these cases, print an informative error message to standard error and exit(1). Read the file Error_messages.txt for standard error messages and why to use them. You do not need to check for any other errors.
Assumptions you may make
We will not put extra characters after the end of a line of the map or after a coordinate.
Coordinates in coordinate list input mode will be in the format (level,row,col,character).
There will be exactly one start location ‘S’ and exactly one spacecraft hangar tile ‘H’ in the space station.
We will not give you the same coordinate twice for the coordinate list input mode.
The input mode line and the integer dimensions of the space station on lines two and three at the beginning of the input file will be by themselves, without interspersed comments, and that they will be correct.
If you see a single ‘/’ character at the beginning of a line, you can assume it is a comment. This makes reading the list mode input MUCH easier.
You will never be given negative numbers for the number of levels, the size of the map, or any portion of a coordinate in list input mode. You can assume that all of these numbers will fit within an unsigned int or uint32_t variable.
Submitting your solution
Project Identifier
You MUST include the project identifier at the top of all source and header files that you submit:
//
Do all of your work (with all needed files, as well as test files) in some directory other than your home directory. This will be your “submit directory”. Before you turn in your code, be sure that:
You have deleted all .o files and your executable(s). Typing ‘make clean’ shall accomplish this.
Your test files are named test-n-flags.txt and no other project file names begin with test. Up to 15 test files may be submitted.
The total size of your program and test files does not exceed 2MB.
You don’t have any unnecessary files or other junk in your submit directory and your submit directory has no subdirectories.
Your code compiles and runs correctly using the g++ compiler. This is available on the CAEN Linux systems (that you can access via login.engin.umich.edu). Even if everything seems to work on another operating system or with different versions of GCC, the course staff will not support anything other than GCC running on CAEN Linux. To keep the compiler used on CAEN in sync with the autograder, we want you to use version 6.2.0 (available on CAEN with the command module load gcc/6.2.0 and/or with a Makefile).
Libraries and Restrictions
Unless otherwise stated, 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, pthread, etc). You are not allowed to use the regular expressions library (it is not fully implemented on gcc) or the thread/atomics libraries (it spoils runtime measurements). Do not use the STL’s unique or shared pointers.
Grading
80 points – Your grade will be primarily based on the correctness of your algorithms. Your program must have correct and working stack and queue algorithms and support both types of input and output modes. Additionally: Part of your grade will be derived from the runtime performance of your algorithms. Fast running algorithms will receive all possible performance points. Slower running algorithms may receive only a portion of the performance points.
10 points – Test file coverage (effectiveness at exposing buggy solutions).
10 points – Your program does not lose any memory as reported by valgrind. Memory that is “still reachable” is fine, but any of the three types of “lost” will lose points.
Grading will be done by the autograder.
Coding style
Your grade will not be directly based upon your coding style. However, a better coding style will make your code easier to write, debug, and get help on. Good coding style consists of the following:
Clean organization and consistency throughout your overall program
Proper partitioning of code into header and cpp files
Descriptive variable names and proper use of C++ idioms
Effective use of library (STL) code
Omitting global variables, unnecessary literals, or unused libraries
Effective use of comments
Reasonable formatting - e.g an 80 column display
Code reuse/no excessive copy-pasted code blocks
Effective use of comments includes stating preconditions, invariants, and postconditions, explaining non-obvious code, and stating big-Oh complexity where appropriate.
It is extremely helpful to compile your code with the gcc options:
-Wall -Wextra -pedantic
This will help you catch bugs in your code early by having the compiler point out when you write code that is either of poor style or might result in behavior that you did not intend.