"""
 tsp.py

 Playing around with the traveling salesman problem.

"""

from math import sqrt
from permute import permute

from random import random
from turtle import (setup, setworldcoordinates, degrees, speed,
                    colormode, pencolor, bgcolor, width, hideturtle,
                    setposition, setheading, mode, clear,
                    pendown, penup, pensize,
                    forward, backward, left, right)

def initialize_turtle_window(width=600, height=600,
                             xmin=0.0, xmax=1.0, ymin=0.0, ymax=1.0,
                             bg_color=(10,10,10),
                             color=(220,220,220)):
    """ initialize turtle graphics window and settings """
    # (0,0) is bottom left; (x,y) euclidian coords
    # pen will be up by default
    setup(width, height)   # Set window width & height (pixels)
    mode('standard')       # Set heading angles to be euclidian
    degrees(360)           # Set turtle orientation units to degrees.
    setworldcoordinates(xmin, ymin, xmax, ymax)
    colormode(255)         # Set color (r,g,b) units to (0 .. 255).
    speed(0)               # No animation. (1=slow,10=fast; 0=fastest)
    hideturtle()           # Don't show a shape for the turtle itself.
    bgcolor(bg_color)      # Set background color.
    setposition(xmax/2, ymax/2) # Put turtle at window center.
    pencolor(color)
    penup()

def box(x, y, size=0.02):
    setposition(x-size/2, y+size/2)
    setheading(0)
    pendown()
    for i in range(4):
        forward(size)
        right(90)
    penup()

def pythagorean(x1, y1, x2, y2):
    """ pythagorean distance between two points """
    return sqrt((x1 - x2)**2 + (y1 - y2)**2)

def draw_line(x1, y1, x2, y2):
    """ draw a line between two points """
    setposition(x1, y1)
    pendown()
    setposition(x2, y2)
    penup()

def main():
    initialize_turtle_window()

    # Create (x,y) points for Traveling Salesman problem.
    n = 10                                # number of points
    xs = [random() for i in range(n)]     # x coords, xs[i]
    ys = [random() for i in range(n)]     # y coords, ys[i]
    
    for i in range(n):       # draw boxes at points
        box(xs[i], ys[i])

    smallest = float('inf')
    best_sequence = []
    for sequence in permute(list(range(n))):
        distance = 0
        for i in range(n):
            i_next = (i+1) % n
            x1 = xs[i]
            y1 = ys[i]
            x2 = xs[i_next]
            y2 = ys[i_next]
            distance = distance + pythagorean(x1, y1, x2, y2)
        if distance < smallest:
            smallest = distance
            best_sequence = list(sequence)

    for i in best_sequence:
            # draw lines between all pairs of points
            i_next = (i+1) % n
            x1 = xs[i]
            y1 = ys[i]
            x2 = xs[i_next]
            y2 = ys[i_next]
            draw_line(x1, y1, x2, y2)
            
    wait = input("Done?")

main()