n = 6
m = 7

print_mode = False

def f(x):
    if x==0: return " "
    elif x==1 : return "o"
    elif x==2 : return "x"

def afficher_grille(grille):
    num = [" "]+[str(j) for j in range(m)]+[" "]
    print(" ".join(num))
    for i in range(n):
        l = [str(i)]
        l += [f(x) for x in grille[i]]
        l.append(str(i))
        print("|".join(l))
    print(" ".join(num))

def coup_possible(hauteur, k):
    return k>=0 and k<m and hauteur[k]<n

def jouer(grille, hauteur, k, p):
    grille[n - 1 - hauteur[k]][k] = p
    hauteur[k]+=1

def victoire(grille, p):
    p4 = [p]*4
    for i in range(n):
        for j in range(m):
            if j <= m-4:
                l = grille[i][j:j+4]
                if l==p4:
                    return True
            if i <= n-4:
                l = [grille[i+k][j] for k in range(4)]
                if l==p4:
                    return True
            if i <= n-4 and j <= m-4:
                l = [grille[i+k][j+k] for k in range(4)]
                if l==p4:
                    return True
            if i <= n-4 and j >= 3:
                l = [grille[i+k][j-k] for k in range(4)]
                if l==p4:
                    return True
    return False

def PvP():
    grille = [[0 for _ in range(m)] for _ in range(n)]
    hauteur = [0 for _ in range(m)]
    joueur_courant = 1
    afficher_grille(grille)
    while True:
        k = int(input("Joueur "+f(joueur_courant)+", entrez votre coup :"))
        while not coup_possible(hauteur, k):
            print("coup non valide")
            k = int(input("Joueur "+f(joueur_courant)+", entrez votre coup :"))
        jouer(grille, hauteur, k, joueur_courant)
        afficher_grille(grille)
        if victoire(grille, joueur_courant):
            print("le joueur",f(joueur_courant), "a gagné la partie")
            return
        if hauteur == [n]*m:
            print("match nul")
            return
        joueur_courant = 3 - joueur_courant


def enlever_coup(grille, hauteur, k):
    hauteur[k]-=1
    grille[n - 1 - hauteur[k]][k] = 0

def eval_serie(L,p):
    opp = 3-p
    nb_p = 0
    nb_opp = 0
    for coup in L:
        if coup == p:
            nb_p +=1
        elif coup == opp:
            nb_opp += 1

    if nb_opp == 0:
        assert nb_p<4
        return nb_p/(4 - nb_p)
    elif nb_p == 0:
        assert nb_opp<4
        return -nb_opp/(4 - nb_opp)
    return 0

def eval(grille, p):
    s = 0
    opp = 3-p
    for i in range(n):
        for j in range(m):
            if j <= m-4:
                l = grille[i][j:j+4]
                s += eval_serie(l,p)
            if i <= n-4:
                l = [grille[i+k][j] for k in range(4)]
                s += eval_serie(l,p)
            if i <= n-4 and j <= m-4:
                l = [grille[i+k][j+k] for k in range(4)]
                s += eval_serie(l,p)
            if i <= n-4 and j >= 3:
                l = [grille[i+k][j-k] for k in range(4)]
                s += eval_serie(l,p)
    return s

def IA(grille, hauteur, p, prof):
    opp = 3-p
    def coup_max(prof2):
        if victoire(grille, opp):
            return -float("inf")
        if hauteur == [n]*m:
            return 0
        if prof2 == 0:
            v = eval(grille, p)
            return v
        vmax = -float("inf")
        for k in range(m):
            if coup_possible(hauteur, k):
                jouer(grille, hauteur, k, p)
                v = coup_min(prof2 - 1)
                enlever_coup(grille, hauteur, k)
                if v > vmax:
                    vmax = v
        return vmax
    def coup_min(prof2):
        if victoire(grille, p):
            return float("inf")
        if hauteur == [n]*m:
            return 0
        if prof2 == 0:
            v = eval(grille, p)
            return v
        vmin = float("inf")
        for k in range(m):
            if coup_possible(hauteur, k):
                jouer(grille, hauteur, k, 3-p)
                v = coup_max(prof2 - 1)
                enlever_coup(grille, hauteur, k)
                if v < vmin:
                    vmin = v
        return vmin

    kmax = 0
    vmax = -float("inf")
    for k in range(m):
        if coup_possible(hauteur, k):
            jouer(grille, hauteur, k, p)
            v = coup_min(prof - 1)
            enlever_coup(grille, hauteur, k)
            if v >= vmax:
                vmax = v
                kmax = k
    print("coup joué :", kmax, "score :", vmax)
    return kmax

from time import *

def PvIA(prof):
    grille = [[0 for _ in range(m)] for _ in range(n)]
    hauteur = [0 for _ in range(m)]
    joueur_courant = 1
    afficher_grille(grille)
    while True:
        if joueur_courant == 2:
            t = time()
            k = IA(grille, hauteur, 2, prof)
            print ("temps : ", time() - t)
        else:
            k = int(input("Joueur "+f(joueur_courant)+", entrez votre coup :"))
            while not coup_possible(hauteur, k):
                print("coup non valide")
                k = int(input("Joueur "+f(joueur_courant)+", entrez votre coup :"))
        jouer(grille, hauteur, k, joueur_courant)
        afficher_grille(grille)
        if victoire(grille, joueur_courant):
            print("le joueur",f(joueur_courant), "a gagné la partie")
            return
        if hauteur == [n]*m:
            print("match nul")
            return
        joueur_courant = 3 - joueur_courant

def IAvIA(IA1, IA2):
    grille = [[0 for _ in range(m)] for _ in range(n)]
    hauteur = [0 for _ in range(m)]
    joueur_courant = 1
    afficher_grille(grille)
    while True:
        if joueur_courant == 2: k = IA2(grille, hauteur, 2)
        else: k = IA1(grille, hauteur, 1)
        jouer(grille, hauteur, k, joueur_courant)
        afficher_grille(grille)
        if victoire(grille, joueur_courant):
            print("le joueur",f(joueur_courant), "a gagné la partie")
            return
        if hauteur == [n]*m:
            print("match nul")
            return
        joueur_courant = 3 - joueur_courant

def IA2(grille, hauteur, p):
    return IA(grille, hauteur, p, 2)

def IA3(grille, hauteur, p):
    return IA(grille, hauteur, p, 4)

def IA4(grille, hauteur, p):
    return IA(grille, hauteur, p, 6)





#Version mémoïsée temps 1.87 (profondeur 6) 181.4 (profondeur 10)

def grille_vers_tuple(grille):
    t = ()
    for i in range(n):
        t = t + tuple(grille[i])
    return t



def IA(grille, hauteur, p, prof):
    D = {}
    def coup_max(prof2):
        t = grille_vers_tuple(grille)
        if t in D:
            return D[t]
        if hauteur == [n]*m:
            return 0
        if victoire(grille, 3-p):
            v = -float("inf")
            D[t] = v
            return v
        if prof2 == 0:
            v = eval(grille, p)
            D[t] = v
            return v
        vmax = -float("inf")
        for k in range(m):
            if coup_possible(hauteur, k):
                jouer(grille, hauteur, k, p)
                v = coup_min(prof2 - 1)
                enlever_coup(grille, hauteur, k)
                if v > vmax:
                    vmax = v
        D[t] = vmax
        return vmax
    def coup_min(prof2):
        t = grille_vers_tuple(grille)
        if t in D:
            return D[t]
        if hauteur == [n]*m:
            return 0
        if victoire(grille, p):
            v = float("inf")
            D[t] = v
            return v
        if prof2 == 0:
            v = eval(grille, p)
            D[t] = v
            return v
        vmin = float("inf")
        for k in range(m):
            if coup_possible(hauteur, k):
                jouer(grille, hauteur, k, 3-p)
                if print_mode: print("\t"*(prof - prof2) , "o : ", k)
                v = coup_max(prof2 - 1)
                if print_mode: print("\t"*(prof - prof2) , "o : ", k, " -> ", v)
                enlever_coup(grille, hauteur, k)
                if v < vmin:
                    vmin = v
        D[t] = vmin
        return vmin

    kmax = 0
    vmax = -float("inf")
    for k in range(m):
        if coup_possible(hauteur, k):
            jouer(grille, hauteur, k, p)
            v = coup_min(prof - 1)
            enlever_coup(grille, hauteur, k)
            if v >= vmax:
                vmax = v
                kmax = k
    print("coup joué :", kmax, "score :", vmax)
    return kmax


#Bonus :
#alpha-beta memoise, ordre optimal sur les coups temps 0.1 (6) 7.68 (10)

ordre = [3,2,4,1,5,0,6]

def IA(grille, hauteur, p, prof):
    D = {}
    alpha = -float("inf")
    beta = float("inf")
    def noeud_max(prof2, alpha, beta):
        t = grille_vers_tuple(grille)
        if t in D:
            return D[t]
        if victoire(grille, 3-p):
            v = -float("inf")
            D[t] = (v, None)
            return v, None
        if prof2 == 0:
            v = eval(grille, p)
            D[t] = (v, None)
            return v, None
        kmax = None
        vmax = -float("inf")
        for k in ordre:
            if coup_possible(hauteur, k):
                jouer(grille, hauteur, k, p)
                v,_ = noeud_min(prof2 - 1, alpha, beta)
                enlever_coup(grille, hauteur, k)
                if v >= vmax:
                    kmax = k
                    vmax = v
                if vmax > beta:
                    D[t] = vmax,kmax
                    return vmax, kmax
                alpha = max(alpha, vmax)
        D[t] = vmax,kmax
        return vmax,kmax
    def noeud_min(prof2, alpha, beta):
        t = grille_vers_tuple(grille)
        if t in D:
            return D[t]
        if victoire(grille, p):
            v = float("inf")
            D[t] = (v,None)
            return v, None
        if prof2 == 0:
            v = eval(grille, p)
            D[t] = v, None
            return v, None
        kmin = None
        vmin = float("inf")
        for k in ordre:
            if coup_possible(hauteur, k):
                jouer(grille, hauteur, k, 3-p)
                v,_ = noeud_max(prof2 - 1, alpha, beta)
                enlever_coup(grille, hauteur, k)
                if v < vmin:
                    kmin = k
                    vmin = v
                if vmin < alpha:
                    D[t] = vmin,kmin
                    return vmin, kmin
                beta = min(beta, vmin)
        D[t] = vmin,kmin
        return vmin,kmin

    vmax, kmax = noeud_max(prof, alpha, beta)
    print("coup joué :", kmax, "score :", vmax)
    return kmax