Homework 6: OOP, Linked Lists
2586字约9分钟
2024-12-30
说明
下载 hw06.zip。在存档中，您将找到一个名为 hw06.py 的文件，以及 ok 自动评分器的副本。
如果官方链接失效，你也可以通过我的 github 仓库 CS61A_Fall2024来获取我的代码。
提示
初始代码可以在 github 仓库历史 Commits 中的 Commits on Dec 29, 2024 的 initial hw06 找到
Required Questions
Midsemester Survey
Q1: Mid-Semester Feedback
伯克利内部作业，略
OOP
Q2: Vending Machine
在本题中，你将创建一台 自动售货机，该机器只销售一种产品，并在需要时提供零钱。
实现 VendingMachine 类，该类为一种特定产品建模自动售货机。 VendingMachine 对象的方法返回字符串来描述机器的状态和操作。确保输出与 doctests 中提供的字符串完全匹配，包括标点符号和空格。
提示
您可能会发现 Python 的格式化字符串文字或 f 字符串很有用。一个简单的例子：
>>> feeling = 'love'
>>> course = '61A!'
>>> combined_string = f'I {feeling} {course}'
>>> combined_string
'I love 61A!'class VendingMachine:
"""A vending machine that vends some product for some price.
>>> v = VendingMachine('candy', 10)
>>> v.vend()
'Nothing left to vend. Please restock.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> v.restock(2)
'Current candy stock: 2'
>>> v.vend()
'Please add $10 more funds.'
>>> v.add_funds(7)
'Current balance: $7'
>>> v.vend()
'Please add $3 more funds.'
>>> v.add_funds(5)
'Current balance: $12'
>>> v.vend()
'Here is your candy and $2 change.'
>>> v.add_funds(10)
'Current balance: $10'
>>> v.vend()
'Here is your candy.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> w = VendingMachine('soda', 2)
>>> w.restock(3)
'Current soda stock: 3'
>>> w.restock(3)
'Current soda stock: 6'
>>> w.add_funds(2)
'Current balance: $2'
>>> w.vend()
'Here is your soda.'
"""
def __init__(self, product, price):
"""Set the product and its price, as well as other instance attributes."""
"*** YOUR CODE HERE ***"
def restock(self, n):
"""Add n to the stock and return a message about the updated stock level.
E.g., Current candy stock: 3
"""
"*** YOUR CODE HERE ***"
def add_funds(self, n):
"""If the machine is out of stock, return a message informing the user to restock
(and return their n dollars).
E.g., Nothing left to vend. Please restock. Here is your $4.
Otherwise, add n to the balance and return a message about the updated balance.
E.g., Current balance: $4
"""
"*** YOUR CODE HERE ***"
def vend(self):
"""Dispense the product if there is sufficient stock and funds and
return a message. Update the stock and balance accordingly.
E.g., Here is your candy and $2 change.
If not, return a message suggesting how to correct the problem.
E.g., Nothing left to vend. Please restock.
Please add $3 more funds.
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q VendingMachine以下内容包含答案
class VendingMachine:
"""A vending machine that vends some product for some price.
>>> v = VendingMachine('candy', 10)
>>> v.vend()
'Nothing left to vend. Please restock.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> v.restock(2)
'Current candy stock: 2'
>>> v.vend()
'Please add $10 more funds.'
>>> v.add_funds(7)
'Current balance: $7'
>>> v.vend()
'Please add $3 more funds.'
>>> v.add_funds(5)
'Current balance: $12'
>>> v.vend()
'Here is your candy and $2 change.'
>>> v.add_funds(10)
'Current balance: $10'
>>> v.vend()
'Here is your candy.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> w = VendingMachine('soda', 2)
>>> w.restock(3)
'Current soda stock: 3'
>>> w.restock(3)
'Current soda stock: 6'
>>> w.add_funds(2)
'Current balance: $2'
>>> w.vend()
'Here is your soda.'
"""
def __init__(self, product, price):
"""Set the product and its price, as well as other instance attributes."""
"*** YOUR CODE HERE ***"
self.product = product
self.price = price
self.balance = 0
self.num = 0
def restock(self, n):
"""Add n to the stock and return a message about the updated stock level.
E.g., Current candy stock: 3
"""
"*** YOUR CODE HERE ***"
self.num += n
print(f"'Current {self.product} stock: {self.num}'")
def add_funds(self, n):
"""If the machine is out of stock, return a message informing the user to restock
(and return their n dollars).
E.g., Nothing left to vend. Please restock. Here is your $4.
Otherwise, add n to the balance and return a message about the updated balance.
E.g., Current balance: $4
"""
"*** YOUR CODE HERE ***"
if self.num == 0:
print(f"'Nothing left to vend. Please restock. Here is your ${n}.'")
else:
self.balance += n
print(f"'Current balance: ${self.balance}'")
def vend(self):
"""Dispense the product if there is sufficient stock and funds and
return a message. Update the stock and balance accordingly.
E.g., Here is your candy and $2 change.
If not, return a message suggesting how to correct the problem.
E.g., Nothing left to vend. Please restock.
Please add $3 more funds.
"""
"*** YOUR CODE HERE ***"
if self.num == 0:
print(f"'Nothing left to vend. Please restock.'")
return
if self.balance < self.price:
print(f"'Please add ${self.price - self.balance} more funds.'")
return
elif self.balance == self.price:
print(f"'Here is your {self.product}.'")
else:
print(f"'Here is your {self.product} and ${self.balance - self.price} change.'")
self.balance = 0
self.num -= 1Linked Lists
Q3: Store Digits
编写一个函数 store_digits ，该函数接受一个整数 n ，并返回一个包含 n 的数字的链接列表，这些数字的顺序相同（从左到右）。
重要
请勿使用任何字符串操作函数，例如 str 或 reversed。
def store_digits(n):
"""Stores the digits of a positive number n in a linked list.
>>> s = store_digits(1)
>>> s
Link(1)
>>> store_digits(2345)
Link(2, Link(3, Link(4, Link(5))))
>>> store_digits(876)
Link(8, Link(7, Link(6)))
>>> store_digits(2450)
Link(2, Link(4, Link(5, Link(0))))
>>> store_digits(20105)
Link(2, Link(0, Link(1, Link(0, Link(5)))))
>>> # a check for restricted functions
>>> import inspect, re
>>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
>>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q store_digits以下内容包含答案
def store_digits(n):
"""Stores the digits of a positive number n in a linked list.
>>> s = store_digits(1)
>>> s
Link(1)
>>> store_digits(2345)
Link(2, Link(3, Link(4, Link(5))))
>>> store_digits(876)
Link(8, Link(7, Link(6)))
>>> store_digits(2450)
Link(2, Link(4, Link(5, Link(0))))
>>> store_digits(20105)
Link(2, Link(0, Link(1, Link(0, Link(5)))))
>>> # a check for restricted functions
>>> import inspect, re
>>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
>>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
"""
"*** YOUR CODE HERE ***"
first = n % 10
n = n // 10
current = Link(first, Link.empty)
while n:
first = n % 10
n = n // 10
new = Link(first, current)
current = new
return current Q4: Mutable Mapping
实现 deep_map_mut(func, s) ，将函数 func 应用于链表 s 中的每个元素。如果元素本身是链表，则也以递归方式将 func 应用于其元素。
您的实现应该改变原始链表。不要创建任何新的链表。该函数返回 None。
提示
您可以使用内置的 isinstance 函数来判断元素是否为链表。
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False构造检查：本问题的最后一个测试用例检查您的函数是否不会创建任何新的链接列表。如果您未通过此 doctest，请确保您没有通过调用构造函数来创建链接列表，即
s = Link(1)def deep_map_mut(func, s):
"""Mutates a deep link s by replacing each item found with the
result of calling func on the item. Does NOT create new Links (so
no use of Link's constructor).
Does not return the modified Link object.
>>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
>>> print(link1)
<3 <4> 5 6>
>>> # Disallow the use of making new Links before calling deep_map_mut
>>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
>>> try:
... deep_map_mut(lambda x: x * x, link1)
... finally:
... Link.__init__ = hold
>>> print(link1)
<9 <16> 25 36>
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q deep_map_mut以下内容包含答案
def deep_map_mut(func, s):
"""Mutates a deep link s by replacing each item found with the
result of calling func on the item. Does NOT create new Links (so
no use of Link's constructor).
Does not return the modified Link object.
>>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
>>> print(link1)
<3 <4> 5 6>
>>> # Disallow the use of making new Links before calling deep_map_mut
>>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
>>> try:
... deep_map_mut(lambda x: x * x, link1)
... finally:
... Link.__init__ = hold
>>> print(link1)
<9 <16> 25 36>
"""
"*** YOUR CODE HERE ***"
cur = s
while cur.first:
temp = cur
while isinstance(temp.first, Link):
temp = temp.first
temp.first = func(temp.first)
if cur.rest == Link.empty:
return
cur = cur.rest Optional Questions
Q5: Two List
实现一个函数 two_list ，该函数接受两个列表并返回一个链接列表。第一个列表包含我们想要放入链接列表中的值，第二个列表包含每个对应值的数量。假设两个列表的大小相同，且长度为 1 或更大。假设第二个列表中的所有元素都大于 0。
def two_list(vals, counts):
"""
Returns a linked list according to the two lists that were passed in. Assume
vals and counts are the same size. Elements in vals represent the value, and the
corresponding element in counts represents the number of this value desired in the
final linked list. Assume all elements in counts are greater than 0. Assume both
lists have at least one element.
>>> a = [1, 3]
>>> b = [1, 1]
>>> c = two_list(a, b)
>>> c
Link(1, Link(3))
>>> a = [1, 3, 2]
>>> b = [2, 2, 1]
>>> c = two_list(a, b)
>>> c
Link(1, Link(1, Link(3, Link(3, Link(2)))))
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q two_list以下内容包含答案
def two_list(vals, counts):
"""
Returns a linked list according to the two lists that were passed in. Assume
vals and counts are the same size. Elements in vals represent the value, and the
corresponding element in counts represents the number of this value desired in the
final linked list. Assume all elements in counts are greater than 0. Assume both
lists have at least one element.
>>> a = [1, 3]
>>> b = [1, 1]
>>> c = two_list(a, b)
>>> c
Link(1, Link(3))
>>> a = [1, 3, 2]
>>> b = [2, 2, 1]
>>> c = two_list(a, b)
>>> c
Link(1, Link(1, Link(3, Link(3, Link(2)))))
"""
"*** YOUR CODE HERE ***"
s = Link(vals[0])
cur = s
counts[0] -= 1
for i in range(len(counts)):
while counts[i]:
temp = Link(vals[i])
cur.rest = temp
cur = temp
counts[i] -= 1
return s Check Your Score Locally
您可以通过运行
python3 ok --score在本地检查此作业每个问题的得分
这不会提交作业！当您对分数满意时，请将作业提交给 Gradescope 以获得学分。
PS D:\Github\CS61A_Fall2024\hw\hw06> python ok --score
=====================================================================
Assignment: Homework 6
OK, version v1.18.1
=====================================================================
D:\Github\CS61A_Fall2024\hw\hw06\hw06.py:110: SyntaxWarning: invalid escape sequence '\s'
"""Stores the digits of a positive number n in a linked list.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Scoring tests
---------------------------------------------------------------------
Doctests for VendingMachine
>>> from hw06 import *
>>> v = VendingMachine('candy', 10)
>>> v.vend()
'Nothing left to vend. Please restock.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> v.restock(2)
'Current candy stock: 2'
>>> v.vend()
'Please add $10 more funds.'
>>> v.add_funds(7)
'Current balance: $7'
>>> v.vend()
'Please add $3 more funds.'
>>> v.add_funds(5)
'Current balance: $12'
>>> v.vend()
'Here is your candy and $2 change.'
>>> v.add_funds(10)
'Current balance: $10'
>>> v.vend()
'Here is your candy.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> w = VendingMachine('soda', 2)
>>> w.restock(3)
'Current soda stock: 3'
>>> w.restock(3)
'Current soda stock: 6'
>>> w.add_funds(2)
'Current balance: $2'
>>> w.vend()
'Here is your soda.'
Score: 1.0/1
---------------------------------------------------------------------
Doctests for midsem_survey
>>> from hw06 import *
>>> midsem_survey(passphrase)
'f65fb8fdaeda6d85eb3089dcdf7784836dde30e260c0ad31b9b2e533'
# Error: expected
# '2bf925d47c03503d3ebe5a6fc12d479b8d12f14c0494b43deba963a0'
# but got
# 'f65fb8fdaeda6d85eb3089dcdf7784836dde30e260c0ad31b9b2e533'
Score: 0.0/1
---------------------------------------------------------------------
Doctests for store_digits
>>> from hw06 import *
>>> s = store_digits(1)
>>> s
Link(1)
>>> store_digits(2345)
Link(2, Link(3, Link(4, Link(5))))
>>> store_digits(876)
Link(8, Link(7, Link(6)))
>>> store_digits(2450)
Link(2, Link(4, Link(5, Link(0))))
>>> store_digits(20105)
Link(2, Link(0, Link(1, Link(0, Link(5)))))
>>> # a check for restricted functions
>>> import inspect, re
>>> cleaned = re.sub(r"#.*\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
>>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
Score: 1.0/1
---------------------------------------------------------------------
Doctests for deep_map_mut
>>> from hw06 import *
>>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
>>> print(link1)
<3 <4> 5 6>
>>> # Disallow the use of making new Links before calling deep_map_mut
>>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
>>> try:
... deep_map_mut(lambda x: x * x, link1)
... finally:
... Link.__init__ = hold
>>> print(link1)
<9 <16> 25 36>
Score: 1.0/1
---------------------------------------------------------------------
Point breakdown
VendingMachine: 1.0/1
midsem_survey: 0.0/1
store_digits: 1.0/1
deep_map_mut: 1.0/1
Score:
Total: 3.0
Backup... 100% complete
Backup past deadline by 66 days, 2 hours, 18 minutes, and 50 seconds
Backup successful for user: zhiyong947@gmail.com
URL: https://okpy.org/cal/cs61a/fa24/hw06/backups/p7w5r2
OK is up to date
PS D:\Github\CS61A_Fall2024\hw\hw06>