#format python
"""TSP solver using various method --yong27, 2005-06-03
"""
import unittest
import random, math, time

class City:
    ID = 0
    def __init__(self):
        self.x = 0
        self.y = 0
        self.name = City.ID
        City.ID+=1
    def setPosition(self, (x,y)):
        self.x = x
        self.y = y
    def setRandomPosition(self):
        self.x = random.random()
        self.y = random.random()
    def getPosition(self):
        return self.x, self.y

    def getDistanceBetween(self, aCity):
        return math.sqrt((self.x - aCity.x)**2 + (self.y - aCity.y)**2)


class SalseMan:
    def __init__(self):
        self.cities = dict()

    def addCity(self, aCity):
        self.cities[aCity.name] = aCity

    def getCity(self, aCityName):
        return self.cities[aCityName]

    def getNumOfCities(self):
        return len(self.cities)

    def getShortestPath(self):
        raise NotImplementedError

    def getDistanceWithCities(self, cities):
        distance = 0
        for i in range(len(cities)-1):
            distance += cities[i].getDistanceBetween(cities[i+1])
        return distance

    def reportTravel(self):
        t1 = time.time()
        path, distance = self.getShortestPath()
        elaspedTime = time.time() - t1

class PermutationSalseMan(SalseMan):
    def __init__(self):
        SalseMan.__init__(self)
    
    def getShortestPath(self):
        shortestDistance = 0
        for cityNames in self.permutate(self.cities.keys()):
            distance = self.getDistanceWithCities(
                    [self.getCity(cityName) for cityName in cityNames])
            if shortestDistance == 0 or distance < shortestDistance:
                shortestDistance = distance
                shortestPath = cityNames
        return shortestPath, shortestDistance
    
    def permutate(self, items):
        return self.xcombinations(items, len(items))
    
    def xcombinations(items, n):
        if n==0: yield []
        else:
            for i in xrange(len(items)):
                for cc in PermutationSalseMan.xcombinations(items[:i]+items[i+1:],n-1):
                    yield [items[i]]+cc
    xcombinations = staticmethod(xcombinations)


class TravelingCenter: 
    def __init__(self, aSalseMan, numOfCities):
        cities = list() 
        self.salseMan = aSalseMan
        for i in range(numOfCities):
            city = City()
            city.setRandomPosition()
            aSalseMan.addCity(city)
    
    def report(self):
        return self.salseMan.reportTravel()

def main(numOfCities):
    reprRecord = lambda l: '||%s||'%'||'.join(map(str,l))
    reportTitles = ("NumOfCities", "Path", "Distance", "Time(sec)")
    print reprRecord(reportTitles)
    for i in range(numOfCities):
        tc= TravelingCenter(PermutationSalseMan(),i)
        print reprRecord(tc.report())
        City.ID = 0

class TestTsp(unittest.TestCase):
    def setUp(self):
        self.sm = SalseMan()
        self.cities=[]
        for i in range(3):
            self.cities.append(City())
        self.cities[0].setPosition((1,1))
        self.cities[1].setPosition((0,1))
        self.cities[2].setPosition((0,0))

    def testCity(self):
        self.assertEquals((1,1),self.cities[0].getPosition())
        self.assertEquals(1, self.cities[1].name)
        self.assertEquals(1, self.cities[0].getDistanceBetween(self.cities[1]))

    def testGetDistanceWithCities(self):
        self.assertEquals(2 ,self.sm.getDistanceWithCities(self.cities))

    def testPermutationSalseMan(self):
        psm = PermutationSalseMan()
        for i in range(3):
            psm.addCity(self.cities[i])
        self.assertEquals(([0,1,2],2) ,psm.getShortestPath())

    def tearDown(self):
        City.ID = 0

if __name__=='__main__':
    #unittest.main()
    main(30)