Section #4: Lists, Grids, & Animations

October 11th, 2020

Written by Juliette Woodrow, Brahm Capoor, Andrew Tierno, 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:

compatibility = % (books liked in common) + % (shows on Netflix liked in common)

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:

def in_common(l1, l2)

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:

def calc_score(netflix_history1, netflix_history2, fav_books1, fav_books2)

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:

def new_friend(name_list, compatibility_scores)

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:

$\begin{bmatrix}1 & 2\\3 & 4\\5 & 6\end{bmatrix}$

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:

$3 \times \begin{bmatrix}1 & 2\\3 & 4\\5 & 6\end{bmatrix} = \begin{bmatrix}3 & 6\\9 & 12\\15 & 18\end{bmatrix}$

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:

$\begin{bmatrix}1 & 2\\3 & 4\\5 & 6\end{bmatrix} + \begin{bmatrix}2 & 3\\4 & 5\\6 & 7\end{bmatrix} = \begin{bmatrix}3 & 5\\7 & 9\\11 & 13\end{bmatrix}$

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]]

Graphics and Animation

Random Circles

Write a program that draws a random number of circles of random sizes at random positions on the canvas. Be careful to make sure that none of the drawn circles are cut off by the edge of your canvas. You are provided with the constants WIDTH and HEIGHT (the canvas width and height, respectively), RADIUS_MAX and RADIUS_MIN (the maximum/minimum radius that each random circle may have), and N_CIRCLES_MAX (the maximum number of circles that may be generated in one run of our program. Note that each run should generate between 1 and N_CIRCLES_MAX circles inclusive on both ends). Specifically, your job is to implement the following function:

            def make_all_circles(canvas)

into which is passed a canvas and whose job is to do the random drawing of the circles. You might find the following functions helpful, some of which are found in the random module:
                # draws an oval on a canvas, the top left corner of whose bounding box
# is at (x0, y0) and the bottom right corner of whose bounding box is
# at (x1, y1)
canvas.create_oval(x0, y0, x1, y1)

# returns a random integer between lower and upper, inclusive of both
# bounds
random.randint(lower, upper)

# returns a random number between 0 and 1

Building a News Ticker

News channels often operate what's called a News Ticker: a banner on the bottom of the screen across which breaking news scrolls whilst the anchor is speaking.

In this problem, you'll be implementing a program that simulates a News Ticker, like so:

A scrolling news ticker with the messages 'CS 106A Students are Crushing it', 'So long and thanks for all the fish', and 'Avengers Assemble'

The program will first read in a sequence of 'headlines', or messages from the user and will then make a new window and scroll each of the messages across the bottom of the window in turn.

This is not a long program, but it is dense: it puts together a lot of the concepts you've been learning about in the last few lectures, so we encourage you to approach it using the milestones we've suggested below. All the code for this problem should be written in

Milestone 1: Animating a single message

To get started, write a program that animates a single label across the screen, like so

We'll start by writing a program that scrolls a single message across the screen, like so:

A first version news ticker with the text 'CS 106A students are crushing it' scrolling by once

Unlike the animation above suggests, the scroll doesn't need to repeat in this milestone. The text just needs to scroll by once.

Here's a few tools that you might find helpful as you write this:

Milestone 2: Repeating the message

Having a message scroll across the window once is progress, but we're not quite there yet. Currently, once our label has scrolled past the left edge of the screen, it just keeps going, leaving us starting at an unspiring blank window.

In this milestone, edit your animation loop to reset your label once it moves past the left edge of the screen. We've provided you with the get_right_x helper function, which takes in the canvas and label ID as parameters and returns the rightmost x-coordinate of the label, which you might find handy.

By the end of this milestone, you should have a program that scrolls the message of your choosing across the window repeatedly.

Milestone 3: Getting Messages from the User

Now, we'll start working on getting messages from the user, as opposed to hardcoding them into the program. To get started, implement the following function:

def get_messages():
    Reads a series of messages from the user, ending when they
    input a blank message. Returns a list of all the messages 
    the user typed.

Here's the run of this function that produced the messages in the sample run above (user input is italicized):

Type a message here or press enter to finish: CS 106A Students are crushing it
Type a message here or press enter to finish: So long and thanks for all the fish
Type a message here or press enter to finish: Avengers Assemble
Type a message here or press enter to finish: User presses enter immediately

Although you can't see it in the sample output, the function returned the list ["CS 106A Students are crushing it", "So long and thanks for all the fish", "Avengers Assemble"] to the function that called it once the user entered an empty message.

Milestone 4: Making messages appear one after the other

All the pieces are in place now: we have a list of messages that we want to display, and we've developed infrastructure for a label with fixed text to scroll across the screen. Now, we just need to put these jigsaw pieces together to have the messages scroll across the screen in turn.

There are a few steps we need to take to achieve this: