#! /usr/bin/python

# Simple non-Gegentic-Algorithm routine that simply searching by producing
# random permutations of the cities for each salesman, for each generation.

# Usage:
#  GA-Random.py  inputfilename outputfilename
#    prints: either OK or error message

# Format of input filename:  (Note: city locations will be in circular order)
#  [num-cities num-salesmen num-generations]
#  [[city1-x city1-y] [city2-x city2-y] ... [city-last-x city-last-y]]

# Format of output file:
#  [num-cities num-salesmen num-generations]
#  [[city1-x city1-y] [city2-x city2-y] ... ]
#  [salesman1-city-1-index salesman1-city-2-index ... salesman1-city-last-index]
#  [salesman2-city-index-1 salesman2-city-index-2 ... salesman2-city-last-index]
#  [...]
#  [salesman-last-city-1-index salesman-last-city-2-index ... salesman-last-city-last-index]
#  generation-1-smallest-pathlength
#  generation-2-smallest-pathlength
#  ...
#  generation-last-smallest-pathlength



import json, random, sys, math

def main(inputfile='',outputfile=''):
    if inputfile == '':
        # OK, we're getting the filename from the command-line
        # Check for usage errors...
        if len(sys.argv) != 3:
            print ('Error.  Correct usage: GA-Random.py inputfilename outputfilename')
            return
        inputfile = sys.argv[1]
    try:
        fin = open(inputfile,'rU')
    except:
        print ('Error: cannot open inputfile: %s' % inputfile)
        return
    slines = fin.read().split('\n')
    fin.close()
    ln = len(slines)
    if (ln != 2 and ln!=3) or (ln == 3 and len(slines[2].strip()) != 0):
        print ('Error. Incorrect contents of input file.')
        return
    if outputfile == '':
        outputfile = sys.argv[2]
    try:
        fout=open(outputfile,'w')
    except:
        print ('Error. Cannot write to output file: %s' % outputfile)
        return
    fout.close()

    print (Process(slines,outputfile))

def Process(lines,outputfilename):
    ncities,nsales,ngen = json.loads(lines[0].replace(' ',','))
    cities = json.loads(lines[1].replace(' ',','))

    # pre-calculate all pairs of city-to-city distances
    distances = []
    for i in range(ncities):
        distances.append([0]*ncities)
    for city1 in range(ncities-1):
        for city2 in range(city1+1,ncities):
            distances[city1][city2] = City2CityDistance(cities,city1,city2)
            distances[city2][city1] = distances[city1][city2]

    # calculate Generation One:
    # Assign to each salesman a random permutation of the city-paths
    salesmen_index = [Permute(ncities) for i in range(nsales)]
    # calculate the path-length for each salesman, and store as [path_length,path_indexes] list
    salesmen_path = [[PathLength(salesmen_index[i],distances),salesmen_index[i]] for i in range(nsales)]
    # find (and keep) the shortest pair
    min_sales = min(salesmen_path)
    # also, keep the best path-length
    best_pathlengths = [min_sales[0]]

    # now do this ngen-1 times:
    for q in range(ngen-1):
        # the best salesman's path is stored in min-sales, so work with only nsales-1 salesmen
        salesmen_index = [Permute(ncities) for i in range(nsales-1)]
        salesmen_path = [[PathLength(salesmen_index[i],distances),salesmen_index[i]] for i in range(nsales-1)]
        # add in the min_sales that we kept, and find the new shortest
        salesmen_path.append(min_sales)
        min_sales = min(salesmen_path)
        best_pathlengths.append(min_sales[0])

    # output
    fout = open(outputfilename,'w')
    # write out the same two lines that we received
    fout.write('%s\n%s\n' % (lines[0],lines[1]))
    # write out the salesmen, in order of increasing path-length
    salesmen_path.sort()
    for i in range(nsales):
        fout.write('%s\n' % (json.dumps(salesmen_path[i][1]).replace(', ',' ')))
    # write out the sequence of best path-lengths
    for i in range(len(best_pathlengths)):
        fout.write('%f\n' % best_pathlengths[i])

    fout.close()
    return '%d Generations' % ngen
    
def City2CityDistance(cities,c1,c2):
    p1 = cities[c1]
    p2 = cities[c2]
    return math.sqrt((p2[0]-p1[0])*(p2[0]-p1[0])+(p2[1]-p1[1])*(p2[1]-p1[1]))

def PathLength(indexes,city_distances):
    # copy the first city also to the end
    circular_indexes = indexes+[indexes[0]]
    total = 0
    for i in range(len(indexes)):
        total += city_distances[circular_indexes[i]][circular_indexes[i+1]]
    return total

def Permute(n):
    a = range(n)
    random.shuffle(a)
    return a

main()