import itertools
from time import time

#piece = [centre, nw, ne, se, sw]
#1 = trou ; 0 = plein
PIECES = [("p1", [1, 1, 0, 0, 0]),\
          ("p2", [0, 1, 0, 0, 0]),\
          ("p3", [0, 1, 0, 1, 0]),\
          ("p4", [0, 1, 1, 0, 0])]

# probleme est une liste contenant successivement :
# le nombre de barques devant apparaitre
# le nombre de bateaux blancs devant apparaitre
# le nombre de bateaux rouges devant apparaitre
# le nombre de montagnes devant apparaitre
# le nombre d'iles devant apparaitre

PR1 = [0,5,0,0,0]
PR2 = [0,0,3,2,0]
PR3 = [3,0,0,0,2]
PR4 = [0,0,0,2,2]
PR5 = [0,0,3,1,0]
PR6 = [2,0,3,2,0]
PR7 = [0,1,0,2,0]
PR8 = [2,5,0,0,0]
PR9 = [0,1,3,0,0]
PR10 = [0,0,0,2,3]
PR11 = [2,0,3,0,0]
PR12 = [0,0,1,2,0]
PR13 = [0,5,1,0,0]
PR14 = [0,2,3,2,0]
PR15 = [0,0,2,2,3]
PR16 = [0,3,3,0,0]
PR17 = [0,3,0,0,0]
PR18 = [2,0,3,0,1]
PR19 = [1,0,1,2,3]
PR20 = [1,5,0,0,1]
PR21 = [0,1,3,1,2]
PR22 = [0,1,2,1,3]
PR23 = [0,1,1,0,1]
PR24 = [0,1,3,2,1]
PR25 = [0,3,3,0,1]
PR26 = [0,1,1,0,2]
PR27 = [0,1,2,0,0]
PR28 = [0,0,2,1,2]
PR29 = [0,4,0,0,2]
PR30 = [0,4,2,0,1]
PR31 = [0,1,2,2,2]
PR32 = [0,0,1,1,1]
PR33 = [1,0,0,2,3]
PR34 = [1,0,3,1,2]
PR35 = [0,0,3,1,1]
PR36 = [0,0,2,1,0]
PR37 = [3,1,1,1,0]
PR38 = [2,0,1,1,0]
PR39 = [0,4,0,1,2]
PR40 = [2,1,0,2,0]
PR41 = [2,0,3,1,1]
PR42 = [0,0,2,2,2]
PR43 = [2,0,1,2,0]
PR44 = [0,2,2,1,2]
PR45 = [0,1,2,0,2]
PR46 = [0,4,1,0,2]
PR47 = [1,1,2,0,3]
PR48 = [0,0,1,1,2]
PRS = [PR1, PR2, PR3, PR4, PR5, PR6, PR7, PR8, PR9,\
       PR10, PR11, PR12, PR13, PR14, PR15, PR16, PR17, PR18, PR19,\
       PR20, PR21, PR22, PR23, PR24, PR25, PR26, PR27, PR28, PR29,\
       PR30, PR31, PR32, PR33, PR34, PR35, PR36, PR37, PR38, PR39,\
       PR40, PR41, PR42, PR43, PR44, PR45, PR46, PR47, PR48]
RIEN = 0
BARQUE = 1
BATEAU_BLANC = 2
BATEAU_ROUGE = 3
MONTAGNE = 4
ILE = 5
PLATEAU = [[RIEN, BARQUE, BARQUE, MONTAGNE, BATEAU_BLANC],\
           [BATEAU_ROUGE, RIEN, MONTAGNE, BATEAU_BLANC, ILE],\
           [ILE, BATEAU_ROUGE, BATEAU_BLANC, BATEAU_BLANC, RIEN],\
           [BATEAU_BLANC, BARQUE, BATEAU_ROUGE, ILE, RIEN]]

noms_pieces = ["p1", "p2", "p3", "p4"]

def generer_rotations(piece):
    """
    Fonction générant toutes les rotations d'une pièce. Le centre (à l'indice 0) ne bouge pas
    """
    tete = piece[0]
    peripherie = piece[1:]
    retour = []
    for i in range(1,5):
        tour = peripherie[i:] + peripherie[:i]
        tour.insert(0, tete)
        retour.append(tour)
    return retour

def creer_table_rotations(pieces):
    """
    Création d'un dictionnaire associant à chaque pièce ses 4 rotations possibles.
    """
    retour = {}
    for couple in pieces:
        rotations = generer_rotations(couple[1])
        retour[couple[0]] = rotations
    return retour

def generer_config_rotations():
    """
    Création d'un tableau spécifiant toutes les possibilités de rotation des pièces
    à chaque position.
    """
    retour = []
    for i1 in range(4):
        for i2 in range(4):
            for i3 in range(4):
                for i4 in range(4):
                    retour.append([i1, i2, i3, i4])
    return retour

def resoudre(pieces_disponibles, probleme, solution=[]):
    if len(pieces_disponibles) == 0:
        return solution
    for piece in pieces_disponibles:
        nom_piece = piece[0]
        #print("On essaie de placer la pièce",nom_piece,"en case",len(solution))
        pieces_restantes = pieces_disponibles[:]
        pieces_restantes.remove(piece)
        for position in table_rotations[nom_piece]:
            solution_suivante = solution + [position]
            if not evaluer(probleme, solution_suivante):
                continue
            resultat = resoudre(pieces_restantes, probleme, solution_suivante)
            if resultat is not None:
                return resultat
    return None
    
def evaluer(probleme, solution):
    visu = [0, 0, 0, 0, 0, 0]
    for num_piece in range(len(solution)):
        for num_emplacement in range(5):
            visu[solution[num_piece][num_emplacement] *  PLATEAU[num_piece][num_emplacement]] += 1
    if visu[BARQUE] > probleme[BARQUE-1]:
        #print("Trop de barques")
        return False
    if visu[BATEAU_BLANC] > probleme[BATEAU_BLANC-1]:
        #print("Trop de bateaux blancs")
        return False
    if visu[BATEAU_ROUGE] > probleme[BATEAU_ROUGE-1]:
        #print("Trop de bateaux rouges")
        return False
    if visu[MONTAGNE] > probleme[MONTAGNE-1]:
        #print("Trop de montagnes")
        return False
    if visu[ILE] > probleme[ILE-1]:
        #print("Trop d'îles")
        return False
    return True
            
def generer_position(table_rotations, permutation, config):
    position = []
    erreur = False
    for indice_piece in range(4):
        piece = permutation[indice_piece]
        numero_rotation = config[indice_piece]
        if piece == "p3" and numero_rotation > 1:
            # la pièce p3 possède une symétrie centrale ;
            # On considère donc ses positions 2 et 3 comme illégales
            raise Exception()
        else:
            position.append(table_rotations[piece][numero_rotation])
    return position

def verifier_correction(probleme, position):
    visu = []
    for i in range(4):
        visu.append([0] * 5)
    for case in range(4):
        for place in range(5):
            # Un trou étant représenté par un "1",  multiplier par un trou
            # préserve l'objet.
            # Un plein étant représenté par un "0", multipier par un plein
            # masque l'objet
            visu[case][place] = PLATEAU[case][place] * position[case][place]
    visu_globale = [objet for case in visu for objet in case]
    visu_resumee = [visu_globale.count(BARQUE),\
                    visu_globale.count(BATEAU_BLANC),\
                    visu_globale.count(BATEAU_ROUGE),\
                    visu_globale.count(MONTAGNE),\
                    visu_globale.count(ILE)]
    return visu_resumee == probleme

def jeu(probleme):
    solution = resoudre(PIECES, probleme)
    chaines = list(map(representer, solution))
    print("---------")
    print("|"+ chaines[0][0] + "|" + chaines[1][0] + "|")
    print("|"+ chaines[0][1] + "|" + chaines[1][1] + "|")
    print("|"+ chaines[0][2] + "|" + chaines[1][2] + "|")
    print("---------")
    print("|"+ chaines[2][0] + "|" + chaines[3][0] + "|")
    print("|"+ chaines[2][1] + "|" + chaines[3][1] + "|")
    print("|"+ chaines[2][2] + "|" + chaines[3][2] + "|")
    print("---------")

def jeu2(probleme):
    solution = resoudre(PIECES, probleme)
    chaines = list(map(representer, solution))
    print("---------")
    print("|"+ chaines[0][0] + "|" + chaines[1][0] + "|")
    print("|"+ chaines[0][1] + "|" + chaines[1][1] + "|")
    print("|"+ chaines[0][2] + "|" + chaines[1][2] + "|")
    print("---------")
    print("|"+ chaines[2][0] + "|" + chaines[3][0] + "|")
    print("|"+ chaines[2][1] + "|" + chaines[3][1] + "|")
    print("|"+ chaines[2][2] + "|" + chaines[3][2] + "|")
    print("---------")

def representer(piece):
  ligne1 = car(piece[1]) + "*" + car(piece[2])
  ligne2 = "*" + car(piece[0]) + "*"
  ligne3 = car(piece[4]) + "*" + car(piece[3])
  return [ligne1, ligne2, ligne3]

def car(x):
    return " " if x == 1 else "*"

table_rotations = creer_table_rotations(PIECES)
config_rotations = generer_config_rotations()

def tout_tester():
    for probleme in PRS:
        solution = resoudre(PIECES, probleme)

def calcTempsFonction(f):
    t1 = time()
    f()
    t2 = time()
    return t2 - t1