from time import time

OPERATIONS = [ ("+", lambda x,y: x + y),\
               ("-", lambda x,y: x - y),\
               ("x", lambda x,y: x * y),\
               ("/", lambda x,y: x / y)]


def is_valide(resultat, operande1, operande2):
    retour  = resultat != 0 and\
                   int(resultat) == resultat and\
                   resultat != operande1 and\
                   resultat != operande2
    return retour

def generer_nouvelles_plaques2(anciennes_plaques, resultat, indice_premiere_plaque, indice_deuxieme_plaque):
    # version que je pensais plus rapide, mais en fait plus lente que l'autre
    nb_plaques = len(anciennes_plaques)
    nouvelles_plaques = [resultat] * (nb_plaques - 1)
    indice_nouveau = 1
    for i in range(0, nb_plaques):
        if i != indice_premiere_plaque and i != indice_deuxieme_plaque:
            nouvelles_plaques[indice_nouveau] = anciennes_plaques[i]
            indice_nouveau += 1
    return nouvelles_plaques

def generer_nouvelles_plaques(anciennes_plaques, resultat, indice_premiere_plaque, indice_deuxieme_plaque):
    nouvelles_plaques = [resultat] +\
        anciennes_plaques[:indice_premiere_plaque] +\
        anciennes_plaques[indice_premiere_plaque+1:indice_deuxieme_plaque] +\
        anciennes_plaques[indice_deuxieme_plaque+1:]
    return nouvelles_plaques

def generer_description_calcul(operande_max, operateur, operande_min, resultat):
    description_calcul = str(operande_max) + " " +\
        operateur + " " +\
        str(operande_min) + " = " +\
        str(resultat)
    return description_calcul
    
def generer_nouvelle_trace(ancienne_trace, description_calcul):
    nouvelle_trace = ancienne_trace[:]
    nouvelle_trace.append(description_calcul)
    return nouvelle_trace

def poursuivre(compte, plaques, trace, i, j, operande_min, operande_max, operation, resultat):
    resultat = int(resultat)
    nouvelles_plaques = generer_nouvelles_plaques(plaques, resultat, i, j)
    description_calcul = generer_description_calcul(operande_max, operation[0], operande_min, resultat)
    nouvelle_trace = generer_nouvelle_trace(trace, description_calcul)
    resultat = resoudre(compte, nouvelles_plaques, nouvelle_trace)
    return resultat

def essayer_operations(i, j, compte, plaques, trace):
    operande_max = max(plaques[i], plaques[j])
    operande_min = min(plaques[i], plaques[j])
    solutions = []
    for operation in OPERATIONS:
        resultat = operation[1](operande_max, operande_min)
        if is_valide(resultat, operande_max, operande_min):
            suite = poursuivre(compte, plaques, trace, i, j, operande_min, operande_max, operation, resultat)
            solutions += suite
    return solutions

def resoudre(compte, plaques, trace):
    solutions = []
    if plaques[0] == compte:
        return [trace]
    elif len(plaques) == 1:
        return []
    for i in range(len(plaques)-1):
        for j in range(i+1, len(plaques)):
            solutions += essayer_operations(i,j, compte, plaques, trace)
    return solutions

def garder_plus_courtes(listes):
    longueur_la_plus_courte = len(listes[0]) + 1
    for liste in listes:
        if len(liste) < longueur_la_plus_courte:
            longueur_la_plus_courte = len(liste)
            resultat = [liste]
        elif len(liste) == longueur_la_plus_courte:
            resultat.append(liste)
    return resultat

def solutions(compte, plaques):
    tout = resoudre(compte, plaques, [])
    retour = garder_plus_courtes(tout)
    return retour

def tester():
    return solutions(245, [2, 3, 50, 10, 9, 4])

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