Lab 14: Final Review
Starter Files
Download lab14.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Submission
This lab will not be graded. You do not need to submit anything.
Object Oriented Programming
- Starter code for Question 1 is in lab14.py.
Question 1: Keyboard
We'd like to create a Keyboard class that takes in an arbitrary
number of Buttons and stores these Buttons in a dictionary. The
keys in the dictionary will be ints that represent the postition on the
Keyboard, and the values will be the respective Button. Fill out
the methods in the Keyboard class according to each description,
using the doctests as a reference for the behavior of a Keyboard.
class Keyboard:
"""A Keyboard takes in an arbitrary amount of buttons, and has a
dictionary of positions as keys, and values as Buttons.
>>> b1 = Button(0, "H")
>>> b2 = Button(1, "I")
>>> k = Keyboard(b1, b2)
>>> k.buttons[0].key
'H'
>>> k.press(1)
'I'
>>> k.typing([0, 1])
'HI'
>>> k.typing([1, 0])
'IH'
>>> b1.pressed
2
>>> b2.pressed
3
"""
def __init__(self, *args):
"*** YOUR CODE HERE ***"
self.buttons = {}
for button in args:
self.buttons[button.pos] = button
def press(self, info):
"""Takes in a position of the button pressed, and
returns that button's output"""
"*** YOUR CODE HERE ***"
if info in self.buttons.keys():
b = self.buttons[info]
b.pressed += 1
return b.key
return ''
def typing(self, typing_input):
"""Takes in a list of positions of buttons pressed, and
returns the total output"""
"*** YOUR CODE HERE ***"
accumulate = ''
for pos in typing_input:
accumulate+=self.press(pos)
return accumulate
class Button:
def __init__(self, pos, key):
self.pos = pos
self.key = key
self.pressed = 0Use OK to test your code:
python3 ok -q KeyboardRecursive Objects
- Starter code for Question 2 and 3 is in lab14.py.
Question 2: Every Other
Implement every_other, which takes a linked list s. It mutates s such
that all of the odd-indexed elements (using 0-based indexing) are removed from
the list. For example:
>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
TrueIf s contains fewer than two elements, s remains unchanged.
Do not return anything!
every_othershould mutate the original list.
def every_other(s):
"""Mutates a linked list so that all the odd-indiced elements are removed
(using 0-based indexing).
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> every_other(s)
>>> s
Link(1, Link(3))
>>> odd_length = Link(5, Link(3, Link(1)))
>>> every_other(odd_length)
>>> odd_length
Link(5, Link(1))
>>> singleton = Link(4)
>>> every_other(singleton)
>>> singleton
Link(4)
"""
"*** YOUR CODE HERE ***"
if s is Link.empty or s.rest is Link.empty:
return
else:
s.rest = s.rest.rest
every_other(s.rest)Use OK to test your code:
python3 ok -q every_otherQuestion 3: Long Paths
Implement long_paths, which returns a list of all paths in a tree with
length at least n. A path in a tree is a linked list of node values that
starts with the root and ends at a leaf. Each subsequent element must be from a
child of the previous value's node. The length of a path is the number of
edges in the path (i.e. one less than the number of nodes in the path).
Paths are listed in order from left to right.
def long_paths(tree, n):
"""Return a list all paths in tree with length at least n.
>>> t = Tree(3, [Tree(4), Tree(4), Tree(5)])
>>> left = Tree(1, [Tree(2), t])
>>> mid = Tree(6, [Tree(7, [Tree(8)]), Tree(9)])
>>> right = Tree(11, [Tree(12)])
>>> whole = Tree(0, [left, Tree(13), mid, right])
>>> for path in long_paths(whole, 2):
... print(path)
...
Link(0, Link(1, Link(2)))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(5))))
Link(0, Link(6, Link(7, Link(8))))
Link(0, Link(6, Link(9)))
Link(0, Link(11, Link(12)))
>>> for path in long_paths(whole, 3):
... print(path)
...
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(5))))
Link(0, Link(6, Link(7, Link(8))))
>>> long_paths(whole, 4)
[]
"""
"*** YOUR CODE HERE ***"
paths = []
if n <= 0 and not tree.children:
paths.append(Link(tree.entry))
for b in tree.children:
for path in long_paths(b, n - 1):
paths.append(Link(tree.entry, path))
return pathsUse OK to test your code:
python3 ok -q long_pathsScheme
- Starter code for Questions 4, 5, 6, and 7 is in lab14.scm.
When we write recursive functions acting on linked lists, we often find that they have the following form:
(define (func lst)
(if (null? lst)
'BASE CASE
(EXPRESSION INVOLVING (func (cdr lst)))))In the spirit of abstraction, we want to factor out this commonly seen pattern.
It turns out that we can define an abstraction called fold that do this.
A linked list can be represented as a series of cons constructors, where the
rest of each linked list is either another linked list or nil.
We represent such a list in the diagram below:
In this diagram, the recursive list
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil)))))is represented with : as the constructor and [] as nil.
We define a function foldr that takes in a function f which takes two
arguments, and a value z. foldr essentially replaces cons with f, and
nil with z. It then evaluates the expression and returns the result. This is
equivalent to:
(f 1 (f 2 (f 3 (f 4 (f 5 z)))))We call this operation a right fold.
Similarily we can define a left fold foldl that folds a list starting
from the beginning, such that the function f will be applied this
way:
(f (f (f (f (f z 1) 2) 3) 4) 5)
A left fold is equivalent to Python's reduce with a starting value.
Question 4: Foldl
Write the left fold function by filling in the blanks.
(define (foldl fn init lst)
'YOUR-CODE-HERE
(if (null? lst)
init
(foldl fn (fn init (car lst)) (cdr lst))))Use OK to test your code:
python3 ok -q foldlQuestion 5: Foldr
Now write the right fold function.
(define (foldr fn init lst)
'YOUR-CODE-HERE
(if (null? lst)
init
(fn (car lst) (foldr fn init (cdr lst)))))Use OK to test your code:
python3 ok -q foldrNow that we've written the fold functions, let's write some useful functions using list folding!
Question 6: Map
Write the map function, which takes in a linked list lst and a function
fn, and returns a new linked list where every element is the function applied
to every element of the original list. Use either foldl or foldr. Hint: it
is much easier to write with one of them than the other!
(define (map lst fn)
'YOUR-CODE-HERE
(foldr (lambda (x xs) (cons (fn x) xs))
nil
lst))Use OK to test your code:
python3 ok -q mapQuestion 7: Tally
Implement tally, which takes a list of names and returns a
list of pairs, one pair for each unique name in names. Each pair should
contain a name and the number of times that the name appeared in names. Each
name should appear only once in the output, and the names should be ordered by
when they first appear in names.
Hint: Use the eq? procedure to test if two names are the same.
(define (tally names)
'YOUR-CODE-HERE
'replace-this)
(map (lambda (name) (cons name (count name names))) (unique names)))
(define (test-tally)
(print (list 'testing 'tally))
(assert-equal '((obama . 1))
'(tally '(obama)))
(assert-equal '((taft . 3))
'(tally '(taft taft taft)))
(assert-equal '((jerry . 2) (brown . 1))
'(tally '(jerry jerry brown)))
(assert-equal '((jane . 5) (jack . 2) (jill . 1))
'(tally '(jane jack jane jane jack jill jane jane)))
(assert-equal '((jane . 5) (jack . 2) (jill . 1))
'(tally '(jane jack jane jane jill jane jane jack)))
)Hint: You may want to implement the count and unique helper procedures in
your solution. You may also want to use map and filter in your solution.
; Using this helper procedure is optional. You are allowed to delete it.
(define (unique s)
'YOUR-CODE-HERE
'replace-this)
(if (null? s) nil
(cons (car s)
(unique (filter (lambda (x) (not (eq? (car s) x))) (cdr s))))))
; Using this helper procedure is optional. You are allowed to delete it.
(define (count name s)
'YOUR-CODE-HERE
'replace-this)
(if (null? s) 0
(+ (if (eq? name (car s)) 1 0)
(count name (cdr s)))))
; Passing these tests is optional. You are allowed to delete them.
(define (test-tally-helpers)
(print (list 'testing 'unique))
(assert-equal '(jane) '(unique '(jane jane jane)))
(assert-equal '(jane jack jill) '(unique '(jane jack jane jack jill jane)))
(assert-equal '(jane jack jill) '(unique '(jane jack jane jill jane jack)))
(print (list 'testing 'count))
(assert-equal 3 '(count 'jane '(jane jane jane)))
(assert-equal 0 '(count 'jill '(jane jane jane)))
(assert-equal 2 '(count 'jack '(jane jack jane jack jill jane)))
)
(test-tally-helpers)
(test-tally)Use OK to unlock and test your code:
python3 ok -q tally -u
python3 ok -q tallyInterpreters
- You do not need to edit any files for these questions.
Question 8: Parsing Practice
With your Project 4 implementation, what would Python display when evaluating the following expressions?
>>> scheme_read(Buffer(tokenize_lines(['(+ 1 (- 2) 3)'])))
______Pair('+', Pair(1, Pair(Pair('-', Pair(2, nil)), Pair(3, nil))))
>>> read_tail(Buffer(tokenize_lines(['1 2 . 3)'])))
______Pair(1, Pair(2, 3))
>>> scheme_read(Buffer(tokenize_lines(['1 2 . 3)'])))
______1
>>> read_tail(Buffer(tokenize_lines(['. 5)'])))
______5Question 9: Eval/Apply
This question is from the final review.With your Project 4 implementation, how many total calls to scheme_eval
and scheme_apply would be made when evaluating the following two
expressions? Assume that you are not using the tail call optimized
scheme_eval_optimized function.
(define (square x) (* x x))
(+ (square 3) (- 3 2))14 eval calls, 4 apply callsLogic
- Starter code for Questions 10, 11, and 12 is in lab14.logic.
Question 10: Nested
Write facts for a relation nest that constructs a nested pair
representation of a flat list:
; Expected behavior:
;
; logic> (query (nest (1 2 3 4 5) ?nested))
; Success!
; nested: (1 (2 (3 (4 (5 ())))))
; YOUR CODE HERE
(fact (nest () ()))
(fact (nest (?a . ?rest) (?a ?nested)) (nest ?rest ?nested))Use OK to test your code:
python3 ok -q nestQuestion 11: Fruits Tail
Below is a list of fruits. Write facts for fruits-tail, which
relates sublists of fruits starting at a given fruit:
(fact (fruits apple banana cherry date elderberry fig guava))
; YOUR CODE HERE
(fact (fruits-tail . ?fruits) (fruits . ?fruits))
(fact (fruits-tail . ?fruits) (fruits-tail ?first . ?fruits))
; (query (fruits-tail date elderberry fig guava))
; expect Success!
; (query (fruits-tail banana . ?after-banana))
; expect Success! ; after-banana: (cherry date elderberry fig guava)
; (query (fruits-tail ?e fig guava))
; expect Success! ; e: elderberryQuestion 12: Fruits Range
Write facts for fruits-range, which relates a ?before and ?after
fruit to a list of the fruits in ?between, which is never empty. You
may want to use the prefix fact from discussion section, along with
other facts that you create yourself:
(fact (prefix () ?s))
(fact (prefix (?first . ?p) (?first . ?s))
(prefix ?p ?s))
; YOUR CODE HERE
(fact (ends-before ?fruit (?last)) (fruits-tail ?last ?fruit . ?tail))
(fact (ends-before ?fruit (?first ?second . ?rest))
(ends-before ?fruit ( ?second . ?rest))
(fruits-tail ?first ?second . ?tail))
(fact (fruit-range ?before ?after ?between)
(ends-before ?after ?between)
(fruits-tail ?before . ?tail)
(prefix ?between ?tail))
; (query (fruit-range cherry guava (date elderberry fig)))
; expect Success!
; (query (fruit-range cherry elderberry date))
; expect Failed.
; (query (fruit-range cherry elderberry ?between))
; expect Success! ; between: (date)
; (query (fruit-range cherry date ()))
; expect Failed.
; (query (fruit-range banana fig ?between))
; expect Success! ; between: (cherry date elderberry)Use OK to test your code:
python3 ok -q fruitsGenerators and Coroutines
- Starter code for Questions 13 and 14 is in lab14.py.
Question 13: Remainder Generator
- This question is a repeat from Lab 13.
Like functions,
generators can also be higher-order. For this
problem, we will be writing remainders_generator, which yields a
series of generator objects.
remainders_generator takes in an integer m, and yields m different
generators. The first generator is a generator of multiples of m, i.e. numbers
where the remainder is 0. The second, a generator of natural numbers with
remainder 1 when divided by m. The last generator yield natural numbers with
remainder m - 1 when divided by m.
def remainders_generator(m):
"""
Takes in an integer m, and yields m different remainder groups
of m.
>>> remainders_mod_four = remainders_generator(4)
>>> for rem_group in remainders_mod_four:
... for _ in range(3):
... print(next(rem_group))
0
4
8
1
5
9
2
6
10
3
7
11
"""
"*** YOUR CODE HERE ***"
def remainder_group(rem):
start = rem
while True:
yield start
start += m
for rem in range(m):
yield remainder_group(rem)Note that if you have implemented this correctly, each of the
generators yielded by remainder_generator will be infinite - you
can keep calling next on them forever without running into a
StopIteration exception.
Hint: Consider defining an inner generator function. What arguments should it take in? Where should you call it?
Use OK to test your code:
python3 ok -q remainders_generatorQuestion 14: Slapper
Write a pipeline to model the creation of the ultimate playlist.
There are three stages to the playlist pipeline. Friends come up with songs and send them to a judge. The judge then approves or rejects songs. The list of songs is then aggregated into a playlist. In this example, the friends are the suppliers, the playlist is the consumer, and the judge is the filter.
The friends and playlist have been created for you. First friends
takes in a list of songs and a judge to send the songs to.
Each song is represented by a dictionary.
For example: {'name': 'Love Yourself', 'artist': 'Justin Bieber', 'rating': 2}.
Friends only send a song to the judge if its rating is at least 1.
def friends(songs, judge):
for song in songs:
try:
if song["rating"] > 1:
judge.send(song)
except StopIteration:
break
judge.close()The playlist is the consumer and takes in no arguments.
Once we send the list of songs to the playlist, it checks to see if
a minimum threshold has been met. If we close this coroutine before
creating a good playlist, it will print an error.
def playlist():
good_playlist = False
threshold = 15
while True:
try:
tammys_slappers = yield
print('Playlist created.')
total = sum([i[1] for i in tammys_slappers])
good_playlist = total >= threshold
except GeneratorExit:
if not good_playlist:
print('There were not enough slappers on the playlist. Try again.')
raiseImplement the filter, judge. This function will take in just one argument,
the next coroutine, and do the following:
- Receive a song using a
yield. - Create a list where each element is a list containing the song name and rating.
- Add a song to the list if it meets the criteria: if the artist is on the list of approved artists OR if the rating exceeds the
min_rating - Send the list of songs to
playlistif there are at least 5 songs. - If the coroutine is closed print
'The judge is done'
def judge(playlist):
"""
>>> bad_playlist = playlist()
>>> next(bad_playlist)
>>> tammy = judge(bad_playlist)
>>> next(tammy)
>>> friends([{'name': 'shake it off', 'artist': 'swift', 'rating': 20}], tammy)
The judge is done
There were not enough slappers on the playlist. Try again.
>>> good_playlist = playlist()
>>> next(good_playlist)
>>> tammy = judge(good_playlist)
>>> next(tammy)
>>> friends([{'name': 'one dance', 'artist': 'drake', 'rating': 5}, \
{'name': 'treat you better', 'artist': 'mendes', 'rating': 1000}, \
{'name': 'hello', 'artist': 'adele', 'rating': 20} \
], tammy)
Playlist created.
The judge is done
"""
total_songs = 3
songs = []
artists = ['gucci', 'drake', 'bieber']
min_rating = 2
"*** YOUR CODE HERE ***"
while True:
try:
song = yield
except GeneratorExit:
print('The judge is done')
playlist.close()
raise
for artist in artists:
if artist in song['artist']:
songs += [[song['name'], song['rating']]]
if not [song['name'], song['rating']] in songs:
if song['rating'] > min_rating:
songs += [[song['name'], song['rating']]]
if len(songs) == total_songs:
playlist.send(songs)Use OK to test your code:
python3 ok -q judge