Assignment 3 (Python)

CptS355 - Assignment 3 (Python)

Python Warm-up

Weight: This assignment will count for 6% of your final grade.
This assignment is to be your own work. Refer to the course academic integrity statement in the
syllabus.
Turning in your assignment
All the problem solutions should be placed in a single file named HW3.py.When you are done and
certain that everything is working correctly, turn in your file by uploading on the Assignment-3(Python)
DROPBOX on Blackboard (under AssignmentSubmisions menu). The file that you upload must be named
HW3.py. You may turn in your assignment up to 4 times. Only the last one submitted will be graded.
Implement your code for Python3.
At the top of the file in a comment, please include your name and the names of the students with
whom you discussed any of the problems in this homework. This is an individual assignment and the
final writing in the submitted file should be *solely yours*. You may NOT copy another student’s code or
work together on writing code. You may not copy code from the web, or anything else that lets you
avoid solving the problems for yourself.
Grading
The assignment will be marked for good programming style (appropriate algorithms, good indentation
and appropriate comments -- refer to the Python style guide) -- as well as thoroughness of testing and
clean and correct execution. You will lose points if you don’t (1) provide test functions / additional test
cases, (2) explain your code with appropriate comments, and (3) follow a good programming style. For
each problem below, around 10% of the points will be reserved for the test functions and the
programming style.
- Good python style favors for loops rather than while loops (when possible).
- Also, code to do the same thing (or something easily parameterizable) at different points in a
program should not be duplicated but extracted into a callable function.
- Turning in "final" code that produces debugging output is bad form, and points may be deducted if
you have extensive debugging output. We suggest you the following:
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”)
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 - busStops(b) – 15%
Pullman Transit offers many bus routes in Pullman. Assume that they maintain the bus stops for
their routes as a dictionary. The keys in the dictionary are the bus routes and the values are the
stops for the bus routes (see below for an example).
buses = {
"Lentil": ["Chinook", "Orchard", "Valley", "Emerald","Providence",
"Stadium", "Main", "Arbor", "Sunnyside", "Fountain", "Crestview",
"Wheatland", "Walmart", "Bishop", "Derby", "Dilke"],
"Wheat": ["Chinook", "Orchard", "Valley", "Maple","Aspen", "TerreView",
"Clay", "Dismores", "Martin", "Bishop", "Walmart", "PorchLight",
"Campus"],
"Silver": ["TransferStation", "PorchLight", "Stadium",
"Bishop","Walmart", "Shopco", "RockeyWay"],
"Blue": ["TransferStation", "State", "Larry", "TerreView","Grand",
"TacoBell", "Chinook", "Library"],
"Gray": ["TransferStation", "Wawawai", "Main", "Sunnyside","Crestview",
"CityHall", "Stadium", "Colorado"]
}
Write a function busStops that takes a dictionary mapping bus routes to bus stops (as shown
above) and returns another dictionary mapping bus stops to list of bus routes which stop at that
stop. The route list for each stop should be alphabetically sorted. For example:
busStops(buses) returns
{'Chinook': ['Blue', 'Lentil', 'Wheat'], 'Orchard': ['Lentil',
'Wheat'], 'Valley': ['Lentil', 'Wheat'], 'Emerald': ['Lentil'],
'Providence': ['Lentil'], 'Stadium': ['Gray', 'Lentil', 'Silver'],
'Main': ['Gray', 'Lentil'], 'Arbor': ['Lentil'], 'Sunnyside': ['Gray',
'Lentil'], 'Fountain': ['Lentil'], 'Crestview': ['Gray', 'Lentil'],
'Wheatland': ['Lentil'], 'Walmart': ['Lentil', 'Silver', 'Wheat'],
'Bishop': ['Lentil', 'Silver', 'Wheat'], 'Derby': ['Lentil'], 'Dilke':
['Lentil'], 'Maple': ['Wheat'], 'Aspen': ['Wheat'], 'TerreView':
['Blue', 'Wheat'], 'Clay': ['Wheat'], 'Dismores': ['Wheat'], 'Martin':
['Wheat'], 'PorchLight': ['Silver', 'Wheat'], 'Campus': ['Wheat'],
'TransferStation': ['Blue', 'Gray', 'Silver'], 'Shopco': ['Silver'],
'RockeyWay': ['Silver'], 'State': ['Blue'], 'Larry': ['Blue'], 'Grand':
['Blue'], 'TacoBell': ['Blue'], 'Library': ['Blue'], 'Wawawai':
['Gray'], 'CityHall': ['Gray'], 'Colorado': ['Gray']}
You should not hardcode route names and the bus stop names in your function.
You can start with the following code:
def busStops(b):
#write your code here
def testbusStops():
#write your code here
2. (Dictionaries)
a) addDict(d) – 10%
Assume you keep track of the number of hours you study every day for each of the courses you
are enrolled in. You maintain the weekly log of your hours in a Python dictionary as follows:
{'Mon':{'355':2,'451':1,'360':2},'Tue':{'451':2,'360':3},
'Thu':{'355':3,'451':2,'360':3}, 'Fri':{'355':2},
'Sun':{'355':1,'451':3,'360':1}}
The keys of the dictionary are the days you studied and the values are the dictionaries which
include the number of hours for each of the courses you studied. Please note that you may not
study for some courses on some days OR you may not study at all on some days of the week.
Define a function, addDict(d) which adds up the number of hours you studied for each of
the courses during the week and returns the summed values as a dictionary. Note that the keys
in the resulting dictionary should be the course names and the values should be the total
number of hours you have studied for the corresponding courses. addDict would return the
following for the above dictionary: {'355': 8, '451': 8, '360': 9}
(Important note: Your function should not hardcode the course numbers and days of the week. It should
simply iterate over the keys that appear in the given dictionary and should work on any dictionary with
arbitrary course numbers and days of the week)
(Important note: When we say a function returns a value, it doesn’t mean that it prints the value. Please
pay attention to the difference.)
Define a function testaddDict() that tests your addDict(d) function, returning True if
the code passes your tests, and False if the tests fail. You can start with the following code:
def addDict(d):
#write your code here
def testaddDict():
#write your code here
b) addDictN(L) – 10%
Now assume that you kept the log of number of hours you studied for each week on each class
throughout the semester and stored that data as a list of dictionaries. This list includes a
dictionary for each week you recorded your log. Assuming you kept the log for N weeks, your list
will include N dictionaries.
Define a function addDictN which takes a list of weekly log dictionaries and returns a
dictionary which includes the total number of hours that you have studied for your enrolled
courses throughout the semester. Your function definition should use the Python map and
reduce functions as well as the addDict function you defined in part(a). You may need to
define an additional helper function.
Example:
Assume you have recorded your log for 3 weeks only.
[{'Mon':{'355':2,'360':2},'Tue':{'451':2,'360':3},'Thu':{'360':3},
'Fri':{'355':2}, 'Sun':{'355':1}},
{'Tue':{'360':2},'Wed':{'355':2},'Fri':{'360':3, '355':1}},
{'Mon':{'360':5},'Wed':{'451':4},'Thu':{'355':3},'Fri':{'360':6},
'Sun':{'355':5}}]
For the above dictionary addDictN will return:
{'355': 16, '360': 24, '451': 6}
(The items in the dictionary can have arbitrary order.)
You can start with the following code:
def addDictN(L):
#write your code here
def testaddDictN():
#write your code here
3. Dictionaries and lists
a) searchDicts(L,k)– 5%
Write a function searchDicts that takes a list of dictionaries L and a key k as input and
checks each dictionary in L starting from the end of the list. If k appears in a dictionary,
searchDicts returns the value for key k. If k appears in more than one dictionary, it will
return the one that it finds first (closer to the end of the list).
For example:
L1 = [{"x":1,"y":True,"z":"found"},{"x":2},{"y":False}]
searchDicts(L1,"x") returns 2
searchDicts(L1,"y") returns False
searchDicts(L1,"z") returns "found"
searchDicts(L1,"t") returns None
You can start with the following code:
def searchDicts(L,k):
#write your code here
def testsearchDicts():
#write your code here
b) searchDicts2(tL,k) – 10%
Write a function searchDicts2 that takes a list of tuples (tL) and a key k as input. Each
tuple in the input list includes an integer index value and a dictionary. The index in each tuple
represent a link to another tuple in the list (e.g. index 3 refers to the 4th tuple, i.e., the tuple at
index 3 in the list) searchDicts2 checks the dictionary in each tuple in tL starting from the
end of the list and following the indexes specified in the tuples.
For example, assume the following:
[(0,d0),(0,d1),(0,d2),(1,d3),(2,d4),(3,d5),(5,d6)]
0 1 2 3 4 5 6
The searchDicts2 function will check the dictionaries d6,d5,d3,d1,d0 in order (it will
skip over d4 and d2) The tuple in the beginning of the list will always have index 0.
It will return the first value found for key k. If k is couldn’t be found in any dictionary, then it
will return None.
For example:
L2 = [(0,{"x":0,"y":True,"z":"zero"}),
(0,{"x":1}),
(1,{"y":False}),
(1,{"x":3, "z":"three"}),
(2,{})]
searchDicts2 (L2,"x") returns 1
searchDicts2 (L2,"y") returns False
searchDicts2 (L2,"z") returns "zero"
searchDicts2 (L2,"t") returns None
(Note: I suggest you to provide a recursive solution to this problem.
Hint: Define a helper function with an additional parameter that hold the list index which will be
searched in the next recursive call.)
You can start with the following code:
def searchDicts2(L,k):
#write your code here
def testsearchDicts2():
#write your code here
4. (Lists) subsets – 20%
Write a function subsets , which takes a list, L, as input and returns a list of lists, each of the
sublists being one of the 2
length(L) subsets of L. The subsets should appear in increasing length.
You may assume that all of the elements of the original list are distinct.
(Hint: Try solving this using recursion and map function.)
For example:
subsets ([1,2,3])
returns [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
subsets([(1,"one"),(2,"two")])
returns [[],[(1,"one")],[(2,"two")],[(1,"one"),(2,"two")]]
subsets([])
returns [[]]
You can start with the following code:
def subsets(L):
#write your code here
def testsubsets():
#write your code here
5. (Recursion) numPaths(m,n) – 10%
Consider a robot in a MxN grid who is only capable of moving right or down in the grid. The
robot starts at the top left corner, (0,0), and is supposed to reach to the bottom right corner,
(M-1,N-1). Write a function numPaths that takes the grid length and width (i.e., M, N) as
argument and returns the number of different paths the robot can take from the start to the
goal. Give and answer using recursion. (A correct solution without recursion will worth half the
points.)
start

end

For example, the 2x2 grid has a total of two ways for the robot to move from the start to the
goal. For the 3x3 grid, the robot has 6 different paths (only 3 are shown above).
numPaths(2,2) returns 2
numPaths(3,3) returns 6
numPaths(4,5) returns 35
You can start with the following code:
def numPaths(m,n):
#write your code here
def testnumPaths():
#write your code here
6. Iterators
a) iterPrimes()– 10%
Create an iterator that represents the sequence of prime numbers starting at 2.
For example:
primes = iterPrimes()
primes.__next__()
2
primes.__next__()
3
primes.__next__()
5
You can start with the following code:
class iterPrimes():
#write your code here
b) numbersToSum(iNumbers,sum) – 10%
Define a function numbersToSum that takes an iterator “iNumbers” (representing a
sequence of positive integers) and a positive integer value sum, and returns the next n elements
from iNumbers such that the next n elements of the iterator add to less than sum, but the
next (n + 1) elements of the iterator add to sum or more. numbersToSum should return a
list of integers. (Note: Your implementation of numbersToSum doesn’t need to be recursive.
You can’t assume a minimum value for sum. Note that the iterator retrieves the next element in
the sequence in the second call to numbersToSum.)
start
end
For example:
primes = iterPrimes()
numbersToSum(primes,58)
[2, 3, 5, 7, 11, 13]
numbersToSum(primes,100)
[17, 19, 23, 29]
You can start with the following code:
def numbersToSum(iNumbers,sum):
#write your code here
def testnumbersToSum():
#write your code here; see the sample test function below
Test your code:
Here is an example test function for testing numbersToSum. Make sure to include 2 test cases for
each function.
# function to test numbersToSum
# return True if successful, False if any test fails
def testnumbersToSum():
primes = iterPrimes()
if numbersToSum(primes, 58) != [2, 3, 5, 7, 11, 13]:
return False
if numbersToSum(primes, 100) != [17, 19, 23, 29]:
return False
return True
You don’t need to provide a test function for 6(a) – iterPrimes. You should write test functions for
all other problems.
Go on writing test code for ALL of your code here; think about edge cases, and other points where you
are likely to make a mistake.
Main Program
So far we've just defined a bunch of functions in our HW3.py program. To actually execute the code, we
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...
For this assignment, we want to run all the tests, so your main should look like:
testFunctions = {"busStops":testbusStops, "addDict": testaddDict,
"addDictN": testaddDictN, "searchDicts": testsearchDicts, "searchDicts2":
testsearchDicts2, "subsets":testsubsets, "numPaths": testnumPaths,
"numbersToSum":testnumbersToSum }
if __name__ == '__main__':
for testName,testFunc in testFunctions.items():
print(testName,': ',testFunc())
print('---------------------')