IntegerZero

from collections import defaultdict
 
def format_tape(tape, pos, width=80):
    left = ""
    right = ""
    center = "|" + str(tape[0]) + "|"
    if pos == 0:
        center = "*" + str(tape[0]) + "*"
    mi = min(tape.keys())
    ma = max(tape.keys())
    for i in xrange(mi, 0):
        if pos == i:
            left += "_" + str(tape[i]) + "_ "
        else:
            left += " " + str(tape[i]) + "  "
    for i in xrange(1, ma + 1):
        if pos == i:
            right += " _" + str(tape[i]) + "_"
        else:
            right += "  " + str(tape[i]) + " "
    return " "*(38 - len(left)) + left + center + right
 
instructions = dict()
 
instructions[(0, 0)] = (1, 1, 1)
instructions[(1, 0)] = (1, -1, 0)
instructions[(2, 0)] = (1, -1, 1)
instructions[(0, 1)] = (1, -1, 2)
instructions[(1, 1)] = (1, 1, 1)
instructions[(2, 1)] = (1, 0, -1)
 
 
#{(state, symbol) : (write, move, state change)}
#move = {-1, 0, 1}
#write = (a number from alphabet) or None (do nothing)
#state change = (a number from states) or -1 (halt) or None (no change)
 
output = int(raw_input("Print tape as we go? (1 or 0): "))
 
tape = defaultdict(int)
 
state = 0
pos = 0
 
while state != -1:
    #Halt if no rule is present
    if not (state, tape[pos]) in instructions:
        print "No rule for (" + str(state) + ", " + str(tape[pos]) + ")"
        break
 
    instruction = instructions[(state, tape[pos])]
 
    #Excecute instruction
    if instruction[0] != None:
        tape[pos] = instruction[0]
    pos += instruction[1]
    if instruction[2] != None:
        state = instruction[2]
 
    if output:
        print format_tape(tape, pos)
print "Halted."

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"