import math

plik = open("paris.txt", "r").read().split("\n")[1:]

class City:
  id = ""
  town = ""
  population = 0
  latitude = 0.0
  longitude = 0.0

  def __init__(self, id, town, population, latitude, longitude):
    self.id = id
    self.town = town
    self.population = int(population)
    self.latitude = float(latitude)
    self.longitude = float(longitude)

  def __str__(self):
    return self.id

  def __repr__(self):
      return self.id

cities = []

for i in range(len(plik)):
  linia = plik[i].split(" ")
  city = City(linia[0], linia[1], linia[2], linia[3], linia[4])
  cities.append(city)

def pierwsze(N, obecna_permutacja, odpowiedz):
  if len(obecna_permutacja) == N:
    odpowiedz.append(obecna_permutacja)
    return
  for i in range(N):
    nowe = cities[i]
    if nowe not in obecna_permutacja:
      pierwsze(N, obecna_permutacja + [nowe], odpowiedz)
  return odpowiedz

def drugie(M, N, obecna_kombinacja, odpowiedz):
  if len(obecna_kombinacja) == M:
    odpowiedz.append(obecna_kombinacja)
    return
  for i in range(N):
    nowe = cities[i]
    drugie(M, N, obecna_kombinacja + [nowe], odpowiedz)
  return odpowiedz

def podzbior(M, aktualny, pozostale, odpowiedz):
  if len(aktualny) == M or not pozostale:
    odpowiedz.append(aktualny)
    return
  podzbior(M, aktualny, pozostale[1:], odpowiedz)
  podzbior(M, aktualny + [pozostale[0]], pozostale[1:], odpowiedz)
  return odpowiedz

def odleglosc(miasto1: City, miasto2: City):
  return math.sqrt(((miasto2.latitude - miasto1.latitude) ** 2) + ((miasto2.longitude - miasto1.longitude) ** 2))

def trzecie():
  N = 5
  permutacje = pierwsze(N, [], [])
  odleglosci = []
  for i in range(len(permutacje)):
    obecna_permutacja = permutacje[i]
    poprzednie_miasto = obecna_permutacja[0]
    obecna_odleglosc = 0
    for j in range(1, len(obecna_permutacja)):
      obecna_odleglosc += odleglosc(poprzednie_miasto, obecna_permutacja[j])
      poprzednie_miasto = obecna_permutacja[j]
    obecna_odleglosc += odleglosc(obecna_permutacja[0], obecna_permutacja[len(obecna_permutacja) - 1])
    odleglosci.append(obecna_odleglosc)
  zlaczone = list(zip(permutacje, odleglosci))
  zlaczone.sort(key=lambda x: x[1])
  return zlaczone

def czwarte():
  N = 5
  podzbiory = podzbior(N, [], cities[:N], [])
  laczna_suma_50 = sum(map(lambda x: x.population, cities[:N])) / 2
  sumki = []
  for obecny_podzbior in podzbiory:
    sumka = sum(map(lambda x: x.population, obecny_podzbior)) - laczna_suma_50
    sumki.append(sumka)
  zlaczone = list(zip(podzbiory, sumki))
  zlaczone.sort(key=lambda x: abs(x[1]))
  return zlaczone


print(pierwsze(3, [], []))
print(drugie(3, 4, [], []))
print(trzecie()[0])
print(podzbior(3, [], cities[:3], []))
print("sumki")
print(czwarte())