2 recursive methods
CS300_Fall_2022_P06_City_Route_Planner 2 1 Getting Started Start by creating a new Java Project in eclipse called P06 City Route Planner, or something similar. As always make sure that you are using Java 17, don’t add a module, and that you use the default package. Now create a new class called Intersection. This class represents a single intersection point where two streets cross at specified x and y coordinate positions. Implement this class following the provided javadocs. You will not be required to write tester methods for this class, but you are free to implement your own. You can picture Intersections as crossroad points on a 2D grid of streets. As an example, the following image represents four instances of the Intersection class located at (0, 0), (3, 0), (0, 4), and (4, 2). Create a new class called Path. This class represents a path through a city grid which ONLY moves exactly one step up, or one step to the right at each step. Moving both up and right (diagonally) in a single step is NOT allowed. Implement this class following the provided javadocs. You will not be required to write tester methods for this class, but you are free to implement your own. As an example, the following images represent two distinct paths starting at (0, 0) and ending at (4, 2). 2 City Path Planning Now that we have a way to represent a grid street plan, it’s time to use recursion to find our way through the city! Recall that our city consists of blocks of buildings surrounded by streets. 3 Streets run at right angles to each other, forming a grid of intersections. Create a new class called PathUtils with two methods countPaths and findAllPaths as specified by the javadocs. This is a utility class which solves the following problems. Suppose we have two Intersections on a city grid, call them A and B, which we want to travel between by moving only north or east at each step as in the Path class. Recall that in our Paths we can only move up and right, never backtracking left or down, and that we cannot cut diagonally through a block of buildings. Two possible questions we can ask are 1. How many possible paths are there from A to B? 2. What exactly are these paths? In this case, there are four possible paths, which look as follows: It will be your job to answer these two questions in the countPaths and findAllPathsmethods. 4 • In countPaths, you will count the number of paths going between a chosen starting and ending Intersection. As an example, for the above scenario, countPaths(new Intersection(0, 1), new Intersection(3, 2)) should return 4. Think of the base cases, recursive cases, and how to decompose the problem to smaller subproblems before you start coding. You will not receive credit if you implement this method iteratively or combinatorially. You will only receive credit if you implement it in a directly recursive manner, or utilize a private static helper method which is recursive. You also may not use your implementation of findAllPaths. • In findAllPaths, you will create an ArrayList containing all of the Path objects going between a chosen starting an ending Intersection. For example, for the above scenario, findAllPaths(new Intersection(0, 1), new Intersection(3, 2)) should return an ArrayList with four Paths which look as follows: (0,1)->(1,1)->(2,1)->(3,1)->(3,2) (0,1)->(1,1)->(2,1)->(2,2)->(3,2) (0,1)->(1,1)->(1,2)->(2,2)->(3,2) (0,1)->(0,2)->(1,2)->(2,2)->(3,2) These Paths can be in any order in the returned ArrayList, but the result should contain exactly these Paths. Think of the base cases, recursive cases, and how to decompose the problem to smaller subproblems before you start coding. This method generalizes countPaths, so we recommend you complete that method first. You will not receive credit if you implement this method iteratively. You will only receive credit if you implement it in a directly recursive manner, or utilize a private static helper method which is recursive. • Hint: To get from A to B, there are at most two possible directions we can travel in the first step, namely north and east. For each of these new Intersections X, if we can move from A directly to X in one step, and we know how many paths there are from X to B, how many paths are there from A to B which go through X? Then how many total paths are there from A to B? • Hint: When is there nothing left to do (i.e. there are no smaller subproblems)? If I’m trying to get to a specified destination from my current location, when is there nothing else left to do? Remember that a Path containing a single Intersection X is a valid Path which takes you from X to X. For each of these methods you may use the provided Javadocs verbatim, but remember to include the appropriate file headers, and to write inline comments to explain the overall design of your methods and helper methods as necessary. 5 3 Test Methods Create a new class called PathUtilsTester with the six required public static boolean test methods: testCountPathsNoPath, testCountPathsOnePath, testCountPathsRecursive, testFindAllPathsNoPath, testFindAllPathsOnePath, and testFindAllPathsRecursive. Implement these test methods as specified in the javadocs. Create your own test cases which are di↵erent from the provided examples. For the findAllPaths tests, make sure that there is both the correct number of Paths, and that the returned Paths exactly match what you expect to see. Remember that the order the Paths appear in the output will not necessarily be exactly the same as in your implementation. For each of these methods you may use the provided Javadocs verbatim, but remember to include the appropriate file headers, and to write inline comments to explain your test cases. You can also use the following provided driver method to test your implementation. public static void main(String[] args) { try (Scanner keyboard = new Scanner(System.in)) { int startX, startY, endX, endY; String input = "Y"; while (input.equalsIgnoreCase("Y")) { System.out.print("Enter starting X coordinate: "); startX = keyboard.nextInt(); System.out.print("Enter starting Y coordinate: "); startY = keyboard.nextInt(); System.out.print("Enter ending X coordinate: "); endX = keyboard.nextInt(); System.out.print("Enter ending Y coordinate: "); endY = keyboard.nextInt(); Intersection start = new Intersection(startX, startY); Intersection end = new Intersection(endX, endY); System.out.println("Number of paths from start to end: " + PathUtils.countPaths(start, end)); System.out.println("List of possible paths:"); for (Path p : PathUtils.findAllPaths(start, end)) { System.out.println(p); } do { System.out.print("Try another route? (Y/N): "); input = keyboard.next(); } while (!input.equalsIgnoreCase("Y") && !input.equalsIgnoreCase("N")); } } } 6