from graphe import Graphe

# sommet = (d, l, b) avec
#    0 <= d <= 3 le nombre de dragons sur la rive gauche
#    0 <= l <= 3 le nombre de licornes sur la rive droite
#    b un booléen indiquant si le bateau est sur la rive gauche
g = Graphe()
for d in range(4):
    for l in range(4):
        if l == 0 or l == 3 or (d <= l and 3-d <= 3-l):
            g.ajouter_sommet((d, l, False))
            g.ajouter_sommet((d, l, True))

print(g.nb_sommets(), "sommets")

def voyage(s, s1):
    if g.sommet(s1):
        g.ajouter_arc(s, s1)

for s in g.sommets():
    dg, lg, gauche = s
    dd, ld = 3 - dg, 3 - lg
    if gauche:
        # on transporte uniquement des dragons
        for d in range(1, min(3, dg + 1)):
            voyage(s, (dg - d, lg, False))
        # on transporte uniquement des licornes
        for l in range(1, min(3, lg + 1)):
            voyage(s, (dg, lg - l, False))
        # on transporte un de chaque
        if dg >= 1 and lg >= 1:
            voyage(s, (dg - 1, lg - 1, False))
    else:
        # on transporte uniquement des dragons
        for d in range(1, min(3, dd + 1)):
            voyage(s, (dg + d, lg, True))
        # on transporte uniquement des licornes
        for l in range(1, min(3, ld + 1)):
            voyage(s, (dg, lg + l, True))
        # on transporte un de chaque
        if dd >= 1 and ld >= 1:
            voyage(s, (dg + 1, lg + 1, True))

print(g.nb_arcs(), "arcs")

# recherche d'un chemin avec un parcours en largeur

from largeur import chemin

for s in chemin(g, (3, 3, True), (0, 0, False)):
    print(s)