Section 9

Variables & Control Flow

• Converting numbers to binary

  Write a function convert_to_binary that takes as a parameter a positive integer n and returns a string containing the binary representation of n. To convert a number to binary, simply intger-divide the number by 2 until it is equal to 0. The binary representation is simply the remainder of each division operation, written in reverse order. For example, below is the procedure to convert the number 43 to binary:

  1. Divide 43 by 2 to get 21, remainder 1.
  2. Divide 21 by 2 to get 10, remainder 1.
  3. Divide 10 by 2 to get 5, remainder 0.
  4. Divide 5 by 2 to get 2, remainder 1.
  5. Divide 2 by 2 to get 1, remainder 0.
  6. Divide 1 by 2 to get 0, remainder 1.
  
  

  Now, we write out the remainders in reverse to find that the binary representation is "101011".

• Fibonacci Numbers

  Implement a function called find_fibonacci_number, which takes as a parameter an integer n and returns the n-th fibonacci number. The fibonacci numbers are a sequence of numbers defined by the following rule: the first two fibonacci numbers are both 1, and every subsequent number is the sum of the two previous ones. The first few numbers in the sequence are 1, 1, 2, 3, 5, 8, 13 and so on. As a result, calling find_fibonacci_number(2) should return 1, and calling find_fibonacci_number(6) should return 8.

• Trace #1

  What is the output of the following program?

                  
  def foo(a, b, c):
      a = b 
      b = c + 1 
      c = a // 2
      return b * c
  
  def bar(n, m):
      n *= 2
      m = n * m 
  
  def main():
    x = 2
    y = 4
    z = 3
    bar(x, 2)
    print(foo(z, x, y))
  
  if __name__ == "__main__":
      main()
                  
                

• Trace #2

  What is the output of the following program?

                  
  def swap(lst):
      lst[0] = lst[1]
      lst[1] = lst[0]
  
  def make():
      lst = []
      for i in range(6):
          lst.append(i)
      for i in range(3):
          lst.pop()
      return lst 
  
  def main():
      l = make()
      swap(l)
      print(l)
  
  if __name__ == "__main__":
      main()
                  
                

Images: Blur

This problem comes from a past CS 106A assignment. As a result, it's a little more involved than what we would reasonably put on an exam. That said, we're including it in the handout because it's a great overview of the different kinds of things you'd need to do in image problems.

In this problem you are going to write a function that simulates a filter on an image. This filter is going to blur the given image. To do this, implement the following method:

Which takes as parameter a SimpleImage and returns a blurred version of that image. One way to do this is to create a new image whose pixel values are averaged with the values of their immediate neighbors from the source image; this simulates a "blurring" effect between pixels.

The general idea is that for a pixel located at row r and column c in the source image, you will set its red, green, and blue components to be the average (rounded down to the nearest integer) of the nine red, green, and blue components in the pixels at locations (r-1, c-1) through (r+1, c+1).

For example, in the diagram below, the pixel (row 1, column 2) should be modified to store the average of the nine pixels (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), and (2, 3). These are the eight neighbors of (1, 2) as well as (1, 2) itself. So the red part of (1, 2) would be changed from 32 to (84+74+16+66+32+95+28+47+31)/9 = 52. The green component would be changed from 67 to (22+38+17+53+67+65+49+21+41)/9 = 41. The blue component would be changed from 12 to (99+69+18+88+12+35+31+94+51)/9 = 55. Therefore the overall pixel value at (1, 2) in the result image would be (52, 41, 55).

A special case is the set of pixels along the edges of the image. When blurring those pixels, they do not have eight neighbors like other pixels do, so the average includes fewer data points. For example, in the diagram above, the pixel at (0, 0) has no neighbors above or left of it, so it should become the average of the four pixels (0, 0), (0, 1), (1, 0), and (1, 1). So the red component of (0, 0) would become (14+84+21+66)/4 = 46, and so on. The pixel at (3, 3) has no neighbors below it, so it should become the average of the six pixels (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), and (3, 4). The red component of (3, 3) would become (47+31+246+15+60+188)/6 = 97, and so on. Take care that your algorithm does not crash by trying to access outside the bounds of the image.

A common bug in this algorithm is to try to modify the image in-place. You should not do this; you should create a new second pixel image to store the result image's pixels. The reason is because you don't want modifications made to one pixel to impact another pixel in the same pass over the image. In our previous example, we already stated that pixel (1, 2) should be changed from (32, 67, 12) to (52, 41, 55). But if you store (52, 41, 55) into this pixel and then use that value for further calculations on pixels in the same pass over the array, their averages will be incorrect. For example, when computing the average for pixel (1, 3), the pixel (1, 2) is one of its neighbors. But you should use that pixel's original value of (32, 67, 12) when computing that average.

Drawing

• Implement the function draw_diagonals(canvas, width, height, n) that takes as a parameter a TKinter canvas, its width, its height and an integer n and draws n equally-spaced diagonal lines across the canvas, if called with width=400, height=600 and n=7: Note that only 6 lines are actually visible, since the first line is just a point in the top left corner.
• Write a function draw_grid(canvas, width, height, n) that divides a canvas into a grid drawn using n x n horizontal and vertical lines, like so:

Strings

• Password Checker

  Implement the is_valid_password function, which takes as a parameter a string password representing a new user's chosen password and returns True if this is a valid password and False otherwise. A valid password must be at least 7 characters, contain at least 1 uppercase letter, lower case letter, and number.

• Binary Checker

  Binary is a numeric system that only uses two digits: 0s and 1s. Computers operate in binary which means they use only patterns of 0s and 1s to perform calculations, store information, and run all the cool programs that you write. Each pattern of 0s and 1s is a binary code which signals a series of electrical pulses that tell the computer what operation to run. A valid binary pattern must be a multiple of 8 digits and contain only 0s and 1s. Implement the is_valid_binary function, which takes as a parameter a string test_string and returns True if that string is a valid binary pattern and False otherwise.

Grids

• Muddying the Waters

  Recall the sand assignment, in which you were given a grid in which an 's' in a cell represents a grain of sand. In that problem, the sand fell down if and only if there was an empty space below in it.

  In this problem, we introduce an additional kind of cell representing water, indicated by a 'w' in the grid. Water also follows the same gravitational rules as sand, with one additional feature: when a sand particle is directly above a drop of water, it falls down and becomes mud, represented by a 'm' in the grid. Mud remains stationary, much like rock in the original assignment.

  Your job is to implement a do_sand_move function, which takes as parameters a grid, and coordinates x1, y1, x2, and y2. You may assume that the element at (x1, y1) is in bounds sand, but the element below it is either water, rock, sand or empty. For example, given this grid:

                  [['r', 's', None],
                  [None, 'w', None]]
                

  calling do_sand_move(grid, 0, 1, 1, 1) would return this grid:

                  [['r', None, None],
                  [None, 'm', None]]
                

• Fogging the air

  Now, assume that we've introduced a new kind of element to our simulation: fog, represented by an 'f' in the grid. Fog also obeys gravity, but spreads out as it falls. Specifically, a particle of fog spreads to all 3 of its lower neighbours as it falls, regardless of what was previously in those neighbours. For example, this grid:

                  [['r', 'f', None],
                   [None, 'r', 's']]
                

  will turn into this grid after the fog particle descends:

                  [['r', None, None],
                   ['f', 'f', 'f']]
                

  Implement the do_fog_move(grid, x, y) function, which takes in a grid and a coordinate guaranteed to contain a fog particle, and performs the gravitational action.

Lists: Camel Casing

Lower camel case is a way to write phrases--used commonly for variable naming in programming--such that each word other than the first in the phrase starts with a capital letter and the words are not separated by spaces. The first word in the phrase is not capitalized in lower camel case. Some examples of words in lower camel case are iPhone, lowerCamelCase and eBay

Specifically, implement the following function:

which takes as parameter a list of phrases where a phrase is a string of two or more words separated by spaces, and returns a list of strings where each string is the camel case version of the corresponding phrase. You may assume that each string won't have any punctuation or non-space whitespace. For example, make_camel_case(['camels are awesome', 'live love camel case']) would return the list ['camelsAreAwesome', 'liveLoveCamelCase'].

Parsing

• Words that start with

  Write a function words_that_start_with(s, ch) that takes in a string s and a character ch and returns a list of all the words in the string that case-insensitively begin with that character. For example, calling words_that_start_with("My name is mildred mortensen.", "m") would return ["My", "mildred", "mortensen."]. Here, words are defined as tokens in a string that are separated by spaces. Solve this problem using a "while True" parsing structure

• Finding questions

  Write a function find_questions(s) that takes in a string s and returns a list of all the questions in the string. A question is defined as a sentence that ends with a question mark, and you can assume that all sentences end with a character that is contained in some list PUNCTUATION. For example, calling find_questions on the string "What's my name? Oh, it's Brahm. Wait, am I sure?" would return ["What's my name?", "Wait, am I sure?"].

Files and File Reading

• Word Counter

  Implement a function called word_count, which takes in a string filename and prints the number of characters, words and lines in the file. A word is defined as any token in the file separated by spaces.

• Removing Repeated Lines

  Write a function called remove_repeated_lines which takes in a string filename and returns a list of all of the unique lines in the file, in the order that they first appear. For example, given this file poem.txt:

  Roses are red,
  Violets are Blue,
  The first line of this poem was,
  Roses are red,
  And the second was that Violets are blue
                

  Calling remove_repeated_lines('poem.txt') would return the list ["Roses are red,", "Violets are Blue,", "The first line of this poem was,", "And the second was that Violets are blue"]. Be sure to account for newline characters in your solution (two lines are considered equal if they are the same, regardless of whether they are followed by a newline).

• Reading spreadsheets

  Spreadsheets are commonly represented as .csv files, in which each row of the spreadsheet is a separate line of the file, and the elements of each row are separated by commas, like so in people.csv:

  Name, favorite number, favorite color
  Brahm, 42, blue 
  Nick, 3, green
  Juliette, 100, orange
                

  Write a function read_csv_file which takes in a csv filename string and returns a list of lists, where each inner list is a list of the elements of each row of the file. For example, calling read_csv_file("people.csv") would return [["Name", "favorite number", "favorite color"], ["Brahm", "42", "blue"], ["Nick", "3", "green"], ["Juliette", "100", "orange"]]

Dictionaries

• Recipes

  You are putting together an app that helps people find recipes they can make with the ingredients that they already have on hand. Implement the following function:

  def find_recipes(curr_ingredients, recipe_book)
  
  

  which takes as parameters curr_ingredients, a list of ingredients that the user already has on hand and recipe_book, a dictionary representing a recipe book in which the keys are recipe names and values are the list of ingredients required to make that recipe. The function should return a list of recipe names that the user can make.

• Building a glossary

  Implement the following function:

  def make_glossary(filename)

  that takes as a parameter a string filename and constructs a glossary of the file. A glossary is defined as a dictionary from words to lists of tuples whose first elements are line numbers and second elements are the lines themselves. For example, calling the function on this file:

  1st line 
  2nd line
                

  would return this dictionary:

  {"1st": [(0, "1st line")], "line": [(0, "1st line"), (1, "2nd line")], "2nd": [(1, "2nd line")]}
  
  

  Be sure to remove newline characters from the line. You may assume that each word appears at most once per line of the file.

• Calculating enrollments

  Implement the following function:

  def compute_enrollments(individuals)
  
  

  That takes as a parameter individuals, a list of 2-length tuples whose first elements are the year of a student and whose send elements are a class that they're enrolled in. Your job is to construct a dictionary mapping class names to dictionaries that map years to the number of students from that year enrolled in that particular class. For example, calling the function on this list:

  [("frosh", "CS 106A"), ("sophomore", "ARTHIST 152"), ("frosh, "CS 106A"), ("PhD", "ARTHIST 152")]
  
  

  would return the following dictionary:

  {"CS 106A": {"frosh": 2}, "ARTHIST 152": {"sophomore": 1, "PhD": 1}}

Tuples: student residences

Given a list of tuples all_housing_assignments in which the first value is a student's name and the second value is the name of a dorm they have lived in, write a function map_students_to_dorms to create a and return a dictionary which associates each student with a list of all dorms they have lived in throughout their time at Stanford. The list contains undergraduates of all years so some students may only have one residence while others may have multiple.

Sorting, lambdas and List Comprehensions

Each of these problems should be solved with one line of code.

• Construct a list of all the numbers 1-1000 inclusive that are divisible by 8.
• Construct a list of all the numbers 1-1000 that contain 3 as a digit at least once
• Find the number of spaces in a string s
• Given a string s, construct a list of all the non-vowel characters in the string, regardless of their case. You may assume you have a constant VOWELS, which is a list of all the vowels in the english alphabet in lowercase.
• Given a list tups which contains an arbitrary number of tuples of 2 integers each, sort the tuples by the absolute difference between the first and second element. You might find the abs function, which takes in as a parameter a number and returns its absolute value, helpful.
• Given a list of strings strs, sort it in reverse alphabetical order of last character, case-insensitively (i.e. lowercase and uppercase 'Z's are equal). Break ties by the length of the string.

More sorting: stock prices

You are hired to help a company analyze their stock. To start, they give you a list of tuples in which the first element is an int representing the time in minutes since the stock market opened that day, and the second value is the price of the company's stock at that time. They have different lists for each day and the lists are in no particular order (you can see they definitely need your help). To save space, a tuple value is only created and stored in the list if the stock price has changed (either increased or decreased) since the previous value was recorded. The value at T=0, or the time when the stock market opens, is always recorded.

First, implement the following function:

which returns a tuple containing the first and last stock prices within the given time interval where a is the start of the interval and b is the end. Both a and b are included in the time range.

Next, implement the following function:

which returns the time at which the stock had the lowest price in the given time interval.

Weather Map

This problem puts together various pieces of material from the class to solve a slightly more difficult problem. This is out of the scope of the final, but is a good way of testing that you fully understand each individual component.

The local weatherman has called in sick for the week. Unfortunately, we are not climatologists, but we can use our python programming skills to analyze the weather map and step in for the weatherman.

Given an image representing a weathermap, find all of the areas that are going to be severely impacted by the incoming snowstorm. An area is predicted to be hit by the snowstorm if its blue pixel component value is at least 128.

To help, you are given the function translate_coordinate_to_location(x,y) which takes as parameters the x and y coordinate of a given pixel, and returns a string representing the name of the location that the pixel represents on the weathermap image.

Your job is to implement the following function:

which takes as parameter an image of a weather map and returns a list of all towns/cities that are going to be affected by the incoming snow storm. To make this list useful, make sure to only include the name of each town or city once in the list. You may assume you have a constant MINIMUM_BLUE_THRESHOLD that is equal to 128.