# PSET 6 Writeup - Experiment Testing
## Looking at Tile Puzzle
When approaching the experiment testing for tile puzzles, we wanted to test 4 different puzzle cases:
* 2x2
* 3x3
* 4x4
* Unsolvable

and we wanted to test these puzzles using our three kinds of solvers:
* Regular BFS (Breadth-First Search)
* Fast BFS
* DFS (Depth-First Search)

Using a modified version of the testing code the staff heads have provided for us in tests.ml, we reimplemented the test_tile_puzzle () function into a module to have the ability to test a multitude of different tile puzzles.

Although warned by CS51 staff, we wanted to uncomment the code for the DFS solver to try and see its runtime; however, the program actually ran indefinitely until the phrase "Killed" was displayed in the terminal. We were not able to retrieve runtimes for the 3x3 and 4x4 tile puzzles, but we were able to retrive this the runtime from the 2x2 puzzle.

Testing 2x2 Tile:
TESTING TILE PUZZLE...
DFS Time: 
time (msecs): 0.254869

Additionally, when trying to run our unsolvable tile puzzle,

Ex:

| | | |
| --- | --- | --- |
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 8 | 7 | |

the program once again ran indefinitely for both the BFS and Fast BFS solvers.

Below are the runtimes, in miliseconds, for BFS and FastBFS, where both search regimes solve our tile puzzles:

| Tile Puzzle | Regular BFS Time (ms) | Fast BFS Time (ms) |
| ----------- | --------------------- | ------------------ |
| 2x2 | 0.386000 | **0.348091** |
| 3x3 | 235.903025 | **100.455999** |
| 4x4 | 110001.641035 | **2910.134077** |


Note how consistently the regular BFS solver took more time to run the Fast BFS. We even saw drastic differences between the two in the 4x4 puzzle! The time in the Regular BFS solver was actually so large that we chose not to represent it on the graph for readability.

### Tile Puzzle Conclusions

It is interesting how in almost all of the puzzle cases, except for the 2x2, DFS was unusable for tile puzzles in terms of the 3x3 and 4x4 puzzle. This makes sense because in **Depth-First Searching**, a branch in the "solve-tree" is searched as far as possible in the left-tree before moving along to other trees. So in a puzzle where all neighbors are relatively near each other, and in a puzzle with so many possible combinations, it will take a very long time to find a solution as it might try to solve a lot more tile states.

Again, this makes sense why both the Regular BFS and Fast BFS both struggle when it comes to solving the 4x4 puzzle. The amount of possible combinations required to solve the puzzle can explain why these solvers struggle to find a solution. Additionally when trying to solve the unsolvable tile puzzle, no solvers can actually reach the CantReachGoal. With the huge amount of possibilities, to reach this exception the solver must actually search through every possible solution and can explain why it takes forever to run.

Also, it is interesting how the Fast BFS beats the regular BFS in every tile puzzle. Even with the 4x4 it is incredibly interesting to see how it surpasses the time by almost 107000 ms!

## Looking at Maze Puzzle

When approaching the experiment testing for tile puzzles, we wanted to test 12 different puzzle cases. In the following, a **nearby solution** refers to a solution with a goal state at coordinate (2,2), a **diagonal solution** refers to a solution with a goal state at the bottom-right-most coordinate of the puzzle, a **horizontal solution** refers to a solution with a goal state at the top-right-most coordinate of the puzzle, and a **vertical solution** refers to a solution with a goal state at the bottom-left-most coordinate of the puzzle.
* **NearbyMazeI** : A **5x5** puzzle with a **nearby** solution
* **NearbyMazeII** A **10x10** puzzle with a **nearby** solution
* **NearbyMazeIII** A **15x15** puzzle with a **nearby** solution
* **DiagonalMazeI** A **5x5** puzzle with a **diagonal** solution
* **DiagonalMazeII** A **10x10** puzzle with a **diagonal** solution
* **DiagonalMazeIII** A **15x15** puzzle with a **diagonal** solution
* **HorizontalMazeI** A **5x5** puzzle with a **horizontal** solution
* **HorizontalMazeII** A **10x10** puzzle with a **horizontal** solution
* **HorizontalMazeIII** A **15x15** puzzle with a **horizontal** solution
* **VerticalMazeI** A **5x5** puzzle with a **vertical** solution
* **VerticalMazeII** A **10x10** puzzle with a **vertical** solution
* **VerticalMazeIII** A **15x15** puzzle with a **vertical** solution

and we wanted to test these puzzles using our three kinds of solvers:
* **Regular BFS** (Breadth-First Search)
* **Fast BFS**
* **DFS** (Depth-First Search)

Below are the results from testing each puzzle and search regime. The quickest times are bolded:

| Puzzle | Regular BFS Time (ms) | Fast BFS Time (ms) | DFS Time (ms) |
| ----------------- | --------------------- | ------------------ | ------------- |
| NearbyMazeI | 0.047922 | **0.041962** | 0.158072 |
| NearbyMazeII | 0.045061 | **0.041962** | 0.399828 |
| NearbyMazeIII | 0.158072 | **0.084162** | 2.645969 |
| DiagonalMazeI | 0.200987 | 0.191927 | **0.082016** |
| DiagonalMazeII | 0.908136 | 0.704050 | **0.140905** |
| DiagonalMazeIII | 3.523111 | 2.907038 | **0.522852** |
| TopRightMazeI | 0.277996 | **0.190973** | 0.195980 |
| TopRightMazeII | 1.371861 | 3.580093 | **0.436068** |
| TopRightMazeIII | 2.362967 | 2.003908 | **0.876188** |
| BottomLeftMazeI | 0.258923 | **0.142813** | 0.177860 |
| BottomLeftMazeII | 0.812054 | **0.689030** | 1.510143 |
| BottomLeftMazeIII | 5.496979 | 4.485130 | **3.968954** |


### Maze Puzzle Observations
#### Initial Observations
After running our tests, we discovered that **the fastest search regime heavily depended on the specific maze that we were testing**. For instance, for all **Nearby Mazes**, the **Fast BFS** regime was consistently the quickest regime. However, for the **Diagonal Mazes**, the **DFS** regime was consistently the quickest.

#### DFS' Behavior
For **Nearby Mazes**, the **DFS** regime was consistently the slowest search regime. During its search for the goal state, it went *around* the nearby solution and traversed nearly the entire maze before finding the solution. This is because the DFS regime's strategy is to search deeply within each branch of a search tree for a solution. If it does not find a solution at the bottom of that branch, it returns to the top of that branch, and deeply searches it, repeating the aforementioned process until it finds the goal state.

#### BFS' Behavior
The BFS regime searches the neighbors of an initial state, adds them to a queue of first-level states, then searches each of their neighbors, dequeuing each first-level state upon finding their second-level neighbors, and continues this until it finds the solution. This allows it to find nearby solutions quicker than DFS, which, as mentioned earlier, has to search deeply through every path in a search tree.

#### FastBFS' Behavior
The FastBFS regime is mostly similar to the BFS regime, except that its time complexity is O(1), where c is any constant, unlike BFS, which has a time-complexity of Ο(n), allowing it to solve puzzles quicker for larger mazes or far goal states.

#### Maze Puzzle Conclusions
For the **Bottom Left Mazes**, and **Top Right Mazes** there was no clear winner, as both alternated between **FastBFS** and **DFS**, where **DFS** was quicker for larger **Bottom Right Mazes**, while the trials we have for **Top Right Maze** did not leave us with any conclusive evidence.

Based on the observations described above, we were able to draw the conclusion that: **Fast BFS is best for mazes where the goal state is close to the initial state, but as the goal state grows further away from the initial state, DFS is able to solve the puzzle quicker**

## Final Conclusion

The Fast BFS was the best solver for all the tile puzzles; however, when introduced puzzles much greater than a 4x4, almost all the solvers failed to produce a solution in a reasonable amount of time.

In all of our puzzles, solution times that our solver fast BFS produced was consistently faster or very similar times than the regular BFS solver. This makes sense as fast BFS is not O(n) when adding elements rather it is constant time. Oppositely, BFS is O(n) as it has to traverse the entire list to add elements.

For maze puzzles, it depended on which scenario the puzzles/mazes were given to see which solver was more efficient. For goal states that were farther from the initial state, DFS produced solutions in faster times. However, in cases where the goal state was closer to the initial state, fast BFS produced faster solutions when compared to DFS and regular BFS. This makes sense as DFS searches deep within a particular search tree before moving onto another tree. It will go a lot further around solutions near the initial state whereas BFS always finds the shortest path.