import numpy as np

## préambule pour générer des graphes non orientés (NE PAS MODIFIER)
def liste_u(n):
    liste = [42]
    for k in range(n):
        x = (19999999 * liste[-1])%19999981
        liste.append(x)
    return liste

def generateur_graphe(n,p):
    graphe = [[] for k in range(n)]
    k = 0
    u = liste_u(n*(n-1)//2)
    for i in range(n-1):
        for j in range(i+1,n):
            if u[k]%10000 < p:
                graphe[i].append(j)
                graphe[j].append(i)
            k += 1
    return graphe

##
graphe1 = generateur_graphe(10,654)
graphe2 = generateur_graphe(100,543)
graphe3 = generateur_graphe(1000,12)
graphe4 = generateur_graphe(50,250)

liste_graphes = [graphe1, graphe2, graphe3, graphe4]

## Question 1
print(graphe1[0])
print(graphe1[4])
print(graphe2[1])

## Question 2
def nb_arretes(graphe):
    return sum([len(liste) for liste in graphe])//2

# ou
def nb_arretes(graphe):
    nb = 0
    for liste in graphe:
        nb += len(liste)
    return nb//2

# test
for graphe in liste_graphes:
    print(nb_arretes(graphe))

## Question 3
def parcours_largeur(graphe, x):
    file = [x]
    liste = []
    while file != []:
        y = file.pop(0)
        if y not in liste:
            liste.append(y)
            for z in graphe[y]:
                if z not in liste :
                    file.append(z)
    return liste

# test
print(parcours_largeur(graphe4, 11))

## Question 4
def parcours_profondeur(graphe, x):
    pile = [x]
    liste = []
    while pile != []:
        y = pile.pop()
        if y not in liste:
            liste.append(y)
            for z in graphe[y]:
                if z not in liste:
                    pile.append(z)
    return liste

#test
print(parcours_profondeur(graphe3,60))

## Question 5
def nb_composantes_connexes(graphe):
    nb = 0
    n = len(graphe)
    deja_vu = []
    for x in range(n):
        if x not in deja_vu:
            deja_vu += parcours_profondeur(graphe, x)
            nb += 1
    return nb

# test
for graphe in liste_graphes:
    print(nb_composantes_connexes(graphe))

################################################################################
############################# Chasse au trésor #################################
################################################################################

## préambule (NE PAS MODIFIER)
def generateur_graphe_bis(n,p):
    graphe = generateur_graphe(n,p)
    for i in range(n-1):
        if i not in graphe[i+1]:
            graphe[i].append(i+1)
            graphe[i+1].append(i)
    return graphe

graphe_fig1 = [[3,5], [3,4,5], [3], [0,1,2,5], [1,5,6], [0,1,3,4], [4], [8], [7]]
graphe_tresor1 = generateur_graphe_bis(100,4)
graphe_tresor2 = generateur_graphe_bis(100,32)
graphe_tresor3 = generateur_graphe_bis(200,21)
graphe_tresor4 = generateur_graphe_bis(1000,1)

## Question 6
def distance_a_x(graphe, x):
    n = len(graphe)
    distance = [np.inf for k in range(n)]
    distance[x] = 0
    file = [x]
    while file != []:
        y = file.pop(0)
        for z in graphe[y]:
            if z not in file and distance[z] == np.inf:
                file.append(z)
                distance[z] = distance[y] + 1
    return distance

distance = distance_a_x(graphe_fig1, 2)
print(distance)

##
def piece_plus_proche(graphe, x, pieces):
    distance = distance_a_x(graphe, x)
    n = len(graphe)
    d_min = np.inf
    for i in range(n):
        if distance[i] < d_min and pieces[i]:
            d_min = distance[i]
            i_min = i
    return i_min, d_min

# test
k = 2
n = len(graphe_tresor1)
pieces = pieces = [False]*(n-k) + [True]*k
print(piece_plus_proche(graphe_tresor1, 0, pieces))

##
def nb_deplacements(graphe, k):
    n = len(graphe)
    i = 0
    nb = 0
    pieces = [False]*(n-k) + [True]*k
    compteur_pieces = 0
    while compteur_pieces < k:
        i, d = piece_plus_proche(graphe, i, pieces)
        #print(i) # prochaine pièce
        nb += d
        compteur_pieces += 1
        pieces[i] = False
        # print(i)
        # print(pieces)
    return nb

# test
print(nb_deplacements(graphe_tresor2, 10))
print(nb_deplacements(graphe_tresor3, 15))
print(nb_deplacements(graphe_tresor4, 20))