# 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:
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

```
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])
```