# -*- coding: utf-8 -*-
"""
Created on Fri Dec 18 15:47:50 2020

@author: Roupoil
"""

def appartient(L,x) :
    for i in L :
        if i==x :
            return True
    return False
    
def compte(L,x) :
    c=0
    for i in L :
        if i==x :
            c=c+1
    return c
    
def remplace(L,x,y) :
    for i in range(len(L)) :
        if L[i]==x :
            L[i]=y
    return L
    
def successifs(L,x) :
    c=0
    n=len(L)
    while (c<n) and (L[c]==x) :
        c=c+1
    return c
    
def maxsuccessifs(L,x) :
    chaine=0
    n=len(L)
    for i in range(n) :
        if L[i]==x :
            j=i+1
            c=1
            while (j<n) and (L[j]==x) :
                j=j+1
                c=c+1
            if c>chaine :
                chaine=c
    return chaine
    
def memelongueur(L) :
    a=len(L[0])
    for i in L[1 :] :
        if len(i) !=a :
            return False
    return True

def initialisegrille(n,p):
    l=[[0 for i in range(p)] for j in range(n)]
    return l
    
def affichegrille(g) :
    for i in range(len(g)) :
        s='|'
        for j in range(len(g[i])) :
            s=s+str(g[i][j])+'|'
        print(s)
    return
    
def couppossible(g,i) :
    return g[0][i-1]==0

def coupj1(g,i) :
    if not couppossible(g,i) :
        return g
    c=0
    while c<len(g)-1 and g[c+1][i-1]==0 :
        c+=1
    g[c][i-1]=1
    return g

def coupj2(g,i) :
    if not couppossible(g,i) :
        return g
    c=0
    while c<len(g)-1 and g[c+1][i-1]==0 :
        c+=1
    g[c][i-1]=2
    return g

def verifiegain(g) :
    for joueur in range(1,3) :
        m=0
        for i in range(len(g)) :
            a=maxsuccessifs(g[i],joueur)
            if a>m :
                m=a
        for j in range(len(g[0])) :
            liste=[g[i][j] for i in range(len(g))]
            a=maxsuccessifs(liste,joueur)
            if a>m :
                m=a
        if m>=4 :
            print('Le joueur ',joueur,' a gagne la partie !')
            return True
    return False
    
def puissance4(n,p) :
    g=initialisegrille(n,p)
    affichegrille(g)
    coups=0
    joueur=1
    while coups<n*p :
        print('Joueur ',joueur,', choisissez une colonne')
        i=input()
        if joueur==1 :
            g=coupj1(g,i)
            joueur=2
        else :
            g=coupj2(g,i)
            joueur=1
        coups+=1
        affichegrille(g)
        verifiegain(g)
        if verifiegain(g) :
            return
    return('Match nul !')
    
from random import randint

def puissordibete(n,p) :
    g=initialisegrille(n,p)
    affichegrille(g)
    coups=0
    while coups<n*p :
        print('Joueur humain, choisissez une colonne')
        i=input()
        g=coupj1(g,i)
        r=randint(1,p)
        g=coupj2(g,r)
        coups+=2
        affichegrille(g)
        verifiegain(g)
        if verifiegain(g) :
            return
    return('Match nul !')

def meilleuralign(g) :
    m=0
    for i in range(len(g)) :
        a=maxsuccessifs(g[i],2)
        if a>m :
            m=a
    for j in range(len(g[0])) :
        liste=[g[i][j] for i in range(len(g))]
        a=maxsuccessifs(liste,2)
        if a>m :
            m=a
    return m

from copy import deepcopy

def meilleurcoup(g):
    z=1
    l=meilleuralign(g)
    for i in range(1,len(g[0])+1):
        grilleprovisoire=deepcopy(g)
        grilleprovisoire=coupj2(grilleprovisoire,i)
        l2=meilleuralign(grilleprovisoire)
        if l2>l:
            z=i
    return z

def puissordi(n,p) :
    g=initialisegrille(n,p)
    affichegrille(g)
    coups=0
    while coups<n*p :
        print('Joueur humain, choisissez une colonne')
        i=input()
        g=coupj1(g,i)
        o=meilleurcoup(g)
        g=coupj2(g,o)
        coups+=2
        affichegrille(g)
        verifiegain(g)
        if verifiegain(g) :
            return
    return('Match nul !')