October 11th, 2020
Written by Juliette Woodrow, Brahm Capoor, Andrew Tierno, Peter Maldonado, Kara Eng, Tori Qiu and Parth Sarin
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.
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([])
[]
"""
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]]
"""
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]]
"""
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)
# 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
random.random()
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:
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
news_ticker.py
.
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:
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:
Calling
canvas.create_text(x, y, anchor='w', fill='black',
text='Hello!')
will create a black text label on the screen whose left side is
centered at (x, y)
and which says Hello!
.
Additionally, you can specify the font of the label by providing the
parameter font=('fontname', fontsize)
. For example, we
made the label in the example have a font of Calibri and fontsize of
24 by specifying font=('Calibri', 24)
.
create_text
returns the Object ID of the label, which
can then be used to move the canvas or get its coordinates.
We've also provided two constants, CANVAS_WIDTH
and
CANVAS_HEIGHT
that represent the dimensions of your
canvas. The label should be centered vertically and should start off
beyond the right edge of the canvas.
Recall that the basic animation loop looks like this:
while True:
# update location of objects, often using canvas.move
canvas.update()
time.sleep(DELAY)
canvas.move()
takes in as parameters the ID of the
object to move (remember that
canvas.create_text
returns this label), as well as two
integers representing how far you want the object to move in the x
and y directions. We've provided two constants DX
and
DY
for you to use, although these just represent
magnitudes - it's up to you to figure out what to do with
DX
to make the label scroll to the left.
We've also provided a constant DELAY
for you to use in
the call to time.sleep
. You're welcome to change this
constant's value as you see fit.
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.
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.
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:
get_messages
function to get a
list of messages from the user.