<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Traveling Salesman Problem
In this assignment you will implement one or more algorithms for the traveling salesman problem, such as the dynamic programming algorithm covered in the video lectures. 
The file tsp.txt describes a TSP instance. The first line indicates the number of cities. Each city is a point in the plane, and each subsequent line indicates the x- and y-coordinates of a single city.
The distance between two cities is defined as the Euclidean distance --- that is, two cities at locations (x,y) and (z,w) have distance √((x−z)^2+(y−w)^2 between them.
In the box below, type in the minimum cost of a traveling salesman tour for this instance, rounded down to the nearest integer.
OPTIONAL
Step1:  Draw points
Step2:  Initialize the 2-D Array
Step3:  Run the Dynamic Programming algorithm
<ASSISTANT_TASK:>
Python Code:
import numpy as np
file = "tsp.txt"
# file = "test2.txt"
data = open(file, 'r').readlines()
n = int(data[0])
graph = {}
for i,v in enumerate(data[1:]):
    graph[i] = tuple(map(float, v.strip().split(" ")))
    
dist_val = np.zeros([n,n])
for i in range(n):
    for k in range(n):
        dist_val[i,k] = dist_val[k,i] = np.sqrt((graph[k][0]-graph[i][0])**2 + (graph[k][1]-graph[i][1])**2)
print (graph)
Explanation: Traveling Salesman Problem
In this assignment you will implement one or more algorithms for the traveling salesman problem, such as the dynamic programming algorithm covered in the video lectures. 
The file tsp.txt describes a TSP instance. The first line indicates the number of cities. Each city is a point in the plane, and each subsequent line indicates the x- and y-coordinates of a single city.
The distance between two cities is defined as the Euclidean distance --- that is, two cities at locations (x,y) and (z,w) have distance √((x−z)^2+(y−w)^2 between them.
In the box below, type in the minimum cost of a traveling salesman tour for this instance, rounded down to the nearest integer.
OPTIONAL: If you want bigger data sets to play with, check out the TSP instances from around the world https://www.tsp.gatech.edu/world/countries.html. The smallest data set (Western Sahara) has 29 cities, and most of the data sets are much bigger than that. What's the largest of these data sets that you're able to solve --- using dynamic programming or, if you like, a completely different method?
HINT: You might experiment with ways to reduce the data set size. For example, trying plotting the points. Can you infer any structure of the optimal solution? Can you use that structure to speed up your algorithm?
End of explanation
%matplotlib inline
import matplotlib.pyplot as plt
values = list(graph.values())
y = [values[i][0] for i in range(len(values))]
x = [values[i][1] for i in range(len(values))]
plt.scatter(y,x)
plt.show()
import collections
    
def to_key(a):
    
    my_str = ""
    
    for i in a:
        my_str += str(int(i))
    return my_str
                      
def to_subset(v, n):
    a = np.zeros(n)
    a[v] = 1
    
    return a
def create_all_subset(n):
    A = collections.defaultdict(dict)
    
    for m in range(1,n):
        for a in (itertools.combinations(range(n), m)):
            key = a + tuple([0 for i in range(n-m)])
            print (a, tuple([0 for i in range(n-m)]), key, m, n)
            for j in range(n):
                A[to_key(key)][j] = np.inf
        
    A[to_key(to_subset(0,n))][0] = 0
      
    return A
# res= to_subset([2,3],5)
# print (res)
# print (to_key(res))
# A = create_all_subset(3)
# print (A)
# print (index_to_set(10,'25'))
# print(set_to_index([1,3]))
import itertools
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(1,len(s)+1))
def index_to_set(index, n='8'):
    
    fmt = '{0:0'+n+'b}'
    res = fmt.format(index)
    
    mylist = list(res)    
    mylist.reverse()
    
    print (res)
    
    mylist = np.asarray(mylist, dtype=int)
    
    ret = np.where(mylist==1)
    
#     ret = []
#     for i, j in enumerate(mylist):
#         if j=="1":
#             ret.append(i)
            
    return list(ret[0])
    
def set_to_index(my_set):
    # i = [1, 5, 7]
    
    ret = 0
    for i in my_set:
        ret += 2**i
        
    return ret
print ("~~ Test")
# print (set_to_index([1]))
# print (index_to_set(set_to_index([1])))
ex_all_sets = powerset(range(5))
for s in ex_all_sets:
    print ("~~ Original set:", s)
    print ("index:", set_to_index(s))
    print ("recovered set:", index_to_set(set_to_index(s),'5'))
Explanation: Draw points
End of explanation
A = np.full([2**n, n], np.inf)
A[set_to_index([0]),0]=0
for i in range(0, n):
    A[set_to_index([i]),i] = dist_val[i,0]
    print (set_to_index([i]), dist_val[i,0])
Explanation: Initialize the 2-D Array
End of explanation
from tqdm import tqdm
def _dist(k, j):
    return np.sqrt((graph[k][0]-graph[j][0])**2 + (graph[k][1]-graph[j][1])**2)
    
FULL = range(n)
for m in range(1,n):
#     all_sets = powerset(range(1,m))
    all_sets = itertools.combinations(FULL, m+1)
    print ("Subset Size:",m)
    for _set in all_sets:
        
        if not _set:
            continue
            
        _set = list(_set)
#         print ("Len Set", len(_set))
        set2_idx = set_to_index(_set)
        
        for j in _set:
            _set2 = _set.copy()            
            _set2.remove(j)
            
            if j==0 or not _set2:
                continue            
#             print ("_set2", _set2)
            _set2_idx = set_to_index(_set2)
    
#             print ("handle Set", _set2, "idx",_set2_idx, "j:", j)
            minval = np.inf         
            for k in _set2:
#                 print ("idxSet:", _set2_idx, "k:", k, "dist", A[_set2_idx,k])
                val = A[_set2_idx,k] + dist_val[k,j]
                if val < minval:
                    minval = val
#             print ("minval",minval)
            A[set2_idx,j] = minval
# print (A)
my_set = [i for i in range(n)]
print ("Full Set", my_set, set_to_index(my_set))
minval = np.inf 
for j in range(1,n):
    val = A[set_to_index(my_set),j] + dist_val[j,0]
    if val < minval:
        minval = val
        
print ("minval", minval)
       
# print (A[set_to_index(my_set),:])
Explanation: Run the Dynamic Programming algorithm
End of explanation
<END_TASK>