from time import time

class Ville:
    def __init__(self, taille, ouest, nord, est, sud):
        self.taille = taille
        self.ouest = ouest
        self.nord = nord
        self.est = est
        self.sud = sud
        self.grille = []
        for _ in range(taille):
            self.grille.append([None] * taille)

    def __str__(self):
        separation = "-" * (self.taille * 3 + 1) + "\n"
        retour = separation
        for num_ligne in range(self.taille):
            for num_colonne in range(self.taille):
                repr_case = "|" + Ville.car(self.grille[num_ligne][num_colonne])
                retour += repr_case
            retour += "|\n"
            retour += separation
        return retour

    def remplirCases(self, num_ligne=0, num_colonne=0):
        if num_ligne == self.taille:
            print("Trouvé")
            return self
        retour = None
        for valeur in range(1, self.taille+1):
            #print("case [",num_ligne,",",num_colonne,"]",sep="")
            #print("  valeur =", valeur)
            if self.ligneContient(valeur, num_ligne, num_colonne):
                #print("erreur ligne")
                continue
            if self.colonneContient(valeur, num_ligne, num_colonne):
                #print("erreur colonne")
                continue
            self.grille[num_ligne][num_colonne] = valeur
            if self.ligneIncompatible(num_ligne, num_colonne):
                #print("ligne incompatible")
                continue
            if self.colonneIncompatible(num_ligne, num_colonne):
                #print("colonne incompatible")
                continue
            nouv_num_ligne, nouv_num_colonne = self.caseSuivante(num_ligne, num_colonne)
            retour = self.remplirCases(nouv_num_ligne, nouv_num_colonne)
            if not retour is None:
                return retour
        return None
        
    def car(contenu):
        if contenu is None:
            return "  "
        else:
            return str(10 * contenu)
            
    def copier(self):
        nouveau = Ville(self.taille, self.ouest, self.nord, self.est, self.sud)
        for num_ligne in range(self.taille):
            for num_colonne in range(self.taille):
                nouveau.grille[num_ligne][num_colonne] = self.grille[num_ligne][num_colonne]
        return nouveau
    
    def ligneContient(self, valeur, num_ligne, num_colonne):
        debut_ligne = self.grille[num_ligne][:num_colonne]
        return valeur in debut_ligne

    def colonneContient(self, valeur, num_ligne, num_colonne):
        for i in range(num_ligne):
            if self.grille[i][num_colonne] == valeur:
                return True
        return False

    def ligneIncompatible(self, num_ligne, num_colonne):
        future_ligne = self.grille[num_ligne][:num_colonne+1]
        vue_ouest = Ville.vueOuest(future_ligne)
        if not self.ouest[num_ligne] is None:
            if vue_ouest > self.ouest[num_ligne]:
                #print("vue ouest incompatible")
                return True
            elif num_colonne == self.taille - 1 and vue_ouest < self.ouest[num_ligne]:
                return True
        if not self.est[num_ligne] is None and num_colonne == self.taille-1:
            #print("On vérifie la vue est")
            vue_est = Ville.vueEst(future_ligne)
            if not vue_est == self.est[num_ligne]:
                return True
        return False

    def vueOuest(ligne):
        plus_haut = 0
        nb_vues = 0
        for immeuble in ligne:
            if immeuble > plus_haut:
                plus_haut = immeuble
                nb_vues += 1
        return nb_vues
    
    def vueEst(ligne):
        plus_haut = 0
        nb_vues = 0
        for num_immeuble in range(-1, -len(ligne)-1, -1):
            immeuble = ligne[num_immeuble]
            if immeuble > plus_haut:
                plus_haut = immeuble
                nb_vues += 1
        return nb_vues

    def colonneIncompatible(self, num_ligne, num_colonne):
        if self.nord[num_colonne] is not None:
            vue_nord = self.vueNord(num_ligne, num_colonne)
            if vue_nord > self.nord[num_colonne]:
                return True
            elif num_ligne == self.taille - 1 and vue_nord < self.nord[num_colonne]:
                return True
        #print("colonne", num_colonne, ": vue nord compatible")
        if self.sud[num_colonne] is not None and num_ligne == self.taille-1:
            vue_sud = self.vueSud(num_colonne)
            if vue_sud != self.sud[num_colonne]:
                return True
        #print("colonne", num_colonne, ": vue sud compatible")
        return False

    def vueNord(self, num_ligne, num_colonne):
        nb_vues = 0
        plus_haut = 0
        for i in range(num_ligne+1):
            immeuble = self.grille[i][num_colonne]
            if immeuble > plus_haut:
                plus_haut = immeuble
                nb_vues += 1
        return nb_vues

    def vueSud(self, num_colonne):
        nb_vues = 0
        plus_haut = 0
        for i in range(-1, -self.taille-1, -1):
            immeuble = self.grille[i][num_colonne]
            if immeuble > plus_haut:
                plus_haut = immeuble
                nb_vues += 1
        return nb_vues
    
    def caseSuivante(self, num_ligne, num_colonne):
        nouvelle_colonne = num_colonne + 1
        if nouvelle_colonne == self.taille:
            nouvelle_ligne = num_ligne + 1
            nouvelle_colonne = 0
        else:
            nouvelle_ligne = num_ligne
        #print("on passe de ",num_ligne,",",num_colonne," à ", nouvelle_ligne,",",nouvelle_colonne)
        return (nouvelle_ligne, nouvelle_colonne)
    
def resoudre3():
    ville = Ville(3, [None, None, None], [1, None, None], [2, 1, None], [None, None, None])
    print(ville.remplirCases())
 
def resoudre4():
    ville = Ville(4, [None, 2, 3, None], [3, None, 2, None], [None, 1, None, 3], [None, 3, None, None])
    print(ville.remplirCases())

def resoudre5():
    ville = Ville(5, [3, None, 2, None, 4],\
             [2, None, 1, 2, None],\
             [None, 3, 1, 3, None],\
             [None, None, None, None, None])
    print(ville.remplirCases())

def resoudre5a():
    ville = Ville(5, [None, 4, None, None, None],\
             [None, 5, None, None, None],\
             [3, None, 4, None, None],\
             [3, None, None, None, None])
    print(ville.remplirCases())

def resoudre5b():
    ville = Ville(5, [5, 2, None, None, 3],\
             [None, None, 2, None, None],\
             [None, None, 3, 2, None],\
             [3, None, None, None, None])
    print(ville.remplirCases())

def resoudre6a():
    ville = Ville(6, [None, 4, 2, None, None, None],\
             [None, 4, None, None, 3, None],\
             [2, 2, None, None, None, 4],\
             [3, None, None, 3, 3, 3])
    print(ville.remplirCases())

def resoudre6b():
    ville = Ville(6,[2, None, None, 4, 4, None],\
             [3, 2, None, None, 2, 4],\
             [None, 3, None, None, None, 1],\
             [None, 3, 3, 3, None, None])
    print(ville.remplirCases())
    
def calcTempsFonction(f):
      t1 = time()
      f()
      t2 = time()
      return t2 - t1