from macslib import *
from itertools import permutations

# add the points as variables here
A = (2,6)

# make sure you add all the points to the points dictionary
# use a string label for each as the key, and the variable as the value
points = {'A':A}

# you might want to give your graph a title:
# edit the next line to add a title of your choice
drawTSPPoints(points)

# put your guess at the shortest route in pathGuess
# list the points in the order they should be visited
pathGuess = [A]
drawTSPPath(pathGuess, 'guess')

# brute force algorithm to calculate the shortest path
# this algorithm runs in factorial time
# don't use more than a few points or it will never complete!
possiblePaths = list(permutations(points.values()))
shortestLength = -1
shortestPath = []
for path in possiblePaths:
    pathLength = 0
    for i in range(len(path)):
        x1 = path[i][0]
        y1 = path[i][1]
        x2 = path[(i+1) % len(path)][0]
        y2 = path[(i+1) % len(path)][1]
        pathLength += sqrt((x1-x2)**2 + (y1-y2)**2)

    if shortestLength == -1 or pathLength < shortestLength:
        shortestLength = pathLength
        shortestPath = path

# uncomment next line to display the shortest path
#drawTSPPath(shortestPath, 'shortest', 'b--')