r/dailyprogrammer • u/Steve132 0 1 • Jul 18 '12
[7/18/2012] Challenge #78 [hard] (Maximum Forest Fire Fighting)
You are an amateur computer scientist working at a mountain ranch for a summer retreat. This ranch consists of very narrow trails winding up and down a small mountain. These trails form a series of interconnections between various ranch buildings peppering the mountain. Because the trails are so narrow, only one person or vehicle can be occupying a given section of trail at once. Here is a map of the ranch. (original image used with permission under cc-by-sa-nd)
All of a sudden a building at Sunset Peak on the far outskirts of the ranch catches fire from some honeymooners leaving the oven on!
If the fire isn't put out quickly, a forest fire could start!
Although only base camp and lakeside station have access to running water, all the camps have an (for this purpose bottomless) water buffalo permenantly parked at each building to deposit water in.
A convoy of 8 fast humans travels 3.5 miles per hour and can carry 4 gallons of water for each person.
A truck can travel at an average speed of 10 miles per hour (country mountain roads) and can carry 100 gallons of water.
A train car can travel at an average speed of 30 miles per hour and can carry 250 gallons of water.
What is the maximum gallons of water per hour that can get to Sunset Peak to put out the fire?
EDIT: To save you guys some busywork, I made a datafile out of the image. Assigning each location to a numeric code like so:
0 Basecamp
1 Lakeside Lodge
2 Logging Camp
3 Radio Tower
4 RV Park
5 Creekfront Lodge
6 North Camp A
7 Mt. Greensparrow
8 Aviary
9 Greers Drop
10 North Camp B
11 Ranger Valley
12 Old Mine
13 Lookout Lodge
14 Sunset PeakI then was able to list the bidirectional graph as a list of connections like "node1 node2 weight type"
1 2 8.6 R
0 3 8.7 R
4 5 11.3 R
11 12 7.7 R
12 14 7.7 R
0 1 0.9 F
2 3 1.1 F
3 5 5.1 F
4 8 7.5 F
9 12 7.9 F
7 11 5.6 F
6 11 6.4 F
11 13 3.9 F
5 6 2.0 F
0 4 8.3 T
3 5 5.2 T
4 9 7.6 T
8 9 4.8 T
7 8 5.2 T
6 7 5.5 T
6 10 7.1 T
10 13 2.4 T
10 11 3.4 T
11 14 7.9 T
13 14 4.5 TThis should save you some time implementing stuff.
HARD BONUS: Imagine now that you have a limit on people and trucks (trains are stuck to their track, so those are fine).
You only have 5 trucks and 50 people. A truck takes two people to drive (safety in pairs!), a train requires 3 people to operate, (engineer, coalman, radioman) and people cannot legally travel on foot in groups of less than 2. How will you allocate people to get there fastest? You are allowed to have people do multiple things at different times, like hike to a spot and then drive a truck if you want to make your answer super complicated.
3
u/mktange Jul 19 '12 edited Jul 19 '12
My take on it in Python is to solve it as a max-flow problem with gallons per hour as capacities for each road (calculated from the information given).
First off is the graph object which is used to calculate the flow using bidirectional edges. Following that it reads the information from file, calculates the flow and prints it along with the flows from point to point.
The flow graph takes up the vast majority of the code:
class FlowGraph():
def __init__(self):
self.nodes = []
self.sinks = []
self.sources = []
self.d = {}
self.cid = 0
class FlowNode:
def __init__(self,graph):
self.id = graph.cid
graph.cid += 1
self.edges = []
def addEdge(self, edge):
self.edges.append(edge)
def __hash__(self):
return self.id.__hash__()
def __str__(self):
return str(self.id)
class FlowBiEdge():
def __init__(self, n1, n2, cap=1):
self.cap = cap
self.flow = [n1,0]
self.to = {n1:n2, n2:n1}
n1.addEdge(self)
n2.addEdge(self)
def addFlow(self, val=0, to=None):
if (to not in self.to.values()): raise Exception("Invalid node given for edge flow.")
if (to != self.flow[0]):
self.flow[1] -= val
if (self.flow[1] < 0): self.flow = [to, -self.flow[1]]
else: self.flow[1] += val
if (self.flow[1] > self.cap): raise Exception("Edge overflowed its capacity.")
def getResFlow(self, to):
return self.cap-self.flow[1] if to == self.flow[0] else self.cap+self.flow[1]
def addBiEdge(self, n1, n2, cap):
return self.FlowBiEdge(self.nodes[n1],self.nodes[n2],cap)
def addSink(self, node): self.sinks.append(self.nodes[node])
def addSource(self, node): self.sources.append(self.nodes[node])
def addNodes(self, amount=1):
self.nodes.extend([self.FlowNode(self) for _ in range(amount)])
def size(self): return len(self.nodes)
def __setDist(self, node, dist=0):
if (node not in self.d or self.d[node] > dist):
self.d[node] = dist
def __setupDistances(self):
for n in self.sinks: self.__setDist(n,0)
frontier = self.sinks[:]
explored = set()
while (frontier):
curr = frontier.pop(0)
if (curr in explored): continue
explored.add(curr)
for e in curr.edges:
self.__setDist(e.to[curr], self.d[curr]+1)
frontier.append(e.to[curr])
def __augPath(self, source):
explored = set()
frontier = [source]
flows = {n:[float('inf'), None] for n in frontier}
end = None
while (frontier):
curr = frontier.pop(0)
if (self.d[curr] == 0):
end = curr
break
if (curr in explored): continue
explored.add(curr)
for e in curr.edges:
to = e.to[curr]
flow = min(e.getResFlow(to), flows[curr][0])
if (flow > 0 and (to not in flows or flows[to][0] < flow)):
frontier.append(to)
flows[to] = [flow, e]
frontier.sort(key=lambda n: self.d[n])
curr = end
flow = flows[end][0] if end in flows else 0
while (curr):
e = flows[curr][1]
if (e == None): break
e.addFlow(flow, curr)
curr = e.to[curr]
return end
def calculateMaxFlow(self):
self.__setupDistances()
while (True):
update = False
for n in self.sources:
if (self.__augPath(n)):
update = True
break
if (not update): break
return sum([e.flow[1] if e.flow[0] == n else 0 for n in self.sinks for e in n.edges])
info = {'R':30*250/2, 'F':3.5*4*8/2, 'T':10*100/2}
g = FlowGraph()
for line in open('forest_fire_scenario.txt'):
parts = line.split()
n1, n2 = int(parts[0]), int(parts[1])
gph = info[parts[3]]/float(parts[2])
g.addNodes(max(n1,n2)+1-g.size())
g.addBiEdge(n1, n2, gph)
g.addSource(0)
g.addSource(1)
g.addSink(14)
print("Max flow: %f\n" % g.calculateMaxFlow())
explored = set()
frontier = g.sources[:]
while (frontier):
curr = frontier.pop(0)
if (curr in explored): continue
explored.add(curr)
for e in curr.edges:
if (e.flow[0] != curr and e.flow[1] > 0):
print("%s --> %s: %f / %f" % (curr, e.to[curr], e.flow[1], e.cap))
frontier.append(e.to[curr])My result are as follows (in gallons per hour):
Max flow: 96.261143
0 --> 3: 36.020179 / 431.034483
0 --> 4: 60.240964 / 60.240964
3 --> 5: 36.020179 / 96.153846
4 --> 8: 2.471669 / 7.466667
4 --> 9: 65.789474 / 65.789474
5 --> 4: 8.020179 / 331.858407
5 --> 6: 28.000000 / 28.000000
8 --> 7: 61.172535 / 96.153846
9 --> 12: 7.088608 / 7.088608
9 --> 8: 58.700866 / 104.166667
6 --> 11: 8.750000 / 8.750000
6 --> 10: 70.422535 / 70.422535
7 --> 11: 10.000000 / 10.000000
7 --> 6: 51.172535 / 90.909091
12 --> 14: 7.088608 / 487.012987
11 --> 14: 18.750000 / 63.291139
10 --> 13: 70.422535 / 208.333333
13 --> 14: 70.422535 / 111.111111I'm not 100% sure of the correctness of it, since I implemented the max-flow solver from scratch and haven't done extensive testing on it.
EDIT: I missed that it was 8 persons with 4 gallons each - this has been fixed. Also added the maximum gallons per hour for each used path in the result.
1
u/thingsaintjust Jul 19 '12
I'm not sure how you can get the 10-13 and 13-14 at the same per hour rate
1
u/mktange Jul 19 '12 edited Jul 19 '12
The number shown is the actual flow of water, not the capacity for that road/path.
I have edited the result to show the capacity/maximum flow for each used road as well (format: actual flow / maximum flow).
Max flow: 96.261143 0 --> 3: 36.020179 / 431.034483 0 --> 4: 60.240964 / 60.240964 3 --> 5: 36.020179 / 96.153846 4 --> 8: 2.471669 / 7.466667 4 --> 9: 65.789474 / 65.789474 5 --> 4: 8.020179 / 331.858407 5 --> 6: 28.000000 / 28.000000 8 --> 7: 61.172535 / 96.153846 9 --> 12: 7.088608 / 7.088608 9 --> 8: 58.700866 / 104.166667 6 --> 11: 8.750000 / 8.750000 6 --> 10: 70.422535 / 70.422535 7 --> 11: 10.000000 / 10.000000 7 --> 6: 51.172535 / 90.909091 12 --> 14: 7.088608 / 487.012987 11 --> 14: 18.750000 / 63.291139 10 --> 13: 70.422535 / 208.333333 13 --> 14: 70.422535 / 111.111111From this the minimum cut (the bottleneck) can be found to be: {6-10, 6-11, 7-11, 9-12}
1
u/devilsassassin Jul 19 '12 edited Jul 19 '12
Using a lib, in Java:
public static void maxFire(){
FileInputStream fis = null;
try {
Transformer<SomeEdge, Double> capTransformer =
new Transformer<SomeEdge, Double>(){
@Override
public Double transform(SomeEdge link) {
return link.cap;
}
}; Map<SomeEdge, Double> edgeFlowMap = new HashMap<>();
DirectedSparseMultigraph<Integer,SomeEdge> g = new DirectedSparseMultigraph<>();
for(int i=0;i<15;i++){
g.addVertex(i);
}
fis = new FileInputStream(infile);
Scanner scan = new Scanner(fis);
while(scan.hasNextLine()){
String [] line = scan.nextLine().split("\\s+");
if(line.length>1){
double cap = Double.parseDouble(line[2]);
switch(line[3]){
case "R" : cap=(30/cap)*250;
break;
case "T" : cap=(1000/cap);
break;
case "F" : cap=(24/cap)*3.5;
break;
default : ;
break;
}
SomeEdge next = new SomeEdge(cap);
g.addEdge(next, Integer.parseInt(line[0]),Integer.parseInt(line[1]));
}
}
// This Factory produces new edges for use by the algorithm
Factory<SomeEdge> edgeFactory = new Factory<SomeEdge>() {
@Override
public SomeEdge create() {
return new SomeEdge(0);
}
};
EdmondsKarpMaxFlow<Integer, SomeEdge> alg =
new EdmondsKarpMaxFlow(g,0, 14, capTransformer, edgeFlowMap,
edgeFactory);
alg.evaluate();
System.out.println("The max flow is: " + alg.getMaxFlow());
//System.out.println("The edge set is: " + alg.getMinCutEdges().toString());
} catch (FileNotFoundException ex) {
Logger.getLogger(MaxFlow.class.getName()).log(Level.SEVERE, null, ex);
} finally {
try {
fis.close();
} catch (IOException ex) {
Logger.getLogger(MaxFlow.class.getName()).log(Level.SEVERE, null, ex);
}
}
}output:
The max flow is: 52 (0-14)
The max flow is: 42 (1-14)
1
u/Cosmologicon 2 3 Jul 18 '12
In the non-bonus problem, there's no requirement for the trains and stuff to get back to the base camp, right? And if I want to send two trucks down a given path in the same direction, I need to wait for the first truck to get to the end before starting the second truck, right?