from geopy.distance import distance
from itertools import combinations
from geopy import geocoders
from time import sleep
import pickle
import urllib
import json
with open("cache", "rb") as f:
cache = pickle.load(f)
def dist(start, end):
return distance(start[1], end[1]).meters
def duration(start, end):
if not (start[0], end[0]) in cache:
url = 'http://maps.google.com/maps/nav?key=ABQIAAAAzr2EBOXUKnm_jVnk0OJI7xSosDVG8KKPE1-m51RBrvYughuyMxQ-i1QfUnH94QxWIa6N4U6MouMmBA&q='
url += 'from:' + start[0].replace(' ', '+') + '+to:' + end[0].replace(' ', '+')
data = json.loads(urllib.urlopen(url).read())
cache[(start[0], end[0])] = data['Directions']['Duration']['seconds']
with open("cache", "wb") as f:
pickle.dump(cache, f)
sleep(5)
return cache[(start[0], end[0])]
g = geocoders.Google()
#us = geocoders.GeocoderDotUS()
def geocode_wait(loc, geocoder=g):
if not loc in cache:
r = geocoder.geocode(loc)
cache[loc] = r
with open("cache", "wb") as f:
pickle.dump(cache, f)
sleep(2)
return cache[loc]
def tri(n):
return (n**2 + n) / 2
def selections(mset, k):
res = set()
for c in combinations(mset, k):
res.add(tuple(sorted(c)))
return res
read = str(raw_input("Read data from file? (y/n): "))
print ""
while read not in ['y', 'n']:
print "I did not understand that. Please respond with 'y' or 'n'."
read = str(raw_input("Read data from file? (y/n): "))
print ""
if read == 'n':
print "Please enter your destination."
dest = str(raw_input("Destination: "))
print ""
print "Please enter the number of people who need rides."
need_count = int(raw_input("Rides needed: "))
print ""
print "Please enter the number of people who can offer rides."
avail_count = int(raw_input("Rides available: "))
print ""
need = []
print "Please enter the locations of the people who need rides."
for i in xrange(need_count):
need.append(str(raw_input("Passenger " + str(i + 1) + ": ")))
print ""
del need_count
avail = []
slots = []
print "Please enter the locations of the people who can offer rides and the number of slots available in each vehicle."
for i in xrange(avail_count):
avail.append(str(raw_input("Driver " + str(i + 1) + ": ")))
slots.append(int(raw_input("Slots: ")))
print ""
del avail_count
else:
name = str(raw_input("Please enter file name: "))
print ""
dest = ""
need = []
avail = []
slots = []
print "Reading data from file..."
with open(name) as f:
for line in f:
ldata = line.split(";")
if ldata[0] == "destination":
dest = ldata[1]
elif ldata[0] == "passenger":
need.append(ldata[1])
elif ldata[0] == "driver":
avail.append(ldata[1])
slots.append(int(ldata[2]))
print "Done reading data from file.\n"
if sum(slots) < len(need):
exit("Not enough slots available for all passengers. Had " + str(sum(slots)) + " slots, needed a total of " + str(len(need)) + ".")
print "Geocoding locations..."
#Destination
dest = g.geocode(dest)
#Passengers
need = map(geocode_wait, need)
#Drivers
avail = map(geocode_wait, avail)
print "Done Geocoding locations.\n"
print "Destination is", dest[0]
print ""
for p in xrange(len(need)):
print "Passenger", p + 1, "is at", need[p][0]
print ""
for d in xrange(len(avail)):
if slots[d] == 1:
print "Driver", d + 1, "is at", avail[d][0], "and can take", slots[d], "passenger"
else:
print "Driver", d + 1, "is at", avail[d][0], "and can take", slots[d], "passengers"
print ""
mset = []
for n in xrange(len(slots)):
mset += [n] * slots[n]
choices = selections(mset, len(need))
del mset
def routes(plan, nodes, start=None):
if not start is None:
origin = start
else:
origin = avail[plan[0]]
paths = dict()
for i in xrange(len(nodes)):
cnode = nodes[i]
if plan[1:] != tuple():
if plan[1] == plan[0]:
ops = routes(plan[1:], nodes[:i] + nodes[i+1:], start=cnode)
else:
ops = routes(plan[1:], nodes[:i] + nodes[i+1:])
for op in ops:
paths[(cnode, ) + op] = duration(origin, cnode) + ops[op]
else:
paths[(cnode, )] = duration(origin, cnode)
return paths
best = None
for layout in choices:
pool = need
options = routes(layout, pool)
subbest = (min(options), options[min(options)])
if best is None:
best = (layout,) + subbest
if subbest[1] < best[2]:
best = (layout, ) + subbest
last = -1
for g in xrange(len(best[0])):
if best[0][g] == last:
print "...then continue on to pick up", best[1][g][0]
else:
print "Driver", best[0][g] + 1, "should pick up", best[1][g][0]
last = best[0][g]
print "This setup should yield a total driving time of", best[2], "seconds" |