CS106A Midterm + Solution

Stanford, Fall 2024-25

We fell the midterm was pretty hard - lots of code to write in an hour, and we're pleased with the class' performance overall. That said, there's always a very wide range of scores seen. Generally the "B" range is pretty wide.

Instructions

# CS106A Exam Reference Reminder
# [square brackets] denote functions listed here that we have not used yet
# Exam questions will not depend on functions we have not used yet
Bit:
  bit = Bit(filename)
  bit.front_clear() bit.left_clear() bit.right_clear()
  bit.get_color()
  bit.move() bit.left() bit.right()
  bit.paint('red') [bit.erase()]
General functions:
  len() int() str() range() [list() sorted()]
String functions:
  isalpha() isdigit() isspace() isupper() islower()
  find() upper() lower() strip()
List functions:
  append() index() [extend() pop() insert()]
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)
Grid 2D:
  grid = Grid.build([['row', '0'], ['row', '1']])
  grid.width, grid.height - properties
  grid.in_bounds(x, y) - True if in bounds
  grid.get(x, y) - returns contents at that x,y, or None if empty
  grid.set(x, y, value) - sets new value into grid at x,y

1. Short Answer (6 points)

a. By each ???, write what value comes from the Python expression:

>>> 1 + 2 * 3 - 1 + 2
???


>>> 57 % 5
???


>>> s = 'Voter'
>>> s[1:4]
???


>>> s[:2]
???


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

def foo(a, b):
    a = a + 1
    b = b + 1
    return a + b


def caller():
    a = 3
    b = 4
    c = foo(b, 1)
    print(a, b, c)
# What 3 numbers print ???

2. Bit (6 points)

Bit is on flat ground, facing the right side of the world. Move bit forward zero or more squares until a hole appears below. The hole is 1 square wide and multiple squares deep. Move bit down the hole until an opening appears towards the right side of the world. The opening marks the entrance to a 1 square high horizontal cave. Move bit through the cave until blocked. Use a series of three while loops.

Bit before and after:
alt: bit mesa

def loop3(filename):
    bit = Bit(filename)
    # Your code here




3. Image (16 points)

Given an image filename and ints a and b which are 1 or more. Produce a new out image with three features: (1) a blank rectangle a pixels high and the same width as the original image, directly above the image. (2) a vertically flipped copy of the original image immediately below the blank rectangle. (3) To the left and right of the rectangle and image, two vertical stripes, each b pixels wide, with the stripe on the right painted aqua, and the stripe on the left remaining blank. The stripes run the full height of the output. Please try to avoid writing too close to the right edge of the paper.
alt: blank rectangle, flipped image, 2 stripes

1. Write one line of code to create the out image.

2. Almost all of the code to write the flipped image is provided — looping over the original image, writing the colors at each "pixel" to "pixel_out". Write the one line of code which sets the "pixel_out" variable used by the later lines in this loop. It's ok if you need to put the parameters on multiple lines to make it fit.

3. Write the loops and other needed code to produce the aqua stripe at the right side. These are separate loops, not nested inside the earlier loops. To set each white pixel to aqua, the last line in the loop is like pixel_out.red = 0. We'll assume there is a return out as the last line.

def do_image(filename, a, b):
    image = SimpleImage(filename)
    #### 1. Create "out" image


    # Write flipped image to out
    for y in range(image.height):
        for x in range(image.width):
            pixel = image.get_pixel(x, y)
            #### 2. Set "pixel_out"




            pixel_out.red = pixel.red
            pixel_out.green = pixel.green
            pixel_out.blue = pixel.blue
    #### 3. Fill aqua rectangle







4. Strings (38 points)

a. Given a string s, return a string such that: for every lowercase char in s, the result has 2 copies of that char. Omit all the other chars.

'ab#XYz' -> 'aabbzz' |  def lower2x(s):
'Yo' -> 'oo'         |
'+NO+' -> ''         |









b. Given a string s. Build and return a new string made of the chars of s, except omit chars which are already in the result. In effect, this means that each char in the result is unique. So for example the string 'bookkeeper' returns 'bokepr'.

'bookkeeper' -> 'bokepr'  | def unique(s):
'abbacab'    -> 'abc'     |
'abc'  -> 'abc'           |
'a'    -> 'a'
''     -> ''








c. Given a string s. If there is a digit at index 3, then return that number times 10. Otherwise, if there is an '@' at index 1, then return the number 0. In all other cases, return -1.

'ab24xx' -> 40     | def lucky13(s):
'a@456x' -> 50     |
'ab4de'  -> -1     |
'a@2x'   -> 0      |
'aa'     -> -1
''       -> -1







d. For this problem, we are all about the '$'. Find the first '$' char in s. If it is present, and the 3rd char after the '$' is a digit, then return the value of that digit times 2, e.g. 'xx$#x3x' returns 6. If the digit is not present, then if a '*' immediately precedes the '$', then return the number 8. In all other cases, return -1. Use s.find().

'xx$ab3c'   -> 6          | def dollar(s):
'woof$3456' -> 10         |
'woof$xxxx' -> -1         |
'woof$'     -> -1         |
'woo*$xxxx' -> 8          |
'woo*$1111' -> 2          |
'$*'        -> -1
'nope'      -> -1










e. Given a string s, find the first '@@' in s. Then find the first '+++' that comes after the '@@'. If either is not present, return None. Otherwise, return a list length 2, where the first element is the substring between the '@@' '+++' groups, and the second element is the substring after the '+++'. So for example, the string 'a@@bb+++ccc' returns ['bb', 'ccc']. Use s.find() and slices.

'a@@bb+++ccc'              | def at_plus(s):
   ->  ['bb', 'ccc']       |
'apple@@tea+++cookie       |
   ->  ['tea', 'cookie']   |
'+++@@tea+++cookie         |
   ->  ['tea', 'cookie']   |
'@@+++      ->  ['', '']   |
'xx@@xx++'  ->  None
'x+++a@@x'  ->  None
'nope'      ->  None

5. Grid Bear-Jump (18 points)

In this problem, every square is one of these four values: empty None, bear 'b', honey 'h', or tree 't'. As usual, you can get full credit for each part independently of what you write on the other parts. Write the code for the function bear_jump(grid, x, y, n) assuming the parameters x, y represent an in bounds square that contains a bear, and the parameter n is an int, 1 or greater. Here are the conditions for the bear to jump:

1. There must not be a square containing honey immediately below the bear. Anything other than a square containing honey is acceptable.

2. We will say the "jump" square is 1 column to the left and exactly n squares above the bear. The jump square must be empty, and also the square immediately below the jump square must be empty.

If the conditions (1) and (2) are met, move the bear to the jump square, erase it from its original square, and return the changed grid. In all other cases, return the grid unchanged.

def bear_jump(grid, x, y, n):



















(b) Add the two lines to complete the following Doctest for a call to bear_jump() where the jump action succeeds and the bear moves. The first Grid.build() line is provided which builds a small grid suitable for this Doctest.

>>> grid = Grid.build([[None, 'b'], [None, 't'], ['t', 'b']])
>>>


6. Encryption (16 points)

This problem resembles the homework encryption, but with some differences. As a simplification, we will not handle uppercase chars. For this encryption, there are 2 extra chars in the slug at indexes 0 and 1, so the length of the slug is 2 more than the length of the source. Here are example lists, with the index numbers shown:

alt: source ['a', 'b', 'c', 'd'] and slug ['@', '*', 'w', 'e', 'r', 'k']

1. If the input char is in the source, then its encrypted form is at the corresponding index in the slug, shifted over to skip indeces 0 and 1 in the slug — e.g. with the example data, the encrypted form of 'a' is 'w'

Otherwise we have the cases where the char is not in the source.

2. If the input char is alphabetic and is not in the source, then its encrypted form is the slug char at index 0 — e.g. with the example data, the encrypted form of 'x' is '@', and the encrypted form of 'y' is also '@'. Many alphabetic chars may share this encrypted form.

3. If the input char is not alphabetic and is not in the source, then its encrypted form is the slug char at index 1 — e.g. the encrypted form of '$' is '*'. Many non-alphabetic chars may share this encrypted form.

Encryption examples
'a' -> 'w' (Rule 1)
'd' -> 'k' (Rule 1)
'x' -> '@' (Rule 2)
'y' -> '@' (Rule 2)
'$' -> '*' (Rule 3)
def encrypt_char(source, slug, ch):
    # Your code here
    

Solutions


#### 1. Short Answer

8
2
ote
Vo


3 4 7

#### 2. Bit

def loop3(filename):
    bit = Bit(filename)
    # Find the hole to our right
    while not bit.right_clear():
        bit.move()

    # Move down the hole looking for cave
    bit.right()
    bit.move()  # move into hole so loop works
    while not bit.left_clear():
        bit.move()

    # Move through the cave
    bit.left()
    while bit.front_clear():
        bit.move()

#### 3. Image

out = SimpleImage.blank(image.width + 2 * b, image.height + a)


pixel_out = out.get_pixel(b + x, a + image.height - 1 - y)
# or out.height - 1 - y


for y in range(image.height + a)
    for x in range(b):
        out_pix = out.get_pixel(b + image.width + x, y)
        out_pix.red = 0

return out


#### 4. String

a.
def lower2x(s):
    result = ''
    for ch in s:
        if ch.islower():
            result += ch + ch
    return result

b.
def unique(s):
    result = ''
    for ch in s:
        if ch not in result:
            result += ch
    return result

c.
def lucky13(s):
    # Use < to check index before using [ ]
    if 3 < len(s) and s[3].isdigit():
        return int(s[3]) * 10
    
    if 1 < len(s) and s[1] == '@':
        return 0
    
    return -1


d. 
def dollar(s):
    dollar = s.find('$')
    # Add var here helps, but not required
    after = dollar + 3
    if dollar != -1:
        if after < len(s) and s[after].isdigit():
            return int(s[after]) * 2
        # Could use "and" instead of nested ifs
    
    # Subtle: avoid negative index (minor deduction)
    if dollar - 1 >= 0:
        if s[dollar - 1] == '*':
            return 8
    return -1


e.
def at_plus(s):
    at = s.find('@@')
    plus = s.find('+++', at + 2)  # + 2 not required
    if at == -1 or plus == -1:
        return None
    
    mid = s[at + 2:plus]  # key: correct slice numbers
    end = s[end + 3:]
    result = []
    result.append(mid)
    result.append(end)
    return result
    # Building list with .append() is one way


#### 5. Grid

def bear_move(grid, x, y, n):
    # honey below is deal killer
    if grid.in_bounds(x, y + 1) and grid.get(x, y + 1) == 'h':
        return grid
    
    # Need empty squares up at (x - 1, y - n) and y - n + 1
    if grid.in_bounds(x - 1, y - n) and
          grid.get(x - 1, y - n) == None and
          grid.get(x - 1, y - n + 1) == None:
        grid.set(x, y, None)
        grid.set(x - 1, y - n, 'b')
        return grid  # Works without this line too

    # Fallback if conditions not met
    return grid


## b. Doctest
>>> grid = Grid.build([[None, 'b'], [None, 't'], ['t', 'b']])
>>>


## Move the bear at (1, 2) with n=2
bear_move(grid, 1, 2, 2)
[['b', 'b'], [None, 't'], ['t', None]]


## 6. Encryption

def encrypt_char(source, slug, ch):
    if ch in source:
        idx = source.index(ch)
        return slug[idx + 2]   # + 2 is key
    if ch.isalpha():
        return slug[0]
    
    # Can have an if here, but it's not necessary -
    # if we get here, it's not in source and not alphabetic.
    return slug[1]
    
    # Could use "else" structure, but the "returns"
    # narrow the cases nicely