Advertisement
vikramk3

Untitled

Jul 24th, 2014
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 15.59 KB | None | 0 0
  1. # --------------------------- #
  2. # Intro to CS Final Project   #
  3. # Gaming Social Network       #
  4. # --------------------------- #
  5. #
  6. # For students who have subscribed to the course,
  7. # please read the submission instructions in the Instructor Notes below.
  8. # -----------------------------------------------------------------------------
  9.  
  10. # Background
  11. # ==========
  12. # You and your friend have decided to start a company that hosts a gaming
  13. # social network site. Your friend will handle the website creation (they know
  14. # what they are doing, having taken our web development class). However, it is
  15. # up to you to create a data structure that manages the game-network information
  16. # and to define several procedures that operate on the network.
  17. #
  18. # In a website, the data is stored in a database. In our case, however, all the
  19. # information comes in a big string of text. Each pair of sentences in the text
  20. # is formatted as follows:
  21. #
  22. # <user> is connected to <user1>, ..., <userM>.<user> likes to play <game1>, ..., <gameN>.
  23. #
  24. # For example:
  25. #
  26. # John is connected to Bryant, Debra, Walter.John likes to play The Movie: The Game, The Legend of Corgi, Dinosaur Diner.
  27. #
  28. # Note that each sentence will be separated from the next by only a period. There will
  29. # not be whitespace or new lines between sentences.
  30. #
  31. # Your friend records the information in that string based on user activity on
  32. # the website and gives it to you to manage. You can think of every pair of
  33. # sentences as defining a user's profile.
  34. #
  35. # Consider the data structures that we have used in class - lists, dictionaries,
  36. # and combinations of the two (e.g. lists of dictionaries). Pick one that
  37. # will allow you to manage the data above and implement the procedures below.
  38. #
  39. # You may assume that <user> is a unique identifier for a user. For example, there
  40. # can be at most one 'John' in the network. Furthermore, connections are not
  41. # symmetric - if 'Bob' is connected to 'Alice', it does not mean that 'Alice' is
  42. # connected to 'Bob'.
  43. #
  44. # Project Description
  45. # ====================
  46. # Your task is to complete the procedures according to the specifications below
  47. # as well as to implement a Make-Your-Own procedure (MYOP). You are encouraged
  48. # to define any additional helper procedures that can assist you in accomplishing
  49. # a task. You are encouraged to test your code by using print statements and the
  50. # Test Run button.
  51. # -----------------------------------------------------------------------------
  52.  
  53. # Example string input. Use it to test your code.
  54. example_input="John is connected to Bryant, Debra, Walter.\
  55. John likes to play The Movie: The Game, The Legend of Corgi, Dinosaur Diner.\
  56. Bryant is connected to Olive, Ollie, Freda, Mercedes.\
  57. Bryant likes to play City Comptroller: The Fiscal Dilemma, Super Mushroom Man.\
  58. Mercedes is connected to Walter, Robin, Bryant.\
  59. Mercedes likes to play The Legend of Corgi, Pirates in Java Island, Seahorse Adventures.\
  60. Olive is connected to John, Ollie.\
  61. Olive likes to play The Legend of Corgi, Starfleet Commander.\
  62. Debra is connected to Walter, Levi, Jennie, Robin.\
  63. Debra likes to play Seven Schemers, Pirates in Java Island, Dwarves and Swords.\
  64. Walter is connected to John, Levi, Bryant.\
  65. Walter likes to play Seahorse Adventures, Ninja Hamsters, Super Mushroom Man.\
  66. Levi is connected to Ollie, John, Walter.\
  67. Levi likes to play The Legend of Corgi, Seven Schemers, City Comptroller: The Fiscal Dilemma.\
  68. Ollie is connected to Mercedes, Freda, Bryant.\
  69. Ollie likes to play Call of Arms, Dwarves and Swords, The Movie: The Game.\
  70. Jennie is connected to Levi, John, Freda, Robin.\
  71. Jennie likes to play Super Mushroom Man, Dinosaur Diner, Call of Arms.\
  72. Robin is connected to Ollie.\
  73. Robin likes to play Call of Arms, Dwarves and Swords.\
  74. Freda is connected to Olive, John, Debra.\
  75. Freda likes to play Starfleet Commander, Ninja Hamsters, Seahorse Adventures."
  76.  
  77. # -----------------------------------------------------------------------------
  78. # create_data_structure(string_input):
  79. #   Parses a block of text (such as the one above) and stores relevant
  80. #   information into a data structure. You are free to choose and design any
  81. #   data structure you would like to use to manage the information.
  82. #
  83. # Arguments:
  84. #   string_input: block of text containing the network information
  85. #
  86. #   You may assume that for all the test cases we will use, you will be given the
  87. #   connections and games liked for all users listed on the right-hand side of an
  88. #   'is connected to' statement. For example, we will not use the string
  89. #   "A is connected to B.A likes to play X, Y, Z.C is connected to A.C likes to play X."
  90. #   as a test case for create_data_structure because the string does not
  91. #   list B's connections or liked games.
  92. #  
  93. #   The procedure should be able to handle an empty string (the string '') as input, in
  94. #   which case it should return a network with no users.
  95. #
  96. # Return:
  97. #   The newly created network data structure
  98.  
  99. def create_data_structure(text_input):
  100.     if text_input=='':
  101.         network={}
  102.         return network
  103.     sentences=text_input.split('.')
  104.     sentences.pop() # the above split function creates a blank line. Don't know why?
  105.     network={}
  106.     for sentence in sentences:
  107.         if 'is connected to' in sentence:
  108.             partial_sentence=sentence.split(' is connected to ') #split and eliminate 'is connected to'
  109.             name=partial_sentence.pop(0) #name of user
  110.             contacts=partial_sentence[0].split(', ') #split to separate contacts
  111.             network[name]={} #create dictionary within a dictionary
  112.             network[name]['connected']=[]
  113.             for contact in contacts:
  114.                 network[name]['connected'].append(contact) #add connections
  115.         else:
  116.             partial_sentence=sentence.split(' likes to play ') #split and eliminate 'likes to play'
  117.             name=partial_sentence.pop(0)
  118.             games=partial_sentence[0].split(', ') #split to separate games
  119.             network[name]['play']=[]
  120.             for game in games:
  121.                 network[name]['play'].append(game) #add games
  122.     return network
  123. # ----------------------------------------------------------------------------- #
  124. # Note that the first argument to all procedures below is 'network' This is the #
  125. # data structure that you created with your create_data_structure procedure,    #
  126. # though it may be modified as you add new users or new connections. Each       #
  127. # procedure below will then modify or extract information from 'network'        #
  128. # ----------------------------------------------------------------------------- #
  129.  
  130. # -----------------------------------------------------------------------------
  131. # get_connections(network, user):
  132. #   Returns a list of all the connections that user has
  133. #
  134. # Arguments:
  135. #   network: the gamer network data structure
  136. #   user:    a string containing the name of the user
  137. #
  138. # Return:
  139. #   A list of all connections the user has.
  140. #   - If the user has no connections, return an empty list.
  141. #   - If the user is not in network, return None.
  142.  
  143. def get_connections(network, user):
  144.     if user not in network.keys():
  145.         return None
  146.     else:
  147.         return network[user]['connected']
  148.    
  149. #   return []
  150.  
  151. # -----------------------------------------------------------------------------
  152. # get_games_liked(network, user):
  153. #   Returns a list of all the games a user likes
  154. #
  155. # Arguments:
  156. #   network: the gamer network data structure
  157. #   user:    a string containing the name of the user
  158. #
  159. # Return:
  160. #   A list of all games the user likes.
  161. #   - If the user likes no games, return an empty list.
  162. #   - If the user is not in network, return None.
  163.  
  164. def get_games_liked(network,user):
  165.     if user not in network.keys():
  166.         return None
  167.     else:
  168.         return network[user]['play']    
  169.    
  170. #    return []
  171.  
  172. # -----------------------------------------------------------------------------
  173. # add_connection(network, user_A, user_B):
  174. #   Adds a connection from user_A to user_B. Make sure to check that both users
  175. #   exist in network.
  176. #
  177. # Arguments:
  178. #   network: the gamer network data structure
  179. #   user_A:  a string with the name of the user the connection is from
  180. #   user_B:  a string with the name of the user the connection is to
  181. #
  182. # Return:
  183. #   The updated network with the new connection added.
  184. #   - If a connection already exists from user_A to user_B, return network unchanged.
  185. #   - If user_A or user_B is not in network, return False.
  186.  
  187. def add_connection(network, user_A, user_B):
  188.     if (user_A or user_B) not in network.keys():
  189.         return False
  190.     elif user_B in network[user_A]['connected']:
  191.         return network
  192.     else:
  193.         network[user_A]['connected'].append(user_B)      
  194.     return network
  195.  
  196. # -----------------------------------------------------------------------------
  197. # add_new_user(network, user, games):
  198. #   Creates a new user profile and adds that user to the network, along with
  199. #   any game preferences specified in games. Assume that the user has no
  200. #   connections to begin with.
  201. #
  202. # Arguments:
  203. #   network: the gamer network data structure
  204. #   user:    a string containing the name of the user to be added to the network
  205. #   games:   a list of strings containing the user's favorite games, e.g.:
  206. #            ['Ninja Hamsters', 'Super Mushroom Man', 'Dinosaur Diner']
  207. #
  208. # Return:
  209. #   The updated network with the new user and game preferences added. The new user
  210. #   should have no connections.
  211. #   - If the user already exists in network, return network *UNCHANGED* (do not change
  212. #     the user's game preferences)
  213.  
  214. def add_new_user(network, user, games):
  215.     if user in network.keys():
  216.         return network
  217.     else:
  218.         network[user]={}
  219.         network[user]['connected']=[]
  220.         network[user]['play']=games
  221.     return network
  222.        
  223. # -----------------------------------------------------------------------------
  224. # get_secondary_connections(network, user):
  225. #   Finds all the secondary connections (i.e. connections of connections) of a
  226. #   given user.
  227. #
  228. # Arguments:
  229. #   network: the gamer network data structure
  230. #   user:    a string containing the name of the user
  231. #
  232. # Return:
  233. #   A list containing the secondary connections (connections of connections).
  234. #   - If the user is not in the network, return None.
  235. #   - If a user has no primary connections to begin with, return an empty list.
  236. #
  237. # NOTE:
  238. #   It is OK if a user's list of secondary connections includes the user
  239. #   himself/herself. It is also OK if the list contains a user's primary
  240. #   connection that is a secondary connection as well.
  241.  
  242. def get_secondary_connections(network, user):
  243.     second_connection=[]
  244.     if user not in network.keys():
  245.         return None
  246.     elif network[user]['connected']==[]:
  247.         return []
  248.     else:
  249.         for each_connection in network[user]['connected']:
  250.             for each_second_connection in network[each_connection]['connected']:
  251.                 if each_second_connection not in second_connection:
  252.                     second_connection.append(each_second_connection)
  253.         return second_connection
  254.    
  255. #   return []
  256.  
  257. # -----------------------------------------------------------------------------    
  258. # connections_in_common(network, user_A, user_B):
  259. #   Finds the number of people that user_A and user_B have in common.
  260. #  
  261. # Arguments:
  262. #   network: the gamer network data structure
  263. #   user_A:  a string containing the name of user_A
  264. #   user_B:  a string containing the name of user_B
  265. #
  266. # Return:
  267. #   The number of connections in common (as an integer).
  268. #   - If user_A or user_B is not in network, return False.
  269.  
  270. def connections_in_common(network, user_A, user_B):
  271.     if (user_A or user_B) not in network.keys():
  272.         return False
  273.     else:
  274.         count=0
  275.         for contact in network[user_A]['connected']:
  276.             if contact in network[user_B]['connected']:
  277.                 count = count + 1
  278.         return count
  279.    
  280. #    return 0
  281.  
  282. # -----------------------------------------------------------------------------
  283. # path_to_friend(network, user_A, user_B):
  284. #   Finds a connections path from user_A to user_B. It has to be an existing
  285. #   path but it DOES NOT have to be the shortest path.
  286. #  
  287. # Arguments:
  288. #   network: The network you created with create_data_structure.
  289. #   user_A:  String holding the starting username ("Abe")
  290. #   user_B:  String holding the ending username ("Zed")
  291. #
  292. # Return:
  293. #   A list showing the path from user_A to user_B.
  294. #   - If such a path does not exist, return None.
  295. #   - If user_A or user_B is not in network, return None.
  296. #
  297. # Sample output:
  298. #   >>> print path_to_friend(network, "Abe", "Zed")
  299. #   >>> ['Abe', 'Gel', 'Sam', 'Zed']
  300. #   This implies that Abe is connected with Gel, who is connected with Sam,
  301. #   who is connected with Zed.
  302. #
  303. # NOTE:
  304. #   You must solve this problem using recursion!
  305. #
  306. # Hints:
  307. # - Be careful how you handle connection loops, for example, A is connected to B.
  308. #   B is connected to C. C is connected to B. Make sure your code terminates in
  309. #   that case.
  310. # - If you are comfortable with default parameters, you might consider using one
  311. #   in this procedure to keep track of nodes already visited in your search. You
  312. #   may safely add default parameters since all calls used in the grading script
  313. #   will only include the arguments network, user_A, and user_B.
  314.  
  315. def path_to_friend(network, user_A, user_B,path=None):
  316.     if not path: path=[]
  317.     if (user_A or user_B) not in network.keys() :
  318.         return None
  319.     path=path + [user_A]
  320.     connections = get_connections(network,user_A)
  321.     if connections==[]:
  322.         return None
  323.     if user_B in connections:
  324.         path = path + [user_B]
  325.         return path
  326.     for contact in connections:
  327.         if contact not in path:
  328.             if path_to_friend(network,contact,user_B,path):
  329.                 return path_to_friend(network,contact,user_B,path)
  330.     return None
  331.  
  332.     # your RECURSIVE solution here!
  333. #   return None
  334.  
  335. # Make-Your-Own-Procedure (MYOP)
  336. # -----------------------------------------------------------------------------
  337. # Your MYOP should either perform some manipulation of your network data
  338. # structure (like add_new_user) or it should perform some valuable analysis of
  339. # your network (like path_to_friend). Don't forget to comment your MYOP. You
  340. # may give this procedure any name you want.
  341.  
  342. def recommend_new_contact(network,user): #MYOP Recommend new contact based on playing a common game
  343.     if user not in network.keys():
  344.         return 'User not in Network'
  345.     for game in get_games_liked(network,user):
  346.         for name in network.keys():
  347.             if (game in get_games_liked(network,name)) and (name!=user) and (name not in get_connections(network,user)):
  348.                 return'We recommend you connect with ' + name +'. '+ name +' also plays ' +game+'.'
  349.     return 'No recommendation for a new contact at present'
  350.  
  351. # Replace this with your own procedure! You can also uncomment the lines below
  352. # to see how your code behaves. Have fun!
  353.  
  354. network = create_data_structure(example_input)
  355. print network
  356.  
  357. print path_to_friend(network, "John", "Ollie")
  358. print get_connections(network, "Debra")
  359. print add_new_user(network, "Debra", [])
  360. print add_new_user(network, "Nick", ["Seven Schemers", "The Movie: The Game"]) # True
  361. print get_connections(network, "Mercedes")
  362. print get_games_liked(network, "John")
  363. print add_connection(network, "John", "Freda")
  364. print get_secondary_connections(network, "Mercedes")
  365. print connections_in_common(network, "Mercedes", "John")
  366. print recommend_new_contact(network,'Debra')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement