Starter Files

Download Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.


This lab will not be graded. You do not need to submit anything.

Object Oriented Programming

  • Starter code for Question 1 is in

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
    >>> k.typing([0, 1])
    >>> k.typing([1, 0])
    >>> b1.pressed
    >>> b2.pressed

    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: return accumulate
class Button: def __init__(self, pos, key): self.pos = pos self.key = key self.pressed = 0

Use OK to test your code:

python3 ok -q Keyboard

Recursive Objects

  • Starter code for Question 2 and 3 is in

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
>>> is Link.empty

If s contains fewer than two elements, s remains unchanged.

Do not return anything! every_other should 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
"*** YOUR CODE HERE ***"
if s is Link.empty or is Link.empty: return else: = every_other(

Use OK to test your code:

python3 ok -q every_other

Question 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 paths

Use OK to test your code:

python3 ok -q long_paths


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

Right fold

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)

Left fold

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)
(if (null? lst) init (foldl fn (fn init (car lst)) (cdr lst)))

Use OK to test your code:

python3 ok -q foldl

Question 5: Foldr

Now write the right fold function.

(define (foldr fn init lst)
(if (null? lst) init (fn (car lst) (foldr fn init (cdr lst))))

Use OK to test your code:

python3 ok -q foldr

Now 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)
(foldr (lambda (x xs) (cons (fn x) xs)) nil lst)

Use OK to test your code:

python3 ok -q map

Question 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 tally


  • 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)'])))
>>> read_tail(Buffer(tokenize_lines(['. 5)'])))

Question 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 calls


  • 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 ())))))

(fact (nest () ())) (fact (nest (?a . ?rest) (?a ?nested)) (nest ?rest ?nested))

Use OK to test your code:

python3 ok -q nest

Question 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))

(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: elderberry

Question 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))

(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 fruits

Generators and Coroutines

  • Starter code for Questions 13 and 14 is in

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))
"*** 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_generator

Question 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:
            if song["rating"] > 1:
        except StopIteration:

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:
            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.')

Implement 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 playlist if 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