##############################################<START OF PROGRAM>##############################################
def setUpCanvas(root): # These are the REQUIRED magic lines to enter graphics mode.
    root.title("THE TRAVELING SALESMAN PROBLEM by (your name here).")
    canvas = Canvas(root, width  = root.winfo_screenwidth(), height = root.winfo_screenheight(), bg = 'black')
    canvas.pack(expand = YES, fill = BOTH)
    return canvas
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def script(x, y, msg = '', kolor = 'WHITE'):
    canvas.create_text(x, y, text = msg, fill = kolor,  font = ('Helvetica', 10, 'bold'))
#---------------------------------------------------------------------------------Traveling Salesman Problem-

def plot(city): # Plots 5x5 "points" on video screen
    x = city[1]+5; y = city[2]+5 # The +5 is to push away from the side bars.
    if city[0] == -1:
        kolor = 'WHITE'
    else: kolor = 'YELLOW'
    canvas.create_rectangle(x-2, y-2, x+2, y+2, width = 1, fill = kolor)
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def line(city1, city2, kolor = 'RED'):
    canvas.create_line(city1[1]+5, city1[2]+5, city2[1]+5, city2[2]+5, width = 1, fill = kolor)
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def displayDataInConsole(AlgorithmResults, baseCity, city):
    print('===<Traveling Salesman Path Statistics>===')
    print ('   algorithm         path length ')
    for element in AlgorithmResults:
           print ('---%-20s'%element[0], int(element[2]))
    city.sort()
    baseCity.sort()
    if city == baseCity:
        print("---Data verified as unchanged.")
    else:
        print ('ERROR: City data has been corrupted!')
    print('   Run time =', round(clock()-START_TIME, 2), ' seconds.')
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def printCity(city): # Used for debugging.
    count = 0
    for (id,x,y) in city:
        print( '%3d: id =%2d, (%5d, %5d)'%(count,id, int(x), int(y)))
        count += 1
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def displayPathOnScreen(city, statistics):
#=---Normalize data
    (minX, maxX, minY, maxY, meanX, meanY, medianX, medianY, size, m, b) = statistics
    canvas.delete('all')
    cityNorm, (p,q,r,s) = normalizeCityDataToFitScreen(city[:], statistics)

#---Plot points and lines
    cityNorm.append(cityNorm[0])
    plot(cityNorm[0])
    for n in range(1, len(cityNorm)):
        plot(cityNorm[n])
        line(cityNorm[n], cityNorm[n-1])
    script(650,  20, 'path length = ' + str(pathLength(city)))
    canvas.create_rectangle(530,10, 770, 30, width = 1, outline = 'WHITE')
    canvas.update()
    root.mainloop() # Required for graphics.
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def normalizeCityDataToFitScreen(city, statistics):
    """ Coordinates are all assumed to be non-negative."""
    (minX, maxX, minY, maxY, meanX, meanY, medianX, medianY, size, m, b) = statistics
    newCity = []

#---Step 1a. Shift city points to the x- and y-axes.
    for (id, x,y) in city:
        newCity.append ( (id, x-minX, y-minY))

#---Step 1b. Shift line-of-best-fit to the x- and y-axes.
    (x0,y0) = (maxX-minX, m*maxX+b - minY) # = x-intercept of line-of-best-fit.
    (x1,y1) = (minX-minX, m*minX+b - minY) # = y-intercept of line-of-best-fit.


#---Step 1c. Shift max-values to x- and y-axes.
    maxX = maxX-minX
    maxY = maxY-minY

#---Step 2a. # Re-scale city points to fit the screen.
    cityNorm = []
    for (id, x, y) in newCity:
        cityNorm.append ((id, x*SCREEN_WIDTH/maxX, y*SCREEN_HEIGHT/maxY))

#---Step 2b. # Re-scale the x-axis and y-axis intercepts for the line-of-best-fit.
    (x0,y0) = x0/maxX*SCREEN_WIDTH, y0/maxY*SCREEN_HEIGHT # a point on the x-axis
    (x1,y1) = x1/maxX*SCREEN_WIDTH, y1/maxY*SCREEN_HEIGHT # a point on the y-axis

    return cityNorm, (x1,y1,x0,y0) # = the adjusted city xy-values and 2 points on the line-of-best-fit.
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def readDataFromFileAndAppendId(fileName):
    file1 = open(fileName, 'r')
    fileLength = int(file1.readline()) # removes heading
    city = []
    for elt in range(fileLength):
       x, y = file1.readline().split()
       city.append( [0, float(x), float(y)] ) # A place for an id (0, here) is appended.
    file1.close()
    return city
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def getFileLength(fileName):
    file1 = open(fileName, 'r')
    fileLength = int(file1.readline()) # removes heading
    return fileLength
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def pathLength(city):
    totalPath = 0
    for n in range(1, len(city)):
        totalPath += dist( city[n-1], city[n] )
    totalPath += dist( city[n], city[0] )
    return int(totalPath)
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def dataStatistics(city):
    xValues = []
    yValues = []
    size = len(city)
    for (id, x,y) in city:
        xValues.append(x)
        yValues.append(y)
    minX = min(xValues)
    maxX = max(xValues)
    minY = min(yValues)
    maxY = max(yValues)

    assert (minX >= 0 or maxX >= 0 or minY >= 0 or maxY >= 0)

    meanX = sum(xValues)/size
    meanY = sum(yValues)/size
    medianX = city[len(city)//2][0]
    medianY = city[len(city)//2][1]

#---Derive the line of best fit: y = mx+b
    xyDiff   = 0
    xDiffSqr = 0
    for (id, x,y) in city:
        xyDiff  += (meanX - x)*(meanY - y)
        xDiffSqr+= (meanX - x)**2

    m = xyDiff/xDiffSqr
    b = meanY - m*meanX

    return minX, maxX, minY, maxY, meanX, meanY, medianX, medianY, size, m, b
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def dist(cityA, cityB):
    return hypot(cityA[1]-cityB[1], cityA[2] - cityB[2])
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def chunks(l, n):
    n = max(1, n)
    l.pop()
    return [l[i:i + n] for i in range(0, len(l), n)]
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def printToFile(distances, myfile):
    for item in distances:
        myfile.write("%s\n" % item)
        myfile.write("\n")
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def myAlgorithm(distances,city,fileLength):
    for x in range(len(city)):
        for y in range(len(city)):
            if x+y+1<len(city):
                distances.append(dist(city[x],city[x+y+1]))
            elif city[x] !=city[(x+y)%(fileLength-1)]:
                distances.append(dist(city[x],city[(x+y)%(fileLength-1)]))
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def ySort(city):
    for item in city:
        item[1],item[2]=item[2],item[1]
    city.sort()
    for item in city:
        item[1],item[2]=item[2],item[1]
#---------------------------------------------------------------------------------Traveling Salesman Problem--

def xSort(city):
    city.sort()
#====================================<GLOBAL CONSTANTS and GLOBAL IMPORTS>========Traveling Salesman Problem==

from tkinter      import Tk, Canvas, YES, BOTH
from operator     import itemgetter
from itertools    import permutations
from copy         import deepcopy
from random       import shuffle
from time         import clock
from math         import hypot
from operator     import itemgetter
from collections import OrderedDict
root           = Tk()
canvas         = setUpCanvas(root)
START_TIME     = clock()
SCREEN_WIDTH   = root.winfo_screenwidth() //5*5 - 15 # adjusted to exclude task bars on my PC.
SCREEN_HEIGHT  = root.winfo_screenheight()//5*5 - 90 # adjusted to exclude task bars on my PC.
fileName       = "tsp0038.txt" # My file name will be different from yours
#==================================================< MAIN >=======================Traveling Salesman Problem==

def main():
#---0. Read in data, append an id to every pair, and store results in a variable called "city".

    fileLength = getFileLength(fileName)
    city  = readDataFromFileAndAppendId(fileName)

#---1. Extract statistics.

    statistics = (minX, maxX, minY, maxY, meanX, meanY, medianX, medianY, size, m, b) = dataStatistics(city)

#---2. Create a random path.

    shuffle(city)

#---3. Sort on y-coordinate and connect sequentially by y.

    ySort(city)

#---4. Sort on x-coordinate and connect sequentially by x.

    xSort(city)

#---5. Greedy Algorithm
    z=[]
    for x in range(len(city)-1):
        print(x)
        if x==0:
            z.append(city[x])
        temp=dist(city[x],city[x+1])
        for y in range(len(city)-1):
            if dist(city[x],city[y+1])<temp:
                z.append(city[y+1])
                break
    city=z

#---6. Display results.
    displayPathOnScreen(city, statistics)
#---------------------------------------------------------------------------------Traveling Salesman Problem--
if __name__ == '__main__': main()
###############################################<END OF PROGRAM>###############################################