Lab Coding Exercise: Building an Abstraction

This exercise is intended to help you to learn to build an inheritance hierarchy that represents an abstraction.

Submission

While there will not be an official submission for this exercise, this code will be the basis for this week's programming exercise.

Lab Workflow

Here is a review of the steps you will use to work with GIT during lab (as distinct from assigned team projects):

1. On Gitlab, one person should fork the original project lab_maze into their own repository to allow pushing your group's changes
   • On the resulting project web page, go to Settings -> Members to add your partner so both people in the group can access the same repository
   • Search for your partner's name and give them a Maintainer role in the project and choose Add to Project
2. In Terminal, both students should use git clone to copy the one forked repository to their individual machines so they can work on their own separate copies
3. In IntelliJ, both students should Open the cloned folder to create a new project on their personal machine
4. In IntelliJ, add the names and NetIDs of everyone in your group at the top of the DISCUSSION.md file included in the repository
5. As a group, discuss how to change features in the current code and what design issues that reveals using the questions below as a guide
• Report your ideas, reasoning, and the main conclusions in the file DISCUSSION.md using Gitlab's Markdown format
6. In IntelliJ, refactor the code to improve its design (i.e., edit the code) using Pair Programming
7. In Terminal, use GIT to
• git add changed files
• git commit -m to describe your changes
• git push changes back to Gitlab
• git pull changes from Gitlab back to the local machine (if you are not sharing a single computer)
• Repeat as many times as needed, letting each person try the changes/GIT steps in related chunks
8. As a group, discuss the refactored design using the questions below as a guide.
   • Report your ideas, reasoning, and the main conclusions in the file DISCUSSION.md using Gitlab's Markdown format

Specification

This project implements a Maze solver using a variety of search algorithms:

• Random Walk: This “search” randomly chooses a place to step and “hopes” to one day find the goal. An “exploration bias” is included so the algorithm will prefer a step that it has not already taken, making it more likely to find a solution. The benefit of this type of search is that it uses no memory. On the other hand, it may take a very long time to find the goal.
• DFS (Depth-First search): This search algorithm will go as far as possible in one direction. When it reaches a dead end, it backtracks to a point at which it can choose a new path.
• BFS (Breadth-First search): This search looks one step in every viable direction at once. It maintains a list of the open path possibilities and cycles through them sequentially. It will always find the shortest path to the goal.
• Greedy: This search algorithm is similar to Breadth-First, but always chooses to move forward with the path that is closest to the goal. It cannot guarantee to find the shortest path, but it often does so, and more quickly.
• Magic: This is not an actual search algorithm, just something added for fun. It uses the Greedy algorithm, but ignores walls on its way to the goal :)

Take some time to play with it and also explore the code to make sure you understand basically how it works.

They are all subclasses of the minimal superclass SearchAlgorithm, but still contain significant duplicated code. The goal of this exercise is to refactor the classes to remove as much duplicated code as you can by choosing what code belongs in the superclass and what code is specific to each subclass. Note, you can add as many methods as you want: protected (for subclasses to override) and private (to factor out common functionality); but you should not need to add any public methods. or new classes

For this lab, you only need to refactor the code in the solvers package.

Discussion

Examine the code from all the subclasses to identify what parts are common and what parts are different among the different versions.

Then work through the following steps to thoughtfully, deliberately, refactor the code while taking notes on your ideas, goals, issues, progress in your DISCUSSION.md file:

• describe the general steps the maze-solving algorithms share (even if some of them implement them by doing nothing)
• convert each step into a Java method signature (i.e., name, parameters, and return type)
• test your steps by refactoring one subclass so its step() method calls those as private methods
• run the program to make sure it still works correctly (i.e., verify your refactoring did not break the functionality)
• refactor another subclass to see if your methods generalize to another algorithm (if not, then adjust both subclasses as needed)
• run the program to make sure it still works correctly
• now try moving some of the methods (and instance variables) into the superclass to see if you can remove the duplication — what can be made protected and what can be private?
• run the program to make sure it still works correctly

And then continue the process as you have time during lab so that you always feel in control of the changes being made to the code. Refactoring can be a very safe process or lead to a lot of syntax and logic errors that ruin your larger design goals!

Pair Programming

Labs in this course expect you to work either in pairs or with your project team.

Professionally, this practice is called Pair Programming: working closely with another programmer, sharing a "single computer" that we will simulate using a shared computer, shared repository or use IntelliJ's new Code With Me feature. To ensure both people do some coding, you will switch which person actually writes the code every 10-15 minutes (in industry this switch happens only 1-3 times per day). The person who is not actively coding can be advising, suggesting better names, looking up documentation, or searching the Internet for solutions to small problems you are likely to face, but not multi-tasking (i.e., doing their own work or socializing).