#! /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 = 640
canvas_height = 480
n_cities = 25
algo_name = 'greedy'

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)
    ## now try a greedy solution: start with one city and pick the
    ## closest remaining city next.  Keep going until we have
    ## traversed the whole list.
    my_path = city_list[:1]    # start with just one city
    for i in range(len(city_list)):
        remaining_cities = [c for c in city_list if c not in my_path]
        if not remaining_cities:
            break
        last_city = my_path[-1]
        next_city_ind = find_closest_city(last_city, remaining_cities)
        my_path.append(remaining_cities[next_city_ind])
        w.delete("all")
        ## we draw the full list of cities (without connections) and
        ## then the current path
        draw_city_path(w, city_list, color='black', connect=False)
        draw_city_path(w, my_path, color='green', connect=True)
        write_info_at_bottom(w, canvas_width, canvas_height, my_path)
        w.update()
        time.sleep(1.0/5.0)    # 5 frames per secon
    mainloop()

def find_closest_city(city, remaining_cities):
    """returns the index of the closest city in remaining_cities"""
    closest_index = 0
    closest_distance = sys.float_info.max
    for i in range(len(remaining_cities)):
        r = distance(city, remaining_cities[i])
        if r < closest_distance:
            closest_distance = r
            closest_index = i
    return closest_index

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):
    n_cities = len(city_list)
    total_distance = path_length(city_list)
    w.create_text(width/2, height-60,
                  text='algorithm picked:: %s' % algo_name,
                  fill='red')
    w.create_text(width/2, height-40, text='n_cities: %d' % n_cities,
                  fill='red')
    w.create_text(width/2, height-20,
                  text='total_distance: %g' % total_distance,
                  fill='red')

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

def path_length(city_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 length

main()