import java.util.ArrayDeque; /** * Project 05 tester. * * javac *.java * java Project05Tester * * Runs every check and keeps going after a failure, then prints a summary. * No windows open and nothing depends on luck: the random-maze checks test * rules that hold for EVERY maze (for example, BFS always finds a shortest path). * * Passing every check does not guarantee full credit. You still need your own * tests, the display, the experiments, and the report. */ public class Project05Tester { private static int passed = 0, failed = 0; private static void check(boolean condition, String message) { if (condition) { passed++; System.out.println(" [PASS] " + message); } else { failed++; System.out.println(" [FAIL] " + message); } } private static void fail(String message) { failed++; System.out.println(" [FAIL] " + message); } private static final int SECONDS = 10; private static final String LOOP_HINT = "\n does your search mark each cell (setPrev) BEFORE adding it, and skip cells already marked?"; private static volatile boolean timedOut = false; /** Runs one section; reports a FAIL instead of hanging if it never finishes. */ private static void runSection(Runnable section) { final Throwable[] thrown = new Throwable[1]; Thread worker = new Thread(() -> { try { section.run(); } catch (Throwable e) { thrown[0] = e; } }); worker.setDaemon(true); worker.start(); try { worker.join(SECONDS * 1000L); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } if (worker.isAlive()) { fail("this section did not finish in " + SECONDS + " seconds. Look for an infinite loop:" + LOOP_HINT); timedOut = true; } else if (thrown[0] != null) { fail("this section stopped early because your code threw " + thrown[0]); } } private static void section(String title) { System.out.println(); System.out.println("== " + title + " =="); } private static AbstractMazeSearch make(boolean bfs, Maze m) { return bfs ? new MazeBreadthFirstSearch(m) : new MazeDepthFirstSearch(m); } private static String name(boolean bfs) { return bfs ? "BFS" : "DFS"; } private static String at(Cell c) { return c == null ? "null" : "(" + c.getRow() + "," + c.getCol() + ")"; } /** Returns what is wrong with a returned path, or null if it is a valid path. */ private static String pathProblem(LinkedList path, Maze m, Cell start, Cell target) { if (path == null) return "expected a path but got null"; if (path.size() == 0) return "returned an empty list"; boolean[][] used = new boolean[m.getRows()][m.getCols()]; Cell previous = null; int count = 0; for (Cell c : path) { count++; if (count > m.getRows() * m.getCols()) return "path is longer than the maze (a prev cycle?)"; if (c == null) return "path contains null"; if (c.getRow() < 0 || c.getRow() >= m.getRows() || c.getCol() < 0 || c.getCol() >= m.getCols() || c != m.get(c.getRow(), c.getCol())) return "path contains a Cell that is not this maze's own Cell object"; if (c.getType() != CellType.FREE) return "path goes through obstacle " + at(c); if (used[c.getRow()][c.getCol()]) return "path visits " + at(c) + " twice"; used[c.getRow()][c.getCol()] = true; if (previous == null && c != start) return "path starts at " + at(c) + ", not the start " + at(start); if (previous != null && Math.abs(c.getRow() - previous.getRow()) + Math.abs(c.getCol() - previous.getCol()) != 1) return "path jumps from " + at(previous) + " to " + at(c); previous = c; } if (previous != target) return "path ends at " + at(previous) + ", not the target " + at(target); if (count != path.size()) return "size() is " + path.size() + " but iteration found " + count + " cells"; return null; } private static void checkPath(LinkedList path, Maze m, Cell start, Cell target, String message) { String problem = pathProblem(path, m, start, target); if (problem == null) check(true, message); else fail(message + ": " + problem); } /** Independent shortest-path length in moves, or -1 if unreachable. */ private static int shortestMoves(Maze m, Cell start, Cell target) { int[][] dist = new int[m.getRows()][m.getCols()]; for (int[] row : dist) java.util.Arrays.fill(row, -1); ArrayDeque todo = new ArrayDeque(); dist[start.getRow()][start.getCol()] = 0; todo.add(new int[] { start.getRow(), start.getCol() }); int[][] steps = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } }; while (!todo.isEmpty()) { int[] p = todo.poll(); for (int[] s : steps) { int r = p[0] + s[0], c = p[1] + s[1]; if (r >= 0 && r < m.getRows() && c >= 0 && c < m.getCols() && m.get(r, c).getType() == CellType.FREE && dist[r][c] < 0) { dist[r][c] = dist[p[0]][p[1]] + 1; todo.add(new int[] { r, c }); } } } return dist[target.getRow()][target.getCol()]; } /** Number of FREE cells reachable from start, including start. */ private static int reachableCount(Maze m, Cell start) { int count = 0; for (Cell c : m) { if (c.getType() == CellType.FREE && shortestMoves(m, start, c) >= 0) count++; } return count; } // ------------------------------------------------------------------ // Sections // ------------------------------------------------------------------ private static void frontierSection(boolean bfs) { section("Task 4: " + name(bfs) + " frontier methods"); Maze m = new Maze(3, 3, 0); AbstractMazeSearch s = make(bfs, m); Cell a = m.get(0, 0), b = m.get(0, 1), c = m.get(0, 2); check(s.numRemainingCells() == 0, "new searcher has an empty frontier"); s.addCell(a); s.addCell(b); s.addCell(c); check(s.numRemainingCells() == 3, "numRemainingCells is 3 after adding 3 cells"); Cell first = s.findNextCell(), second = s.findNextCell(), third = s.findNextCell(); if (bfs) check(first == a && second == b && third == c, "findNextCell returns oldest first (Queue)"); else check(first == c && second == b && third == a, "findNextCell returns newest first (Stack)"); check(s.numRemainingCells() == 0 && s.findNextCell() == null, "empty frontier: size 0, findNextCell null"); s.addCell(a); s.addCell(b); s.clearFrontier(); check(s.numRemainingCells() == 0 && s.findNextCell() == null, "clearFrontier empties the frontier"); s.addCell(c); check(s.numRemainingCells() == 1 && s.findNextCell() == c, "frontier still works after clearFrontier"); } private static void resetSection(boolean bfs) { section("Task 1: " + name(bfs) + " reset"); Maze m = new Maze(3, 3, 0); m.get(1, 1).setType(CellType.OBSTACLE); AbstractMazeSearch s = make(bfs, m); s.addCell(m.get(0, 0)); s.addCell(m.get(0, 1)); m.get(0, 0).setPrev(m.get(0, 0)); m.get(0, 1).setPrev(m.get(0, 0)); s.setCur(m.get(0, 1)); s.reset(); check(s.numRemainingCells() == 0, "reset clears the frontier"); check(m.countVisitedCells() == 0, "reset clears every Cell's prev"); check(s.getStart() == null && s.getTarget() == null && s.getCur() == null, "reset sets start, target, and cur to null"); check(m.get(1, 1).getType() == CellType.OBSTACLE, "reset keeps obstacles"); } private static void tracebackSection(boolean bfs) { section("Task 2: " + name(bfs) + " traceback"); Maze m = new Maze(3, 5, 0); AbstractMazeSearch s = make(bfs, m); check(s.traceback(null) == null, "traceback(null) returns null"); check(s.traceback(m.get(1, 1)) == null, "traceback of an undiscovered cell returns null"); Cell start = m.get(0, 0), target = m.get(2, 4); LinkedList path = s.search(start, target); checkPath(s.traceback(target), m, start, target, "traceback(target) after a search is a valid path"); LinkedList self = s.traceback(start); check(self != null && self.size() == 1 && self.peek() == start, "traceback(start) is just the start"); if (path != null && path.size() >= 3) { // Break the chain in the middle: point a path cell at itself. Cell middle = null; int i = 0; for (Cell c : path) if (i++ == path.size() / 2) middle = c; Cell saved = middle.getPrev(); middle.setPrev(middle); check(s.traceback(target) == null, "a chain that self-links somewhere other than start returns null"); middle.setPrev(null); check(s.traceback(target) == null, "a chain that reaches an undiscovered cell returns null"); middle.setPrev(saved); } else { fail("could not test broken chains because search did not return a path"); } } private static boolean rejects(AbstractMazeSearch s, Cell start, Cell target, int delay) { try { s.search(start, target, false, delay); return false; } catch (IllegalArgumentException e) { return true; } catch (RuntimeException e) { System.out.println(" (threw " + e.getClass().getSimpleName() + " instead of IllegalArgumentException)"); return false; } } private static void validationSection(boolean bfs) { section("Task 3: " + name(bfs) + " rejects bad arguments"); Maze m = new Maze(3, 4, 0); m.get(1, 1).setType(CellType.OBSTACLE); Maze other = new Maze(3, 4, 0); AbstractMazeSearch s = make(bfs, m); Cell ok = m.get(0, 0), ok2 = m.get(2, 3); check(rejects(s, null, ok2, 0), "null start"); check(rejects(s, ok, null, 0), "null target"); check(rejects(s, m.get(1, 1), ok2, 0), "start is an obstacle"); check(rejects(s, ok, m.get(1, 1), 0), "target is an obstacle"); check(rejects(s, new Cell(0, 0, CellType.FREE), ok2, 0), "start is a Cell not in this maze"); check(rejects(s, ok, other.get(2, 3), 0), "target is from another maze (equal coordinates, different object)"); check(rejects(s, ok, new Cell(9, 9, CellType.FREE), 0), "target with coordinates outside the maze"); check(rejects(s, ok, ok2, -1), "negative delay"); } private static void fixedGridSection(boolean bfs) { String label = name(bfs) + " "; section("Task 3: " + name(bfs) + " search on fixed grids"); Maze m = new Maze(3, 5, 0); AbstractMazeSearch s = make(bfs, m); Cell start = m.get(0, 0), target = m.get(2, 4); LinkedList result = s.search(start, target, false, 0); checkPath(result, m, start, target, label + "open 3x5 grid, corner to corner"); if (bfs) check(result != null && result.size() == 7, label + "finds the 6-move shortest path"); check(s.getStart() == start && s.getTarget() == target, label + "saves start and target"); check(s.getCur() == target, label + "cur is the target after success"); result = s.search(target, target); checkPath(result, m, target, target, label + "start equals target, after a previous search"); check(result != null && result.size() == 1, label + "start equals target: one Cell, zero moves"); for (int r = 0; r < 3; r++) m.get(r, 2).setType(CellType.OBSTACLE); check(s.search(start, target) == null, label + "wall across the grid: target unreachable, returns null"); check(s.numRemainingCells() == 0, label + "frontier is empty after a failed search"); check(m.countVisitedCells() == 6, label + "failed search discovers exactly the 6 reachable cells"); m.get(2, 2).setType(CellType.FREE); result = s.search(start, target); checkPath(result, m, start, target, label + "same searcher reused after a failure"); if (bfs) check(result != null && result.size() == 7, label + "reuse: still a 6-move shortest path"); m.get(0, 1).setType(CellType.OBSTACLE); m.get(1, 1).setType(CellType.OBSTACLE); target = m.get(0, 4); result = s.search(start, target); checkPath(result, m, start, target, label + "forced detour"); if (bfs) check(result != null && result.size() == 9, label + "forced detour: 8-move shortest path"); target = m.get(1, 0); result = s.search(start, target); checkPath(result, m, start, target, label + "adjacent endpoints"); check(result != null && result.size() == 2, label + "adjacent endpoints: two Cells, one move"); int obstacles = 0; for (Cell c : m) if (c.getType() == CellType.OBSTACLE) obstacles++; check(obstacles == 4, label + "searching never changes obstacles"); Maze wide = new Maze(2, 7, 0); AbstractMazeSearch w = make(bfs, wide); checkPath(w.search(wide.get(1, 0), wide.get(0, 6)), wide, wide.get(1, 0), wide.get(0, 6), label + "wide 2x7 grid (rows and columns not mixed up)"); } private static void randomSection() { section("Both: rules that hold on every random maze"); double[] densities = { 0.1, 0.2, 0.3, 0.4, 0.5 }; int trials = 0, badDfsPath = 0, badBfsPath = 0, reachDisagree = 0, notShortest = 0, dfsShorter = 0, partialFailure = 0, leftovers = 0; String firstProblem = null; for (double density : densities) { for (int t = 0; t < 60; t++) { trials++; Maze m = new Maze(8, 10, density); Cell start = m.get(0, 0), target = m.get(7, 9); start.setType(CellType.FREE); target.setType(CellType.FREE); int shortest = shortestMoves(m, start, target); AbstractMazeSearch dfs = new MazeDepthFirstSearch(m); LinkedList dPath = dfs.search(start, target); int dfsVisited = m.countVisitedCells(); int dfsLeft = dfs.numRemainingCells(); AbstractMazeSearch bfs = new MazeBreadthFirstSearch(m); LinkedList bPath = bfs.search(start, target); int bfsVisited = m.countVisitedCells(); int bfsLeft = bfs.numRemainingCells(); boolean reachable = shortest >= 0; if ((dPath != null) != reachable || (bPath != null) != reachable) { reachDisagree++; if (firstProblem == null) firstProblem = "density " + density + ": target is " + (reachable ? "" : "not ") + "reachable, but DFS returned " + (dPath == null ? "null" : "a path") + " and BFS returned " + (bPath == null ? "null" : "a path"); continue; } if (!reachable) { int component = reachableCount(m, start); if (dfsVisited != component || bfsVisited != component) partialFailure++; if (dfsLeft != 0 || bfsLeft != 0) leftovers++; continue; } if (pathProblem(dPath, m, start, target) != null) { badDfsPath++; if (firstProblem == null) firstProblem = "DFS: " + pathProblem(dPath, m, start, target); } if (pathProblem(bPath, m, start, target) != null) { badBfsPath++; if (firstProblem == null) firstProblem = "BFS: " + pathProblem(bPath, m, start, target); } if (bPath.size() - 1 != shortest) { notShortest++; if (firstProblem == null) firstProblem = "BFS path has " + (bPath.size() - 1) + " moves but the shortest has " + shortest; } if (dPath.size() - 1 < shortest) dfsShorter++; } } System.out.println(" (" + trials + " random 8x10 mazes, densities 0.1 to 0.5, corners forced FREE)"); check(reachDisagree == 0, "DFS and BFS both find a path exactly when one exists" + (reachDisagree > 0 ? " (" + reachDisagree + " mazes wrong)" : "")); check(badDfsPath == 0, "every DFS path is valid" + (badDfsPath > 0 ? " (" + badDfsPath + " bad)" : "")); check(badBfsPath == 0, "every BFS path is valid" + (badBfsPath > 0 ? " (" + badBfsPath + " bad)" : "")); check(notShortest == 0, "every BFS path is a shortest path" + (notShortest > 0 ? " (" + notShortest + " were longer)" : "")); check(dfsShorter == 0, "no DFS path is shorter than the shortest (sanity check)"); check(partialFailure == 0, "a failed search discovers every cell reachable from start" + (partialFailure > 0 ? " (" + partialFailure + " did not)" : "")); check(leftovers == 0, "a failed search ends with an empty frontier"); if (firstProblem != null) System.out.println(" first problem seen: " + firstProblem); } public static void main(String[] args) { System.out.println("Project 05 Tester"); java.util.List sections = new java.util.ArrayList(); for (boolean bfs : new boolean[] { false, true }) { sections.add(() -> frontierSection(bfs)); sections.add(() -> resetSection(bfs)); sections.add(() -> tracebackSection(bfs)); sections.add(() -> validationSection(bfs)); sections.add(() -> fixedGridSection(bfs)); } sections.add(Project05Tester::randomSection); for (Runnable section : sections) { if (timedOut) break; runSection(section); } if (timedOut) System.out.println("\n Stopped after a section timed out; fix that first, then run again."); System.out.println(); System.out.println("Summary: " + passed + " passed, " + failed + " failed."); if (failed == 0) { System.out.println("All checks passed. Also run your own tests, the display, and the experiments."); } else { System.out.println("Fix the first FAIL above first; later failures are often caused by it."); } System.exit(failed == 0 ? 0 : 1); // also ends any stuck section } }