#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Jan 11 16:45:04 2023

@author: vincentleprince
"""

def graphChomp(n,p):
    """définit, sous forme d'un dictionnaire, le graphe (non biparti)
    associé au jeu de chomp à n lignes et p colonnes.
    Un état est représenté par un couple (l,c), représentant le nombre 
    de colonnes et de lignes restant."""
    def successeurs(l,c):
        listeS = []
        for j in range(1,c):
            listeS.append((l,j))
        for i in range(1,l):
            listeS.append((i,c))
        return listeS
    d = {}
    for l in range(1,n+1):
        for c in range(1,p+1):
            d[(l,c)] = successeurs(l,c)
    return d
#test :
d = graphChomp(2,3)

print(d)
#ou bien, pour une présentation plus agréable :
for clef , valeur in d.items():
    print(str(clef)+" : "+str(valeur))
    
"""On doit obtenir (pas forcément dans cet ordre) :
 {(2,3) : [(1,3),(2,1),(2,2)],
   (1,3) : [(1,2),(1,1)],
   (2,1) : [(1,1)],
   (2,2) : [(2,1),(1,2)],
   (1,2) : [(1,1)],
   (1,1) : []
 }
"""



def graphBipartiChomp(n,p):
    """définit, sous forme d'un dictionnaire, le graphe biparti
    associé au jeu de chomp à n lignes et p colonnes.
    Un état est représenté par un couple (l,c,joueur), représentant le nombre 
    de colonnes et de lignes restant et le joueur ayant la main."""
    d = graphChomp(n,p)
    dBiparti = {}
    for sommet in d.keys():
            l , c = sommet
            for joueur in [1,2]:
                autreJoueur = 3 - joueur
                dBiparti[(l,c,joueur)] = [(u,v,autreJoueur) for u,v in d[(l,c)]]
    return dBiparti
                
dBip = graphBipartiChomp(2,3)
#print(dBip)
#ou bien, pour une présentation plus agréable :
for clef , valeur in dBip.items():
    print(str(clef)+" : "+str(valeur))


"""Dans les deux fonctions suivantes, dBip est un dictionnaire représentant un 
graphe biparti de la façon dont on l'a défini ci dessus """

def test1(dBip,s, listeSommets):
    """teste si la liste de sommets listeSommets est accessible à partir du 
    sommet s """
    successeurs = dBip[s]
    for sommet in successeurs:
        if sommet in listeSommets:
            return True
    return False



def test2(dBip,s, listeSommets):
    """teste si tous les sommets accessibles à partir de s 
    sont dans la liste de sommets listeSommets.
    Attention : si dBip[s] est vide, la fonction devra renvoyer False également."""
    if len(dBip[s])==0:
        return False
    else:
        successeurs = dBip[s]
        for sommet in successeurs:
            if not(sommet in listeSommets):
                return False
        return True
                
        
        


#tests
dBip = graphBipartiChomp(2,3)
s = (1,3,1)
listeSommets = [(1,1,2),(1,1,1)]
print(test1(dBip,s, listeSommets))
print(test2(dBip,s, listeSommets))

listeSommets = [(1,1,2),(2,1,1)]
s = (2,2,2)
print(test1(dBip,s, listeSommets))
print(test2(dBip,s, listeSommets))

     


def attracteurChomp(n,p,joueur):
    """renvoie l'attracteur A de joueur sous forme d'une liste de sommets
    du graphe biparti.
    A sera la liste des sommets de l'attracteur d'ordre i"""
    dBip = graphBipartiChomp(n,p)
    autreJoueur = 3 - joueur
    A = [(1,1, autreJoueur)]  # on initialise avec la position gagnante de joueur
    evol = True # passe à False quand A n'évolue plus
    while evol:
        nouveauxSommetsDansA = []
        for s in dBip.keys():
            if (not (s in A)) : # inutile de tester les sommets déjà dans A
                                #de plus, cela créerait des doublons
                if s[2]==joueur:
                    if test1(dBip,s,A):
                        nouveauxSommetsDansA.append(s)
                    
                elif s[2]==autreJoueur:
                    if test2(dBip,s,A):
                        nouveauxSommetsDansA.append(s)
        if nouveauxSommetsDansA == []:
            evol = False
        #print(nouveauxSommetsDansA) #provisoire, pour tester
        A = A + nouveauxSommetsDansA
    return A

print(attracteurChomp(2,3,1))
        
        
    
def strategieChomp(n,p,joueur,pos):
    """pos est la position dans laquelle se trouve joueur ;
    la fonction doit renvoyer une position (de l'autre joueur)
     qui assurera le gain de la partie pour joueur (c'est à dire 
     une position dans l'attracteur de la position gagnante de joueur"""
    assert pos[2] == joueur , 'position incorrecte'
    dBip = graphBipartiChomp(n,p) 
    Att = attracteurChomp(n,p,joueur)
    assert pos in Att , 'pas de stratégie gagnante'
    """Ce début pourrait être amélioré car on fait deux fois 
    appel à graphBipartiChomp(n,p) """
    for cible in Att:
        if cible in dBip[pos]:
            return cible
        
print(strategieChomp(2,3,1,(2,3,1)))

print(strategieChomp(2,3,1,(1,3,1)))

print(strategieChomp(2,3,1,(2,3,2)))

print(strategieChomp(2,3,1,(2,2,1)))