import itertools
import functools


def billard(bornes):
    """
    Résolution du problème par la méthode du billard
    Exemple : billard((5,3))
    """
    config = [0, 0]
    bornes = list(reversed(sorted(bornes)))
    while config != bornes:
        if config[0] == 0:
            config[0] = bornes[0]
            print("Remplir le grand : ", config)
        elif config[1] == bornes[1]:
            config[1] = 0
            print("Vider le petit : ", config)
        else:
            t = min(config[0], bornes[1] - config[1])
            config[0] -= t
            config[1] += t
            print("Transvaser du grand vers le petit : ", config)


def atteignables(source, bornes):
    """
    Renvoie l'ensemble des configurations atteignables à partir
    de la configuration 'source', avec des récipients de taille 'bornes'.
    Exemple : atteignables((5,0),(5,3))
    """
    l = []
    for i in range(len(source)):
        d = list(source)
        d[i] = bornes[i]
        l.append(tuple(d))
        d[i] = 0
        l.append(tuple(d))
    for i, j in itertools.product(range(len(source)), range(len(source))):
        t = min(source[i], bornes[j]-source[j])
        d = list(source)
        d[i] -= t
        d[j] += t
        l.append(tuple(d))
    l = set(l)
    if source in l:
        l.remove(source)
    return l


def longueur(point, chemins):
    """
    Calcule la distance d'un point du graphe 
    à l'origine
    """
    if not point in chemins:
        return None
    d = 0
    while chemins[point][0] is not None:
        point = chemins[point][0]
        d += 1
    return d


def explore(depart, bornes):
    """
    Calcule la liste des chemins les plus courts vers chacun des noeuds
    en partant de 'depart', avec des récipient de tailles 'bornes'.
    Exemple : c=explore((0,0),(5,3))
    """
    chemins = {depart: [None, 0]}
    frontiere = set((depart,))
    while len(frontiere):
        source = frontiere.pop()
        s = longueur(source, chemins)
        prochains = atteignables(source, bornes)
        for n in prochains:
            if n not in chemins or s+1 < longueur(n, chemins):
                chemins[n] = [source, -1]
                frontiere.add(n)
    maj_distances(chemins)
    return chemins


def maj_distances(chemins):
    """
    Une fois le graphe 'chemins' créé, calcul pour chaque 
    noeud sa distance à l'origine. Le graphe est modifié.
    """
    def maj_rec(noeud, chemins):
        if chemins[noeud][1] >= 0:
            return chemins[noeud][1]
        v = maj_rec(chemins[noeud][0], chemins)
        chemins[noeud][1] = v+1
        return v+1

    for k in chemins:
        maj_rec(k, chemins)


def volumes_atteignables(chemins):
    """
    Analyse un graphe pour renvoyer l'ensemble des volumes 
    qu'il est possible de construire et le nombre minimum d'étapes 
    nécessaires pour le faire
    """
    s = functools.reduce(set.__or__, [set(k) for k in chemins], set())
    liste = [-1]*(max(s)+1)
    for i in s:
        liste[i] = min([(v[1], k) for k, v in chemins.items() if i in k])[0]

    return liste


def chemin_graphe(chemins, filename="out.png"):
    """ Trace une image du graphe (utilise graphviz) """
    import pygraphviz as pgv
    def tstr(v): return ",".join(str(c) for c in v)
    G = pgv.AGraph(rankdir="RL")
    for k, v in chemins.items():
        if v[0] is not None:
            G.add_edge(tstr(k), tstr(v[0]))
    G.node_attr.update(fillcolor='#ffffcc', style='filled')
    G.draw(filename, prog='dot')
    return G


def creation_couples(n):
    """ Renvoie la liste des couples premiers entre eux jusqu'à en avoir n """
    from math import gcd
    liste = []
    i = 3
    while True:
        for j in range(2, i):
            if gcd(i, j) == 1:
                liste.append((i, j))
                if len(liste) == n:
                    return liste
        i += 1
    return liste