Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
132 lines (97 sloc) 3.78 KB
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.