## attracteur d'un jeu
def attracteur(G : dict, fA) -> list :
    """Prend en argument un dictionnaire d'adjacence G
    et une fonction fA qui détect si un sommet correspond
    au joueur A et renvoie la liste des attracteurs.
    """
    d = {}
    def aux(v) :
        if v not in d :
            if fA(v) : # si v correspond au joueur A
                # on cherche s'il existe un sommet adjacent
                # qui est attracteur.
                d[v] = False
                for w in G[v] :
                    if aux(w) :
                        d[v] = True
            else : # si v correspond au joueur A
                # on cherche si tout les sommets adjacents
                # sont attracteurs.
                d[v] = True
                for w in G[v] :
                    if not aux(w) :
                        d[v] = False
        return d[v]
    return [v for v in G if aux(v)]
# une version plus compacte utilisant les fonctions any (resp all) qui 
# prennent en argument une liste de booléens et renvoie vrai si l'un 
# est vrai (resp. vrai si tous sont vrais) et faux sinon.
def attracteur2(G : dict, fA) -> list :
    """Prend en argument un dictionnaire d'adjacence G
    et une fonction fA qui détect si un sommet correspond
    au joueur A et renvoie la liste des attracteurs.
    """
    d = {}
    def aux(v) :
        if v not in d :
            if fA(v) : # si v correspond au joueur A
                # on cherche s'il existe un sommet adjacent
                # qui est attracteur.
                d[v] = any([aux(w) for w in G[v]])
            else : # si v correspond au joueur A
                # on cherche si tout les sommets adjacents
                # sont attracteurs.
                d[v] = all([aux(w) for w in G[v]])
        return d[v]
    return [v for v in G if aux(v)]

## Construction du graphe du jeu de Nim
def nim(n : int) -> dict :
    """Prend en argument un entier n et renvoie le
    dictionnaire d'adjacence du jeu de Nim à n allumettes.
    """
    G = {}
    for i in range(0, n+1) :
        LA = []
        LB = []
        for k in range(i+1, min(i +4, n+1)) :
            LA.append((k,'B'))
            LB.append((k,'A'))
        G[(i,'A')], G[(i,'B')] = LA, LB
    return G

## Application
G = nim(4)
def fA(v) :
    return v[1] == "A"
A = attracteur2(G,fA)
print(A)