#format python

"""TravelingSalesmanProblem solving using GeneticAlgorithm
"""

import random, math

class Map:
    def __init__(self):
        self.distanceMap = \
                [[ 0, 10, 20, 30, 40, 50], 
                 [10,  0,  9, 40, 25, 15], 
                 [20,  9,  0, 32,  9, 41], 
                 [30, 40, 32,  0, 39,  5],  
                 [40, 25,  9, 39,  0, 27], 
                 [50, 15, 41,  5, 27,  0]]

    def getDistanceBetweenTwoCities(self, aCity1, aCity2):
        return self.distanceMap[aCity1-1][aCity2-1]

    def getDistance(self, aPath):
        i = 0
        sum = 0
        for eachCity in aPath:
            if i == len(aPath)-1:
                break
	    city1 = aPath[i]
	    city2 = aPath[i+1]
            sum += self.getDistanceBetweenTwoCities(city1, city2)
            i += 1
        return sum

class RealMap(Map):
    def __init__(self, numOfCities=6):
        self.addressOfCities = {}
        for eachCityNum in range(numOfCities):
            cityname = eachCityNum + 1
	    xpos = random.uniform(0,100)
	    ypos = random.uniform(0,100)
	    self.addressOfCities[cityname] = (xpos, ypos)

    def getCities(self):
        return self.addressOfCities

    def getAddressOfCity(self, aCityName):
    	return self.addressOfCities[aCityName]

    def getDistanceBetweenTwoCities(self, aCity1, aCity2):
        ad1 = self.getAddressOfCity(aCity1)
	ad2 = self.getAddressOfCity(aCity2)
        return math.sqrt((ad1[0] - ad2[0])**2 + (ad1[1] - ad2[1])**2)

    def loadMap(self, aMapOfDict):
        self.addressOfCities = aMapOfDict
    	

def encode(aCityPath):
    ordinalrep = []
    aPathcopy = range(1,100)
    for eachCity in aCityPath:
        index = aPathcopy.index(eachCity) + 1
        aPathcopy.remove(eachCity)
        ordinalrep.append(index)
    return ordinalrep

def decode(aOrdinalRep):
    citypath = []
    replist = range(1,100)
    for eachIndex in aOrdinalRep:
        eachCity = replist[eachIndex - 1]
        citypath.append(eachCity)
        replist.remove(eachCity)
    return citypath
	
def crossover(p1, p2, xpoint):
    encodedp1, encodedp2 = encode(p1), encode(p2)
    newep1 = encodedp1[:xpoint] + encodedp2[xpoint:]
    newep2 = encodedp2[:xpoint] + encodedp1[xpoint:]
    return decode(newep1), decode(newep2)

def getPermutation(aList):
    if len(aList)<=1:
            return [aList]
    p=[]
    for eachElement in aList:
            theRest=aList[:]
            theRest.remove(eachElement)
            for eachPerm in getPermutation(theRest):
                    p.append([eachElement]+eachPerm)
    return p
    
def perms(list): 
    if not list: return [[]] 
    return [[list[i]] + p for i in range(len(list)) 
        for p in perms(list[:i] + list[i+1:])] 
        
def getOptima():
    cities=[1,2,3,4,5,6]
    allRoutes=getPermutation(cities)
    myMap = Map()
    l=[]
    for eachRoute in allRoutes:
        l.append(myMap.getDistance(eachRoute))
    return max(l),min(l),allRoutes[l.index(max(l))],allRoutes[l.index(min(l))]