Java – How to Read Graph Inputs for a Programming Puzzle and Solve It

javapuzzlespython

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 ?

Best Answer

This question is basically two-fold:

  1. How do you solve the actual problem? and
  2. How do you generally read in graph data?

The first question is a bit narrow, and it sounds like the second one is of more interest to you in the long run. So, let me just point you to flow algorithms. It's a step up from Dijkstra in terms of implementation complexity, but as you already realized, there is just so much you can do with a single path. Network flows are a whole different thing.

As for reading your input, it dramatically depends on the kind of graph library you want to use. A few years ago, when I was active in these competitions, we weren't allowed to use 3rd-party libraries, so had to roll our own implementations.

In that case, you have to think ahead if you want to read in a complete matrix, or if you want to keep the graph as an adjacency list. These are the two most important data structures to know for graph algorithms. (more precisely, often you don't need to think ahead, because the problem input specification directs you to one or the other)

Reading input for an adjacency matrix is as straightforward as two nested for-loops. In the body of the inner loop, you simply read one value and assign it to one matrix cell. Done.

For adjacency lists you need to prepare the list of neighbors of a node for each of the nodes, i.e. for n nodes you prepare a list of size n that contains an empty list for each entry. Then you again have two nested for-loops: the outer loop goes over the nodes, the inner loop reads the neighbors of that node and adds them to the corresponding inner list. Voila - an adjacency list representation of the graph.

Important addition for programming challenges/competitions: Make sure that you know in your dreams how to write both variants before you even think about competing. There are limitless sample questions and practice sites out there. Search around for problems with graph input, then write and rewrite the input code again and again. It should almost always be nearly the same code, and once you've grown accustomed to it, reading in input like the one you gave above takes you 5 minutes at most. If you want to compete with the really strong players in that field, you should be able to code the input reading for this within about 1 minute or less.

Related Topic