"""Cet algorithme rentre dans la catégorie "heuristique". Il s'agit
d'une stratégie très basique qui rajoute les villes dans leur ordre
d'apparition dans le fichier instance. Cette stratégie peut être
soumise lors d'un rendu, mais il est attendu de faire mieux.

L'instance pathologique associée est construite en alternant des
villes superposées réparties dans deux régions distinctes. La tournée
consistera alors à faire des aller-retours successifs entre les deux
régions alors qu'un seul suffit.

"""

import collections
import datetime
import functools
import heapq
import itertools
import math
import matplotlib
import networkx  # Méthodes relatives au TSP interdites
import numpy
import os
import pulp
import random
import re
import sys
import time


# Class to represent, read and solve a problem instance
class Problem:
    # Parsing of instance file
    def __init__(self, file_name):
        with open(file_name, "r") as f:
            lines = f.readlines()
        self.nb_cities = int(lines[0].split()[1])
        self.cost = []
        for line in lines[1 : 1 + self.nb_cities]:
            self.cost.append([int(i) for i in line.split()])
        print(self)

    def eval(self, indexes):
        cost = self.cost[indexes[self.nb_cities - 1]][indexes[0]]
        for i in range(self.nb_cities - 1):
            cost += self.cost[indexes[i]][indexes[i + 1]]
        return cost

    # Dumb greedy algorithm
    def solve(self):
        indexes = list(range(self.nb_cities))
        print(f"Found solution with value {self.eval(indexes)}")
        return Solution(indexes)

    def __str__(self):
        return "Instance with " + str(self.nb_cities) + " cities"


# Class to represent a solution and write it in a file
class Solution:
    def __init__(self, indexes):
        self.indexes = indexes

    def write(self, file_name):
        with open(file_name, "w") as f:
            f.write(" ".join(str(i) for i in self.indexes))


if __name__ == "__main__":
    pulp.LpSolverDefault.msg = 0
    instance_file_name = sys.argv[1]
    solution_file_name = sys.argv[2]
    p = Problem(instance_file_name)
    s = p.solve()
    s.write(solution_file_name)
