Section #5: Grids & Strings

May 10th, 2020

---

Written by Brahm Capoor, Juliette Woodrow, Peter Maldonado, Kara Eng, Tori Qiu and Parth Sarin

Lists Review: Compatibility Calculations

You've just begun working for a company whose goal is to help users make new friends based on what they like to watch and read. Users input information about themselves, such as their Netflix history and favorite books. Your program will use this information to calculate a 'compatibility score' between two people, which serves as an estimate of how likely those people are to get along with one another. The compatibility score of two people is calculated as follows:

In this problem, we'll represent the books and movies liked by a particular user as separate lists. Given the lists representing, for example, the books liked by two different users, we find the number of elements present in both lists and divide it by the sum of the lengths of the two lists. To that end, your first job is to implement the following function:

which takes in two lists of strings and returns the number of elements the two lists have in common divided (using float division) by the total number of elements in both lists. For example, percent_in_common(['a', 'b', 'c', 'd'], ['c', 'd', 'm', 'n', 'x', 'z']) would return 0.2, because both lists contain 'c' and 'd' and there are 4 elements in the first list and 6 in the second.

Next, implement the following function:

which takes the names and preferences of two users and returns their compatibility score. The compatibility score between two users is the fraction of shows on Netflix in common + the fraction of books in common, using the calculation you implemented in the calc_score function. You may assume that there are no repeated elements in any of the lists.

Finally, implement the following function to predict for a particular user which user they will be the most compatible with:

which takes in a list of names of all other users and a list of compatibility scores between the chosen user and all other users, and returns a list where the first element is the name of the user who is most compatible and the second element is their compatibility score. name_list stores the name for each user at the same index as the compatibility_scores list stores the corresponding compatabiity score. For example, for user Barack if we have name_list = ['Michelle', 'Joe'] and compability_scores = [1, 0.8], this means the the compatibility score between Barack and Michelle is 1 and the compatibility score between Barack and Joe is only 0.8. In this example, new_friend(name_list, compatability_scores) would return ['Michelle', 1]. You may break ties between equally-compatible users arbitrarily.

Nested Lists & Grids

Enumerating a list

Implement the following function:

        
def enumerate(lst):
    """
    returns a nested list where each element is a list containing 
    the index of an element in the original list and the element itself. 
    These lists should appear in increasing order of indices.

    >>> enumerate(['cs106a', 'is', 'super', 'fun'])
    [[0, 'cs106a'], [1, 'is'], [2, 'super'], [3, 'fun']]
    >>> enumerate(['hello'])
    [[0, 'hello']]
    >>> enumerate([])
    []
    """
        
      

Matrix Math

Nested lists are often used to represent matrices, which are grids of numbers commonly used in linear algebra, computer graphics, and artificial intelligence. For example, the nested list [[1, 2], [3, 4], [5, 6]] represents this matrix:

Two common operations you might perform on matrices are to multiply a matrix's elements by a constant, or to add two matrices of equal dimensions together. For example, we'd multiply a matrix by a constant like so:

Note that each element of the matrix is multiplied by $3$. We add two matrices of equal dimension by adding their pairs of corresponding elements:

Your job is to implement the following functions, which each represent one of the above operations:

        
def matrix_constant_multiply(c, m):
    """
    Multiplies the 2-dimensional matrix m (represented as a list of lists) 
    by a constant factor c and returns the result. m should not be modified.

    >>> matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    >>> matrix_constant_multiply(2, m)
    [[2, 4, 6], [8, 10, 12], [14, 16, 18]]
    """

def matrix_add(m1, m2):
    """
    Adds matrices m1 and m2 together and returns the result. m1 and m2 are 
    guaranteed to be the same size. Neither m1 nor m2 should be modified.

    >>> m1 = [[1, 2], [3, 4], [5, 6]]
    >>> m2 = [[2, 3], [4, 5], [6, 7]]
    >>> matrix_add(m1, m2)
    [[3, 5], [7, 9], [11, 13]]
    """
        
      

Times Table

Implement the following function:

        
def make_times_table(m, n):
    """
    Makes and returns a list of m rows, each with n columns. 
    Each element is found by multiplying its row number by 
    its column number, where we start counting rows and columns 
    from 1. 

    >>> make_times_table(3, 4)
    [[1, 2, 3, 4], [2, 4, 6, 8], [3, 6, 9, 12]]
    """
        
      

Strings

String Slicing

How would you slice into this string to obtain the following results?

• 'ython'
• 'Py'
• 'Tim'
• 'Time'
• 'T'
• 'PythonTime'

Remember, strings in Python are 0-indexed. In addition, the slice s[1:8] is inclusive of the first index, and exculsive of the second (that is, it will get the string beginning at index 1 and up to, but not including, index 8, i.e. 'ythonTi').

String Construction

Implement the following functions:

1. only_one_first_char(s): removes all occurrences of the first character of s except the first character itself. For example, only_one_first_char('recurrence') returns 'recuence'. You may assume s has at least one character.
2. make_gerund(s): which adds 'ing' to the end of the given string s and returns this new word. If s already ends with 'ing', add an 'ly' to the end of s instead. You may assume that s is at least 3 characters long.
3. put_in_middle(outer, inner): which returns a string where inner has been inserted into the middle of the string outer. To find the middle of a string, take the length of the string and divide it by 2 using integer division. The first half of the string should be all characters leading up to, but not including, the character at this index. The second half should start with the character at this index and include the rest of the characters in the string.

Word Puzzles

In these problems, we'll investigate properties of words in the English language. In each problem, we'll define a special rule and write a function to determine whether a word obeys that rule or violates that rule. For this problem, you can assume that word will be a string containing uppercase alphabetic characters only.

Tridromes

We say that a word is a tridrome if the first three letters of the word are the same as the last three letters of the word (and appear in the same order). All tridromes must be at least 6 letters long. For example, ENTERTAINMENT, MURMUR, and UNDERGROUND are tridromes. Write a function is_tridrome(word) that returns True if a word is a tridrome and False otherwise.

Peaceful Words

We say that a word is peaceful if its letters are in alphabetical order. For example, ABORT, ALMOST, CHIPS, DIRTY, FIRST, and HOST are all peaceful words. Write a function is_peaceful(word) that returns True if a word is peaceful and False otherwise. You may assume you have access to a constant ALPHABET which is a string of the uppercase letters in the alphabet, in sequential order, i.e., ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.

Stacatto Words

We say that a word is a stacatto word if all of the letters in even positions are vowels (i.e., the second, fourth, sixth, etc. letters are vowels). For this problem, the vowels are A, E, I, O, U, and Y. For example, AUTOMATIC, CAFETERIA, HESITATE, LEGITIMATE, and POPULATE are stacatto words. Write a function is_stacatto(word) that returns True if a word is a stacatto word and False otherwise.

No More Counting Dollars, We'll Be Counting Words

Suppose you're given a file that contains all the words in the English language, where each one is on a different line. Write the following functions, using the functions you wrote in the previous problem:

1. count_tridromes(filename) which returns the number of English words that are tridromes.
2. count_peaceful(filename) which returns the number of English words that are peaceful.
3. count_stacatto(filename) which returns the number of English words that are stacatto words.

A few things to note:

• You're given the name of a file that contains English words, so you have to open the file and process the words.
• The words are not all uppercase. Convert them to uppercase before you call the function that you wrote in the last problem.
• Lines will end with a newline character, \n. You can remove this character from a string using the strip function, i.e. s.strip().

You can actually run this program! We've provided a file of all the words in the English language called words.txt in the section project.