CSCI 200 - Foundational Programming Concepts & Design - A5

→This assignment is due by Tuesday, April 25, 2023 11:59 PM.←
→ As with all assignments, this must be an individual effort and cannot be pair programmed. Any debugging assistance must follow the course collaboration policy and be cited in the comment header block for the assignment.←
→ Do not forget to complete the following labs with this set: L5A, L5B, L5C ←
→ Do not forget to complete zyBooks Assignment 5 for this set.←

· Instructions · Rubric ·Submission ·

We will now combine the two-dimensional lists, stacks, and queues to implement a Maze solver using Breadth-First Search and Depth-First Search. The maze will be represented as a 2D List. The goal is to determine if it is possible to move from the Start Space to the End Space.

Create the Maze

Mazes will be specified in an external file. The format of the file is:

R C
#####
#S#E#
#...#
#####

The first line specifies the size of the maze as R rows and C columns. Next, an RxC 2D array of characters follow. The following properties describe the makeup of the character array:

# - signifies a wall. These spaces are unable to moved to.
. - signifies an open space. These spaces may be moved to.
S - signifies the starting space. You will begin your search from here. This space may be moved to.
E - signifies the end space. You will end your search here. This space may be moved to.
The maze will always be well-formed. Meaning, it will always be of size RxC and only contain the four characters specified above.
S and E will each always appear only one time in the maze.
The size of the maze will be bound by 3 ≤ R ≤ 102 and 4 ≤ C ≤ 102.

Begin by checking if a command line argument was specified with the filename. If not, prompt the user to enter a file containing the maze. As you read the file, create a 2D list of characters that matches the size of the maze. Read the maze contents into your 2D list. Be sure to note what location the S character is in to start your upcoming search.

Solve the Maze (Maybe)

After the maze has been successfully read into memory, ask the user how they wish to solve the maze. Either by BFS or by DFS.

Based on the user's selection, search the maze using BFS with a Queue or DFS with a Stack as appropriate. Begin your search at the S space and continue until the E space is reached or the search is exhausted.

When the search is complete, print out if the maze can be solved or not.

Then print out the maze showing which locations were visited. Use @ to show which . spaces were visited by the search.

An example of a successful search is shown below:

> ./A5 input/1.maze
Opening file "input/1.maze"
File opened successfully!

Enter 1 to search via BFS.
Enter 2 to search via DFS.
Choice: 1
End was reached!
#########
#S#@@@#E#
#@#@#@#@#
#@#@#@#@#
#@@@#@@@#
#########

An example of an unsuccessful search is shown below:

> ./A5 input/4.maze
Opening file "input/4.maze"
File opened successfully!

Enter 1 to search via BFS.
Enter 2 to search via DFS.
Choice: 1
End cannot be reached
##########################
#S#@@@@@@@@@@@@#@@@@#@##.#
#@#@@@###@@@@###@##@#@#.E#
#@#@###@#@@#@@@#@##@#@##.#
#@@@@@#@@@###@@@@#@@@@####
###@##@@##@#@@####@##@####
###@@##@@@@####@@@@#######
##########################

To aide in testing your searches through various scenarios and conditions, a maze pack has been provided with 10 public test cases.

Hints

To aid in the debugging of your BFS/DFS algorithm: print the maze and then prompt the user to hit enter before running the next iteration. This way you can watch each step of the process and follow the expansion of the search strategy. The following snippet of code will assist with prompting the user.
```
print_maze(...); // replace with the process to print the current state of the maze
std::cout << "Press enter to continue" << std::endl;
std::cin.get();
```
Be very careful with passing objects to a function. If you pass an object to a function by value, then the copy constructor is called and any manipulations to the target will result in the copy being modified. The argument will remain unmodified. When dealing with objects as parameters, we'll want to be using either pass-by-reference or pass-by-pointer.
```
void foo(ClassName& object) { ... }
void bar(ClassName* pObject) { ... }
```
Be very careful with returning objects from a function. If you return an object from a function by value, then the copy constructor is called and any manipulations to the result will result in the copy being modified. The returned object will remain unmodified. When dealing with objects as returned values, we'll want to be using either return-by-reference or return-by-pointer.
```
ClassName& foo() { ... }
ClassName* bar() { ... }
```

Testing

The graders will build your program with the Makefile you provide to match your code structure and run your program against five private test mazes.

Best Practices To Follow

One clear and consistent coding style used (such as K&R, 1TBS, or Allman).
Course naming scheme is followed for variable, function, class, and other identifiers. See the course style guide for more specifics.
Code is self-documenting. Variables sensibly named, function names descriptive of their purpose.
Don't use global variables unless absolutely necessary. Instead, encapsulate them and design your interfaces effectively. If there is no way around using a global variable, be prepared to defend and justify its usage.
Program flow uses structural blocks (conditionals/loops) effectively, appropriately, and efficiently.
Code compiles and links without any errors or warnings.
Program runs without any run time errors. Exceptions are properly caught, user input is validated appropriately, and program exits successfully without error.
Use const wherever possible:
- If you declare a variable and that variable is never modified, that variable should be const.
- If your function takes a parameter and does not modify that parameter, that parameter should be const.
- If a member function does not modify the callee, that member function should be const.
- If you are pointing at a value that does not change, the pointer should point at a constant value (e.g. const T*).
- If the pointer itself is never modified, the pointer should be a constant pointer (e.g. T* const).
- If the pointer itself is never modified AND the value pointed at does not change, the pointer should be a constant pointer AND the pointer should point at a constant value (e.g. const T* const).
Keep your headers clean. Put the absolute minimum required in your headers for your interface to be used. Anything that can go in a source file should. Don't #include any system headers in your .h files that aren't absolutely required in that file specifically. Avoid using namespace in headers.
Implement the Big-3 as appropriate.
Don't leak memory. Every allocation using new needs to have a corresponding delete.
Use appropriate inheritance access. Only expose necessary members to derived classes.
Use virtual and override as appropraite. Mark members as final wherever possible and/or appropriate on derived classes.
Follow and apply the following design principles:
- Write Once, Use Many / Write Once, Read Many (WORM) / Don't Repeat Yourself (DRY): Use loops, functions, classes, and const as appropriate.
- Encapsulate what varies: Use functions and classes as appropriate. Identify the aspects that vary and separate them from what stays the same.
- Favor composition over inheritance.
- Program to an interface, not an implementation & SOLID Principles: When using object-oriented inheritance & polymorphism, do the following:
  - No variable should hold a reference to a concrete class.
  - No class should derive from a concrete class.
  - No method should override an implemented method of any of its base classes.

Grading Rubric

Your submission will be graded according to the following rubric.

Points	Requirement Description
15	All labs completed and submitted L5A, L5B, L5C
6	Solves a maze with edge walls and no loops using BFS & DFS.
8	Solves a maze with edge walls and loops using BFS & DFS.
8	Solves a maze with no edge walls using BFS & DFS.
6	Solves a maze with no solution using BFS & DFS.
1	Public mazes solved correctly.
2	Private mazes solved correctly.
5	Best practices are followed: +5 Code is easily readable, follows best practices, well structured +4 Code is easy to follow, only a few small violations of best practices +3 No egregiously bad practices +2 Lots of violations of best practices +1 Little effort to follow best practices +0 No effort to follow best practices
51	Total Points

Submission

Always, always, ALWAYS update the header comments at the top of your main.cpp file. And if you ever get stuck, remember that there is LOTS of help available.

It is critical that you follow these steps when submitting homework.

If you do not follow these instructions, your assignment will receive a major deduction. Why all the fuss? Because we have several hundred of these assignments to grade, and we use computer tools to automate as much of the process as possible. If you deviate from these instructions, our grading tools will not work.

Submission Instructions

Here are step-by-step instructions for submitting your homework properly:

Make sure you have the appropriate comment header block at the top of every source code file for this set. The header block should include the following information at a minimum.
```
/* CSCI 200: Assignment 5: A5 - a-MAZE-ing
 *
 * Author: XXXX (INSERT_NAME)
 * Resources used (Office Hours, Tutoring, Other Students, etc & in what capacity):
 *     // list here any outside assistance you used/received while following the
 *     // CS@Mines Collaboration Policy and the Mines Academic Code of Honor
 *
 * XXXXXXXX (MORE_COMPLETE_DESCRIPTION_HERE)
 */
```
Be sure to fill in the appropriate information, including:
- Assignment number
- Assignment title
- Your name
- If you received any type of assistance (office hours - whose, tutoring - when), then list where/what/who gave you the assistance and describe the assistance received
- A description of the assignment task and what the code in this file accomplishes.
Additionally, update the Makefile for A5 to generate a target executable named A5.
File and folder names are extremely important in this process. Please double-check carefully, to ensure things are named correctly.
1. The top-level folder of your project must be named Set5
2. Inside Set5, create 4 sub-folders that are required for this Set. The name of each sub-folder is defined in that Set (e.g. L5A, L5B, L5C, and A5).
3. Copy your files into the subdirectories ofSet5 (steps 2-3), zip this Set5 folder (steps 4-5), and then submit the zipped file (steps 6-11) to Canvas.
4. For example, when you zip/submit Set5, there will be 4 sub-folders called L5A, L5B, L5C, and A5 inside the Set5 folder, and each of these sub-folders will have the associated files.
Using Windows Explorer (not to be confused with Internet Explorer), find the files named main.cpp, Makefile, *.h, *.hpp, *.cpp.

STOP: Are you really sure you are viewing the correct assignment's folder?
Now, for A5, right click on main.cpp, Makefile, *.h, *.hpp, *.cpp to copy the files. Then, return to the Set5/A5 folder and right click to paste the files. In other words, put a copy of your homework's main.cpp, Makefile, *.h, *.hpp, *.cpp source code into the Set5/A5 folder.

Follow the same steps for each lab to put a copy of each lab's deliverable into the Set5/L5 folders. Do this process for Set5/L5A (main.cpp), Set5/L5B (main.cpp, Makefile, *.h, *.hpp, *.cpp), Set5/L5C (main.cpp, Makefile, *.h, *.hpp, *.cpp).

STOP: Are you sure your Set5 folder now has all your code to submit?

The structure of the submission is as follows:
- Set5/
  - A5/
    - main.cpp
    - Makefile
    - *.h
    - *.hpp
    - *.cpp
  - L5A/
    - main.cpp
  - L5B/
    - main.cpp
    - Makefile
    - *.h
    - *.hpp
    - *.cpp
  - L5C/
    - main.cpp
    - Makefile
    - *.h
    - *.hpp
    - *.cpp
Now, right-click on the "Set5" folder.
1. In the pop-up menu that opens, move the mouse "Send to..." and expand the sub-menu.
2. In the sub-menu that opens, select "Compressed (zipped) folder".
STOP: Are you really sure you are zipping a Set5 folder with sub-folders that each contain a main.cpp file in it?
After the previous step, you should now see a "Set5.zip" file.
Now visit the Canvas page for this course and click the "Assignments" button in the sidebar.
Find Set5, click on it, find the "Submit Assignment" area, and then click the "Choose File" button.
Find the "Set5.zip" file created earlier and click the "Open" button.

STOP: Are you really sure you are selecting the right homework assignment? Are you double-sure?
WAIT! There's one more super-important step. Click on the blue "Submit Assignment" button to submit your homework.
No, really, make sure you click the "Submit Assignment" button to actually submit your homework. Clicking the "Choose File" button in the previous step kind of makes it feel like you're done, but you must click the Submit button as well! And you must allow the file time to upload before you turn off your computer!
Canvas should say "Submitted!". Click "Submission Details" and you can download the zip file you just submitted. In other words, verify you submitted what you think you submitted!

In summary, you must zip the "Set5" folder and only the "Set5" folder, this zip folder must have several sub-folders, you must name all these folders correctly, you must submit the correct zip file for this homework, and you must click the "Submit Assignment" button. Not doing these steps is like bringing your homework to class but forgetting to hand it in. No concessions will be made for incorrectly submitted work. If you incorrectly submit your homework, we will not be able to give you full credit. And that makes us unhappy.