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
ight (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 ou
way through the city! Recall that our city consists of blocks of buildings su
ounded 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
y 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 A
ayList 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
eturn an A
ayList 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 A
ayList, 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 cu
ent 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 ve
atim, 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
oth the co
ect 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 ve
atim, 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