Write all of your Python code for this assignment in a single file named lab1.py. You may use any development environment you want, as long as you submit the Python source file on Canvas. You should have three functions, followed by the main program at the bottom: # Problem 1 def is_multisubset(A, B): # Your code here # Problem 2 def read_parts_list(filename): # Your code here # Problem 3 def get_missing_parts(goal, inventory): # Your code here # Problem 4 # Your code here Your code for this assignment must use dictionaries as described. No credit will be given for importing modules specifically designed to work with multisets. A multiset is a set-like collection that allows the same element to be repeated. The number of times that an element appears in a multiset is the multiplicity of that element. If an element does not appear in a multiset, its multiplicity is 0. For example, in the multiset A= {13,8,13,8,8,9}, 1

8 has a multiplicity of 3. 9 has a multiplicity of 1. 13 has a multiplicity of 2. 42 has a multiplicity of 0. Given two multisets Aand B, Ais a multisubset of B(denoted using the same symbol for subset, A B) if the multiplicities of all elements in Aare less than or equal to the multiplicities of those elements in B. A multiset can be conveniently stored in Python as a dictionary, where the keys are the elements and the values are positive integers representing the multiplicities of those elements. For example, for the multiset Adefined above: A = {8: 3, 9: 1, 13: 2} 1. (6 points) Write a function is multisubset(A, B) that returns whether or not1 Ais a multi- subset of B. You may assume that both parameters are dictionaries as described above. 2. (8 points) Heres a fun application of multisets: LEGO! Multisets can be used to represent collections of LEGO parts. Each type of part is assigned a unique ID, which serves as the keys in the dictionary. The values in the dictionary are how many of that part exist in the collection. Ive provided several text files describing collections of LEGO parts. Each line of each file consists of a part ID, followed by one space and then how many of that part exists in the collection. The part IDs are based on actual IDs and color codes used on www.bricklink.com. Write a function read parts list(filename) that reads a file formatted like the ones above, returning a multiset in dictionary representation. Note that a part ID may appear more than once in a single file. If this occurs, the dictionary should combine the values together into a single key. For example, suppose you have a file named sample.txt that contains these lines: 6541-11 4 3070b-11 1 22484-85 2 3070b-11 5 6541-11 1 3070b-11 4 Then calling read parts list(sample.txt) should return a dictionary that looks something like this: {6541-11: 5, 3070b-11: 10, 22484-85: 2} 1The function must return a bool value, either True or False.

Python note: Heres an easy way to read a file in Python: with open(filename.txt) as f: content = f.read().splitlines() # content is a list of strings. Each element of content contains one line of # the file, *without* the ending line break. 3. (8 points) Suppose you have an inventory of LEGO parts, and you want to determine if you have the right parts to build a certain goal model. Write a function get missing parts(goal, inventory) that returns a dictionary containing all extra parts that need to be added to inventory to build the goal. If no extra parts are needed (i.e., if goal is a multisubset of inventory), the function returns an empty dictionary. You may assume that goal and inventory are dictionaries as described earlier. The returned dictionary should be built the same way. 4. (3 points) Below your function definitions, write a program that performs the following: Call read parts list on each of the text files provided with the assignment. Store the returned dictionaries into variables named parts1 through parts6. Verify the following by calling the appropriate functions and printing their return values: parts1 is not a multisubset of parts2 parts1 is a multisubset of parts3 parts2 is a multisubset of parts3 parts3 is a multisubset of itself parts3 is not a multisubset of parts1 parts3 is not a multisubset of parts2 parts6 is a multisubset of parts4 parts6 is not a multisubset of parts5 get missing parts(parts3, parts3) returns an empty dictionary get missing parts(parts6, parts4) returns an empty dictionary get missing parts(parts6, parts5) returns a dictionary with the following key- value pairs: 48336-115: 1, 3003-86: 3, 4286-155: 18, 54200-12: 10