Container Class
Problem 1 Container objects. This problem has two parts. In the first part, you will implement a class called Container. In the second part (described below), you will implement some functions with containers as parameters. You are provided a test file called testcontainer.py to test your code for this problem, which you can do by typing python3 testcontainer.py at the command line.
A Container object is an object that stores an unordered collection of items. You will implement this class in a module called problem1a.py. An item may occur several times in a container. Note that a container may contain an arbitrary collection of objects (for example, a container may contain integers, strings, lists, or other objects). You are asked to implement the following methods for the Container class (recall that all methods have self as the first parameter):
1. init: The constructor creates an empty container. We store the contents of the container in a list. Hence, the constructor will simply create an instance attribute and initialize it as an empty list.
2. insert: This method has a single parameter item that is inserted into the container.
3. erase one: This method has a single parameter item. One occurrence of item is deleted from the container. Recall that since the items in a container are unordered, it doesn’t matter which occurrence is deleted. The container remains unchanged if the item does not occur in the container.
4. erase all: This method has a single parameter item. All occurrences of items are deleted from the container.
5. count: This method has a single parameter item. The number of occurrences of item
in the container is returned.
6. items: This method has no parameters. A list of the distinct items in the container is re- turned. For example, if a container C has the items 1, "abc", 1, 2, 3, [4,5,6], 2, "abc", [4], [4,5,6], then C.items() should return 1, "abc", 2, 3, [4,5,6],[4]. The order of items in the returned list does not matter.
7. str: Returns a string representation of the container. Recall that the return value must be a string. Make sure that multiple occurrences of the same item appear consecutively in the returned string. Other than that, the order of the items does not matter. Note that you cannot sort the list, since it is an arbitrary collection of items that may not be comparable.
8. repr: Also returns a printable representation of the container.
9. getitem : This method overloads the [] (index) operator. If idx is the parameter to the index operator, getitem must return the idx-th element of the container. If there are N items in the container, the valid values for idx are 0, 1, 2, . . . , N − 1.
10. add: This method overloads the + operator and returns the “sum” of two containers. The sum of two containers is a new container that contains all the items of the two operand containers. Hence, if A is a container with items 1, 2, "abc", 2, [4] and B is a container with items 3, 2, 4, "abcd", [4], "xy", then A + B is the container with items 1, 2, "abc", 2, [4], 3, 2, 4, "abcd", [4], "xy". Keep in mind that the actual parameters should not be modified by this method.
11. sub: This method overloads the - operator and returns the “difference” of two containers. The difference of the two containers A and B is a new container that contains only those items in A that do not occur in B. For example, if A and B are as shown in the example above, then A - B is the container 1, "abc", and B - A is the container 3, 4, "abcd", "xy". Again, the actual parameters should not be modified by this method.
12. mul: This method overloads the * operator and returns the “intersection” of two containers. The intersection of two containers A and B is a new container that contains items that are common to A and B. Note that the count of an item in the intersection is the minimum of the counts of that item in each of A and B. For example, if A and B are as shown in the example above, then A * B is the container with items 2, [4]. Again, the actual parameters should not be modified by this method.
Containers as parameters to functions. After completing the python assignment from the above class implementation, you are asked to implement some functions that have containers as parameters and possibly as return values. Implement these functions in a module called problem1b.py. On the first line of this module, import the Container class from the problem1a module.
The following functions manipulate container objects. The Container class methods provide the interface required to manipulate objects of that class (the idea of encapsulation discussed
in class), and you must use container methods to implement these functions. Do not manipulate container instance attributes directly (you will not be able to if instance attributes are made private, as you are asked to do). You will not receive any credit if you do.
• Implement a function called symmetric difference with two parameters, a container c1, and a container c2. The function returns a container that contains items that belong to c1 or to c2, but not to both. For example, if A and B are the containers used in the examples above, the symmetric difference(A, B) should return the container with items 1, "abc", 3, 4, "abcd", "xy".
• Implement a function called sub-container with two parameters, a container c1, and a container c2. The function returns True if c1 is a sub-container of c2 and False otherwise. A container A is said to be a sub-container of container B if every item in A is also in B. Note that this definition implies that the count of an item in A has to be at most its count in B.
• Implement a function called remove repeats with a single parameter, a container C. The function removes all but one copy of each item in the container. That is, repetitions of an item are removed from the container. Note that container C will be modified by this function.
• Implement a function called similar with two parameters, a container A and a container
B. The function returns True if the two containers are “similar” and False otherwise. Two containers are said to be similar if they contain exactly the same items (but the counts of the items may be different in the two containers). Hence, a container with items 1, 2, 2, 3, 4, 4, 4 is said to be similar to a container with items 1, 2, 3, 3, 4.
Problem 2 Change Jar. In this problem, you are asked to create a class for change jars. A change jar contains an arbitrary collection of coins i.e., quarters, dimes, nickels, and pennies. There are no dollar bills of any denomination in a change jar. We may use change jars to get exact change for some specified amount, or we may add more coins into it. Create a module called problem2.py to implement these and other methods for change jars in a class called ChangeJar. Further details are provided below:
1. init: The constructor has a single parameter, which is a dictionary of key: value pairs in which the keys must be 25, 10, 5, or 1 (for quarters, dimes, nickels, and pennies). All other keys are invalid (you may raise an exception in this case). The value associated with each key is the number of coins of that denomination in the change jar. Note that not every key need appears in the parameter. If a key does not appear, it means that there are no coins of that denomination in the jar. Set the default value of the parameter to be the empty dictionary, which will allow us to create change jars with no quarters, dimes, nickels, or pennies.
The constructor should create a dictionary as an instance attribute that has exactly four keys: 25, 10, 5, and 1. The value associated with each key should be the number of coins of that type in the jar.
For example, the statement J = ChangeJar({25:8, 5:10, 1:45}) creates a change jar that has 8 quarters, 0 dimes, 10 nickels, and 45 pennies. The statement J = ChangeJar() creates a change jar with 0 quarters, 0 dimes, 0 nickels, and 0 pennies.
2. get change: This method has a single parameter, dollar amt, which is a value corresponding to a dollar amount. It should return a ChangeJar object that contains the number of quarters, dimes, nickels, and pennies required to create exact change corresponding to that dollar amount. The corresponding numbers of coins should be deducted from the activating change jar.
There is more than one way to make exact changes for a specified value. Here, you are used to using the fewest number of coins possible to make the change. Note that you must return the exact change. This means that if the coins in the jar cannot form an exact change for dollar amt, the method should return an empty change jar. Keep in mind that this may happen even if there is enough total money in the change jar. For example, if a change jar has 4 quarters, 3 dimes, and 4 pennies, we cannot get an exact change for $1.25 from the jar, even though it has $1.34 in it.
Tip: Convert dollar amt to cents before you find the change. That is, work with integer values, rather than real values.
3. getitem: This method overloads the index operator. When the index value is 25, 10, 5, or 1, the method returns the number of quarters, dimes, nickels, or pennies, respectively, in the jar. All other index values smaller than 25 should return 0, and an index value greater than 25 should raise the StopIteration exception.
4. insert: This method is used to add more coins of a particular value into the change jar. The method has two parameters: coin value (which has values 25, 10, 5, or 1) and num coins (the number of coins of that value being inserted into the jar). Note that you are adding to the existing coins in the jar. For example, if J is a ChangeJar instance, J.insert(10, 12) will insert 12 more dimes into J.
5. total value: This method returns the total dollar value of the change jar as a real number.
6. str: This method returns a string representation of the change jar. Recall that this method must return a string. It should contain succinct information about the number of quarters, dimes, nickels, and pennies in the change jar.
7. repr: This method returns a printable representation (also a string) of the change jar.
8. add: This method overloads the + operator. It returns a change jar that contains all the coins from the two change jars that are the operands. Keep in mind that the operands themselves should not get modified by this method.
9. eq : This method overloads the == operator. It returns True if the two change jars have exactly the same numbers of coins of each type, and False otherwise.
10. no: This method overloads the != operator. It returns True if the two change jars are not equal (as defined above) and False otherwise.
Solution:
1 (a).
class Container:
def __init__(self):
"""
Create an empty container
"""
self.__items = list()
def insert(self, item):
"""
Append an element at the end of the container
"""
self.__items.append(item)
def erase_one(self, item):
"""
Delete the first occurrence of the item
"""
if item in self.__items:
self.__items.remove(item)
def erase_all(self, item):
"""
Delete all occurrence of the item in the list
"""
while item in self.__items:
self.__items.remove(item)
def count(self, item):
"""
Count the occurrence of item in the list
"""
occurrence = 0
for some_item in self.__items:
if some_item == item:
occurrence += 1
return occurrence
def items(self):
"""
Return distinct items in the list
"""
distinct_items = list()
for item in self.__items:
if item not in distinct_items:
distinct_items.append(item)
return distinct_items
def __str__(self):
"""
Return a string representation of the container
"""
return str(self.__items)[1:-1]
def __repr__(self):
"""
Returns a printable representation of the container
"""
return str(self.__items)[1:-1]
def __getitem__(self, idx):
"""
Access an item from the list given the index
"""
return self.__items[idx]
def __add__(self, other_container):
"""
Return a new container that contains all the items
that is here and the other container
"""
new_container = Container()
new_container.__items = self.__items + other_container.__items
return new_container
def __sub__(self, other_container):
"""
Return a new container where items here does not exist
on the other container
"""
paired_indices = list()
for i in range(len(other_container.__items)):
paired_indices.append(False)
new_container = Container()
for i in range(len(self.__items)):
pair_found = False
for j in range(len(other_container.__items)):
if self.__items[i] == other_container.__items[j] and not paired_indices[j]:
pair_found = True
paired_indices[j] = True
break
if not pair_found:
new_container.__items.append(self.__items[i])
return new_container
def __mul__(self, other_container):
"""
Find the intersection of two containers
"""
paired_indices = list()
for i in range(len(other_container.__items)):
paired_indices.append(False)
new_container = Container()
for i in range(len(self.__items)):
pair_found = False
for j in range(len(other_container.__items)):
if self.__items[i] == other_container[j] and not paired_indices[j]:
pair_found = True
paired_indices[j] = True
break
if pair_found:
new_container.__items.append(self.__items[i])
return new_container
1 (b).
from problem1a import Container
def symmetric_difference(c1, c2):
"""
Return a new container that contains items that belong
to either container but not both
"""
left_diff_container = c1 - c2
right_diff_container = c2 - c1
return left_diff_container + right_diff_container
def subcontainer(c1, c2):
"""
Return true if c1 is a subcontainer of c2, otherwise returns false
"""
for item in c1.items():
if item in c2.items():
if c2.count(item) < c1.count(item):
return False
return True
def remove_repeats(c):
"""
Removes all but one copy of each item in the container
"""
items = c.items()
for item in items:
c.erase_all(item)
for item in items:
c.insert(item)
def similar(c1, c2):
"""
Return true if the two containers are similar, otherwise false
"""
for item in c1.items():
if item not in c2.items():
return False
for item in c2.items():
if item not in c1.items():
return False
return True
2.
class ChangeJar:
def __init__(self, coins={}):
"""
Initialize the jar with coins of different denomination
"""
self.__coins = {25: 0, 10: 0, 5: 0, 1: 0}
for coin in coins.keys():
if coin in self.__coins.keys():
self.__coins[coin] = coins[coin]
def get_change(self, dollar_amt):
"""
Return a jar object that contains the number of quarters,
dimes, nickels, and pennies to create the exact amount of
the given dollar
"""
# Create a copy of the content of this jar so we won't modify
# the original. We do this so that while processing and we found
# out that it's not possible to create a change then at least
# we haven't modified the original copy
coins_copy = self.__coins.copy()
# Convert the dollar to cents to make it easy to get a change
total_cents = dollar_amt * 100
# Work with making a change containing as fewest possible number of coins
coins_change = {25: 0, 10: 0, 5: 0, 1: 0}
while total_cents > 0:
if total_cents >= 25 and coins_copy[25] > 0:
coins_change[25] += 1
coins_copy[25] -= 1
total_cents -= 25
elif total_cents >= 10 and coins_copy[10] > 0:
coins_change[10] += 1
coins_copy[10] -= 1
total_cents -= 10
elif total_cents >= 5 and coins_copy[5] > 0:
coins_change[5] += 1
coins_copy[5] -= 1
total_cents -= 5
elif total_cents >= 1 and coins_copy[1] > 0:
coins_change[1] += 1
coins_copy[1] -= 1
total_cents -= 1
else:
# If code reaches here, we ran out of coins for change
# So we return an empty jar
return ChangeJar()
# If code reaches here, we successfully made the change
self.__coins = coins_copy
return ChangeJar(coins_change)
def __getitem__(self, coin):
"""
Return the quantity of a coin
"""
if coin in self.__coins.keys():
return self.__coins[coin]
if coin < 25:
return 0
raise StopIteration
def insert(self, coin_value, num_coins):
"""
Add more coins of a particular value
"""
if coin_value not in self.__coins.keys():
return
self.__coins[coin_value] += num_coins
def total_value(self):
"""
Return the total dollar value of the jar
"""
cents = self.__coins[25] * 25
cents += self.__coins[10] * 10
cents += self.__coins[5] * 5
cents += self.__coins[1]
return cents / 100
def __str__(self):
"""
Return a string representation of the Jar
"""
string = str(self.__coins[25] )+ " quarters, "
string += str(self.__coins[10]) + " dimes, "
string += str(self.__coins[5]) + " nickels, and "
string += str(self.__coins[1]) + " pennies"
return string
def __repr__(self):
"""
Return a printable string representation of the jar
"""
string = str(self.__coins[25]) + " quarters, "
string += str(self.__coins[10]) + " dimes, "
string += str(self.__coins[5]) + " nickels, and "
string += str(self.__coins[1]) + " pennies"
return string
def __add__(self, other_jar):
"""
Returns a Jar that contains all the coins from this Jar and
the other jar
"""
coins = dict()
coins[25] = self.__coins[25] + other_jar.__coins[25]
coins[10] = self.__coins[10] + other_jar.__coins[10]
coins[5] = self.__coins[5] + other_jar.__coins[5]
coins[1] = self.__coins[1] + other_jar.__coins[1]
return ChangeJar(coins)
def __eq__(self, other_jar):
"""
Returns true if the two change jars have exactly the
same number of coins of each type
"""
return self.__coins[25] == other_jar.__coins[25] \
and self.__coins[10] == other_jar.__coins[10] \
and self.__coins[5] == other_jar.__coins[5]\
and self.__coins[1] == other_jar.__coins[1]
def __ne__(self, other_jar):
"""
Returns true if the two change jars are not equal of
the same number of coins of each type
"""
return self.__coins[25] != other_jar.__coins[25] \
or self.__coins[10] != other_jar.__coins[10] \
or self.__coins[5] != other_jar.__coins[5] \
or self.__coins[1] != other_jar.__coins[1]