In [13]:

    

from itertools import permutations
import pprint
from geopy.distance import vincenty
from random import randint
from copy import deepcopy
from datetime import date, timedelta

pp = pprint.PrettyPrinter(indent=4)

dataset = {
    "cities": {
        "ATL": {
            "name": "Atlanta",
            "location": (33.7550, 84.3900)
        },
        "BOS": {
            "name": "Boston",
            "location": (42.3601, 71.0589)
        },
        "CHI": {
            "name": "Chicago",
            "location": (41.8369, 87.6847)
        },
        "PIT": {
            "name": "Pittsburgh",
            "location": (40.4397, 79.9764)
        }
    },
    "flights":[]
}

cities = dataset["cities"]
flights = dataset["flights"]

base_date = date.today()

def get_price(distance):
    base_price = int(distance.miles / 5)
    float_price = int(base_price / 3)
    return base_price + randint(-float_price, float_price)

# Generte random flight data with price based on location and random
for begin, end in permutations(cities, 2):
    for day in range(20):
        cur = {"origin": begin, "destination": end}
        cur["distance"] = vincenty(cities[begin]["location"], cities[end]["location"])
        cur["date"] = base_date + timedelta(days=day)
        cur["price"] = get_price(cur["distance"])
        flights.append(cur)


def get_flight(origin, destination, days):
    desired_date = base_date + timedelta(days=days)
    for flight in flights:
        if flight["origin"] == origin and flight["destination"] == destination and flight["date"] == desired_date:
            return flight


    

In [14]:

    

min_price = 2 ** 30
final_sequence = []

min_day = 2
max_total_day = 18
# (current_city, current_day, current_price)
initial_state = ("ATL", 0, 0)
city_sequence = [("ATL", 0, 0)]
visited = {city: False for city in dataset["cities"]}
visited["ATL"] = True
def search(state):
    global min_price, final_sequence
    current_city, current_day, current_price = state
    unvisited = [city for city in visited if visited[city] == False]
    
    if not unvisited: # no city left
        for days in range(current_day + min_day, max_total_day):
            flight = get_flight(current_city, "ATL", days)
            final_price = current_price + flight["price"]
            city_sequence.append(("ATL", days, final_price))
            if final_price < min_price:
                min_price = final_price
                final_sequence = deepcopy(city_sequence)
            city_sequence.pop()
            
    for city in unvisited:
        for days in range(current_day + min_day, max_total_day):
            flight = get_flight(current_city, city, days)
            next_state = (city, days, current_price + flight["price"])
            city_sequence.append(next_state)
            visited[city] = True
            search(next_state)
            visited[city] = False
            city_sequence.pop()

search(initial_state)


    

In [15]:

    

print("Generated Sequence:")
for index, step in enumerate(final_sequence):
    print("Step %d: At %s, Day %02d, Total Price $%03d" % (index, step[0], step[1], step[2]))


    

    




Generated Sequence:
Step 0: At ATL, Day 00, Total Price $000
Step 1: At BOS, Day 05, Total Price $126
Step 2: At PIT, Day 10, Total Price $191
Step 3: At CHI, Day 12, Total Price $267
Step 4: At ATL, Day 17, Total Price $345