Java Problem: Recommend a Bus Route Given a transit network, the start and end bus stops of the trip, and the riders expected arrival at a bus stop, provide a trip itinerary to get the rider to their destination as quickly as possible. For example, given the following transit network, followed by a trip query the route 2 15 A3 4 B3 3 C3 5 D3 2 end route 4 10 B1 3 B2 1 B3 6 B4 3 end route 3 20 D3 3 D4 1 C4 6 B4 4 A4 3 end end A3 A4 1 end Figure 2: Sample transit network and directions query. resulting recommendations would be: At stop A3 take bus #2 At stop B3 switch to bus #4 At stop B4 switch to bus #3 Get off at stop A4 Figure 3: Recommended bus route based on input in Figure 2

Notice that an alternative longer (not recommended) route is: At stop A3 take bus #2 At stop D3 switch to bus #3 Get off at stop A4 Figure 4: A longer bus route based on input in Figure 2

Your task is to create a program that reads a the bus network and one or more queries, and generates bus route recommendations. Write a program called RouteRecommender.java that reads in a bus network and one or more trip queries from the console (System.in) and outputs a trip recommendation for each query. Your RouteRecommender class must implement the provided Tester interface and also contain the main() method where your program starts running. This is because your program will be tested via this interface. The interface contains a single method: public ArrayList compute( Scanner input ); This method must perform the required computation.

Input The compute() method takes a Scanner object, which contains the input. The input is divided into two parts: a bus network portion and a query portion. The bus network part consists of one or more bus routes followed by a line with a single end. Each bus route begins with the line: route R F where R is the route number and F denotes the frequency of the busses on this route, and will be one of 10, 15, 20, or 30, meaning the bus runs every 10, 15, 20, or 30 minutes. This line is followed by one or more lines specifying bus stops on the route. Each bus stop is speci ed by a name and the time it takes the bus to arrive from the previous bus stop. S T where S is a single word with no spaces, and T is an integer, denoting the time it takes for the bus to travel from the previous bus stop. For the rst bus stop in a route, the number is interpreted as the number of minutes after the hour that the bus arrives. For example, in Figure 2, the bus network portion has three bus routes: 2, 4, and 3, with bus frequencies of 15, 10, and 20 minutes respectively. Bus route 2 has 4 stops: A3, B3, C3, D3. The bus arrives at A3 at 4 minutes past the hour, and every 15 minutes after that. It takes 3 minutes to travel from A3 to B3 and 5 minutes to travel from B3 to C3. A bus route is ended by a single line containing the end key word. After all bus routes are done, a second line containing the end keyword occurs. The second portion of the input consist of one or more queries for route recommendations. Each query is a triple of the form Orig Dest t where Orig is where the rider will start and Dest is where the rider is trying to get to. The third value, t, is an integer, between 0 and 60, indicating the time in minutes past the hour when the rider will arrive at the starting bus stop. The last line of the queries section contains the end keyword. For example, in Figure 2, the rider will arrive at bus stop A3 at 1 minute past the hour, and would like to arrive at bus stop A4. Hint: Use the nextLine() method of the Scanner object to read one line of input at a time, and then parse the line.

Semantics All bus routes have unique numbers and none of the bus routes have cycles. If a rider arrives at a bus stop, they must wait until the next bus arrives. The goal is to minimize the total time spent waiting at bus stop(s) and riding busses. You may assume that all queries and all inputs will be valid.

Output The method compute( Scanner input ) should return an ArrayList of Strings denoting the route recommendations, one per query. Each route recommendation consists of two or more lines. The rst line of a recommendation is of the form At stop S take bus #B where S is where rider is to board bus and B is the route number. For each stop where the rider needs to switch busses, output a line of the form: At stop S switch to bus #B where S and B are the same bus stop and route number, just as before. The last line of the recommendation should be of the form: Get off at stop S where S is the destination stop. See Figure 3 for an example. Example Sample Input route 2 15 A3 4 B3 3 C3 5 D3 2 end route 4 10 B1 3 B2 1 B3 6 B4 3 end route 3 20 D3 3 D4 1 C4 6 B4 4 A4 3 end end A3 A4 1 end

Sample Output At stop A3 take bus #2 At stop B3 switch to bus #4 At stop B4 switch to bus #3 Get off at stop A4

Hints and Suggestions Use a 2-phase algorithm: Create a weighted graph representing the transit network. Then, use a shortest weighted path algorithm (Dijkstra's) to solve each query. Be sure to take into account the time spent waiting for busses. You may assume that all input will be correct. Be sure to test your programs using the provided JUnit test class.

Junit Test Class

import static org.junit.jupiter.api.Assertions.*; import java.util.ArrayList; import java.util.Scanner; import org.junit.jupiter.api.Test; class RouteRecommenderTest { private static String testInput0 = "route 2 15 " + "A3 4 " + "B3 3 " + "C3 5 " + "D3 2 " + "end " + "end " + "A3 D3 1 " + "end "; private static String [] testOutput0 = { "At stop A3 take bus #2", "Get off at stop D3" }; private static String testInput1 = "route 2 15 " + "A3 4 " + "B3 3 " + "C3 5 " + "D3 2 " + "end " + "route 4 10 " + "B1 3 " + "B2 1 " + "B3 6 " + "B4 2 " + "B5 3 " + "end " + "end " + "A3 B5 1 " + "end "; private static String [] testOutput1 = { "At stop A3 take bus #2", "At stop B3 switch to bus #4", "Get off at stop B5" }; private static String testInput2 = "route 1 15 " + "A3 4 " + "B3 3 " + "C3 5 " + "D3 2 " + "end " + "route 2 15 " + "A3 4 " + "D3 2 " + "end " + "end " + "A3 D3 1 " + "end " + ""; private static String [] testOutput2 = { "At stop A3 take bus #2", "Get off at stop D3" }; private static String testInput3 = "route 1 15 " + "A3 4 " + "B3 3 " + "C3 5 " + "D3 2 " + "end " + "route 2 15 " + "A3 0 " + "D3 2 " + "end " + "end " + "A3 D3 1 " + "end " + ""; private static String [] testOutput3 = { "At stop A3 take bus #1", "Get off at stop D3" }; private static String testInput4 = "route 2 15 " + "A3 4 " + "B3 3 " + "C3 5 " + "D3 2 " + "end " + "route 4 10 " + "B1 3 " + "B2 1 " + "B3 6 " + "B4 3 " + "end " + "route 3 20 " + "D3 3 " + "D4 1 " + "C4 6 " + "B4 4 " + "A4 3 " + "end " + "end " + "A3 A4 1 " + "end " + ""; private static String [] testOutput4 = { "At stop A3 take bus #2", "At stop B3 switch to bus #4", "At stop B4 switch to bus #3", "Get off at stop A4" }; private static String testInput5 = "route 2 15 " + "A3 4 " + "B3 3 " + "C3 5 " + "D3 2 " + "end " + "route 4 10 " + "B1 3 " + "B2 1 " + "B3 6 " + "B4 3 " + "end " + "route 3 20 " + "D3 3 " + "D4 1 " + "C4 6 " + "B4 4 " + "A4 3 " + "end " + "end " + "A3 A4 1 " + "B1 C4 2 " + "end " + ""; private static String [] testOutput5 = { "At stop A3 take bus #2", "At stop B3 switch to bus #4", "At stop B4 switch to bus #3", "Get off at stop A4", "At stop B1 take bus #4", "At stop B3 switch to bus #2", "At stop D3 switch to bus #3", "Get off at stop C4" }; private static Scanner mkTest( String input ) { return new Scanner( input ); } private static ArrayList mkOutput( String [] output ) { ArrayList al = new ArrayList(); for( String s : output ) { al.add( s ); } return al; } private static boolean doTest( String input, String [] output ) { Tester t = new RouteRecommender(); ArrayList al = t.compute( mkTest( input ) ); System.out.println( "Input: " ); System.out.println( input ); System.out.println( "Generated output" ); for( String s : al ) { System.out.println( s ); } System.out.println( "Expected output" ); for( String s : output ) { System.out.println( s ); } System.out.println( "---------------------------------------------------" ); return al != null && al.equals( mkOutput( output ) ); } @Test void testEmpty() { assertTrue( doTest( testInput0, testOutput0 ), "Basic route" ); } @Test void test1() { assertTrue( doTest( testInput1, testOutput1 ), "One switch route" ); } @Test void test2() { assertTrue( doTest( testInput2, testOutput2 ), "Take the shorter route" ); } @Test void test3() { assertTrue( doTest( testInput3, testOutput3 ), "Waiting for bus affects schedule" ); } @Test void test4() { assertTrue( doTest( testInput4, testOutput4 ), "Multiple bus switches" ); } @Test void test5() { assertTrue( doTest( testInput5, testOutput5 ), "Multiple queries" ); } } 

Java Tester Interface Class

import java.util.ArrayList; import java.util.Scanner; public interface Tester { // This method takes a Scanner object contianing the input // and returns an ArrayList object containing the output. // // Parameters: // Scanner input: is a Scanner object that is a stream of text // containing the input to your program. // // Returns: an ArrayList of Strings. Each string is a line of output // from your program. public ArrayList compute( Scanner log ); }