Routing Mario's Time Machine

# optimize Mario's Time Machine
from collections import namedtuple
from itertools import permutations

LOCATION_WHEEL = [
    'Menlo Park',
    'Orleans',
    'London',
    'Alexandria',
    'Calcutta',
    'Mainz',
    'Philadelphia',
    'Vienna',
    'The Pacific',
    'Gobi Desert',
    'Florence',
    'Cambridge',
    'Athens',
    'Stratford',
]

class Destination(namedtuple('Destination', ['obj', 'pos', 'location', 'year', 'ad'])):
    __slots__ = ()
    def __str__(self):
        return '{} @ position {} ({}, {} {})'.format(self.obj, self.pos,
            self.location, self.year, 'AD' if self.ad else 'BC')

INITIAL_POSITION = Destination(obj=None, pos=None, location='Menlo Park', year='1993', ad=True)
FLOORS = [
    [
        Destination(obj='apple', pos=1, location='Cambridge', year='1867', ad=True),
        Destination(obj='shield', pos=2, location='Orleans', year='1429', ad=True),
        Destination(obj='papers', pos=3, location='Florence', year='1505', ad=True),
        Destination(obj='music', pos=4, location='Vienna', year='1824', ad=True),
        Destination(obj='declaration', pos=5, location='Philadelphia', year='1776', ad=True),
    ],
    [
        Destination(obj='filament', pos=1, location='Menlo Park', year='1879', ad=True),
        Destination(obj='block', pos=2, location='Gobi Desert', year='1292', ad=True),
        Destination(obj='book', pos=3, location='Athens', year='0369', ad=False),
        Destination(obj='crown', pos=4, location='London', year='1595', ad=True),
        Destination(obj='flag', pos=5, location='Calcutta', year='1947', ad=True),
    ],
    [
        Destination(obj='printer', pos=1, location='Mainz', year='1455', ad=True),
        Destination(obj='globe', pos=2, location='The Pacific', year='1521', ad=True),
        Destination(obj='chisel', pos=3, location='Florence', year='1503', ad=True),
        Destination(obj='skull', pos=4, location='Stratford', year='1601', ad=True),
        Destination(obj='staff', pos=5, location='Alexandria', year='0047', ad=False),
    ],
]

LOCATION_WHEEL_TIME = 64
YEAR_WHEEL_TIME = 68
AD_SLIDER_TIME = 16

def time_between(a, b):
    destdiff = abs(LOCATION_WHEEL.index(a.location) - LOCATION_WHEEL.index(b.location))
    destdiff = min(destdiff, len(LOCATION_WHEEL) - destdiff)

    yeardiff = 0
    for x,y in zip(a.year, b.year):
        xi, yi = int(x), int(y)
        yeardiff += min(10 - abs(xi-yi), abs(xi-yi))

    adslider = AD_SLIDER_TIME if a.ad != b.ad else 0
    return destdiff * LOCATION_WHEEL_TIME + yeardiff * YEAR_WHEEL_TIME + adslider

best, bcost = None, 1000000000000
for floor1 in permutations(FLOORS[0]):
    for floor2 in permutations(FLOORS[1]):
        for floor3 in permutations(FLOORS[2]):
            order = floor1 + floor2 + floor3
            cost = time_between(INITIAL_POSITION, order[0])
            for x,y in zip(order[:-1], order[1:]):
                cost += time_between(x,y)
            if cost < bcost:
                best, bcost = order, cost

print("\n".join(str(dest) for dest in best))