Untitled

# -------------------------------- #
# Intro to CS Final Project        #
# Gaming Social Network [Option 1] #
# -------------------------------- #
#
# For students who have paid for the full course experience:
# please check submission instructions in the Instructor Note below.
# -----------------------------------------------------------------------------

# Background
# ==========
# You and your friend have decided to start a company that hosts a gaming
# social network site. Your friend will handle the website creation (they know
# what they are doing, having taken our web development class). However, it is
# up to you to create a data structure that manages the game-network information
# and to define several procedures that operate on the network.
#
# In a website, the data is stored in a database. In our case, however, all the
# information comes in a big string of text. Each pair of sentences in the text
# is formatted as follows:
#
# <username> is connected to <name1>, <name2>,...,<nameN>.
# <username> likes to play <game1>,...,<gameN>.
#
# Your friend records the information in that string based on user activity on
# the website and gives it to you to manage. You can think of every pair of
# sentences as defining a gamer profile. For example:
#
# John is connected to Bryant, Debra, Walter.
# John likes to play The Movie: The Game, The Legend of Corgi, Dinosaur Diner.
#
# Consider the data structures that we have used in class - lists, dictionaries,
# and combinations of the two - (e.g. lists of dictionaries). Pick one which
# will allow you to manage the data above and implement the procedures below.
#
# You can assume that <username> is a unique identifier for a user. In other
# words, there is only one John in the network. Furthermore, connections are not
# symmetric - if John is connected with Alice, it does not mean that Alice is
# connected with John.
#
# Project Description
# ====================
# Your task is to complete the procedures according to the specifications below
# as well as to implement a Make-Your-Own procedure (MYOP). You are encouraged
# to define any additional helper procedures that can assist you in accomplishing
# a task. You are encouraged to test your code by using print statements and the
# Test Run button.
# -----------------------------------------------------------------------------

# Example string input. Use it to test your code.
# Some details:  Each sentence will be separated from one another with only
# a period (there will not be whitespace or new lines between sentences)
example_input="John is connected to Bryant, Debra, Walter.\
John likes to play The Movie: The Game, The Legend of Corgi, Dinosaur Diner.\
Bryant is connected to Olive, Ollie, Freda, Mercedes.\
Bryant likes to play City Comptroller: The Fiscal Dilemma, Super Mushroom Man.\
Mercedes is connected to Walter, Robin, Bryant.\
Mercedes likes to play The Legend of Corgi, Pirates in Java Island, Seahorse Adventures.\
Olive is connected to John, Ollie.\
Olive likes to play The Legend of Corgi, Starfleet Commander.\
Debra is connected to Walter, Levi, Jennie, Robin.\
Debra likes to play Seven Schemers, Pirates in Java Island, Dwarves and Swords.\
Walter is connected to John, Levi, Bryant.\
Walter likes to play Seahorse Adventures, Ninja Hamsters, Super Mushroom Man.\
Levi is connected to Ollie, John, Walter.\
Levi likes to play The Legend of Corgi, Seven Schemers, City Comptroller: The Fiscal Dilemma.\
Ollie is connected to Mercedes, Freda, Bryant.\
Ollie likes to play Call of Arms, Dwarves and Swords, The Movie: The Game.\
Jennie is connected to Levi, John, Freda, Robin.\
Jennie likes to play Super Mushroom Man, Dinosaur Diner, Call of Arms.\
Robin is connected to Ollie.\
Robin likes to play Call of Arms, Dwarves and Swords.\
Freda is connected to Olive, John, Debra.\
Freda likes to play Starfleet Commander, Ninja Hamsters, Seahorse Adventures."

example_input_alternate="""John is connected to Bryant, Debra, Walter. John likes to play The Movie: The Game, The Legend of Corgi, Dinosaur Diner. Bryant is connected to Olive, Ollie, Freda, Mercedes. Bryant likes to play City Comptroller: The Fiscal Dilemma, Super Mushroom Man. Mercedes is connected to Walter, Robin, Bryant. Mercedes likes to play The Legend of Corgi, Pirates in Java Island, Seahorse Adventures. Olive is connected to John, Ollie. Olive likes to play The Legend of Corgi, Starfleet Commander. Debra is connected to Walter, Levi, Jennie, Robin. Debra likes to play Seven Schemers, Pirates in Java Island, Dwarves and Swords. Walter is connected to John, Levi, Bryant. Walter likes to play Seahorse Adventures, Ninja Hamsters, Super Mushroom Man. Levi is connected to Ollie, John, Walter. Levi likes to play The Legend of Corgi, Seven Schemers, City Comptroller: The Fiscal Dilemma. Ollie is connected to Mercedes, Freda, Bryant. Ollie likes to play Call of Arms, Dwarves and Swords, The Movie: The Game. Jennie is connected to Levi, John, Freda, Robin. Jennie likes to play Super Mushroom Man, Dinosaur Diner, Call of Arms. Robin is connected to Ollie. Robin likes to play Call of Arms, Dwarves and Swords. Freda is connected to Olive, John, Debra. Freda likes to play Starfleet Commander, Ninja Hamsters, Seahorse Adventures."""

# -----------------------------------------------------------------------------
# create_data_structure(string_input):
#   Parses a block of text (such as the one above) and stores relevant
#   information into a data structure. You are free to choose and design any
#   data structure you would like to use to manage the information.
#
# Arguments:
#   string_input: block of text containing the network information
#
# Return:
#   The new network data structure
#################################
##       Helper Functions      ##
##  for create_data_structure  ##
#################################

def find_each_sentence(string_input):
    '''Separates a paragraph into a list of strings. Only works if only periods are separating sentences.'''
    sentences, agg = [], ''
    for c in string_input:
        if c == '.':
            sentences.append(agg.strip())
            agg = ''
        else:
            agg += c
    return sentences

def separate_into_connections_and_likes(list_of_strings):
    '''Sorts sentences into a dictionary based on connections and games. Only uses specific phrases'''
    dictionary = {}
    dictionary['connections'] = []
    dictionary['likes'] = []
    for elem in list_of_strings:
        if "connected" in elem:
            dictionary["connections"].append(elem)
        elif "likes to play" in elem:
            dictionary['likes'].append(elem)
    return dictionary

# I debated whether or not I should combine find_user and find_objects. I decided against it
# as find_user returns a string and find_objects returns a list of strings.

def find_user(string):
    '''Returns the user of a sentence. Only works with specific phrases'''
    user = -1
    if " is connected to" in string:
        loc = string.find(" is connected to")
    elif " likes to play" in string:
        loc = string.find(" likes to play")
    else:
        print "Please see the docstring"
    user = string[:loc]                       # Splices the string up to the verb
    return user

def find_objects(string):
    '''Returns the objects in the form of a list of strings. Only works with specific phrases.'''
    list_of_objects = []
    if " is connected to" in string:
        loc = string.find(" is connected to")
        objects = string[loc + len(" is connected to"):]
    elif " likes to play" in string:
        loc = string.find(" likes to play")
        objects = string[loc + len(" likes to play"):]
    else:
        print "Format of string is wrong"
    for i in range(objects.count(",")):                    # This loop doesn't execute if there is only 1 object
        loc_c = objects.find(',')
        list_of_objects.append(objects[:loc_c].strip())
        objects = objects[loc_c+1:].strip()
    list_of_objects.append(objects.strip())                # This statement appends the last object (or the only object in the case of exactly one object)
    return list_of_objects

def pull_arguments(list_of_strings):
    '''Turns separated sentences into a dictionary on one type. Either connections OR likes - not both'''
    user_dict = {}
    user = ''
    for elem in list_of_strings:
        user = find_user(elem)
        user_dict[user] = find_objects(list_of_strings[list_of_strings.index(elem)])
    return user_dict

###############################
##  End of Helper Functions  ##
###############################

def create_data_structure(string_input):
    '''Combines two dictionaries created from pull_arguments. Returns the network.'''
    network = {}
    separated = separate_into_connections_and_likes(find_each_sentence(string_input))
    connected = pull_arguments(separated['connections'])
    liked = pull_arguments(separated['likes'])
    for name in connected:
        network[name] = {'Connections' : connected[name], 'Likes' : liked[name]}
    return network

# ----------------------------------------------------------------------------- #
# Note that the first argument to all procedures below is 'network' This is the #
# data structure that you created with your create_data_structure procedure,    #
# though it may be modified as you add new users or new connections. Each       #
# procedure below will then modify or extract information from 'network'        #
# ----------------------------------------------------------------------------- #

# -----------------------------------------------------------------------------
# get_connections(network, user):
#   Returns a list of all the connections a user has.
#
# Arguments:
#   network: The network you created with create_data_structure.
#   user:    String containing the name of the user.
#
# Return:
#   A list of all connections the user has. If the user has no connections,
#   return an empty list. If the user is not in network, return None.

def get_connections(network, user):
    '''Returns forward connections for a user.'''
    if user not in network:
        return None
    if len(network[user]['Connections']):   # Network was designed as a dictionary that could easily pull out connections and likes
        return network[user]['Connections']
    return []

# -----------------------------------------------------------------------------
# add_connection(network, user_A, user_B):
#   Adds a connection from user_A to user_B. Make sure to check that both users
#   exist in network.
#
# Arguments:
#   network: The network you created with create_data_structure.
#   user_A:  String with the name of the user ("Gary")
#   user_B:  String with the name of the user that will be the new connection.
#
# Return:
#   The updated network with the new connection added (if necessary), or False
#   if user_A or user_B do not exist in network.

def add_connection(network, user_A, user_B):
    if user_A not in network or user_B not in network:
        return False
    if network[user_A]['Connections'] == ['']:
        network[user_A]['Connections'] = user_B
    else:
        network[user_A]['Connections'] = network[user_A]['Connections'] + [user_B]
    return network

# -----------------------------------------------------------------------------
# add_new_user(network, user, games):
#   Creates a new user profile and adds that user to the network, along with
#   any game preferences specified in games. Assume that the user has no
#   connections to begin with.
#
# Arguments:
#   network: The network you created with create_data_structure.
#   user:    String containing the users name to be added (e.g. "Dave")
#   games:   List containing the user's favorite games, e.g.:
#            ['Ninja Hamsters', 'Super Mushroom Man', 'Dinosaur Diner']
#
# Return:
#   The updated network with the new user and game preferences added. If the
#   user is already in the network, update their game preferences as necessary.

def add_new_user(network, user, games):
    if user in network:
        for game in games:
            if game not in network[user]['Likes']:
                network[user]['Likes'].append(game)
    else:
        network[user] = {'Connections': [], 'Likes': games} # New users won't have any connections
    return network

# -----------------------------------------------------------------------------
# get_secondary_connections(network, user):
#   Finds all the secondary connections, i.e. connections of connections, of a
#   given user.
#
# Arguments:
#   network: The network you created with create_data_structure.
#   user:    String containing the name of a user.
#
# Return:
#   A list containing the secondary connections (connections of connections).
#   If the user is not in the network, return None. If a user has no primary
#   connections to begin with, you should return an empty list.
#
# NOTE:
#   It is OK if a user's list of secondary connections includes the user
#   himself/herself. It is also OK if the list contains a user's primary
#   connection that is a secondary connection as well.

def get_secondary_connections(network, user):
    '''Returns a list of friends of friends of a user'''
    if user not in network:
        return None
    agg = []
    for primary in get_connections(network, user):        # Get friends
        for second in get_connections(network, primary):  # Get friends of friends
            if second not in agg:                         # Don't add the same friend more than once
                agg.append(second)
    return agg

# -----------------------------------------------------------------------------
# connections_in_common(network, user_A, user_B):
#   Finds the number of people that user_A and user_B have in common.
#
# Arguments:
#   network: The network you created with create_data_structure.
#   user_A:    String containing the name of user_A.
#   user_B:    String containing the name of user_B.
#
# Return:
#   The number of connections in common (integer). Should return False if
#   user_A or user_B are not in network.

def connections_in_common(network, user_A, user_B):
    '''Returns an int of forward friends in common'''
    if user_A not in network or user_B not in network:
        return False
    count = 0
    A = get_connections(network, user_A)
    B = get_connections(network, user_B)
    for friend in A:                            # It doesn't matter which friendlist you use as long as you use the other in the next line
        if friend in B:
            count += 1
    return count

# -----------------------------------------------------------------------------
# path_to_friend(network, user, connection):
#   Finds the connections path from user_A to user_B. It has to be an existing
#   path but it DOES NOT have to be the shortest path.
#                   Solve this problem using recursion.
# Arguments:
#   network: The network you created with create_data_structure.
#   user_A:  String holding the starting username ("Abe")
#   user_B:  String holding the ending username ("Zed")
#
# Return:
#   A List showing the path from user_A to user_B. If such a path does not
#   exist, return None
#
# Sample output:
#   >>> print path_to_friend(network, "Abe", "Zed")
#   >>> ['Abe', 'Gel', 'Sam', 'Zed']
#   This implies that Abe is connected with Gel, who is connected with Sam,
#   who is connected with Zed.
#
# NOTE:
#   You must solve this problem using recursion!
#
# Hint:
#   Be careful how you handle connection loops, for example, A is connected to B.
#   B is connected to C. C is connected to B. Make sure your code terminates in
#   that case.

# This is a depth first search
def path_to_friend(network, user_A, user_B, connection=None, expanded=None):
    if not expanded:                            # This statement will only ever be True on the first run of the code
        connection, expanded = [], []
        connection.append(user_A)
        expanded.append(user_A)
    #print connection                           # - ### - Try out this print statement using example below. You can see the stack (connections) growing and shrinking.
    if connection:                              # If the stack isn't empty. Once the stack is empty, you know there are no possible connections
        if user_B == connection[-1]:            # Base case
            return connection
        friends = get_connections(network, connection[-1]) # Get friends of the last person in the connection
        # There are two "for friend in friends" statements. This is intentional. We want to check all of the friends two separate times
        for friend in friends:                  # Check ALL possible current edges (friends) to see if we've reached the goal state
            if friend == user_B:
                connection.append(user_B)
                return connection
        for friend in friends:                   # If nothing is the goal state, check ALL the nodes to expand to try again
            if friend not in expanded:
                connection.append(friend)
                expanded.append(friend)
                return path_to_friend(network, user_A, user_B, connection, expanded)
        connection.pop()                         # This only evaluates if the stack has reached a dead end, in which case it takes a step back
        return path_to_friend(network, user_A, user_B, connection, expanded)
    return None                                  # return None if no connection is found

# Make-Your-Own-Procedure (MYOP)
# -----------------------------------------------------------------------------
# Your MYOP should either perform some manipulation of your network data
# structure (like add_new_user) or it should perform some valuable analysis of
# your network (like path_to_friend). Don't forget to comment your MYOP. You
# may give this procedure any name you want.

# Replace this with your own procedure! You can also uncomment the lines below
# to see how your code behaves. Have fun!

# This will find the shortest path from user_A to user_B.
# My first programming class was Intro to Artificial Intelligence where I learned about DFS, BFS, stacks, and queues.
# This is especially different from path_to_friend because it holds a long list of lists of strings - path_to_friend only carries one list of strings

def breadth_first_search(network, user_A, user_B):
    connection = [user_A]
    queue = [connection]                                   # queue will be a list of lists
    while queue:
        connection = queue.pop(0)                          # Dequeuing (popping the first element instead of the last) a list
        last_node = connection[-1]                         # Analyzing that list for the goal state
        #print "Connection is " + str(connection)
        if last_node == user_B:
            return connection
        for friend in get_connections(network, last_node): # Adds lists to the queue
            if friend not in connection:
                agg = []
                agg = connection + [friend]
                queue.append(agg)
    return None

#network = create_data_structure(example_input_alternate)
#print "BFS from Freda to Jennie is " + str(breadth_first_search(network, "Freda", "Jennie"))

#for key in network:
#    for key2 in network:
#        if key != key2:
#            print "Path from " + str(key) + " to " + str(key2) + " is " + str(breadth_first_search(network, key, key2))
#            print

def suggest_friends(network, user):
    '''Returns a suggested friend based on shared likes and mutual friends.
    The connection is always user --> mutual friend --> suggested friend.
    It MIGHT OR MIGHT NOT be user --> mutual friend --> suggested friend --> mutual friend
    '''
    mutual, suggested, games = '', '', ''
    friends_of_friends = get_secondary_connections(network, user)
    for friend in friends_of_friends:
        if friend not in get_connections(network, user) and friend != user: # If user is not already friends with suggested
            for game in network[friend]['Likes']:
                if game in network[user]['Likes']:
                    games = game
            if len(games):
                suggested = friend
                mutual = breadth_first_search(network, user, suggested)[1] # This instance of BFS will always create a list of length 3
                return str(user) + "! You have a suggested friend, " + str(friend) + ". You both like to play " + str(games) + ". You have a mutual friend, " + str(mutual) + "."
    return "Try again later, " + str(user) + ". There are no suggested friends for you at this time"

#for user in network:
#    print suggest_friends(network, user)
#    print