CS106AP Midterm + Solutions

Stanford, Spring 2018-19

Instructions

• There are 6 problems to complete
• In Bluebook, "Problem 1" is these instructions and reference code
• Problems 2-7 are the actual problems
• This is a closed note exam
• The exam is 50 minutes and 100 points
• We will not grade off for syntax errors, so long as we see the correct idea
• We will not grade off if you omit the final "return" at the end of a function, so long as the code computes the correct result
• Good luck!

# CS106AP Exam Reference Reminder
# [square brackets] denote functions listed here that we have not used yet
# Exam questions will not depend on functions we have note used yet
General functions:
  len() int() str() range() list() sorted()
String functions:
  isalpha() isdigit() isspace() isupper() islower()
  find() upper() lower() strip()
List functions:
  append() extend() [pop() insert()]
Dict functions:
  keys() [values() items()]

SimpleImage:
  # read filename
  image = SimpleImage(filename)
  # create blank image
  image = SimpleImage.blank(width, height)

  # foreach loop
  for pixel in image:

  # range/y/x loop
  for y in range(image.height):
      for x in range(image.width):
          pixel = image.get_pixel(x, y)

Read lines out of a text fie:
  with open(filename, 'r') as f:
      for line in f:

2. Short Answer (5 points)

What 3 numbers print when the caller() function runs? This code runs without error.

def foo(x):
    x = x + 2
    y = 0
    return x


def caller():
    x = 1
    y = 2
    z = foo(y)
    print(x, y, z)

# Write 3 numbers here

3. Graphics (10 points)

Given an image, create a new blank "out" image which is 2x as wide and 2x as tall as the original. Create an vertically flipped copy of the original image in the lower-right quadrant of the out image, leaving the rest of the out image untouched.

def lower_right(filename):
    image = SimpleImage(filename)

4. Nested (10 points)

Given a non-negative int n, return a list of n length-4 lists like these examples:

fours(1) -> [[10, 11, 12, 13]]
fours(2) -> [[10, 11, 12, 13], [11, 12, 13, 14]]
fours(3) -> [[10, 11, 12, 13], [11, 12, 13, 14], [12, 13, 14, 15]]

def fours(n):

5. Parse1 (20 points)

Given a string s, find the first 'a' in s. If it is followed immediately by 2 random chars and then a second 'a', then return the substring of the 2 random chars. Otherwise return the empty string. So e.g. '1aXYa11' returns 'XY'. Solve this problem without loops using s.find().

extract_aa('1a00a11') -> '00'
extract_aa('000axxa0') -> 'xx'
extract_aa('0000axaa0') -> 'xa'
extract_aa('axxxx') -> ''

def extract_aa(s):

6. Parse2 (40 points)

Given a string s, return a list of all the "binary" substrings in s. Each binary substring is made of one or more '0' or '1' chars. If the binary substring is immediately followed by a '2', then include the '2' on the end of that substring.

So for example ...

parse_binary('xx101xx112x010') -> ['101', '112', '010']
parse_binary('xx0002xx') -> ['0002']
parse_binary('xx2000xx') -> ['000']

def parse_binary(s):

7. Dict (15 points)

Using the dict-count algorithm, count how many times each alphabetic char in s appears. Treat upper and lower case chars in s as lower case. After the count dict is built, print out all the chars seen in alphabetical order, 1 per line, printing the char and followed by its count, like this:

a 26
b 9
c 22
d 6
...

For example with the string 'acbBc', your function should print this:

a 1
b 2
c 2

def count_alpha(s):

Solutions

## 2. Short answer
caller problem 
  1 2 4


## 3. Graphics
def lower_right(filename):
    image = SimpleImage(filename)
    output = SimpleImage.blank(image.width * 2, image.height * 2)
    # image needs to double both width and height
    
    for y in range(image.height):
        for x in range(image.width):
            output_y = 2 * image.height - 1 - y
            output_x = x + image.width
            
            src_pixel = image.get_pixel(x, y)
            dst_pixel = output.get_pixel(output_x, output_y)
            dst_pixel.red = src_pixel.red
            dst_pixel.green = src_pixel.green
            dst_pixel.blue = src_pixel.blue
    
    return output



## 4. Nested
def fours(n):
    lst = []
    for i in range(n):
        inner_lst = []
        starting_num = 10 + i
        for j in range(4):
            inner_lst.append(startin_num + j)
        lst.append(inner_lst)
    return lst


## 5. Parse1
def extract_aa(s):
    first_idx = s.find('a')
    
    if first_idx < len(s) - 3:
        second_idx = first_idx + 3
        if s[second_idx] == 'a':
            return s[first_idx + 1 : second_idx]
    
    return ''


## 6. Parse2

def parse_binary(s):
    search = 0
    words = []
    
    while True:
        begin = search
        while begin < len(s) and not (s[begin] == ‘0’ or s[begin] == ‘1’): 
            begin += 1
            
        if begin >= len(s):
            break
        
        end = begin + 1
        while end < len(s) and (s[end] == ’0’ or s[end] == ‘1’):
            end += 1
            
        if end < len(s) and s[end] == ‘2’:
            end += 1
        
        binary = s[begin : end]
        words.append(binary)
        
        search = end 
        
    return words


## 7. Dict

def count_alpha(words):
    counts = {}
    for i in range(len(words)):
        ch = words[i]
        if ch.isalpha():
            if ch.lower() not in counts:
                counts[ch.lower()] = 0
            counts[ch.lower()] += 1
    
    for key in sorted(counts.keys()):
        print(key, counts[key])