Homework 3
Due by 11:59pm on Tuesday, 2/14
Instructions
Download hw03.zip.
Submission: When you are done, submit with
python3 ok --submit
.
You may submit more than once before the deadline; only the final submission
will be scored. Check that you have successfully submitted your code on
okpy.org.
See Lab 0
for more instructions on submitting assignments.
Using OK: If you have any questions about using OK, please refer to this guide.
Readings: You might find the following references useful:
Vitamins
Vitamin questions must be completed alone.
Question 1: Extending Rationals
Starting with the rational ADT from lecture, implement the
two additional functions div_rat(x,y)
, which divides rational number x
by
y
, and lt_rat(x, y)
, which returns True iff rational number x
is
less than rational y
.
Use OK to test your code:
python3 ok -q div_rat
python3 ok -q lt_rat
Question 2: Has Seven
Write a function has_seven
that takes a positive integer n
and
returns whether n
contains the digit 7. Do not use any assignment
statements - use recursion instead:
def has_seven(k):
"""Returns True if at least one of the digits of k is a 7, False otherwise.
>>> has_seven(3)
False
>>> has_seven(7)
True
>>> has_seven(2734)
True
>>> has_seven(2634)
False
>>> has_seven(734)
True
>>> has_seven(7777)
True
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q has_seven
Required questions
You may choose to work with a partner on homework questions, but you must submit your own solution. That is, try to share ideas rather than code.
Recursion
Question 3: Ping pong
The ping-pong sequence counts up starting from 1 and is always either counting
up or counting down. At element k
, the direction switches if k
is a
multiple of 7 or contains the digit 7. The first 30 elements of the ping-pong
sequence are listed below, with direction swaps marked using brackets at the
7th, 14th, 17th, 21st, 27th, and 28th elements:
1 2 3 4 5 6 [7] 6 5 4 3 2 1 [0] 1 2 [3] 2 1 0 [-1] 0 1 2 3 4 [5] [4] 5 6
Implement a function pingpong
that returns the nth element of the
ping-pong sequence. Do not use any assignment statements; however, you
may use def
statements.
Hint: If you're stuck, try implementing
pingpong
first using assignment and awhile
statement. Any name that changes value will become an argument to a function in the recursive definition.
def pingpong(n):
"""Return the nth element of the ping-pong sequence.
>>> pingpong(7)
7
>>> pingpong(8)
6
>>> pingpong(15)
1
>>> pingpong(21)
-1
>>> pingpong(22)
0
>>> pingpong(30)
6
>>> pingpong(68)
2
>>> pingpong(69)
1
>>> pingpong(70)
0
>>> pingpong(71)
1
>>> pingpong(72)
0
>>> pingpong(100)
2
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
True
"""
"*** YOUR CODE HERE ***"
You may use the function has_seven
, which returns True if a number k
contains the digit 7 at least once.
Use OK to test your code:
python3 ok -q pingpong
Linked Lists
These problems use a slight variation of the rlist
abstraction used in
lecture for linked lists. Specifically, they use the function link
in place of
make_rlist
, and the variable empty
in place of empty_rlist
.
Question 4: Change
Write a function that takes in a linked list, lst
, and two elements,
s
and t
. The function returns a copy of lst but with all instances of s
replaced with t
.
def change(lst, s, t):
"""Returns a link matching lst but with all instances of s (if any)
replaced by t.
>>> lst = link(1, link(2, link(3)))
>>> new = change(lst, 3, 1)
>>> print_link(new)
1 2 1
>>> newer = change(new, 1, 2)
>>> print_link(newer)
2 2 2
>>> newest = change(newer, 5, 1)
>>> print_link(newest)
2 2 2
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q change
Question 5: Insert-at-end
Write a function that returns a new linked list that is the same as
lst
with elem
added at the end.
def insert_at_end(lst, elem):
"""Return a linked list that is the same as lst with elem added
at the end.
>>> lst1 = insert_at_end(empty, 1)
>>> print_link(lst1)
1
>>> lst2 = insert_at_end(lst1, 2)
>>> print_link(lst2)
1 2
>>> lst3 = insert_at_end(lst2, 3)
>>> print_link(lst3)
1 2 3
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q insert_at_end
Question 6: Deep Linked List Length
A linked list that contains as elements one or more linked lists (each of which is
also possibly deep) is called a
deep linked list. For this problem, assume that each list item
(i.e., value returned by first
) is either an integer or a linked list.
Write a function deep_len
that takes in such a (possibly deep)
linked list and returns the deep length of that linked list, which is
the total number of integers contained in the deep list. To test if
a value v
is an integer, you can use type(v) is int
.
def deep_len(lnk):
""" Returns the deep length of a possibly deep linked list of integers.
>>> deep_len(link(1, link(2, link(3, empty))))
3
>>> deep_len(link(link(1, link(2, empty)), link(3, link(4, empty))))
4
>>> deep_len(link(link(link(1, link(2, empty)), \
link(3, empty)), link(link(4, empty), link(5, empty))))
5
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q deep_len
Python Sequences
Question 7: Flatten
Write a function flatten
that takes a (possibly deep) list and "flattens" it.
For example:
>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]
Hint: you can check if something is a list by using the built-in
type
function. For example,
>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
def flatten(lst):
"""Returns a flattened version of lst.
>>> flatten([1, 2, 3]) # normal list
[1, 2, 3]
>>> x = [1, [2, 3], 4] # deep list
>>> flatten(x)
[1, 2, 3, 4]
>>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> flatten(x)
[1, 1, 1, 1, 1, 1]
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q flatten
Question 8: Riffle Shuffle
The familiar riffle shuffle of a deck of cards (or in our case, of a sequence of things) results in a new configuration of cards in which the original top card is followed by the original middle card, then by the original second card, then the card after the middle, and so forth. Assuming the deck (sequence) contains an even number of cards, write a list comprehension that produces the shuffled sequence.
Hint: To write this as a single comprehension, you may find the expression
k%2
, which evaluates to 0 on even numbers and 1 on odd numbers, to be useful.
def riffle(deck):
"""Produces a single, perfect riffle shuffle of DECK, consisting of
DECK[0], DECK[M], DECK[1], DECK[M+1], ... where M is position of the
second half of the deck. Assume that len(DECK) is even.
>>> riffle([3, 4, 5, 6])
[3, 5, 4, 6]
>>> riffle(range(20))
[0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19]
"""
"*** YOUR CODE HERE ***"
return _______
Use OK to test your code:
python3 ok -q riffle
Trees
Question 9: Build ones
Define the function build_binary_ones
, which takes in a height, h
,
as an argument
and returns a new tree whose labels are all 1,
with two branches at each inner (non-leaf) node, and whose height is h
(a tree of height 0 has a single node with label 1.)
Then, write a function build_ones
, which takes in a height as before but now
a branching factor as well. We want to be able to generalize from just two
branches per node to a specified number of branches per node.
You will find the tree abstraction you should use included in the .py
file.
def build_binary_ones(h):
"""
>>> print_tree(build_binary_ones(1))
1
1
1
>>> print_tree(build_binary_ones(2))
1
1
1
1
1
1
1
"""
"*** YOUR CODE HERE ***"
def build_ones(h, branching_factor=2):
"""
>>> print_tree(build_ones(2))
1
1
1
1
1
1
1
>>> print_tree(build_ones(3, 1))
1
1
1
1
"""
"*** YOUR CODE HERE ***"
There are even more ways to generalize this operation! We can determine which number is used to build the tree, e.g. 0. We can also provide a list of branching factors instead of using just one. The list goes on...
Use OK to test your code:
python3 ok -q build_binary_ones
python3 ok -q build_ones