EECS281 Data Structures and Algorithms - Project 1: Back to the Ship!
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)
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.
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
- 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.
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
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)
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.
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:
- Take the “next location” from the search container; we will refer to this as the current location. Remove it from the search container.
- 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
- As soon as you find the hangar tile H, you should stop searching. If you don’t stop, loop back to step 1.
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.
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”.
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.
./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).
