#! /usr/bin/env python3

"""This program demonstrates a greedy solution to the traveling
salesman problem.
"""

import random
import time
import math

## we use the tkinter widget set; this seems to come automatically
## with python3 on ubuntu 16.04, but on some systems one might need to
## install a package with a name like python3-tk
from tkinter import *

canvas_width = 700
canvas_height = 500
n_cities = 70
# canvas_width = 1280
# canvas_height = 1024
# n_cities = 200
algo_name = 'hillclimbing'
iter = 0

def main():
    ## prepare a basic canvas
    root = Tk()
    w = Canvas(root, 
               width=canvas_width,
               height=canvas_height)
    w.pack()       # boiler-plate: we always call pack() on tk windows
    city_list = make_random_cities(0, canvas_width-1, 
                                   0, canvas_height-1, n_cities)
    update_drawing(w, city_list)
    w.update()
    ## Now try a hillclimbing solution: start with one path and swap
    ## random pairs of cities in the path when that swap would shorten
    ## the total path.
    global iter
    for iter in range(1000000):
        swap_pair = hillclimbing_take_step(city_list, shorter=True)
        if not swap_pair:       # no step was taken
            continue
        ## now do the drawing/animation
        update_drawing(w, city_list)
        ## now give special highlight to the cities that were just swapped
        draw_city(w, swap_pair[0][0], swap_pair[0][1], color='red', name='A')
        draw_city(w, swap_pair[1][0], swap_pair[1][1], color='yellow', name='B')
        w.update()
        # time.sleep(1.0/2.0)    # so many frames per second

    mainloop()

def update_drawing(w, city_list):
    w.delete("all")
    ## we draw the full list of cities (without connections) and
    ## then the current path in a different color, so we can see
    ## the progress.
    draw_city_path(w, city_list, color='black', connect=True)
    write_info_at_bottom(w, canvas_width, canvas_height, city_list)

def draw_city_path(w, city_list, color='white', connect=False):
    """draws lines between the cities"""
    for city in city_list:
        draw_city(w, city[0], city[1], color=color)
    draw_city(w, city_list[0][0], city_list[0][1], color='blue', name='Home')
    ## now draw lines between them
    if connect:
        for i in range(len(city_list)-1):
            w.create_line(city_list[i][0], city_list[i][1], 
                          city_list[i+1][0], city_list[i+1][1])

def make_random_cities(xmin, xmax, ymin, ymax, n_cities):
    """returns a list of randomly placed cities in the given rectangle"""
    city_list = []
    for i in range(n_cities):
        x = random.randint(xmin, xmax)
        y = random.randint(ymin, ymax)
        city_list.append((x, y))
    return city_list

def draw_city(w, x, y, color='yellow', name=None):
    """draws a city; if a name is given also writes the name of it"""
    w.create_oval(x-5, y-5, x+5, y+5, fill=color)
    ## if a name was given, write in the name
    if name:
        w.create_text(x, y+10, text=name)

def write_info_at_bottom(w, width, height, city_list):
    """prints some information about the run at the bottom of the
    screen"""
    n_cities = len(city_list)
    total_distance = calculate_path_length(city_list)
    w.create_text(width/2, height-59,
                  text='algorithm picked: %s' % algo_name,
                  fill='red')
    w.create_text(width/2, height-46, text='n_cities: %d' % n_cities,
                  fill='red')
    w.create_text(width/2, height-33,
                  text='iteration: %d' % iter,
                  fill='red')
    w.create_text(width/2, height-20,
                  text='total_distance: %16.12g' % total_distance,
                  fill='red')

def distance(c1, c2):
    """Calculates the distance between two cities."""
    x1 = c1[0]
    y1 = c1[1]
    x2 = c2[0]
    y2 = c2[1]
    r = math.sqrt((x2-x1)**2 + (y2-y1)**2)
    return r

def calculate_path_length(city_list):
    """Calculates the full length of a path through a list of cities,
    including the return home from the last city on the list."""
    total_length = 0
    for i in range(len(city_list)-1):   ## iterate up to the second-last city
        c1 = city_list[i]
        c2 = city_list[i+1]
        length = distance(c1, c2)
        total_length += length
    ## now add in the path length required to get back home
    total_length += distance(city_list[-1], city_list[0])
    return total_length

def hillclimbing_take_step(city_list, shorter=True):
    """Swap two cities in city_list, if the new path is shorter we take
    that step.  If shorter is True (which is the default) we take the
    step if it leads to a shorter path through the cities.  If it is
    set to false then we take the step if it makes the path longer.
    """
    ## the first city of the pair to be swapped needs not be the first
    ## or the last city
    path_before = calculate_path_length(city_list)
    c1_ind = random.randint(1, len(city_list)-1)
    c2_ind = random.randint(1, len(city_list)-1)
    while c2_ind == c1_ind:
        c2_ind = random.randint(1, len(city_list)-1)
    ## extract the cities
    c1 = city_list[c1_ind][:]
    c2 = city_list[c2_ind][:]
    ## make the swap
    city_list[c1_ind] = c2[:]
    city_list[c2_ind] = c1[:]
    ## see if we got better or not
    path_after = calculate_path_length(city_list)
    take_step = False
    if path_after <= path_before:
        take_step = True
    global iter
    print('STEP_%s  %d   %g  %g'
          % (('YES' if take_step else 'NO'), iter, path_before, path_after))
    if take_step:
        return (c1, c2)
    else:                       # no step
        ## undo the swap, since it was not an improvement
        city_list[c1_ind] = c1[:]
        city_list[c2_ind] = c2[:]
        return None

main()