CSc 120: Friends

Restrictions

1. For the long problems, your code should follow the style guidelines for the class.
2. You may not use concepts and/or short-hand syntax not yet covered in class. The restrictions include the following:
   • list (or dictionary) comprehensions, e.g., [n * 2 for i in range(10)]
   • with open (explicitly open and close the file instead)
   • the ternary operator (use an if instead)
   • nested functions (using def within a function to define another function)
   • recursion
   • exceptions and asssertions
   • type annotations
   • lambda expressions
   • generators and user defined iterators
   • default arguments
   • importing libraries, unless a library is explicity allow in the specification
   • New restriction: Using try/except to avoid having to check for None when iterating through a linked list is banned.

Background

Expected Behavior

from linked_list import *

Your program should behave as follows.

1. Read in the name of an input file using input('Input file: '). Read in the contents of this file into your program.

2. The data in the file specifies friendship relationships between pairs of names. Organize the data into the linked list structure specified under Data structures below.

   NOTE: Friendships are two-way relations (in mathematics, such relations are called symmetric). This means that for each input line of the form

   X   Y

   you should set up your data structures to indicate two things:
   • X is a friend of Y; and
   • Y is a friend of X.

3. Read in two names using the function calls below. You can use other variable names or your choice to store the values read in. Strip off whitespace as necessary.

   name1 = input('Name 1: ')
   name2 = input('Name 2: ')

4. If there are friends in common, first print the following line:

       Friends in common: 

   Then print out the name of each mutual friend of name1 and name2, i.e., any name3 such that name3 is a friend of both name1 and name2 (see Output format below). Names must be printed in alphabetical order.

   If there are no friends in common, no further output is produced. (That is, if there are no friends in common, the program only produces the input prompts.)

Input format

William Ethan
Rebecca Lindsey
William Lindsey
William Patrick

You should not make assumptions about the amount of whitespace around and between names.

Output format

    Friends in common: 

If there are no friends in common, no further output is produced. (That is, if there are no friends in common, the program only produces the input prompts and does NOT print Friends in common:. )

Data Structures

• a name (a string);
• the friends for that name (a linked list); and
• a reference to the next node.

For example, for the file in04.txt mentioned above (under Input format), the data structure should be as shown below:

(click on the image for a larger picture)

Programming Requirements

Your program must use linked lists to implement all of the following tasks:

1. the names read in from the input file (which go into the "main" linked list)
2. for each such name, the list of that person's friends
3. the friends in common between two people
4. sorting the common friends alphabetically for printing

Your code should be organized among your files as follows:

• linked_list.py: Code to implement the linked list class.
• friends.py: Code that uses methods from the linked list class to implement the application required by this assignment.

The methods defined in linked_list.py can be accessed in friends.py using an import statement in the latter file.

Errors

One of the names name1 or name2 cannot be found in the list of names. (Read in both names first. Check for name1 first and name2 second. At most one name will be unkown.)

Program behavior: Give the following error message and stop processing further.

Error message: "ERROR: Unknown person " + name

Examples