import math
from random import randint
from time import perf_counter

my_list = ["ala", "ma", "Kota"]
towns = [[2, 3], [3, 4], [5, 8], [7, 2], [7, 7], [3, 10], [8, 1], [1, 5], [4, 7],
         [3, 6], [6, 4], [7, 4]]  # koordynaty miast
generated_towns = []
result = []  # tablica na miasta po uruchomieniu funkcji nearest_neighbor


def distance_between_cities(city_a, city_b):
    distance = math.hypot(city_b[0] - city_a[0], city_b[1] - city_a[1])
    return distance


def find_closest(town, towns_ls):
    towns_list = towns_ls.copy()
    start = town
    distance = distance_between_cities(start, towns_list[0])
    nearest = towns_list[0]
    for x in range(len(towns_list)):
        if (distance_between_cities(start, towns_list[x]) < distance):
            distance = distance_between_cities(start, towns_list[x])
            nearest = towns_list[x]
    return nearest, distance


# funkcja znajdujaca droge metodą najbliższego sąsaida
# town - koordynaty miasta z którego zaczynamy
# town_ls - lista miast do przeszukania
# @return zwraca drogę jaką trzeba przejechać żeby odwiedzić wszystkie miasta
def nearest_neighbor(town, towns_ls):
    time = perf_counter()
    towns_list = towns_ls.copy()
    result.append(town)
    cost = 0
    start = town
    towns_list.remove(town)
    length = len(towns_list)
    for x in range(length):
        res = find_closest(start, towns_list)
        cost += res[1]
        start = res[0]
        result.append(start)
        towns_list.remove(start)
    time = perf_counter() - time
    return cost, time


def generate_towns(numer_of_cities):
    for i in range(numer_of_cities):
        x = randint(1, 100)
        y = randint(1, 100)
        generated_towns.append([x, y])


for x in range(40,60):
    generate_towns(x)
    res = nearest_neighbor(generated_towns[1], generated_towns)
    print("Ilość miast : " + str(x) + " Długość drogi : " + str(res[0]) + " Czas : " + str(res[1]))

# for x in result:
#     print(str(x[0]) + "\t" + str(x[1]))