import csv
import itertools
import math
import random
import sys

"""
Takes a csv file of x,y coords e.g
20.8,21.3
29.1,26.2
30.6,33.7
31.5,11.8
9.3,15.0
16.3,18.7
20.5,8.9
15.8,22.3
30.0,19.3
35.1,27.0
"""


def held_karp(dists):
    """
    Implementation of Held-Karp, an algorithm that solves the Traveling
    Salesman Problem using dynamic programming with memoization.

    Parameters:
        dists: distance matrix

    Returns:
        A tuple, (cost, path).
    """
    n = len(dists)

    # Maps each subset of the nodes to the cost to reach that subset, as well
    # as what node it passed before reaching this subset.
    # Node subsets are represented as set bits.
    C = {}

    # Set transition cost from initial state
    for k in range(1, n):
        C[(1 << k, k)] = (dists[0][k], 0)

    # Iterate subsets of increasing length and store intermediate results
    # in classic dynamic programming manner
    for subset_size in range(2, n):
        for subset in itertools.combinations(range(1, n), subset_size):
            # Set bits for all nodes in this subset
            bits = 0
            for bit in subset:
                bits |= 1 << bit

            # Find the lowest cost to get to this subset
            for k in subset:
                prev = bits & ~(1 << k)

                res = []
                for m in subset:
                    if m == 0 or m == k:
                        continue
                    res.append((C[(prev, m)][0] + dists[m][k], m))
                C[(bits, k)] = min(res)

    # We're interested in all bits but the least significant (the start state)
    bits = (2**n - 1) - 1

    # Calculate optimal cost
    res = []
    for k in range(1, n):
        res.append((C[(bits, k)][0] + dists[k][0], k))
    opt, parent = min(res)

    # Backtrack to find full path
    path = []
    for _ in range(n - 1):
        path.append(parent)
        new_bits = bits & ~(1 << parent)
        _, parent = C[(bits, parent)]
        bits = new_bits

    # Add implicit start state
    path.append(0)

    return opt, list(reversed(path))


def read_coords(filename):
    with open(filename) as file:
        dialect = csv.Sniffer().sniff(file.read(1024))
        csv_file = csv.reader(file, dialect, quotechar='"')
        coords = []

        file.seek(0)

        for row in csv_file:
            if len(row) != 2:
                sys.exit('invalid csv, expected list of x,y coords')
            coords.append([float(i) for i in row])
    return coords


def compare_coords(a, b):
    x_dist = math.fabs(a[0] - b[0])
    y_dist = math.fabs(a[1] - b[1])
    return math.sqrt(x_dist**2 + y_dist**2)


def get_distances(coords):
    dists = []
    n = len(coords)
    for i in range(0, n):
        new_list = []
        for j in range(0, n):
            new_list.append(compare_coords(coords[i], coords[j]))
        dists.append(new_list)
    return dists


if __name__ == '__main__':
    arg = ""
    if len(sys.argv) > 1:
        arg = sys.argv[1]

    if arg.endswith('.csv'):
        coords = read_coords(arg)
        dists = get_distances(coords)
    else:
        sys.exit('No coords csv provided')

    # Pretty-print the distance matrix
    # for row in dists:
        # print(''.join([str(n).rjust(3, ' ') for n in row]))

    print('')
    # print(held_karp(dists))
    [opt, path] = held_karp(dists)
    print('order', [i + 1 for i in path])
    coord_order = []
    for i in path:
        coord_order.append(coords[i])
    for row in coord_order:
        print(row)