import random
#HELPER FUNCTIONS
def bin_search(lst,item):
    """(list, int) -> int
    precondition: list is sorted
    Given a list of integers, return the index of the desired element in that list.
    """
    # RUNTIME = (O)log_n
    start = 0
    end = len(lst) 
    while start != end:
        middle = (start + end) //2
        if item < lst[middle]:
            end = middle
        elif item > lst[middle]:
            start = middle
        elif item == lst[middle]:
            return middle
    return False



def create_network(file_name):
    '''(str)->list of tuples where each tuple has 2 elements the first is int and the second is list of int

    Precondition: file_name has data on social netowrk. In particular:
    The first line in the file contains the number of users in the social network
    Each line that follows has two numbers. The first is a user ID (int) in the social network,
    the second is the ID of his/her friend.
    The friendship is only listed once with the user ID always being smaller than friend ID.
    For example, if 7 and 50 are friends there is a line in the file with 7 50 entry, but there is line 50 7.
    There is no user without a friend
    Users sorted by ID, friends of each user are sorted by ID
    Returns the 2D list representing the frendship nework as described above
    where the network is sorted by the ID and each list of int (in a tuple) is sorted (i.e. each list of friens is sorted).
    '''
    friends = open(file_name).read().splitlines()
    network=[]
    # YOUR CODE GOES HERE
    
    user_list = []
    #
    for i in range(1,len(friends)):
        line = friends[i].split(' ')
        uid = int(line[0])
        friend = int(line[1])
        user_list.append(uid)
        user_list.append(friend)
        
    # sorted() runtime = (O)n
    user_list = sorted(user_list)

    
    accumulated_list = []
    #runtime = (O)n
    for j in range(len(user_list)):
        accumulated_list.append([])
        
    resting_index = []
    for k in range(1,len(friends)):
        line = friends[k].split(' ')
        uid = int(line[0])
        friend = int(line[1])
        uid_index = bin_search(user_list, uid)
        friend_index = bin_search(user_list, friend)
        accumulated_list[uid_index].append(friend)
        accumulated_list[friend_index].append(uid)
        resting_index.append(uid_index)
        resting_index.append(friend_index)
    resting_index = sorted(resting_index)
     
    prev_index = True
    for l in range(len(resting_index)):
        if resting_index[l] != prev_index:
            network.append((user_list[resting_index[l]],accumulated_list[resting_index[l]]))
        prev_index = resting_index[l]
                  
    return network

def getCommonFriends(user1, user2, network):
    '''(int, int, 2D list) ->int
    Precondition: user1 and user2 IDs in the network. 2D list sorted by the IDs, 
    and friends of user 1 and user 2 sorted 
    Given a 2D-list for friendship network, returns the sorted list of common friends of user1 and user2
    '''
    common=[]
    
    # YOUR CODE GOES HERE
    user_list = []
    for i in range(len(network)):
        user_list.append(network[i][0])

    user1_index = bin_search(user_list, user1)
    user2_index = bin_search(user_list, user2)

    for friend in network[user1_index][1]:
        if friend in network[user2_index][1]:
            common.append(friend)
        
    return sorted(common)

    
def recommend(user, network):
    '''(int, 2Dlist)->int or None
    Given a 2D-list for friendship network, returns None if there is no other person
    who has at least one neighbour in common with the given user and who the user does
    not know already.
    
    Otherwise it returns the ID of the recommended friend. A recommended friend is a person
    you are not already friends with and with whom you have the most friends in common in the whole network.
    If there is more than one person with whom you have the maximum number of friends in common
    return the one with the smallest ID. '''

    # YOUR CODE GOES HERE
    user1_friends = []
    prev_max_friend = 0
    recommended_friend = None
    
    # (O)n
    user_list = []
    for i in range(len(network)):
        user_list.append(network[i][0])
        
    user_index = bin_search(user_list,user)
    for i in range(len(network[user_index][1])):
        user1_friends.append(network[user_index][1][i])

    #(O)n^3
    for j in user1_friends:
        j_index = bin_search(user_list,j)
        mini_lst = []
        for k in range(len(network[j_index][1])):
            if network[j_index][1][k] != user:
                mini_lst.append(network[j_index][1][k])
                
        for l in range(len(mini_lst)):
            common_friends = getCommonFriends(user, mini_lst[l], network)
            l_index = bin_search(user_list,mini_lst[l])
            if len(common_friends) > prev_max_friend and not (user in network[l_index][1]) :
                recommended_friend = mini_lst[l]
                prev_max_friend = len(common_friends)

    return recommended_friend
            

    


def k_or_more_friends(network, k):
    '''(2Dlist,int)->int
    Given a 2D-list for friendship network and non-negative integer k,
    returns the number of users who have at least k friends in the network
    Precondition: k is non-negative'''
    # YOUR CODE GOES HERE
    num_users = 0
    for i in range(len(network)):
        if len(network[i][1]) >= k:
            num_users +=1

    return num_users
    
 

def maximum_num_friends(network):
    '''(2Dlist)->int
    Given a 2D-list for friendship network,
    returns the maximum number of friends any user in the network has.
    '''
    # YOUR CODE GOES HERE
    maxf = 0
    # (O) n^2 ?
    for i in range(len(network)):
        if len(network[i][1]) > maxf:
            maxf = len(network[i][1])
    return maxf
    
    

def people_with_most_friends(network):
    '''(2Dlist)->1D list
    Given a 2D-list for friendship network, returns a list of people (IDs) who have the most friends in network.'''
    max_friends=[]
    # YOUR CODE GOES HERE
    
     #(O) n^2 ?
    maxf = maximum_num_friends(network)
    for j in range(len(network)):
        if len(network[j][1]) == maxf:
            max_friends.append(network[j][0])
                       
    return    max_friends


def average_num_friends(network):
    '''(2Dlist)->number
    Returns an average number of friends overs all users in the network'''

    # YOUR CODE GOES HERE
    total = 0
    users = 0

    for i in range(len(network)):
        total += len(network[i][1])
        users += 1

    return total / users
    
    

def knows_everyone(network):
    '''(2Dlist)->bool
    Given a 2D-list for friendship network,
    returns True if there is a user in the network who knows everyone
    and False otherwise'''
    
    # YOUR CODE GOES HERE
    length = len(network)
    for i in range(length):
        if len(network[i][1]) == length - 1:
            return True
    return False
    


####### CHATTING WITH USER CODE:

def is_valid_file_name():
    '''None->str or None'''
    file_name = None
    try:
        file_name=input("Enter the name of the file: ").strip()
        f=open(file_name)
        f.close()
    except FileNotFoundError:
        print("There is no file with that name. Try again.")
        file_name=None
    return file_name 

def get_file_name():
    '''()->str
    Keeps on asking for a file name that exists in the current folder,
    until it succeeds in getting a valid file name.
    Once it succeeds, it returns a string containing that file name'''
    file_name=None
    while file_name==None:
        file_name=is_valid_file_name()
    return file_name


def get_uid(network):
    '''(2Dlist)->int
    Keeps on asking for a user ID that exists in the network
    until it succeeds. Then it returns it'''
    
    # YOUR CODE GOES HERE
    user_list = []
    for i in range(len(network)):
        user_list.append(network[i][0])
        
    while True:
        try:
            uid = int(input("Please enter an integer as a user ID:"))
            if uid in user_list:
                return uid
            else:
                print("That user ID does not exist")
        except:
            print("That was not an integer. Please try again")
            
    
    

##############################
# main
##############################

# NOTHING FOLLOWING THIS LINE CAN BE REMOVED or MODIFIED

file_name=get_file_name()
    
net=create_network(file_name)

print("\nFirst general statistics about the social network:\n")

print("This social network has", len(net), "people/users.")
print("In this social network the maximum number of friends that any one person has is "+str(maximum_num_friends(net))+".")
print("The average number of friends is "+str(average_num_friends(net))+".")
mf=people_with_most_friends(net)
print("There are", len(mf), "people with "+str(maximum_num_friends(net))+" friends and here are their IDs:", end=" ")
for item in mf:
    print(item, end=" ")

print("\n\nI now pick a number at random.", end=" ")
k=random.randint(0,len(net)//4)
print("\nThat number is: "+str(k)+". Let's see how many people has that many friends.")
print("There is", k_or_more_friends(net,k), "people with", k, "or more friends")

if knows_everyone(net):
    print("\nThere at least one person that knows everyone.")
else:
    print("\nThere is nobody that knows everyone.")

print("\nWe are now ready to recommend a friend for a user you specify.")
uid=get_uid(net)
rec=recommend(uid, net)
if rec==None:
    print("We have nobody to recommend for user with ID", uid, "since he/she is dominating in their connected component")
else:
    print("For user with ID", uid,"we recommend the user with ID",rec)
    print("That is because users", uid, "and",rec, "have", len(getCommonFriends(uid,rec,net)), "common friends and")
    print("user", uid, "does not have more common friends with anyone else.")
        

print("\nFinally, you showed interest in knowing common friends of some pairs of users.")
print("About 1st user ...")
uid1=get_uid(net)
print("About 2st user ...")
uid2=get_uid(net)
print("Here is the list of common friends of", uid1, "and", uid2)
common=getCommonFriends(uid1,uid2,net)
for item in common:
    print(item, end=" ")