EECS 281 Winter 2021
Project 1:
Rescue the Countess
Due Tuesday, February 9, 11:59 PM
Overview
Its a-me, Marco! Marco of the Fungus Province has just received news that Louser has taken Countess Cherry captive in his dark, maze-like castle. With his twin brother, Luigino, Marco has traveled many miles to reach the castle, dodging flying shells and jumping on angry mushrooms. Now that he has entered the castle, he needs your help to rescue the Countess. Using C++, you must implement some basic path finding algorithms to guide Marco to the Countess and foil Lousers evil plans!
Castle Layout
You must help Marco navigate through Lousers castle. The castle contains up to 10 rooms, with warp pipes to travel between them. The rooms are all squares of the same size (NxN).
Your program will be given a map or description of the castle that uses the following symbols:
. walkable room space
# walls (which cannot be walked on or through)
! one of Lousers minions (which cannot be walked on or through)
A digit 0 to 9 which indicates a warp pipe traveling to the same spot in the room
with the corresponding number
S Marcos starting location
C location of Countess Cherry
You can assume, for the files that we give you, that there is exactly one location for Countess Cherry and exactly one starting point for Marco. You still might want to verify this, just in case an input file that you create breaks this rule.
Because you have a copy of the castle map, your task is to plan a path for Marco from the starting position (S) to the Countess (C) that does not pass through any walls (#) or minions (!). Marco can walk next to the minions, but cannot walk on top of them. Marco doesnt have time to get in a fight today!
Rooms are to be treated as if they are surrounded by walls; you are to treat both walls and room edges as impassable terrain.
Marco can discover new locations north, east, south or west from any room space (.) as well
Version 1-20-21
2021 Regents of the University of Michigan
1
as the starting location; no discoveries may be made diagonally. Your path planning program must check that it does not move Marco off of the map, onto walls (#), or onto minions (!).
In addition, when Marco steps onto a warp pipe (digits 0-9), he will only be able to discover the location in the same row and column of the room corresponding to the warp pipes number. If Marco steps on a warp pipe with digit, d, at row and column (r, c), in any room, then hell be able to discover (r, c) in the room d. It is possible for this to continue from warp pipe to warp pipe, if there are multiple rooms with warp pipes in the same location.
If room d doesnt exist, no new location can be discovered. Youll need to check for this. For example, a castle with 2 rooms might have a pipe labelled 5, but room 5 does not exist, so Marco wont use this pipe.
Input file format (The Castle Map)
The program gets its description of the castle from a file that will be read from standard input (cin). This input file is a simple text file specifying the layout of the castle. We require that you make your program compatible with two input modes: map (M) and coordinate list (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 maps with a minimal amount of input data; map input mode exists to express maps whose input files are also easily human readable.
For both input modes (M and L):
The first line of every input file will be a single character specifying the input mode, M or L (without quote marks). Unlike the output mode, which is given on the command line (see below), this is part of the input file.
The second line will be a single integer 1 R 10 indicating the number of rooms.
The third line will be a single integer 1 N, indicating the size of each (and every) room
of the castle (each room is NxN in size and all rooms are the same size).
You can assume that N (and thus a row or a column index) will fit inside of an unsigned integer
variable (unsigned int or u int32_t),.
Comment lines begin with // and they are allowed anywhere in the file after the first three lines. When developing your test files, it is good practice to place a comment on line 4 describing the nature of the castle in the test file. Any castles with noteworthy characteristics for testing purposes should be commented. The map file is also easier to read if there is a comment line identifying the room number before the description of that room, but this is not required. Comments are allowed in either input mode.
Version 1-20-21
2021 Regents of the University of Michigan
2
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.
Map input mode (M):
For this input mode, the file should contain a map of each room, in order. The rooms are specified beginning with the lowest number room and working up. The lowest room is room 0; that is to say, the rooms are 0-indexed.
An example map mode input file for a castle with two 44 rooms:
M
2
4
//sample M mode input file with two 44 rooms //castle room 0
.C..
.
S
#.1#
//castle room 1 .
#
.!..
#
BEWARE: DO NOT copy/paste from a PDF file! PDF files contain ligatures (invisible characters) that may cause your code (or the autograder) to behave in unexpected ways. Copy from the sample files that we give you, or retype it by hand.
Coordinate list input mode (L):
A coordinate list input file will contain a list of coordinates for at least a ll walls, minions, and warp pipes in the rooms. 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: (room,row,col,character). The row and col positions range from 0 to N-1, where N is the value specified at the top of the file. By default, all unspecified coordinates within the rooms are of type . (room space); however, it is still valid to redundantly specify them.
Here is a valid L mode input file that describes rooms that are identical to those that the sample M input file did:
Version 1-20-21
2021 Regents of the University of Michigan
3
L
2
4
//sample L mode input file, two 44 rooms //castle room 0
(0,0,1,C) (0,1,0,.) (0,2,3,S) (0,3,0,#) (0,3,2,1) (0,3,3,#) //castle room 1 (1,1,0,#) (1,2,1,!) (1,3,0,#) (1,3,3,.)
Invalid coordinates (for a castle with two 44 rooms):
(2,1,2,#) (1,4,2,.) (0,1,5,!) (0,0,1,F)
Room 2 does not exist!
Row 4 does not exist!
Col 5 does not exist!
F is an invalid map character!
Routing schemes
You are to develop two routing schemes to help Marco get from the starting location to the location of Countess Cherry:
A queue-based routing scheme
A stack-based routing scheme
Be sure to read the document on Canvas titled Project 1 the STL and You; it has some excellent tips, plus a way to implement the two different routing schemes with a single search container (the deque).
In the routing scheme use a search container (queue or stack) of locations within the castle. First, initialize the algorithm by adding the start position S to the search container. Then, loop through the following steps:
1. Remove the next position from the search container.
2. If that position has a warp pipe, add the corresponding position that the pipe leads to,
i.e., the same row/col position but with the specified room number. As noted below, only add this position if it has not been added to the search container before.
Version 1-20-21
2021 Regents of the University of Michigan
4
3. If the position is not a warp pipe, then add all locations adjacent to the location you just removed that are available to move into (walkable room space, warp pipes, or the Countesss location). Add any locations that you are allowed to move to from your present location in the following order: north, east, south, and west.
4. As you add any of these spaces (step 2 or 3) to the search container, check to see if any of them is the location of the Countess C; if so, stop searching for a path.
If the search container becomes empty before you reach the Countess C, the search has failed and there is no path to rescue the Countess.
Whenever you add a position to the search container, you have discovered it. Do not discover any position more than once. Remember that from a walkable room space tile . or your starting location S you can only discover locations north, east, south, or west. Warp pipes are the only way of moving between rooms.
When visiting a warp pipe, you still have to check that you havent added its target location to the data structure when you see it. This will help you prevent Marco from following warp pipe loops. Also, make sure that Marco doesnt warp onto an enemy or into a solid wall! This is considered unhealthy.
The program must run to completion within 35 seconds of total CPU time (user + system) programs running for longer than this period will receive 0 points on that test case. In most cases 35 seconds is much more time than you should need; even if you finish before 35 seconds, you may still receive no points because your solution is too slow. 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 maps (up to several million locations). Be sure you are able to navigate to the Countess in large castle maps within 35 seconds. Smaller castle maps should run MUCH faster.
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 s hared_pointer or u nique_pointer constructs from the memory include file (we want you to learn proper use of pointers yourself). You are not allowed to use the C++11 regular expressions library (it is not fully implemented in gcc 6.x) or the thread/atomics libraries (it spoils runtime measurements).
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
Version 1-20-21
2021 Regents of the University of Michigan
5
command line arguments below for more details.
For both output formats, you will show the path you took from start to finish. If there is no valid solution, then, regardless of output mode, output
No solution, N tiles discovered.
(where N is the number of tiles discovered) followed by a newline.
Map Output Mode (M):
For this output mode, you should first print the starting location (see the example below). Then print the map of the castle rooms, replacing existing characters as needed to show the path you chose. Beginning at the starting location, overwrite the characters in the path with n, e, s, w, or p to indicate which tile Marco moved to next. All pipes Marco used in the final path should be overwritten by p, regardless of what room they lead to or from. Do not overwrite the location of the Countess C 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 room map space. You should only create comments to indicate the room numbers and format them as shown below, all other comments from the input files should be omitted.
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 room 0, row 2, column 3 //castle room 0
.Cww
n
n
#.1#
//castle room 1 .
#
.!..
#
Using the same input file but with the stack-based routing scheme, you should produce the following output:
Start in room 0, row 2, column 3 //castle room 0
eC..
n
nwww
Version 1-20-21
2021 Regents of the University of Michigan
6
#.1#
//castle room 1 .
#
.!..
#
We have highlighted the modifications to the output in red to call attention to them; do not attempt to color your output (this isnt possible, as your output must be a plain text file).
Coordinate List Output Mode (L):
For this 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 C (but you should not print the coordinate for C). The coordinates should be printed in the same format as they are specified in coordinate list input mode (room,row,col,character). The character of the coordinate should be n, e, s, w or a p to indicate spatially which tile is moved to next (as with map output, the p indicates that a warp pipe was taken). You should discard all comments from the input file, but you should add one line, just before you list the coordinates of the path that says 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 castle. If no valid route exists, the program should print No solution, N tiles discovered. (followed by a newline), where N is the number of tiles you discovered while searching, and no other output, in
Version 1-20-21
2021 Regents of the University of Michigan
7
either output mode. If this occurs, do not output the starting location or Path taken: line.
Be aware that input and output modes are independent of each other. Each test can use either input mode and either output mode. They may or may not be the same.
Command line arguments
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):
stack,-s:Ifthisswitchisset,usethestack-basedroutingscheme.
queue,-q:Ifthisswitchisset,usethequeue-basedroutingscheme.
output(M|L),-o(M|L):Indicatestheoutputfileformatbyfollowingtheflag
with an M (map format) or L (coordinate list format). If the output option is not specified, default to map output format (M), if output is specified on the command line, the argument (either M or L) to it is required. See the examples below regarding use.
help,-h:Ifthisswitchisset,theprogramshouldprintabriefhelpmessagewhich describes what the program does and what each of the flags are. The program should then exit(0) or return 0 from main().
When we say stack, or -s, we mean that calling the program with stack does the same thing as calling the program with -s. See getopt for how to do this.
Legal command line arguments 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 call exit(1).
Examples of legal command lines:
./superMarcostack
This will run the program using the stack algorithm and map output mode.
./superMarcoqueueoutputM
This will run the program using the queue algorithm and map output mode.
./superMarcostackoutputL
This will run the program using the stack algorithm and coordinate list output
mode.
Notice that we are using input and output redirection here. While we are reading our input from a file and sending our output to another file in this case, we are NOT using file streams! The < command redirects the file specified by the next command line argument to be the standard input (cin) for the program. The > command redirects the output of the program (things sent to cout) to be printed to the file specified by the next command line argument. The operating system makes calls to cin to read the input file and it makes calls to cout to write to
Version 1-20-21
2021 Regents of the University of Michigan
8
the output file. Come to office hours if this is confusing! Examples of illegal command lines:
./superMarcoqueue-s
./superMarco
You must specify either stack or queue
Testing your solution
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. M ost 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 set 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 castle in either map (M) or coordinate list (L) format. Each test file should be named test-n-flags.txt where 1 n 15. The flags portion should include a combination of letters of flags to enable. Valid letters in the flags portion of the filename are:
s:Runstackmode
q:Runqueuemode
m:Producemapmodeoutput l:Producelistmodeoutput
The flags that you specify as part of your test filename should allow us to produce a valid command line. For instance, dont include both s and q, but include one of them; include m or l, but if you leave it off, well 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 (the autograder will use a random combination of long and short options, such as output instead of -o):
./superMarco -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 88. You
Version 1-20-21
2021 Regents of the University of Michigan
9
may submit up to 15 test files (though it is possible to get full credit with fewer test files). The test cases the autograder runs on your solution are NOT limited to 10x8x8; your solution should not impose any size limits (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 (you should check in both M and L input modes).
For L input mode, you must check that the room, row, and column numbers of each
coordinate are all valid positions.
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 to output).
In all of these cases, print an informative error message to standard error (cerr) and call exit(1). In the starter files, look at the file named Error_messages.txt. If you output any one of those standard error messages when the input is actually valid, the autograder will repeat the error message back to you. This can be helpful when your program thinks that a valid input is invalid, because you can more easily figure out what went wrong.
You do not need to check for any other errors.
Assumptions you may make
You may assume we will not put extra characters after the end of a line of the map or after a coordinate.
You may assume that coordinates in coordinate list input mode will be in the format (room,row,col,character).
You may assume that there will be exactly one start location S and exactly one location of the Countess C in the map.
You may assume that we will not give you the same coordinate twice for the coordinate list input mode.
You may assume the input mode line and the integer dimensions of the castle 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.
Submission to the Autograder
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:
Version 1-20-21
2021 Regents of the University of Michigan
10
Every source code and header file contains the following project identifier in a comment at the top of the file:
// Project Identifier: B99292359FFD910ED13A7E6C7F9705B8742F0D79
The Makefile must also have this identifier (in the first TODO block).
DO NOT copy the above identifier from the PDF! It might contain hidden characters.
Copy it from the Identifier.txt file from Canvas instead.
You have deleted all .o files and your executable(s). Typing make clean shall
accomplish this.
Your makefile is called Makefile. Typing make -R -r builds your code without errors
and generates an executable file called superMarco. The command line options -R
and -r disable automatic build rules, which will not work on the autograder.
Your Makefile specifies that you are compiling with the gcc optimization option -O3. This
is extremely important for getting all of the performance points, as -O3 can often speed up code by an order of magnitude. You should also ensure that you are not submitting a Makefile to the autograder that compiles with the debug flag, -g, as this will slow your code down considerably. If your code works when you dont compile with -O3 and breaks when you do, it means you have a bug in your code!
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 dont 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. At the moment, the default version installed on CAEN is 4.8.5, however we want you to use version 6.2.0 (available on CAEN with a command and/or Makefile); this version is also installed on the autograder machines.
Turn in all of the following files:
All your .h, .hpp, and .cpp files for the project
Your Makefile
Your test files
You must prepare a compressed tar archive (.tar.gz file) of all of your files to submit to the autograder. One way to do this is to have all of your files for submission (and nothing else) in one directory. Our Makefile provides the command make fullsubmit. Alternately you can go into this directory and run this command:
dos2unix *; tar czf ./submit.tar.gz *.cpp *.h *.hpp Makefile test*.txt
This will prepare a suitable file in your working directory.
Version 1-20-21
2021 Regents of the University of Michigan
11
Submit your project files directly to either of the two autograders at:
https://g281-1.eecs.umich.edu/ or https://g281-2.eecs.umich.edu/. When the autograders are turned on and accepting submissions, there will be an announcement on Piazza. The autograders are identical and your daily submission limit will be shared (and kept track of) between them. You may submit up to three times per calendar day (more during the Spring). For this purpose, days begin and end at midnight (Ann Arbor local time). We will count only your best submission for your grade. If you would instead like us to use your LAST submission, see the autograder FAQ page, or use this form. If you use an online revision control system, make sure that your projects and files are PRIVATE; many sites make them public by default! If someone searches and finds your code and uses it, this could trigger Honor Code proceedings for you.
Please make sure that you read all messages shown at the top section of your autograder results! These messages will help explain some of the issues you are having (such as losing points for having a bad Makefile or using disallowed libraries).
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. The autograder machines keep track of the fastest run times (click on View scoreboard from the autograder project page). You may track your progress relative to other students and instructors there.
10 points No memory leaks. Solutions that are proven to run (passing certain autograder test cases) will also be run through valgrind, to check for memory leaks at exit. This is something you should do yourself, to check for memory leaks as well as a number of other issues that valgrind can enumerate. Valgrind is available at the CAEN command prompt, and can also be downloaded to run on Linux-based personal environments.
10 points Testing and Bug Finding (effectiveness at exposing buggy solutions with user-created test files).
Grading will be done by the autograder.
Version 1-20-21
2021 Regents of the University of Michigan
12
Empirical efficiency
We will check for empirical efficiency both by measuring the memory usage and running time of your code and by reading the code. We will focus on things such as whether you use unnecessary temporary variables, whether you copy data when a simple reference to it will do, and whether you use an O(n) algorithm or an O(n2 ) algorithm.
Coding style
Although your project will not be graded on style, style is a very important part of programming and software development. Among other things, 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 globals, 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 -Wconversion. 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.
Hints and advice
Design your data structures and work through algorithms on paper first. Draw pictures. Consider different possibilities before you start coding. If youre having problems at the design stage, come to office hours. After you have done some design and have a general understanding of the assignment, re-read this document. Consult it often during your assignments development to ensure that all of your code is in compliance with the specification.
Always think through your data structures and algorithms before you code them. It is important that you use efficient algorithms in this project and in this course, and coding before thinking often results in inefficient algorithms.
If you are considering linked lists, be sure to review the lecture slides or measure their performance against vectors first (theoretical complexities and actual runtime can tell different stories).
Version 1-20-21
2021 Regents of the University of Michigan
13
Only print the specified output to standard output.
You may print whatever diagnostic information you wish to standard error (cerr).
However, make sure it does not scale with the size of input, or your program may not
complete within the time limit for large test cases.
If the program does find a route, be sure to have main() return 0 (or call exit(0)). If
the input is valid but no route exists, also have main() return 0.
This is not an easy project. Start it immediately!
Have fun coding!
Version 1-20-21
2021 Regents of the University of Michigan
14
Appendix A More Sample Input/Output
An additional simple test input that requires you to correctly use a pipe to solve it.
Map Input:
M
2
4
//sample where using warp pipe is required //castle room 0
.S..
#
..!.
#.1.
//castle room 1 .C..
.0..
.!..
#..#
List Input:
L
2
4
//sample where using warp pipe is required //castle room 0
(0,0,1,S) (0,1,0,#) (0,2,2,!) (0,3,0,#) (0,3,2,1) //castle room 1 (1,0,1,C) (1,1,1,0) (1,2,1,!) (1,3,0,#) (1,3,3,#)
Version 1-20-21
2021 Regents of the University of Michigan
15
Map Output (Queue):
Start in room 0, row 0, column 1 //castle room 0
.s..
#s..
.s!.
#ep.
//castle room 1 .Cw.
.0n.
.!n.
#.n#
List Output (Queue):
Path taken: (0,0,1,s) (0,1,1,s) (0,2,1,s) (0,3,1,e) (0,3,2,p) (1,3,2,n) (1,2,2,n) (1,1,2,n) (1,0,2,w)
Version 1-20-21
2021 Regents of the University of Michigan
16
Map Output (Stack):
Start in room 0, row 0, column 1 //castle room 0
.s..
#s..
.s!.
#ep.
//castle room 1 .Cww
.0.n
.!en
#.n#
List Output (Stack):
Path taken: (0,0,1,s) (0,1,1,s) (0,2,1,s) (0,3,1,e) (0,3,2,p) (1,3,2,n) (1,2,2,e) (1,2,3,n) (1,1,3,n) (1,0,3,w) (1,0,2,w)
Version 1-20-21
2021 Regents of the University of Michigan
17
An additional simple test input that requires you to correctly use a pipe to solve it.
Map Input:
M
1
3
// A map with no solution //castle room 0
S#C .#!
Output (same for all valid command line options):
No solution, 5 tiles discovered.
Appendix B Test Case Legend
Test case name: XnY
X = L,M,S size of input files
n = Test case number, consecutive not informative
Y = s,S stack mode routing (map output, LIST OUTPUT)
q,Q queue mode routing (map output, LIST OUTPUT)
Test case name: INVn
n = Invalid test case number; see Errors you must check for section
Test case name: SpecXYZ
X (optional) = -P- spec example w/ warp,
Z = s,S stack mode routing (map output, LIST OUTPUT)
q,Q queue mode routing (map output, LIST OUTPUT)
When you start submitting test files to the autograder, it will tell you (in the section called Scoring student test files) how many bugs exist, the number needed to start earning points, and the number needed for full points. It will also tell you how many are needed to start earning an extra submit/day!
Version 1-20-21
2021 Regents of the University of Michigan
18
Reviews
There are no reviews yet.