"""
Randy Olson's Shortest Route Program modified By Andrew Liesinger to:
    1: Detect waypoints file at runtime - if found use it, otherwise look up distances via google calls (and then save to waypoint file)
    2: Dynamically create and open an HTML file showing the route when a shorter route is found
    3: Make it easier to tinker with the Generation / Population parameters
"""
from __future__ import print_function
from itertools import combinations
import googlemaps
import pandas as pd
import numpy as np
import os.path
import random
import webbrowser

GOOGLE_MAPS_API_KEY = "AIzaSyCcN9TfZDA9IqyYkMTptWauQ53KTmWxkM4"
waypoints_file = "my-waypoints-dist-dur.tsv"

#This is the general filename - as shorter routes are discovered the Population fitness score will be inserted into the filename
#so that interim results are saved for comparision.  The actual filenames using the default below will be:
#Output_<Population Fitness Score>.html
output_file = 'BrianKuoRoadTrip.html'

#parameters for the Genetic algoritim
thisRunGenerations=10000
thisRunPopulation_size=1000

# ================================================================================
# Family/Friend Constraints
# ================================================================================
# I'll be in Atlanta with my Dad from July 26th - 29th
# I'll be with Allison in Florida between the 15th and the 21st of August
# The best timing for me would probably be mid/late July

# So I just checked my calendar. If I'm going to do 3 weekends, it would have to be between the days of July 6th to July 22nd.

# ================================================================================
# National Parks - 34 (+ 4?)
# ================================================================================
national_park_waypoints = [

"Acadia National Park, Maine, USA", #Acadia National Park
"Cuyahoga Valley National Park, Ohio, USA", #Cuyahoga Valley National Park
"Medora, ND 58645, USA", #Theodore Roosevelt National Park
"Porcupine, SD 57772, USA", #Badlands National Park
"26611 US-385, Hot Springs, SD 57747, USA", #Wind Cave National Park
"Rocky Mountain National Park, Colorado, USA", #Rocky Mountain National Park
"Great Sand Dunes National Park and Preserve, Colorado, USA", #Great Sand Dunes National Park and Preserve
"9800 CO-347, Montrose, CO 81401, USA", #Black Canyon of the Gunnison National Park
"35853 Rd H.5, Mancos, CO 81328, USA", #Mesa Verde National Park
"Canyonlands National Park, Utah, USA", #Canyonlands National Park
"Moab, UT 84532, USA", #Arches National Park
"UT-24, Torrey, UT 84775, USA", #Capitol Reef National Park
"Bryce Canyon National Park, Utah, USA", #Bryce Canyon National Park
"Great Basin National Park, Nevada, USA", #Great Basin National Park
"Grand Teton National Park, Wyoming, USA", #Grand Teton National Park
"30 Yellowstone Ave, West Yellowstone, MT 59758, USA", #Yellowstone National Park
"Glacier National Park, Montana, USA", #Glacier National Park
"North Cascades National Park, Washington, USA", #North Cascades National Park
"Mount Rainier National Park, Washington, USA", #Mount Rainier National Park
"Olympic National Park, 3002 Mt Angeles Rd, Port Angeles, WA 98362, USA", #Olympic National Park
"Crater Lake National Park, Oregon, USA", #Crater Lake National Park
"Redwood National and State Parks, California, USA", #Redwood National and State Parks
"Lassen Volcanic National Park, California, USA", #Lassen Volcanic National Park
"Pinnacles National Park, California 95043, USA", #Pinnacles National Park
"71487 Twentynine Palms Highway, Twentynine Palms, CA 92277, USA", #Joshua Tree National Park
"Furnace Creek, CA 92328, USA", #Death Valley National Park
"Saguaro National Park Rincon Mountain District (West) Visitor Center, 2700 N Kinney Rd, Tucson, AZ 85743, USA", #Saguaro National Park
"Guadalupe Mountains National Park, Salt Flat, TX 79847, USA", #Guadalupe Mountains National Park
"Big Bend National Park, Big Bend National Park, TX, USA", #Big Bend National Park
"Hot Springs National Park, 369 Central Ave, Hot Springs, AR 71901, USA", #Hot Springs National Park
"Mammoth Cave National Park, Kentucky, USA", #Mammoth Cave National Park
"Great Smoky Mountains National Park, United States", #Great Smoky Mountains National Park
"Congaree National Park, 100 National Park Rd, Hopkins, SC 29061, USA", #Congaree National Park
"Shenandoah National Park, Virginia, USA", #Shenandoah National Park

]
# ================================================================================
# 2018 FSGP/ASC
# ================================================================================

# http://americansolarchallenge.org/ASC/wp-content/uploads/2017/08/FSGP-2018-Schedule-Calendar-View.pdf

#FSGP - Hastings, NE
#July 6, 7, 8, 9 - Scrutineering
#July 10, 11, 12 - Raycing

# http://americansolarchallenge.org/ASC/wp-content/uploads/2018/04/ASC-2018-Overview.pdf

#ASC - Omaha, NE
#July 13, 14

#ASC - Grand Island, NE
#July 14

#ASC - Gering, NE
#July 15, 16

#ASC - Casper, WY
#July 16

#ASC - Lander, WY
#July 17, 18

#ASC - Farson, WY
#July 18

#ASC - Arco, WY
#July 19

#ASC - Craters of the Moon, ID
#July 20

#ASC - Mountain Home, ID
#July 20

#ASC - Burns, OR
#July 21, 22

#ASC - Bend, OR
#July 22


# ================================================================================
# Other National Park Service Sites
# ================================================================================
other_NPS_waypoints = []


#                  "Mount Rushmore National Memorial, South Dakota 244, Keystone, SD",
#                  "Lincoln Home National Historic Site Visitor Center, 426 South 7th Street, Springfield, IL",
#                  "Wright Brothers National Memorial Visitor Center, Manteo, NC",
#Manzanar Japanese Internment Camp
#Little Bighorn Battlefield?
#Natural Bridges
#Mount Saint Helens
#First state national historical park?
#White Sands
#Thomas Edison National Historical Park
#Golden Spike National Historic Site
#Lincoln Home National Historic Site
#Minuteman Missile National Historic Site
#Flight 93 national memorial
#Devil's tower
#Mount Rushmore
#Craters of the moon
#Chimney Rock
#antelope Canyon
#Rainbow Bridge


# ================================================================================
# Potential Points of Interest
# ================================================================================
POI_waypoints = []
#"Pikes Peak, Colorado",
#Crazy horse
#NASA Facilities?
#"Gateway Arch, Washington Avenue, St Louis, MO",
#FIREWATCH LOOKOUT TOWER
#Niagara Falls


# ================================================================================
# Cities
# ================================================================================
cities_waypoints = [
"Chicago, IL, USA",
"San Fransisco, CA, USA",
"Seattle, WA, USA",
"Toronto, ON, Canada",
"Philadelphia, PA, USA",
"Boston, MA, USA",
"Denver, CO, USA",
"Portland, OR, USA",
"Vancouver, BC, Canada"
]

# Burlington?
# Providence?
# Hartford?
# Augusta?
# Minneapolis?
# Fargo?
# Big Sur
# Sacramento?
# Los Angeles?
# Dallas?

# ================================================================================
# Questionable
# ================================================================================
questionable_waypoints = [
# "9700 SW 328th St, Homestead, FL 33033, USA", #Biscayne National Park
# "40001 State Hwy 9336, Homestead, FL 33034, USA", #Everglades National Park
# "1901 Spinnaker Dr, Ventura, CA 93001, USA", #Channel Islands National Park
# "Voyageurs National Park, 360 MN-11, International Falls, MN 56649, USA" #Voyageurs National Park

]


all_waypoints = national_park_waypoints + other_NPS_waypoints + POI_waypoints + cities_waypoints + questionable_waypoints

def CreateOptimalRouteHtmlFile(optimal_route, distance, display=True):
    optimal_route = list(optimal_route)
    optimal_route += [optimal_route[0]]

    Page_1 = """
    <!DOCTYPE html>
    <html lang="en">
      <head>
        <meta charset="utf-8">
        <meta name="viewport" content="initial-scale=1.0, user-scalable=no">
        <meta name="description" content="Randy Olson uses machine learning to find the optimal road trip across the U.S.">
        <meta name="author" content="Randal S. Olson">

        <title>The optimal road trip across the U.S. according to machine learning</title>
        <style>
          html, body, #map-canvas {
            height: 100%;
            margin: 0px;
            padding: 0px
          }
          #panel {
            position: absolute;
            top: 5px;
            left: 50%;
            margin-left: -180px;
            z-index: 5;
            background-color: #fff;
            padding: 10px;
            border: 1px solid #999;
          }
        </style>
        <script src="https://maps.googleapis.com/maps/api/js?v=3.exp&signed_in=true"></script>
        <script>

"""
    Page_2 = """
            var routes_list = []
            //var markerOptions = {icon: "http://maps.gstatic.com/mapfiles/markers2/marker.png"};
            //var markerOptions = {icon: "http://i.imgur.com/fUKnx8P.png"};
            var directionsDisplayOptions = {preserveViewport: true,
            //                                markerOptions: markerOptions,
                                            suppressMarkers: true};
            var directionsService = new google.maps.DirectionsService();
            var map;


            function initialize() {
              var center = new google.maps.LatLng(39, -96);
              var mapOptions = {
                zoom: 5,
                center: center,
                mapTypeId: google.maps.MapTypeId.ROADMAP
              };
              map = new google.maps.Map(document.getElementById('map-canvas'), mapOptions);
              for (i=0; i<routes_list.length; i++) {
                routes_list[i].setMap(map);
              }

            var infowindow = new google.maps.InfoWindow;
            var national_park_link = "http://i.imgur.com/fUKnx8P.png";
            var other_NPS_link = "https://i.imgur.com/kUwSLiA.png";
            var POI_link = "https://i.imgur.com/bNIsBJm.png";
            var cities_link = "https://i.imgur.com/ZKFeMTj.png";
            var question_link = "https://i.imgur.com/dfQZ5dD.png";


            var locations = [

// ================================================================================
// National Parks - 34 (+ 4?)
// ================================================================================
            ['Acadia National Park', 44.353199, -68.274928, national_park_link],
            ['Cuyahoga Valley National Park', 41.282981, -81.571746, national_park_link],
            ['Theodore Roosevelt National Park', 46.916649, -103.524464, national_park_link],
            ['Badlands National Park', 43.235865, -102.326154, national_park_link],
            ['Wind Cave National Park', 43.492139, -103.461198, national_park_link],
            ['Rocky Mountain National Park', 40.335739, -105.666891, national_park_link],
            ['Great Sand Dunes National Park and Preserve', 37.747465, -105.500359, national_park_link],
            ['Black Canyon of the Gunnison National Park', 38.540691, -107.700991, national_park_link],
            ['Mesa Verde National Park', 37.334690, -108.406994, national_park_link],
            ['Canyonlands National Park', 38.310718, -109.855298, national_park_link],
            ['Arches National Park', 38.590752, -109.566939, national_park_link],
            ['Capitol Reef National Park', 38.299454, -111.419043, national_park_link],
            ['Bryce Canyon National Park', 37.622720, -112.191269, national_park_link],
            ['Great Basin National Park', 39.006082, -114.217622, national_park_link],
            ['Grand Teton National Park', 43.791731, -110.683027, national_park_link],
            ['Yellowstone National Park', 44.659798, -111.098267, national_park_link],
            ['Glacier National Park', 48.484216, -113.996058, national_park_link],
            ['North Cascades National Park', 48.999747, -121.061963, national_park_link],
            ['Mount Rainier National Park', 46.737220, -121.831287, national_park_link],
            ['Olympic National Park', 48.101289, -123.425841, national_park_link],
            ['Crater Lake National Park', 42.867356, -122.171270, national_park_link],
            ['Redwood National and State Parks', 41.349842, -124.027042, national_park_link],
            ['Lassen Volcanic National Park', 40.497400, -121.421209, national_park_link],
            ['Pinnacles National Park', 36.490279, -121.182504, national_park_link],
            ['Joshua Tree National Park', 34.134354, -116.103262, national_park_link],
            ['Death Valley National Park', 36.448122, -116.852817, national_park_link],
            ['Saguaro National Park', 32.254429, -111.197227, national_park_link],
            ['Guadalupe Mountains National Park', 31.941920, -104.873669, national_park_link],
            ['Big Bend National Park', 29.126625, -103.243469, national_park_link],
            ['Hot Springs National Park', 34.514589, -93.053847, national_park_link],
            ['Mammoth Cave National Park', 37.185517, -86.101458, national_park_link],
            ['Great Smoky Mountains National Park', 35.557637, -84.009101, national_park_link],
            ['Congaree National Park', 33.792382, -80.768785, national_park_link],
            ['Shenandoah National Park', 38.095057, -78.816753, national_park_link],

// ================================================================================
// Other National Park Service Sites
// ================================================================================
//# "Lincoln Home National Historic Site Visitor Center, 426 South 7th Street, Springfield, IL",
//#Manzanar Japanese Internment Camp
//#Natural Bridges
//#First state national historical park?
//#Thomas Edison National Historical Park
//#Lincoln Home National Historic Site
//#Minuteman Missile National Historic Site
//#Craters of the moon
//#Chimney Rock
//#Rainbow Bridge


['Mount Rushmore National Memorial', 43.879036, -103.458946, other_NPS_link],
['Wright Brothers National Memorial', 36.014331, -75.667901, other_NPS_link],
['Mount Saint Helens', 46.276375, -122.216415, other_NPS_link],
['White Sands National Monument', 32.781837, -106.329353, other_NPS_link],
['Golden Spike National Historic Site', 41.617454, -112.550943, other_NPS_link],
['Flight 93 National Memorial', 40.056539, -78.905805, other_NPS_link],
['Antelope Canyon', 36.897225, -111.408851, other_NPS_link],
['Devils Tower National Monument', 44.590225, -104.714607, other_NPS_link],
['Little Bighorn Battlefield', 45.570121, -107.432388, other_NPS_link],
['Craters of the Moon National Monument & Preserve', 43.205791, -113.500202, other_NPS_link],



// ================================================================================
// Potential Points of Interest
// ================================================================================
['Niagara Falls', 43.087956, -79.081180, POI_link],

// Bodie, CA?


// ================================================================================
// Cities
// ================================================================================
['Chicago, IL', 41.877848, -87.631670, cities_link],
['San Fransisco, CA', 37.774277, -122.418903, cities_link],
['Seattle, WA', 47.606001, -122.331966, cities_link],
['Toronto, ON', 43.652830, -79.386018, cities_link],
['Philadelphia, PA', 39.951646, -75.166148, cities_link],
['Boston, MA', 42.358930, -71.059560, cities_link],
['Denver, CO', 39.736549, -104.991118, cities_link],
['Portland, OR', 45.521196, -122.677780, cities_link],
['Vancouver, BC', 49.281396, -123.121168, cities_link],


// ================================================================================
// Questionable
// ================================================================================
            ['Biscayne National Park', 25.464471, -80.334751, question_link],
            ['Everglades National Park', 25.395347, -80.583131, question_link],
            ['Channel Islands National Park', 34.248528, -119.266543, question_link],
            ['Voyageurs National Park', 48.603372, -93.376871, question_link]


            ];

            for (i = 0; i < locations.length; i++) {
              marker = new google.maps.Marker({
               position: new google.maps.LatLng(locations[i][1], locations[i][2]),
               map: map,
               icon: locations[i][3]
             });

              google.maps.event.addListener(marker, 'click', (function(marker, i) {
               return function() {
                 infowindow.setContent(locations[i][0]);
                 infowindow.open(map, marker);
               }
             })(marker, i));
            }


            }

            function calcRoute(start, end, routes) {

              var directionsDisplay = new google.maps.DirectionsRenderer(directionsDisplayOptions);

              var waypts = [];
              for (var i = 0; i < routes.length; i++) {
                waypts.push({
                  location:routes[i],
                  stopover:true});
                }



              var request = {
                  origin: start,
                  destination: end,
                  waypoints: waypts,
                  optimizeWaypoints: false,
                  travelMode: google.maps.TravelMode.DRIVING
              };

              directionsService.route(request, function(response, status) {
                if (status == google.maps.DirectionsStatus.OK) {
                    directionsDisplay.setDirections(response);
                }
              });

              routes_list.push(directionsDisplay);
            }

            function createRoutes(route) {
                // Google's free map API is limited to 10 waypoints so need to break into batches
                route.push(route[0]);
                var subset = 0;
                while (subset < route.length) {
                    var waypointSubset = route.slice(subset, subset + 10);

                    var startPoint = waypointSubset[0];
                    var midPoints = waypointSubset.slice(1, waypointSubset.length - 1);
                    var endPoint = waypointSubset[waypointSubset.length - 1];

                    calcRoute(startPoint, endPoint, midPoints);

                    subset += 9;
                }
            }

            // function createMarker(latlng) {

            //   var marker = new google.maps.Marker({
            //     position: latlng,
            //     map: map,
            //     icon: "http://i.imgur.com/fUKnx8P.png"
            //   });
            // }



            createRoutes(optimal_route);




        // var map = new google.maps.Map(document.getElementById('map'), {
        //   zoom: 4,
        //   center: myLatLng
        // }









            google.maps.event.addDomListener(window, 'load', initialize);

        </script>
      </head>
      <body>
        <div id="map-canvas"></div>
      </body>
    </html>

    """

    localoutput_file = output_file.replace('.html', '_' + str(distance) + '.html')
    with open(localoutput_file, 'w') as fs:
        fs.write(Page_1)
        fs.write("\n\t\t\tnational_park_waypoints = {0}".format(str(national_park_waypoints)))
        fs.write("\n\n\t\t\tother_NPS_waypoints = {0}".format(str(other_NPS_waypoints)))
        fs.write("\n\n\t\t\tPOI_waypoints = {0}".format(str(POI_waypoints)))
        fs.write("\n\n\t\t\tcities_waypoints = {0}\n".format(str(cities_waypoints)))
        fs.write("\n\n\t\t\toptimal_route = {0}\n".format(str(optimal_route)))

        fs.write(Page_2)

    if display:
        webbrowser.open_new_tab(localoutput_file)


def compute_fitness(solution):
    """
        This function returns the total distance traveled on the current road trip.

        The genetic algorithm will favor road trips that have shorter
        total distances traveled.
    """

    solution_fitness = 0.0

    for index in range(len(solution)):
        waypoint1 = solution[index - 1]
        waypoint2 = solution[index]
        solution_fitness += waypoint_distances[frozenset([waypoint1, waypoint2])]

    return solution_fitness

def generate_random_agent():
    """
        Creates a random road trip from the waypoints.
    """

    new_random_agent = list(all_waypoints)
    random.shuffle(new_random_agent)
    return tuple(new_random_agent)

def mutate_agent(agent_genome, max_mutations=3):
    """
        Applies 1 - `max_mutations` point mutations to the given road trip.

        A point mutation swaps the order of two waypoints in the road trip.
    """

    agent_genome = list(agent_genome)
    num_mutations = random.randint(1, max_mutations)

    for mutation in range(num_mutations):
        swap_index1 = random.randint(0, len(agent_genome) - 1)
        swap_index2 = swap_index1

        while swap_index1 == swap_index2:
            swap_index2 = random.randint(0, len(agent_genome) - 1)

        agent_genome[swap_index1], agent_genome[swap_index2] = agent_genome[swap_index2], agent_genome[swap_index1]

    return tuple(agent_genome)

def shuffle_mutation(agent_genome):
    """
        Applies a single shuffle mutation to the given road trip.

        A shuffle mutation takes a random sub-section of the road trip
        and moves it to another location in the road trip.
    """

    agent_genome = list(agent_genome)

    start_index = random.randint(0, len(agent_genome) - 1)
    length = random.randint(2, 20)

    genome_subset = agent_genome[start_index:start_index + length]
    agent_genome = agent_genome[:start_index] + agent_genome[start_index + length:]

    insert_index = random.randint(0, len(agent_genome) + len(genome_subset) - 1)
    agent_genome = agent_genome[:insert_index] + genome_subset + agent_genome[insert_index:]

    return tuple(agent_genome)

def generate_random_population(pop_size):
    """
        Generates a list with `pop_size` number of random road trips.
    """

    random_population = []
    for agent in range(pop_size):
        random_population.append(generate_random_agent())
    return random_population

def run_genetic_algorithm(generations=5000, population_size=100):
    """
        The core of the Genetic Algorithm.

        `generations` and `population_size` must be a multiple of 10.
    """

    current_best_distance = -1
    population_subset_size = int(population_size / 10.)
    generations_10pct = int(generations / 10.)

    # Create a random population of `population_size` number of solutions.
    population = generate_random_population(population_size)

    # For `generations` number of repetitions...
    for generation in range(generations):

        # Compute the fitness of the entire current population
        population_fitness = {}

        for agent_genome in population:
            if agent_genome in population_fitness:
                continue

            population_fitness[agent_genome] = compute_fitness(agent_genome)

        # Take the top 10% shortest road trips and produce offspring each from them
        new_population = []
        for rank, agent_genome in enumerate(sorted(population_fitness,
                                                   key=population_fitness.get)[:population_subset_size]):
            if (generation % generations_10pct == 0 or generation == generations - 1) and rank == 0:
                current_best_genome = agent_genome
                print("Generation %d best: %d | Unique genomes: %d" % (generation,
                                                                       population_fitness[agent_genome],
                                                                       len(population_fitness)))
                print(agent_genome)
                print("")

                # If this is the first route found, or it is shorter than the best route we know,
                # create a html output and display it
                if population_fitness[agent_genome] < current_best_distance or current_best_distance < 0:
                    current_best_distance = population_fitness[agent_genome]
                    CreateOptimalRouteHtmlFile(agent_genome, current_best_distance, False)


            # Create 1 exact copy of each of the top road trips
            new_population.append(agent_genome)

            # Create 2 offspring with 1-3 point mutations
            for offspring in range(2):
                new_population.append(mutate_agent(agent_genome, 3))

            # Create 7 offspring with a single shuffle mutation
            for offspring in range(7):
                new_population.append(shuffle_mutation(agent_genome))

        # Replace the old population with the new population of offspring
        for i in range(len(population))[::-1]:
            del population[i]

        population = new_population
    return current_best_genome


if __name__ == '__main__':
    # If this file exists, read the data stored in it - if not then collect data by asking google
    print("Begin finding shortest route")
    file_path = waypoints_file
    if os.path.exists(file_path):
        print("Waypoints exist")
        #file exists used saved results
        waypoint_distances = {}
        waypoint_durations = {}
        all_waypoints = set()

        waypoint_data = pd.read_csv(file_path, sep="\t")

        for i, row in waypoint_data.iterrows():
            waypoint_distances[frozenset([row.waypoint1, row.waypoint2])] = row.distance_m
            waypoint_durations[frozenset([row.waypoint1, row.waypoint2])] = row.duration_s
            all_waypoints.update([row.waypoint1, row.waypoint2])

    else:
        # File does not exist - compute results
        print("Collecting Waypoints")
        waypoint_distances = {}
        waypoint_durations = {}


        gmaps = googlemaps.Client(GOOGLE_MAPS_API_KEY)
        for (waypoint1, waypoint2) in combinations(all_waypoints, 2):
            try:
                route = gmaps.distance_matrix(origins=[waypoint1],
                                              destinations=[waypoint2],
                                              mode="driving", # Change to "walking" for walking directions,
                                                              # "bicycling" for biking directions, etc.
                                              language="English",
                                              units="metric")

                # "distance" is in meters
                distance = route["rows"][0]["elements"][0]["distance"]["value"]

                # "duration" is in seconds
                duration = route["rows"][0]["elements"][0]["duration"]["value"]

                waypoint_distances[frozenset([waypoint1, waypoint2])] = distance
                waypoint_durations[frozenset([waypoint1, waypoint2])] = duration

            except Exception as e:
                print("Error with finding the route between %s and %s." % (waypoint1, waypoint2))

        print("Saving Waypoints")
        with open(waypoints_file, "w") as out_file:
            out_file.write("\t".join(["waypoint1",
                                      "waypoint2",
                                      "distance_m",
                                      "duration_s"]))

            for (waypoint1, waypoint2) in waypoint_distances.keys():
                out_file.write("\n" +
                               "\t".join([waypoint1,
                                          waypoint2,
                                          str(waypoint_distances[frozenset([waypoint1, waypoint2])]),
                                          str(waypoint_durations[frozenset([waypoint1, waypoint2])])]))

    print("Search for optimal route")
    optimal_route = run_genetic_algorithm(generations=thisRunGenerations, population_size=thisRunPopulation_size)

    # This is probably redundant now that the files are created in run_genetic_algorithm,
    # but leaving it active to ensure  the final result is not lost
    CreateOptimalRouteHtmlFile(optimal_route, 1, True)