Assignment
Python
Rename the HW3SampleTests.py file as HW3Tests.py and add your own test cases in this file. You
are expected to add one more test case for each problem. Choose test inputs different than those
provided in the assignment prompt.
o Near the top of your program write a debug function that can be turned on and off by changing a
single variable. For example,
debugging = True
def debug(*s):
if debugging:
print(*s)
o Where you want to produce debugging output use:
debug(”This is my debugging output”,x,y)
instead of print.
(How it works: Using * in front of the parameter of a function means that a variable number of arguments can be
passed to that parameter. Then using *s as print’s argument passes along those arguments to print.)
Problems:
1. (Dictionaries)
a) organizebyFlavor(feedingLog) – 15%
Consider the cat feeding log data you used in HW1 and HW2 . We re-format the same data as a
Python dictionary where keys are the timestamps (month, year pairs) and values are the feeding
logs.
Assume, you would like to re-organize the data and create a dictionary that includes flavors as keys
and the timestamps and number of cans you fed to your cat as values. For example, when you
organize the above dictionary you will get the following:
Define a function organizebyFlavor that organizes the feeding log data as described above. Your
function should not hardcode the cat food flavors and timestamps.
(The items in the output dictionary can have arbitrary order.)
You can start with the following code:
def organizebyFlavor(feedingLog):
#write your code here
b) popularFlavor(feedingLog) – 15%
Assume, you would like to find your cat’s most popular canned food flavor, i.e., the flavor that has
the max total number of cans. Define a function “popularFlavor” that will return the popular
flavor and its total can count. For example:
popularFlavor(myCatsLog) returns ('Chicken', 37)
#i.e., chicken has the max number of total cans among all food flavors,
which is 37.
Your function definition should not use loops or recursion but use the Python map and reduce
functions. You can also use the organizebyFlavor function you defined in part(a). You may
define and call helper (or anonymous) functions, however your helper functions should not use
loops or recursion. If you are using reduce, make sure to import it from functools.
myCatsLog =
{(7,2020):{"Oceanfish":7, "Tuna":1, "Whitefish":3, "Chicken":4, "Beef":2},
(8,2020):{"Oceanfish":6, "Tuna":2, "Whitefish":1, "Salmon":3, "Chicken":6},
(9,2020):{"Tuna":3, "Whitefish":3, "Salmon":2, "Chicken":5, "Beef":2, "Turkey":1, "Sardines":1},
(10,2020):{"Whitefish":5, "Sardines":3, "Chicken":7, "Beef":3},
(11,2020):{"Oceanfish":3, "Tuna":2, "Whitefish":2, "Salmon":2, "Chicken":4, "Beef":2, "Turkey":1},
(12,2020):{"Tuna":2, "Whitefish":2, "Salmon":2, "Chicken":4, "Beef":2, "Turkey":4, "Sardines":1},
(1,2021):{"Chicken":7,"Beef":3, "Turkey":4, "Whitefish":1, "Sardines":2} }
{'Beef': {(7,2020): 2, (9,2020): 2, (10,2020): 3, (11,2020): 2, (12,2020): 2, (1,2021): 3},
'Chicken': {(7,2020): 4, (8,2020): 6, (9,2020): 5, (10, 2020): 7,(11, 2020): 4,(12,2020): 4,(1,2021):7},
'Oceanfish': {(7,2020): 7, (8,2020): 6, (11,2020): 3},
'Salmon': {(8, 2020): 3, (9, 2020): 2, (11, 2020): 2, (12, 2020): 2},
'Sardines': {(9, 2020): 1, (10, 2020): 3, (12, 2020): 1, (1, 2021): 2},
'Tuna': {(7, 2020): 1, (8, 2020): 2, (9, 2020): 3, (11, 2020): 2, (12, 2020): 2},
'Turkey': {(9, 2020): 1, (11, 2020): 1, (12, 2020): 4, (1, 2021): 4},
'Whitefish': {(7,2020):3, (8,2020):1, (9,2020):3, (10,2020):5, (11,2020):2, (12,2020): 2, (1,2021): 1}}
2. (Lists) unzip(L) – 15%
Write a function unzip that calculates the reverse of the zip operation. unzip takes a list of 3-
tuples as input and returns a tuple of lists, where each list includes the first, second, or third
elements from input tuples, respectively. Give a solution using higher order functions (map,
reduce or filter), without using loops.
For example:
unzip ([(1,"a",10),(2,"b",11),(3,"c",12),(4,"d",13)])
returns
([1, 2, 3, 4], ['a', 'b', 'c', 'd'], [10, 11, 12, 13])
You can start with the following code:
def unzip(L):
#write your code here
3. findCycle(graph,start)– 15%
Consider the following directed graph where each node has at most one outgoing edge. Assume the
graph nodes are assigned unique labels. The edges of this graph can be represented as a Python
dictionary where the keys are the starting nodes of the edges and the values are the ending nodes.
Note that some nodes in the graph are halting nodes, i.e., they don’t have any outgoing edges.
Those nodes are marked with double lines in the graph.
{'A':'B','B':'D','C':'G','D':'E','E':'C','F':'I','G':'B','H':None,'I':'H'}
Write a recursive function, findCycle, which takes a graph dictionary and a starting node as input
and returns the sequence of nodes that form a cycle in the graph. It returns the first cycle that exists
in the path beginning at node “start”. The function returns the list of the cycle node labels where
the starting node of the cycle should be included both in the beginning and at the end. If the graph
doesn’t have any cycles, it returns None.
You may define helper functions to implement your solution. Either your findCycle function or
your helper should be recursive.
For example:
graph = {'A':'B','B':'D','C':'G','D':'E','E':'C','F':'I','G':'B','H':None,'I':'H'}
findCycle(graph,'A') returns ['B', 'D', 'E', 'C', 'G', 'B']
findCycle(graph,'F') returns None
A B C D E F G H I
You can start with the following code:
def findCycle(graph,start):
#write your code here
4. Generators
getNextNode(graph,start) – 10%
Write a generator function, getNextNode, which will generate an iterator for the given graph
dictionary -- similar to the one we defined in problem-4. The generator will be initialized with the graph
dictionary and the starting node label, and it will return the sequence of the node labels in the graph
one at a time.
For example:
graph= {'A':'B','B':'D','C':'G','D':'E','E':'C','F':'I','G':'B','H':None,'I':'H'}
graph_nodes = getNextNode(graph,'A')
graph_nodes.__next__() # returns 'A'
graph_nodes.__next__() # returns 'B'
L = []
for i in range(0,15):
L.append(graph_nodes.__next__())
print(L) #L is ['D','E','C','G','B','D','E','C','G','B','D','E','C','G','B']
You can start with the following code:
def getNextNode(graph,start):
#write your code here
5. Iterators
DecodeIter()– 25%
Create an iterator that represents the decoded sequence of words from an encoded string. The iterator
will be initialized with a dictionary “ttable” (for decoding characters) and an input string (“input”).
When the iterator’s __next__() method is called, it will retrieve the next word from the input,
decode it using the ttable, and return it. The iterator should stop when it reaches the end of the input
string. Decoding a word involves looking up the characters in the ttable and replacing them with
retrieved values. If a character can’t be found in the dictionary, it should be included as it is.
Note that your iterator should not split the complete string input into words and then return those
words one at a time. It should retrieve the next word from the string only when the __next__() call is
made. The “input” can be an iterator representing an infinite sequence of characters. (See the second
test for DecodeIter in HW3SampleTests.py.
ttable = {'C':'A', 'D':'B', 'E':'C', 'F':'D', 'G':'E', 'H':'F', 'I':'G', 'J':'H', 'K'
:'I', 'L':'J', 'M':'K', 'N':'L', 'O':'M', 'P':'N', 'Q':'O', 'R':'P', 'S':'Q', 'T':'R'
, 'U':'S', 'V':'T', 'W':'U', 'X':'V', 'Y':'W', 'Z':'X', '[':'Y', '\\':'Z', 'c':'a', '
d':'b', 'e':'c', 'f':'d', 'g':'e', 'h':'f', 'i':'g', 'j':'h', 'k':'i', 'l':'j', 'm':'
k', 'n':'l', 'o':'m', 'p':'n', 'q':'o', 'r':'p', 's':'q', 't':'r', 'u':'s', 'v':'t',
'w':'u', 'x':'v', 'y':'w', 'z':'x', '{':'y', '|':'z', '2':'0', '3':'1', '4':'2', '5':
'3', '6':'4', '7':'5', '8':'6', '9':'7', ':':'8', ';':'9'}
strInput = "R{vjqp ku cp gcu{ vq ngctp, rqygthwn rtqitcookpi ncpiwcig. Kv jcu ghhkekg
pv jkij-ngxgn fcvc uvtwevwtgu cpf c ukorng dwv ghhgevkxg crrtqcej vq qdlgev qtkgpvgfrtqitcookpi.
R{vjqp'u gngicpv u{pvcz cpf f{pcoke v{rkpi, vqigvjgt ykvj kvu kpvgtrtgvg
f pcvwtg, ocmg kv cp kfgcn ncpiwcig hqt uetkrvkpi cpf tcrkf crrnkecvkqp fgxgnqrogpv k
p ocp{ ctgcu qp oquv rncvhqtou."
For example:
'R{vjqp' is decoded to 'Python'
' jkij-ngxgn' is decoded to 'high-level'
words = DecodeIter(ttable,strInput)
words.__next__() # returns 'Python'
words.__next__() # returns 'is'
words.__next__() # returns 'an'
words.__next__() # returns 'easy'
L = []
for w in words:
L.append(w)
if w == 'language.': break
# L is ['to', 'learn,', 'powerful', 'programming', 'language.']
You can start with the following code:
class DecodeIter ():
# write your code here
Testing your functions (5%)
We will be using the unittest Python testing framework in this assignment. See
https://docs.python.org/3/library/unittest.html for additional documentation.
The file HW3SampleTests.py provides some sample test cases comparing the actual output with the
expected (correct) output for some problems. This file imports the HW3 module (HW3.py file) which
will include your implementations of the given problems.
Rename the HW3SampleTests.py file as HW3Tests.py and add your own test cases in this file. You
are expected to add at least one more test case for each problem. Make sure that your test inputs cover
all boundary cases. Choose test input different than those provided in the assignment prompt.
In Python unittest framework, each test function has a “test_” prefix. To run all tests, execute the
following command on the command line.
python -m unittest HW3SampleTests
You can run tests with more detail (higher verbosity) by passing in the -v flag:
python -m unittest -v HW3SampleTests
If you don’t add new test cases you will be deduced at least 5% in this homework.
In this assignment, we simply write some unit tests to verify and validate the functions. If you would like
to execute the code, you need to write the code for the "main" program. Unlike in C or Java, this is not
done by writing a function with a special name. Instead the following idiom is used. This code is to be
written at the left margin of your input file (or at the same level as the def lines if you've indented
those.
if __name__ == '__main__':
...code to do whatever you want done...