IntegerZero

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"