Midterm Solutions

Written by Mehran Sahami

CS 106A May 9th, 2022

Your Midterm

You can find your midterm score on gradescope. Please use your Stanford email to create an account if you do not already have one.

Regrade Requests

We try to grade as consistently as possible, but we are human and we might make mistakes. If you feel like one of your problems was misgraded, please file a regrade request on Gradescope. The regrade requests are open now and must be submitted before Monday, May 16th at 5pm PT. Note that this is the only way to have your regrade request considered; in particular, asking your section leader to take a quick look to see whether a problem was misgraded is not a way of short circuiting this process. We want you to have the credit you deserve, but filing a formal request helps us make sure that your request goes to the right person. If you submit a regrade regrade request, we do reserve the right to regrade the entire problem and make any necessary corrections.

Midterm Solutions

1. Karel the Robot (25 points)

We want to write a program in which Karel creates a triangle of beepers in the lower left-hand corner of the world. Karel always starts in the first avenue (column) of the world, facing East with a beeper bag containing infinitely many beepers. Karel can start on any street (row) in the first column, except the top-most street (row) in the world.

Karel should make a triangle of beepers in the world, where the height (and width) of the triangle is based on the row of the world Karel initially starts in. The triangle of beepers should extend from Karel’s initial location down to location (1, 1) in the world, and the triangle should exactly as wide as it is high. Each location in the triangle should contain a single beeper. Karel should finish facing East in the lower right-hand corner of the triangle.

Below, we show two examples of Karel’s initial (before the program is run) and final (after the program is run) states to show what the resulting triangle of beepers should look like. In World #1, Karel starts on 4th street, so the triangle has a height and width of 4 beepers. In World #2, Karel starts on 1st street, so the resulting “triangle” is just a single beeper on corner (1, 1).

Remember, that your program should work with any world that meets the specifications described above (not just the specific worlds pictured above).

Here are a few assumptions you can make in your program:

  • The world is guaranteed to be at least as wide as it is high (i.e., the number of avenues (columns) is at least as many as the number of streets (rows)), so the triangle of beepers will always be able to fit properly in the world.
  • The top border of Karel’s world will always be at least one street (row) higher than the top of the triangle (i.e., Karel will never start on the top-most street (row) of the world).
  • Other than the border around the world, there are no other walls or beepers in the world.
  • You can only use the instructions in the Karel course reader and no additional Python features . Notably, you cannot use any variables other than as counters in for loops, and you should not use such counters anywhere other than in determining the number of iterations of the loop (i.e., no use of variables beyond what is done in the Karel course reader).


Starter Code 
from karel.stanfordkarel import *

# turn_right and turn_around are provided for convenience, in case you need them

def turn_right():
    for i in range(3):
        turn_left()

def turn_around():
    for i in range(2):
        turn_left()


if __name__ == "__main__":
    run_karel_program()
Solution Code 
from karel.stanfordkarel import *

def turn_around():
    # Karel turns to opposite direction from which it was originally facing
    for i in range(2):
        turn_left()

def turn_right():
    # Karel turns to the right of the direction it was originally facing
    for i in range(3):
        turn_left()

def beeper_column():
    """
    Pre-condition: Karel is facing East.
    Post-condition: Karel is facing East in row 1 of the world, having placed
    a column of beepers from its original location down to row 1 in the world.
    """
    turn_right()
    while front_is_clear():
        put_beeper()
        move()
    put_beeper()
    turn_left()

def reposition():
    """
    Pre-condition: Karel is facing East at the bottom of a column of beepers.
    Post-condition: Karel is facing East one row down and one column ahead of the
    top of the column of beepers it started in.
    """
    turn_left()					# Face North
    while beepers_present():	# Move to top of beeper column
        move()
    turn_around()					# Move down one row from top of beeper column
    move()							
    move()
    turn_left()					# Face East and move to column to the right
    move()

def main():
    while right_is_clear():	# Karel's right will be blocked only in first row.
        beeper_column()			# Create column of beepers as part of triangle.
        reposition()				# Reposition one column to right and one row down.
    beeper_column()     		# Add last column of triangle (single beeper).

if __name__ == "__main__":
    run_karel_program()

2. Full Program (25 points)

It turns out that people often have difficulty assessing how often random events will happen. As a result, it can be useful to do a computer simulation of a random process to see how often something random will really happen. Let’s consider flipping a pair of fairs coins. Each of the two coins will independently come up “heads” or “tails” with a 50/50 chance. To simplify things, we’ll have the number 0 represent “heads” and the number 1 represent “tails.”

We want to write a Python program that simulates repeatedly flipping two coins. On each round, the computer should generate random integers to simulate flipping two separate coins and write out the results of what was generated (i.e., flipped). The round is considered a “success” if both coins land on the same side (i.e., the random numbers representing the coins are both 0 (“heads”) or are both 1 (“tails”)), otherwise that round is not a success. For each round, the program should write out whether it was a success or not. The program should repeat this process until there are two consecutive rounds that are successes, at which point the program should write out how many total rounds were simulated and end.

To simulate the randomness of each coin flip, you should use the Python random library we talked about in class. Recall, that you can generate a random integer with the function: random.randint(min, max) which returns a random integer between min and max, inclusive.

Two sample runs of the program are shown below (the first in which it takes four rounds total to get two consecutive successful rounds, and the second in which it takes five rounds total to get two consecutive successful rounds):
Sample Round #1 

Round # 1 - generated 0 and 0
That's a success
Round # 2 - generated 1 and 0
Sorry, that's not a success
Round # 3 - generated 0 and 0
That's a success
Round # 4 - generated 1 and 1
That's a success
You simulated 4 rounds
Sample Round #2 
Round # 1 - generated 1 and 1
That's a success
Round # 2 - generated 0 and 1
Sorry, that's not a success
Round # 3 - generated 1 and 0
Sorry, that's not a success
Round # 4 - generated 1 and 1
That's a success
Round # 5 - generated 0 and 0
That's a success

Starter Code 
import random


# This provided line is required at the end of a Python file
# to call the main() function.
if __name__ == '__main__':
    main()
Solution Code 
import random

def generate_values(num_rounds):
    """
    Simulates two "coin flips" and returns True if both "flips" are the
    same.  Otherwise, return False
    """
    value1 = random.randint(0, 1)
    value2 = random.randint(0, 1)
    print("Round #", num_rounds, "- generated", value1, "and", value2)
    return value1 == value2

def main():
    num_matches = 0         # Number of successive matches
    num_rounds = 0          # Total number of rounds in the simulation
    while num_matches < 2:  # Keep running until we get two successive matches
        num_rounds += 1
        matched = generate_values(num_rounds)
        if matched:
            print("That's a success")
            num_matches += 1
        else:
            print("Sorry, that's not a success")
            # When no match, we need to reset number of successive matches to 0
            num_matches = 0
    print("You simulated", num_rounds, "rounds")

# This provided line is required at the end of a Python file
# to call the main() function.
if __name__ == '__main__':
    main()

3. Lists of lists (20 points)

Sudoku is a game where a player tries to fill in a set of 3 x 3 grids with the digits 1 to 9 in order to satisfy certain constraints. One of those constraints is that each 3 x 3 grid in the game contains every digit from 1 to 9 (which also implies that each digit only appears once in the 3 x 3 grid).

We want to write a function that is passed a 3 x 3 grid (represented as a list of lists) of integers and returns True if all of the digits from 1 to 9 appear in the grid and False otherwise.

Immediately below is an example of a grid, which when passed to your function, should return True, since the digits 1 to 9 all appear. Note that the order in which the digits appear does not matter, only that all the digits are present.

And here is an example of a grid, which when passed to your function, should return False, since not all the digits 1 to 9 all appear (i.e., the digits 4 and 7 are missing).

Your task in this problem is to write a function: def is_valid_grid(grid) which is passed a 2-dimensional list representing the grid (as descibed above) and should return either True or False as described above. You can assume that the grid passed into your is_valid_grid function will always be 3 x 3 in size. You do not need to write a complete program, just the is_valid_grid function.
Starter Code 

def is_valid_grid(grid):
    pass
Solution Code 1 
def is_value_present(grid, value):
    # Returns True if value is in the grid, False otherwise
    for row in grid:
        for num in row:
            if num == value:
                return True
    return False

def is_valid_grid(grid):
    for i in range(1, 10):  # loop through values 1 to 9
        if not is_value_present(grid, i):
            return False
    return True
Solution Code 2 
def is_valid_grid(grid):
    correct = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    from_grid = []
    for row in grid:
        for elem in row:
            from_grid.append(elem)
    from_grid.sort()
    return from_grid == correct
Solution Code 3 
def is_valid_grid(grid):
   for i in range(1, 10):
       if (i not in grid[0]) or (i not in grid[1]) or (i not in grid[2]):
          return False
   return True

4. Images (30 points)

A common task when editing images is to copy a rectangular portion of one image and paste it into another image. For example, we might start with the original image of a flower (Figure 1) and want to copy a portion of an image of a burrito (Figure 2) into it, producing the final image shown in Figure 3.

We’ll call the starting image (e.g., the flower in Figure 1), the “original” image. We’ll call the image we want to copy a portion of (e.g., the burrito in Figure 2), the “copy” image.

To do this sort of copy and paste, we need to know the bounding box of the region in the “copy” image that we want to select for copying (we’ll call this region the “selection”). This bounding box (i.e., the “selection”), is specified by both the pixel location of the upper left-hand corner of the region to be copied, denoted by (up_x, up_y), and the pixel location of lower right-hand corner of the region to be copied, denoted by (low_x, low_y). For example, we could define a bounding box in the burrito image with the following coordinates: up_x = 140, up_y = 70 and low_x = 215, low_y = 150, as represented by the red dashed box in Figure 4 below.

We also want to specify where in the “original” image we want to copy the “selection”. To do that, we need to specify a destination coordinate, denoted (dest_x, dest_y), that represents the pixel location in the “original” image that should correspond to where the upper left-hand corner of the “selection” should be copied into the “original” image. For example, if in the image of the flower, we specified the destination location dest_x = 60, dest_y = 80, then we should copy all the pixels from the “selection” in the burrito image into the flower image, as shown in Figure 5.

Your job is to write a function called paste_image with the following header: def paste_image(original_img, copy_img, up_x, up_y, low_x, low_y, dest_x, dest_y):

This function is passed an original image (original_img), the image to copy from (copy_img), the bounding box for the region to copy (i.e., the “selection”), specified by (up_x, up_y) and (low_x, low_y), and the postion in the original image to copy into, specified by (dest_x, dest_y). Your function should copy the pixels from specified “selection” in the copy_img into the original_img. In other words, your function should change the original_img passed in. Note that original_img and copy_img are simpleimage objects (not filenames).

You can assume that the bounding box for the “selection” always has coordinates for the upper left-hand corner (up_x, up_y) that are above and to the left of the coordinates for the lower right-hand corner (low_x, low_y).

You should make sure that you do not copy any pixels that would go past the edges of the original image (that would cause an error). For example, if you tried to copy the selection from Figure 4 into the original flower image (Figure 1) as destination location (150, 160), you should produce the image shown in Figure 6. Note that any pixels from the “selection” that would go off the edge of the original image are not in the result. </br>

You may assume that both the “original” image and the “copy” image passed to your function each contain at least one pixel. You only need to write the paste_image function, not a complete program. But feel free to write any helper functions, if that helps you solve the problem.
Starter Code 

from simpleimage import SimpleImage

def paste_image(original_img, copy_img, up_x, up_y, low_x, low_y, dest_x, dest_y):
    pass
Solution Code 1 
from simpleimage import SimpleImage

def paste_image(original_img, copy_img, up_x, up_y, low_x, low_y, dest_x, dest_y):
    height = original_img.height
    width = original_img.width

    # Determine the differences (offsets) in x and y coordinates between the
    # upper left-hand corner of region to copy into in original image and
    # the "selection" from the copy image
    x_offset = dest_x - up_x
    y_offset = dest_y - up_y

    for y in range(up_y, low_y + 1):        # Loop through rows in "selection"
        for x in range(up_x, low_x + 1):    # Loop through columns in "selection"

            # (new_x, new_y) is location in original image
            # where we should copy pixel (x, y) from "selection"
            new_x = x_offset + x
            new_y = y_offset + y

            # Make sure we don't go off  edge of original image when copying pixels
            if new_y < height and new_x < width:
                original_img.set_pixel(new_x, new_y, copy_img.get_pixel(x, y))
Solution Code 2 
from simpleimage import SimpleImage

def paste_image(original_img, copy_img, up_x, up_y, low_x, low_y, dest_x, dest_y):
    for y in range(up_y, low_y + 1): # looping in range of selected area
	    for x in range(up_x, low_x + 1):
	        pixel = copy_img.get_pixel(x, y)
	        orig_coord_x = x - up_x + dest_x # we started looping at up_x, subtract out
	        orig_coord_y = y - up_y + dest_y
	        if orig_coord_x < original_img.width and orig_coord_y < original_img.height:
	            original_img.set_pixel(orig_coord_x, orig_coord_y, pixel)
Solution Code 3 
from simpleimage import SimpleImage

def paste_image(original_img, copy_img, up_x, up_y, low_x, low_y, dest_x, dest_y):
	cropped_width = low_x - up_x + 1
	cropped_height = low_y - up_y + 1
	for y in range(cropped_height): # looping from 0 to height of cropped patch
	    for x in range(cropped_width): # looping from 0 to width of cropped patch
	        pixel = copy_img.get_pixel(x + up_x, y + up_y)
	        if x + dest_x < original_img.width and y + dest_y < original_img.height:
	            original_img.set_pixel(x + dest_x, y + dest_y, pixel)
Solution Code 4 
from simpleimage import SimpleImage

def paste_image(original_img, copy_img, up_x, up_y, low_x, low_y, dest_x, dest_y):
	cropped_width = low_x - up_x + 1
	cropped_height = low_y - up_y + 1
	for y in range(dest_y, dest_y + cropped_height): # looping over dest patch
	    for x in range(dest_x, dest_x + cropped_width):
	        pixel = copy_img.get_pixel(x - dest_x + up_x, y - dest_y + up_y)
	        if x < original_img.width and y < original_img.height:
	            original_img.set_pixel(x, y, pixel)

5. Strings (20 points)

While Python traditionally uses snake case to specify names of variables (where words in a name are separated by underscore characters, as in number_of_rows), some other languages use a naming convention know as camel case. In camel case, a variable name containing multiple words has all the words appended together with no underscores, but each new word is capitalized to make the name easier to read. For example, we might have a name like NumberOfRows in camel case. (The term “camel” case comes from the fact that capital letters in the middle of a name look like humps on a camel. At least that’s the story we’ve been told.)

Realizing that it would be useful to have a way to be able to easily change the naming style used from snake case to camel case, you decide to write a function that converts a string representing a name in snake case, in which words are separated by underscore characters '_' (such as NUM_COLUMNS), to a camel case version of that same name (which would be NumColumns in this case).

Here are the rules for producing a camel case name:

  • The first letter of the first word is capitalized (upper case),
  • The first letter of every subsequent word after the first is capitalized,(There will be at least one underscore character between words in the original snake case string passed into your function.)
  • All letters that are not the first letter in a word should be lower case,
  • There are no underscores.

Your job is to write a function named change_name_style that takes as a parameter a string representing the snake case version of a name, and returns a string which is the camel case version of that same name. You can assume that the strings passed to your function will only contain underscores and letter characters (but the letters can be upper or lower case).

For example, if you call: change_name_style('NUM_COLUMNS') your function should return the string: 'NumColumns' as the result.

Additional examples of what your function should return are given below: 

change_name_style('SIZE') -> should return "Size"
change_name_style('three_word_name') -> should return "ThreeWordName"
change_name_style('Four____Underscores') -> should return "FourUnderscores"
change_name_style('_start_') -> should return "Start"

In writing your solution, you should keep in mind that you do not need to write a complete program. All you need is the definition of the method change_name_style that returns the desired result. You may write any additional functions that may help you solve this problem.


Starter Code 
	
def change_name_style(str):
    pass
Solution Code 1 
def change_name_style(str):
    """
    This function is passed a string representing a snake case name and it
    returns the camel case equivalent of that name.
    """
    result = ''
    capital_next_letter = True   # Indicates if we should capitalize next letter seen
    for i in range(len(str)):
        ch = str[i]
        if ch == '_':
            capital_next_letter = True
        else:
            if capital_next_letter:
                result += ch.upper()    # Upper case (capitalize) the letter
                capital_next_letter = False
            else:
                result += ch.lower()    # Lower case the latter

    return result
Solution Code 2 
def change_name_style(str):
    """
    This function is passed a string representing a snake case name and it
    returns the camel case equivalent of that name.
    """
    result = ""
    if str[0] != "_":
        result += str[0].upper()
    for i in range(1, len(str)):
        curr_ch = str[i]
        prev_ch = str[i - 1]
        if curr_ch != "_":
            if prev_ch == "_":
                result += curr_ch.upper()
            else:
                result += curr_ch.lower()
    return result
​
Solution Code 3 
def change_name_style(str):
    """
    This function is passed a string representing a snake case name and it
    returns the camel case equivalent of that name.
    """
    result = ""
    no_underscores = str.replace("_", " ")
    word_list = no_underscores.split()
    for word in word_list:
        camel_word = word[0].upper() + word[1:].lower()
        result += camel_word
    return result
​
tests = ["SIZE", "three_word_name", "Four____underscores", "_start_"]
for test in tests:
    print(change_name_style(test))