Join GitHub today
GitHub is home to over 20 million developers working together to host and review code, manage projects, and build software together.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Failed to load latest commit information.|
INTRODUCTION ============ Application should: - have a way to supply the input data via text file - the application must run :) - provide sufficient evidence it is complete Problem ======== The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance! The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute: - the distance along a certain route, - the number of different routes between two towns, - the shortest route between two towns. Input ====== A directed graph where - a *node represents a town* - and an *edge represents a route* between two towns. - The *weighting of the edge represents the distance* between the two towns. A given route will - *never appear more than once*, - and for a given route, the *starting and ending town will not be the same* town. Output ====== For test input 1 through 5, - if no such route exists, output 'NO SUCH ROUTE'. - Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means 1. to start at city A, then 2. travel directly to city B (a distance of 5), then 3. directly to city C (a distance of 4). 1. The distance of the route A-B-C. 2. The distance of the route A-D. 3. The distance of the route A-D-C. 4. The distance of the route A-E-B-C-D. 5. The distance of the route A-E-D. 6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops). 7. The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B). 8. The length of the shortest route (in terms of distance to travel) from A to C. 9. The length of the shortest route (in terms of distance to travel) from B to B. 10. The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC. Test Input ========== For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5. Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7 Expected Output: Output #1: 9 Output #2: 5 Output #3: 13 Output #4: 22 Output #5: NO SUCH ROUTE Output #6: 2 Output #7: 3 Output #8: 9 Output #9: 9 Output #10: 7 REQUIREMENTS ========== - Unix/Linux system - Ruby 1.8.7 - Ruby Test::Unit - Rake USAGE ===== > bin/planner samples/sample.txt The results are written to the standard output: - answer for each task from the file is on a separate line - format of the answer is /(\w+):\s(\.)/. First group is the task name, 2nd - the answer. Also make sure the bin/planner file has execute permissions. Input File Format ----------------- Line starting with "GRAPH:" defines a graph for the tasks. GRAPH: AB10, BC10, CD10, DA10 Line starting with "DISTANCE" will calculate distance of the given route. DISTANCE to_nice_city_and_back: ABCDA Line starting with "SHORTEST" will calculate distance of the shortest path. SHORTEST quickly_get_there: A B Line starting with "COUNT_ROUTES" will calculate the number of different routes between 2 town. The example below calculates number of routes between A and B with not less than 2 and no more than 4 stop and at a distance not longer than 20 COUNT_ROUTES my_options: A B 2 4 20 All other lines are ignored.