Reading graph inputs for a programming puzzle and then solving it
- by Vrashabh
I just took a programming competition question and I absolutely bombed it. I had trouble right at the beginning itself from reading the input set. The question was basically a variant of this puzzle http://codercharts.com/puzzle/evacuation-plan but also had an hour component in the first line(say 3 hours after start of evacuation). It reads like this
This puzzle is a tribute to all the people who suffered from the earthquake in Japan. The goal of this puzzle is, given a network of road and locations, to determine the maximum number of people that can be evacuated.
The people must be evacuated from evacuation points to rescue points. The list of road and the number of people they can carry per hour is provided.
Input Specifications Your program must accept one and only one command line argument: the input file. The input file is formatted as follows: the first line contains 4 integers n r s t n is the number of locations (each location is given by a number from 0 to n-1) r is the number of roads s is the number of locations to be evacuated from (evacuation points) t is the number of locations where people must be evacuated to (rescue points) the second line contains s integers giving the locations of the evacuation points the third line contains t integers giving the locations of the rescue points the r following lines contain to the road definitions. Each road is defined by 3 integers l1 l2 width where l1 and l2 are the locations connected by the road (roads are one-way) and width is the number of people per hour that can fit on the road
Now look at the sample input set
5 5 1 2 3
0
3 4
0 1 10
0 2 5
1 2 4
1 3 5
2 4 10
The 3 in the first line is the additional component and is defined as the number of hours since the resuce has started which is 3 in this case.
Now my solution was to use Dijisktras algorithm to find the shortest path between each of the rescue and evac nodes. Now my problem started with how to read the input set. I read the first line in python and stored the values in variables. But then I did not know how to store the values of the distance between the nodes and what DS to use and how to input it to say a standard implementation of dijikstras algorithm.
So my question is two fold 1.) How do I take the input of such problems? - I have faced this problem in quite a few competitions recently and I hope I can get a simple code snippet or an explanation in java or python to read the data input set in such a way that I can input it as a graph to graph algorithms like dijikstra and floyd/warshall. Also a solution to the above problem would also help.
2.) How to solve this puzzle? My algorithm was:
Find shortest path between evac points (in the above example it is 14 from 0 to 3)
Multiply it by number of hours to get maximal number of saves
Also the answer given for the variant for the input set was 24 which I dont understand. Can someone explain that also.
UPDATE:
I get how the answer is 14 in the given problem link - it seems to be just the shortest path between node 0 and 3. But with the 3 hour component how is the answer 24
UPDATE
I get how it is 24 - its a complete graph traversal at every hour and this is how I solve it
Hour 1
Node 0 to Node 1 - 10 people
Node 0 to Node 2- 5 people
TotalRescueCount=0
Node 1=10
Node 2= 5
Hour 2
Node 1 to Node 3 = 5(Rescued)
Node 2 to Node 4 = 5(Rescued)
Node 0 to Node 1 = 10
Node 0 to Node 2 = 5
Node 1 to Node 2 = 4
TotalRescueCount = 10
Node 1 = 10
Node 2= 5+4 = 9
Hour 3
Node 1 to Node 3 = 5(Rescued)
Node 2 to Node 4 = 5+4 = 9(Rescued)
TotalRescueCount = 9+5+10 = 24
It hard enough for this case , for multiple evac and rescue points how in the world would I write a pgm for this ?
