# CSE 12 PA8 Test Cases
### **These are the exact test cases that will be used to grade your PA. We recommend adding all of these tests to your HeapTest.java/TestSolvers.java to ensure you will get a satisfactory grade on this PA.**
### MazeSolver Tests:
1) testMazeSolver_noSolution
- Input String array: new String[]

{"####",
"__#S",
"_###",
"___F"}

- Input costs array: new int[][]

{{0,0,0,0},
{2,3,0,0},
{2,0,0,0},
{1,5,3,10}}

- Output: `null`
- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should not generate a path because one doesn't exist. So MazeSolver.solve() should return `null`.

2) testMazeSolver_noSolutionDiagonal
- Input String array: new String[]

{"####",
"__#S",
"_#F#",
"____"}
- Input costs array: new int[][]

{{0,0,0,0},
{2,3,0,0},
{2,0,10,0},
{1,5,3,1}

- Output: `null`
- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should not generate a path because one doesn't exist. So MazeSolver.solve() should return `null`.

3) testMazeSolver_solutionLong
- Input String array: new String[]

{"___S",
"_##_",
"_##_",
"___F"}

- Input costs array: new int[][]

{{1,1,1,0},
{1,0,0,5},
{1,0,0,5},
{1,1,1,1}}

- Output: new String[]

{"***S",
"*##_",
"*##_",
"***F"}
- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should generate a valid path. After calling MazeSolver.solve(M), The following lines of code should generate a maze that matches the output shown above.

        ArrayList<Square> sp = M.storePath();
        String actualStr = formatMaze(M.showSolution(sp));
        System.out.println(actualStr);

4) testMazeSolver_solutionShort
- Input String array: new String[]

{"___S",
"_##_",
"_##_",
"___F"}

- Input costs array: new int[][]

{{2,2,2,0},
{2,0,0,5},
{2,0,0,5},
{2,2,2,1}}

- Output: new String[]

{"___S",
"_##*",
"_##*",
"___F"}

- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should generate a valid path. After calling MazeSolver.solve(M), The following lines of code should generate a maze that matches the output shown above.

        ArrayList<Square> sp = M.storePath();
        String actualStr = formatMaze(M.showSolution(sp));
        System.out.println(actualStr);

5) testMazeSolver_solution_1x8
- Input String array: new String[]

{"F______S"}

- Input costs array: new int[][]

{{1,1,1,1,1,1,1,0}}

- Output: new String[]

{"F******S"}

- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should generate a valid path. After calling MazeSolver.solve(M), The following lines of code should generate a maze that matches the output shown above.

        ArrayList<Square> sp = M.storePath();
        String actualStr = formatMaze(M.showSolution(sp));
        System.out.println(actualStr);

6) testMazeSolver_noSolution_1x8
- Input String array: new String[]

{"F__#___S"}

- Input costs array: new int[][]

{{1,1,1,0,1,1,1,0}}

- Output: `null`
- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should not generate a path as one doesn't exist. So MazeSolver.solve() should return `null`.

7) testMazeSolver_solution_4x1
- Input String array: new String[]

{"S",
"_",
"_",
"F"}

- Input costs array: new int[][]

{{0},
{1},
{1},
{1}}

- Output: new String[]

{"S",
"*",
"*",
"F"}

- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should generate a valid path. After calling MazeSolver.solve(M), The following lines of code should generate a maze that matches the output shown above.

        ArrayList<Square> sp = M.storePath();
        String actualStr = formatMaze(M.showSolution(sp));
        System.out.println(actualStr);

8) testMazeSolver_noSolution_4x1
- Input String array: new String[]

{"S",
"#",
"_",
"F"}

- Input costs array: new int[][]

{{0},
{0},
{1},
{1}}

- Output: `null`

- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should not generate a path as one doesn't exist. So MazeSolver.solve() should return `null`.

9) testMazeSolver_Solution_10x10
- Input String array: new String[]

{"##S____#_#",
"_#_#_#_#__",
"#_##______",
"____##__#_",
"##_##_____",
"__#_______",
"##_#______",
"_#___##___",
"____##___#",
"_#_##____F"}

- Input costs array: new int[][]

{{0, 0, 0, 6, 17, 5, 8, 0, 2, 0},
{6, 0, 12, 0, 17, 0, 7, 0, 5, 2},
{0, 17, 0, 0, 7, 8, 10, 11, 15, 3},
{6, 17, 3, 4, 0, 0, 12, 10, 0, 2},
{0, 0, 10, 0, 0, 9, 1, 10, 6, 1},
{12, 17, 0, 10, 3, 1, 7, 16, 16, 9},
{0, 0, 10, 0, 2, 2, 14, 18, 7, 15},
{7, 0, 7, 15, 4, 0, 0, 9, 15, 17},
{5, 17, 14, 19, 0, 0, 4, 2, 7, 0},
{3, 0, 12, 0, 0, 5, 12, 13, 18, 14}}

- Potential Output: new String[]

{"##S****#_#",
"_#_#_#*#__",
"#_##__*___",
"____##*_#_",
"##_##_*___",
"__#___*___",
"##_#__**__",
"_#___##*__",
"____##_**#",
"_#_##___*F"}

- Running cost of generated path: 155

- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should generate a valid path. After calling MazeSolver.solve(M), The following lines of code should generate a valid path who's cost is 155. The above maze could have several solutions, if you're program finds another valid path with the same cost, you will receive credit for this test even if the output string doesn't match what's shown above.

        ArrayList<Square> sp = M.storePath();
        String actualStr = formatMaze(M.showSolution(sp));
        System.out.println(actualStr);

10) testMazeSolver_Solution_15x10
- Input String array: new String[]

{"F_______#_",
"_________#",
"__#_______",
"_____#__#_",
"__#__#___#",
"____######",
"___#______",
"__##_#___#",
"___##__#_#",
"_____#__#_",
"_#____#___",
"__#______#",
"#_____#___",
"___#__#___",
"#___##___S"}

- Input costs array: new int[][]

{{3, 8, 6, 9, 6, 4, 13, 16, 0, 2},
{10, 4, 13, 17, 17, 4, 17, 13, 5, 0},
{8, 2, 0, 9, 3, 11, 13, 14, 10, 3},
{19, 13, 16, 11, 6, 0, 16, 4, 0, 15},
{11, 7, 0, 19, 4, 0, 1, 9, 3, 0},
{7, 14, 19, 16, 0, 0, 0, 0, 0, 0},
{2, 2, 6, 0, 9, 13, 5, 18, 19, 6},
{19, 13, 0, 0, 6, 0, 3, 19, 12, 0},
{9, 6, 17, 0, 0, 10, 15, 0, 12, 0},
{6, 4, 3, 8, 19, 0, 1, 1, 0, 15},
{17, 0, 18, 4, 19, 6, 0, 2, 1, 9},
{8, 10, 0, 19, 13, 14, 7, 16, 13, 0},
{0, 7, 18, 17, 1, 15, 0, 8, 10, 5},
{19, 8, 11, 0, 7, 3, 0, 1, 11, 6},
{0, 10, 6, 18, 0, 0, 4, 16, 14, 0}}

- Potential Output: new String[]

{"F*______#_",
"_*_______#",
"_*#_______",
"_*___#__#_",
"_*#__#___#",
"_*__######",
"_*_#______",
"_*##_#___#",
"_*_##__#_#",
"_***_#__#_",
"_#_***#___",
"__#__***_#",
"#_____#*__",
"___#__#***",
"#___##___S"}

- Running cost of generated path: 179

- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should generate a valid path. After calling MazeSolver.solve(M), The following lines of code should generate a valid path who's cost is 179. The above maze could have several solutions, if you're program finds another valid path with the same cost, you will receive credit for this test even if the output string doesn't match what's shown above.

        ArrayList<Square> sp = M.storePath();
        String actualStr = formatMaze(M.showSolution(sp));
        System.out.println(actualStr);

11) testMazeSolver_Solution_30x10
- Input String array: new String[]

{"S____#_#_#",
"#_________",
"______#_##",
"#____#____",
"##_#______",
"_##___#__#",
"_#___##_##",
"#__##_#___",
"__________",
"__________",
"_#________",
"##________",
"#_#_#__#__",
"____##_#_#",
"_____#__#_",
"____#_#___",
"__________",
"___#_###__",
"__________",
"_##__#____",
"_____##__#",
"__#_#__###",
"____#_____",
"___#_____#",
"#__#__#___",
"__##___#__",
"________##",
"##__#___#_",
"__#___#___",
"__#______F"}

- Input costs array: new int[][]

{{0, 12, 7, 16, 9, 0, 13, 0, 19, 0},
{0, 5, 18, 3, 19, 7, 18, 1, 9, 19},
{15, 11, 11, 8, 8, 4, 0, 8, 0, 0},
{0, 14, 12, 10, 4, 0, 15, 14, 9, 11},
{0, 0, 5, 0, 13, 10, 2, 8, 15, 14},
{16, 0, 0, 12, 12, 1, 0, 4, 5, 0},
{3, 0, 11, 13, 9, 0, 0, 10, 0, 0},
{0, 10, 13, 0, 0, 6, 0, 10, 15, 8},
{1, 7, 3, 9, 6, 6, 10, 4, 5, 16},
{10, 4, 6, 15, 15, 2, 17, 19, 6, 6},
{1, 0, 3, 14, 19, 6, 14, 11, 19, 17},
{0, 0, 19, 1, 2, 15, 9, 4, 11, 14},
{0, 9, 0, 2, 0, 1, 6, 0, 16, 12},
{11, 1, 3, 1, 0, 0, 7, 0, 14, 0},
{1, 19, 4, 11, 13, 0, 8, 10, 0, 4},
{9, 1, 10, 5, 0, 5, 0, 16, 2, 18},
{19, 12, 17, 10, 9, 8, 11, 8, 9, 13},
{5, 6, 2, 0, 13, 0, 0, 0, 19, 2},
{9, 12, 7, 7, 8, 10, 12, 15, 5, 5},
{8, 0, 0, 15, 11, 0, 12, 8, 9, 18},
{9, 2, 5, 4, 12, 0, 0, 5, 11, 0},
{3, 17, 0, 18, 0, 19, 5, 0, 0, 0},
{12, 19, 6, 12, 0, 8, 1, 7, 7, 8},
{12, 10, 15, 0, 7, 18, 6, 16, 9, 0},
{0, 18, 3, 0, 13, 14, 0, 19, 13, 16},
{11, 13, 0, 0, 19, 15, 10, 0, 2, 18},
{1, 1, 18, 5, 15, 7, 10, 11, 0, 0},
{0, 0, 15, 19, 0, 4, 17, 8, 0, 10},
{14, 11, 0, 2, 8, 15, 0, 8, 10, 9},
{11, 3, 0, 5, 18, 16, 2, 16, 16, 13}}

- Potential Output: new String[]

{"S***_#_#_#",
"#__*______",
"___**_#_##",
"#___*#____",
"##_#*_____",
"_##_*_#__#",
"_#***##_##",
"#_*##_#___",
"__*_______",
"__*_______",
"_#**______",
"##_*______",
"#_#*#__#__",
"__**##_#_#",
"__*__#__#_",
"_**_#_#___",
"_*________",
"**_#_###__",
"*_________",
"*##__#____",
"*____##__#",
"*_#_#__###",
"*___#_____",
"**_#_____#",
"#*_#__#___",
"_*##___#__",
"_*******##",
"##__#__*#_",
"__#___#***",
"__#______F"}

- Running cost of generated path: 409

- Description: Calling MazeSolver.solve(M), where M is the maze created with these inputs, should generate a valid path. After calling MazeSolver.solve(M), The following lines of code should generate a valid path who's cost is 409. The above maze could have several solutions, if you're program finds another valid path with the same cost, you will receive credit for this test even if the output string doesn't match what's shown above.

        ArrayList<Square> sp = M.storePath();
        String actualStr = formatMaze(M.showSolution(sp));
        System.out.println(actualStr);

### Heap Tests:

1) testHeapFunctionality_toArray
- Input String array: new String

{"Eric", "Nandini", "Rebecca", "Greg", "Juan"}

- Input weights array: new int[]

{0,1,2,3,4}

- Expectation:

heap.toArray().size() == 5
heap.toArray() contains all inputed values from the input array

- Description: Adding the above names as values and their respective weights as keys into a heap with a min heap comparator from left to right, should guarantee the above expectations.

2) testHeapFunctionality_addMin
- Input String array: new String

{"Garo", "Eric", "Nandini", "Paul", "Greg", "Rebecca"}

- Input costs array: new int[]

{20, 10, 30, 5, 1, 22}

- Expectation:

heap.toArray().size() == 6
heap.toArray() has a valid heap structure

- Description: Adding the above names as values and their respective weights as keys into a heap from left to right, should guarantee the above expectations.

3) testHeapFunctionality_addMax
- Input String array: new String

{"Garo", "Eric", "Nandini", "Paul", "Greg", "Rebecca"}

- Input costs array: new int[]

{20, 10, 30, 5, 1, 22}

- Expectation:

heap.toArray().size() == 6
heap.toArray() has a valid heap structure

- Description: Adding the above names as values and their respective weights as keys into a heap with a max heap comparator from left to right, should guarantee the above expectations.

4) testHeapFunctionality_peek
- Input String array: new String

{"Eric", "Nandini", "Rebecca", "Greg", "Juan"}

- Input costs array: new int[]

{0,1,2,3,4}

- Expectation:

heap.peek().value.equals(names[0])
heap.peek().key.equals(0)

- Description: Adding the above names as values and their respective weights as keys into a heap with a min heap comparator from left to right, should requires the above expectations from the peek() method.

4) testHeapFunctionality_removeMin
- Input String array: new String

{"Garo", "Eric", "Nandini", "Paul", "Greg", "Rebecca"}

- Input costs array: new int[]

{20, 10, 30, 5, 1, 22}

- Expectation:
Removing all elements from the heap via `heap.poll()` should remove them in ascending sorted order.

- Description: Adding the above names as values and their respective weights as keys into a heap with a min heap comparator from left to right, requires the above expectations for the poll() method.

5) testHeapFunctionality_removeMax
- Input String array: new String

{"Garo", "Eric", "Nandini", "Paul", "Greg", "Rebecca"}

- Input costs array: new int[]

{20, 10, 30, 5, 1, 22}

- Expectation:
Removing all elements from the heap via `heap.poll()` should remove them in descending sorted order.

- Description: Adding the above names as values and their respective weights as keys into a heap with a max heap comparator from left to right, requires the above expectations for the poll() method.