def dict_tree(lista):
    """
    funzione che crea un dizionario che funge da albero di followers
    :param lista: lista concatenata in input
    :return: dizonario/albero
    """
    # creo una lista degli utenti
    users = [lista[i][0] for i in range(len(lista))]
    # creo una lista di liste dei followers per ogni user
    followers = [lista[i][1][0::2] for i in range(len(lista))]
    # creo un dizionario che associa ad ogni user la lista dei suoi followers usando prima zip che combina due iteratori(in questo caso liste)
    return dict(zip(users, followers))

def dict_beauty(lista):
    """
    funzione che crea un dizionario che associa ad ogni follower il prodotto di numero psot e mi paice
    :param lista: la lista concatenata in input
    :return: dizionario
    """
    # creo una lista dei followers
    new_followers = [x for i in range(len(lista)) for x in lista[i][1][::2]]
    # creo una lista in cui ogni elemento è un prodotto tra i mi piace il numero di post(belelzza di Giuseppe) di un follower
    new_beauty = [x[0] * x[1] for i in range(len(lista)) for x in lista[i][1][1::2]]
    # creo un secondo dizionario che associa ad ogni follower la sua bellezza di Giuseppe
    return dict(zip(new_followers, new_beauty))

def find_paths(dict_tree, d):
    """
    funzione che crea tutti i possibili percorsi nell'albero(dizionario) di distanza d
    che partono dalla radice dell'albero
    :param dict_tree:il dizionario che funge da albero prodotto dalla funzione dict_tree
    :param d: la distanza massima tra il nodo che funge da radice
    :return:una lista dei percorsi possibili che partono
    """
    paths = []
    def search(node, path, length):
        if length == d or (dict_tree.get(node, []) == [] and length < d):
            paths.append(path)
        for child in dict_tree.get(node, []):
            search(child, path + [child], length + 1)
    search(list(dict_tree.keys())[0], [list(dict_tree.keys())[0]], 0)
    return paths


def beauty(dict_tree, d):
    """
    funzione che calcola la bellezza secondo Sara(somma delle consonanti dei nomi dei followers per ogni percorso possibile)
    :param dict_tree: dizionario che funge da albero dei followers prodotto dalla funzione dict_tree
    :param d:distanza massima dalla radice
    :return:il valore di belelzza secondo Sara
    """
    beauties = []
    # ciclo su tutti i paths di lunghezza
    for x in find_paths(dict_tree, d):
        somma = 0
        for s in x[1:]:
            # faccio la somma di tutti le consonanti presenti nel nome del follower
            count = sum(1 for char in s if char not in 'aeiou')
            somma += count
        beauties.append(somma)
    return max(beauties)


def Giuseppe_beauty(dict_tree, dict_beauties, d):
    """
    funzione che calcola la bellezza secondo Giuseppe
    :param dict_tree: dizionario che funge da albero dei followers prodotto dalla funzione dict_tree
    :param dict_beauties: dizionario che associa ad ogni follower il prodotto di mi piace e post prodotto dalla funzione dict_beauty
    :param d:distanza massima dalla radice
    :return:la bellezza secondo Giuseppe
    """
    new_beauties = []
    for x in find_paths(dict_tree, d):
        somma = 0
        for s in x[1:]:
            somma += dict_beauties[s]
        new_beauties.append(somma)
    return max(new_beauties)




# Lista di esempio
l=[
    ['Sara', ['Davide', [10, 200], 'Michele', [24, 350], 'Nicholas', [120, 4000]]],
     ['Davide', ['Luca', [1, 100], 'Aurora', [10, 300]]],
     ['Nicholas', ['Vimal', [10, 400]]]
   ]

print(dict_tree(l))
print(beauty(dict_tree(l),2))
print(Giuseppe_beauty(dict_tree(l),dict_beauty(l),2))