Download the Python program linked below.
It simulates a vending machine, and is similar to a project assigned in MCS 260 in Fall 2020. Run it, use the "help" command in its text interface to learn about the available commands, and try them out.
This script has a bug which affects certain purchases. For example, try starting the script and depositing \$1.15 as four quarters, one dime, and one nickel, and then selecting item 4 (costing \\$1.10). The expected behavior would be: The item is purchased, and \$0.05 is given in change. Instead, the script will get stuck (and may require you to press Control-C in the terminal to exit).
Debug the program using an active debugging technique (print(...) or pdb) and find the cause of the infinite loop that prevents the program from executing as intended. Devise and test a fix.
The problem is that the given program stores the current credit as a float, and float addition is not exact. For example, in Python
0.1 + 0.05 == 0.15evaluates to False! But 0.01+0.05 and 0.15 are quite close.
A minimal correction to the broken vending machine program would replace a check like cents == 0 with one that only looks for cents to be near zero, allowing for a small amount of floating point error.
The code below does that. It would be hard to verify the correctness of this program, however. How do we know that the error won't accumulate over time and eventually be large enough to fail even the approximate equality test?
In real programs, you should never use floats for financial calculations.
(Also, like the broken code provided in the worksheet, this patched version uses the variable name cents for the current credit in dollars. The misleading variable name was not intentional---Professor Dumas simply forgot to change the name when he added a bug to a working version of the program.)
"""Patched vending machine simulator"""
# MCS 275 Spring 2021 Week 5 Problem 1
# Jennifer Vaccaro
# This code was fixed from an example by David Dumas.
import sys
# Mapping from coin add commands to values (in dollars)
coin_values = {
"quarter": 0.25,
"q": 0.25,
"dime": 0.10,
"d": 0.10,
"nickel": 0.05,
"n": 0.05
}
# Starting inventory. Prices in dollars.
inventory = [
{ "stock":6, "price": 1.25, "name": "Cheesy dibbles" },
{ "stock":8, "price": 1.30, "name": "Slice of cake" },
{ "stock":10, "price": 0.75, "name": "Rock candy" },
{ "stock":5, "price": 1.50, "name": "Single leaf of lettuce" },
{ "stock":5, "price": 1.10, "name": "Dehydrated garlic slices" },
{ "stock":7, "price": 0.90, "name": "Almond cookies" },
]
def dispense_change(cents):
"""print lines to simulate return of `cents` cents"""
while cents >= 0.25:
print("RETURN: quarter")
cents = cents - 0.25
while cents >= 0.10:
print("RETURN: dime")
cents = cents - 0.10
while cents > 10**-5:
# FIXED Changed comparison to a small positive number, to account for float math.
# A more permanent fix would require changing cents to be stored as an integer.
# However, by changing the comparator from !=0 to > 10**-5, the vending machine works.
print("RETURN: nickel")
cents = cents - 0.05
def show_inventory(inventory):
"""Display the `inventory` (list of dicts) in the format required by
the project description
"""
for idx,itemdata in enumerate(inventory):
print(idx,itemdata["name"],
"${:.2f} ({} available)".format(itemdata["price"],
itemdata["stock"]))
def vend(inventory):
"""Run the vending machine simulator with a given `inventory`."""
# Determine the maximum price of an item
maxprice = 0
for d in inventory:
if d["price"] > maxprice:
maxprice = d["price"]
invitems = [ str(x) for x in range(len(inventory)) ]
# Command loop
credit = 0.0
while True:
print("CREDIT: ${:.2f}".format(credit))
cmd = input(">")
if cmd in ["q","d","n","quarter","dime","nickel"]:
# Coin inserted
if credit >= maxprice:
print("RETURN:",cmd)
else:
credit = credit + coin_values[cmd]
elif cmd in invitems:
# Snack purchase request
i = int(cmd) # 0-based index
if inventory[i]["stock"] == 0:
print("MSG: Out of stock")
elif credit < inventory[i]["price"]:
print("MSG: Insufficient credit")
else:
inventory[i]["stock"] = inventory[i]["stock"] - 1
print("VEND:",inventory[i]["name"])
dispense_change(credit - inventory[i]["price"])
credit = 0
elif cmd in ["inventory","i"]:
# Request to display inventory
show_inventory(inventory)
elif cmd in ["return","r"]:
# Return current credit
dispense_change(credit)
credit = 0
elif cmd in ["help","h"]:
# Display help
print("Vending machine simulator knows about these commands:")
print("h or help - show this message")
print("i or inventory - show numbered list of items available for purchase")
print("q or quarter - deposit a quarter ($0.25)")
print("d or dime - deposit a dime ($0.10)")
print("n or nickel - deposit a nickel ($0.05)")
print("r or return - return all credit currently in machine")
print("0, 1, 2, ... - buy an item by number")
elif cmd == "exit":
# exit the simulation
return
else:
# Unknown command
print("Unknown command: {}".format(cmd))
if __name__ == "__main__":
# Start the simulation.
vend(inventory)
A correction that involves more code changes---but which is guaranteed to behave correctly no matter how many arithmetic operations are performed---is to never store anything as a float, but instead to work with prices as integers, measured in cents.
"""Patched vending machine simulator"""
# MCS 275 Spring 2021 Week 5 Problem 1
# David Dumas
import sys
# Mapping from coin add commands to values (in cents)
coin_values = {
"quarter": 25,
"q": 25,
"dime": 10,
"d": 10,
"nickel": 5,
"n": 5
}
# Starting inventory. Prices in cents.
inventory = [
{ "stock":6, "price": 125, "name": "Cheesy dibbles" },
{ "stock":8, "price": 130, "name": "Slice of cake" },
{ "stock":10, "price": 75, "name": "Rock candy" },
{ "stock":5, "price": 150, "name": "Single leaf of lettuce" },
{ "stock":5, "price": 110, "name": "Dehydrated garlic slices" },
{ "stock":7, "price": 90, "name": "Almond cookies" },
]
def dispense_change(cents):
"""print lines to simulate return of `cents` cents"""
while cents >= 25:
print("RETURN: quarter")
cents = cents - 25
while cents >= 10:
print("RETURN: dime")
cents = cents - 10
while cents >= 5:
# FIXED Changed comparison to a small positive number, to account for float math.
# A more permanent fix would require changing cents to be stored as an integer.
# However, by changing the comparator from !=0 to > 10**-5, the vending machine works.
print("RETURN: nickel")
cents = cents - 5
assert cents==0, "This vending machine requires all prices to be multiples of $0.05"
def show_inventory(inventory):
"""Display the `inventory` (list of dicts) in the format required by
the project description
"""
for idx,itemdata in enumerate(inventory):
print(idx,itemdata["name"],
"${:.2f} ({} available)".format(itemdata["price"]/100,
itemdata["stock"]))
def vend(inventory):
"""Run the vending machine simulator with a given `inventory`."""
# Determine the maximum price of an item
maxprice = 0
for d in inventory:
if d["price"] > maxprice:
maxprice = d["price"]
invitems = [ str(x) for x in range(len(inventory)) ]
# Command loop
credit = 0
while True:
print("CREDIT: ${:.2f}".format(credit/100))
cmd = input(">")
if cmd in ["q","d","n","quarter","dime","nickel"]:
# Coin inserted
if credit >= maxprice:
print("RETURN:",cmd)
else:
credit = credit + coin_values[cmd]
elif cmd in invitems:
# Snack purchase request
i = int(cmd) # 0-based index
if inventory[i]["stock"] == 0:
print("MSG: Out of stock")
elif credit < inventory[i]["price"]:
print("MSG: Insufficient credit")
else:
inventory[i]["stock"] = inventory[i]["stock"] - 1
print("VEND:",inventory[i]["name"])
dispense_change(credit - inventory[i]["price"])
credit = 0
elif cmd in ["inventory","i"]:
# Request to display inventory
show_inventory(inventory)
elif cmd in ["return","r"]:
# Return current credit
dispense_change(credit)
credit = 0
elif cmd in ["help","h"]:
# Display help
print("Vending machine simulator knows about these commands:")
print("h or help - show this message")
print("i or inventory - show numbered list of items available for purchase")
print("q or quarter - deposit a quarter ($0.25)")
print("d or dime - deposit a dime ($0.10)")
print("n or nickel - deposit a nickel ($0.05)")
print("r or return - return all credit currently in machine")
print("0, 1, 2, ... - buy an item by number")
elif cmd == "exit":
# exit the simulation
return
else:
# Unknown command
print("Unknown command: {}".format(cmd))
if __name__ == "__main__":
# Start the simulation.
vend(inventory)
The function below is supposed to compute the character histogram of a string, with the option to update an existing histogram so that a large text can be processed in chunks. However, it doesn't work: As you'll see form the example code, it doesn't start from a blank histogram in some cases. Why not?
Use debugging techniques to find the first place where the behavior of the function differs from the documented intention of the programmer.
"""Histogram example for debugging"""
# MCS 275 Spring 2021 - David Dumas
def update_char_histogram(s,hist = dict()):
"""Take a string `s` and look at the non-space characters in it. If `hist` is not given,
compose a histogram of the characters in `s` and return it. If `hist` is given, assume it contains
a histogram of another part of the same text, and update it to take into account the text in `s`."""
for c in s:
if c.isspace():
continue
if c not in hist:
hist[c] = 0
hist[c] += 1
return hist
print("Histogram of 'first line example':")
h = update_char_histogram("first line example") # no hist given, so start from scratch
print(h)
print("Histogram of previous line and 'renewed interest in debugging':")
h = update_char_histogram("renewed interest in debugging",h)
print(h)
print("Histogram of the word 'Mississippi':") # no hist given, so start from scratch
h = update_char_histogram("Mississippi")
print(h) # Unexpected output here; why isn't the default argument of dict() honored?
"""Fixed histogram example"""
# MCS 275 Week 5 Problem 2
# Jennifer Vaccaro
# This code was adapted from starter code by David Dumas
def update_char_histogram(s,hist = None): # FIXED changed hist default argument to None type
"""Take a string `s` and look at the non-space characters in it. If `hist` is not given,
compose a histogram of the characters in `s` and return it. If `hist` is given, assume it contains
a histogram of another part of the same text, and update it to take into account the text in `s`."""
if hist == None: # Check whether a non-None argument was given
hist = dict() # If yes, create a new empty dict()
for c in s:
if c.isspace():
continue
if c not in hist:
hist[c] = 0
hist[c] += 1
return hist
print("Histogram of 'first line example':")
h = update_char_histogram("first line example") # no hist given, so start from scratch
print(h)
print("Histogram of previous line and 'renewed interest in debugging':")
h = update_char_histogram("renewed interest in debugging",h)
print(h)
print("Histogram of the word 'Mississippi':") # no hist given, so start from scratch
h = update_char_histogram("Mississippi")
print(h) # Starts from scratch!
In Python, default values of function arguments are only evaluated once, at the time the function definition is made. Every call to that function uses the same object for the default value, so if a mutable data structure is used as the default value, any changes made to the object persist across function calls.
Compare:
# Integers are immutable
def f(t=1):
t+=1 # Creates a new local variable called `t` that is
# discarded when the function exits
print(t)
f()
f()
f()
# Lists are mutable
def g(L=[]):
L.append("aha") # Asks the default value, a list object, to
# add a new element. This doesn't create a
# local variable, so the change to L persists
# across function calls
print(L)
g()
g()
g()
Because of this, it is usually not a good idea to have a mutable data type (list, dict) as a default value for a function argument if that argument is modified in any way inside the function.
Download the program:
It is a tic-tac-toe game: two players take turns placing 'X' or 'O' on a 3x3 board. The first player to get 3 in a row horizontally, vertically, or diagonally wins.
But this game has a strange bug: No matter where the first player puts their 'X', they win.
Use debugging techniques to find the first place where the behavior of the program differs from the programmer's intention, and to fix it.
Note: This example was based on a collection of unintuitive Python language behaviors collected by Satwik Kansal. The URL for that source document is included below, but be warned, it contains spoilers for this problem (and some crude language). Opening the page is not recommended until after discussion is over:
https://github.com/satwikkansal/wtfpython#-a-tic-tac-toe-where-x-wins-in-the-first-attempt"""Fixed tic-tac-toe game"""
# MCS 275 Spring 2021 Worksheet 5 Problem 3
# Jennifer Vaccaro
# This code was adapted from the starter code written by David Dumas.
def winner(b):
"""Given a TTT board `b`, determine who has won and return. If no one has won,
return None"""
# Row of three
for row in b:
if row[0] == " ":
# First row entry is blank; ignore!
continue
if row[0]==row[1] and row[1]==row[2]:
return row[0]
# Column of three
for i in range(3):
if b[0][i] == " ":
# First column entry is blank; ignore!
continue
if b[0][i]==b[1][i] and b[1][i]==b[2][i]:
return b[0][i]
# Diagonals
if b[1][1] != " ":
# Middle entry not blank, so diagonal win
# is a possibility.
if b[0][0] == b[1][1] and b[1][1]==b[2][2]:
return b[0][0]
if b[0][2] == b[1][1] and b[1][1]==b[2][0]:
return b[0][2]
# implicit return None
def print_board(b):
"""Show the board with 1-based coordinates"""
print(" A|B|C")
for i,r in enumerate(b):
print("{}".format(i+1),"|".join(r))
if i<2:
print("---+-+-")
COLS = ["a","b","c"]
def apply_move(b,player,move):
"""Modify board b (list of lists) to account for move in string `move`.
If the move is illegal, raises an exception."""
move = move.strip().lower()
if len(move)!=2:
raise Exception("Valid move is two characters (e.g. A2 or B3)")
if move[0] not in COLS:
move = move[::-1]
if move[0] not in COLS:
raise Exception("No column spec found")
j = COLS.index(move[0])
i = int(move[1])-1
if b[i][j] != " ":
raise Exception("Another move already filled that position")
b[i][j] = player
if __name__=="__main__":
print("Tic-tac-toe: enter moves by coordinates (e.g. A1 or B3)")
print()
# FIXED
# Create empty board as list literal, so that rows can be modified independently
board = [[" "," "," "], [" "," "," "], [" "," "," "]]
cur,other = "X","O"
while True:
print_board(board)
print()
w = winner(board)
if w:
print("+----------------+")
print("| Player {} wins! |".format(w))
print("+----------------+")
break
print("It is {}'s turn.".format(cur,other))
m = input("Move? ")
print()
try:
apply_move(board,cur,m)
except Exception:
print("That move was not recognized, or not possible.\n")
continue
# switch active player
cur,other = other,cur
The original code stored the same list object in three different positions in board. The problematic code can be written in an equivalent way that makes the problem more evident:
L = [" ", " ", " "]
board = [L,L,L] # so board[0], board[1], board[2] all refer to L!which shows board[1][0] = "X" actually becomes L[0] = "X", which changes the single object L that appears three times in board.
If the intent is to have each row of the board independently modifiable, we need three different list objects. The fixed code above does that.
Download the program:
This program prints the first 1,000,000 terms of a sequence of integers. It does not have docstrings, which may make exploring the code in a debugger more of a challenge.
In this program, the list of integers from the sequence is stored in the computed_terms list.
Use the debugger (pdb) to answer the following questions about this program:
computed_terms first has length four, the last element of that list is computed as a sum of previous terms from the list. Which ones?reducer is called, what is the value of t in the main program?pdb to do post mortem analysis on that exception.return statements in function reducer is executed when calculating that term in the sequence?Some exploration with the debugger reveals the answers:
Working with the other members of your breakout room, write a Python program that looks like it will work but which actually exits with an exception. Your goal to should to make something that will pass a casual inspection by your peers, creating the impression that the program would do a certain thing, while actually containing a hidden bug. The program's docstring should describe its desired (not actual) behavior. Try to conceal the circumstances leading to the exception, so that even the traceback shown on exit doesn't immediately reveal the true source of the problem. Follow these rules:
.py file, and not depend on any modules other than the Python standard library.When you are done, use the Zoom "Ask for help" function, and give your code to the TA. She will swap your buggy programs, and you will try to solve another team's problem.
Your task is to run the program in pdb and to use post-mortem analysis to determine the complete cause of the exception, including what the software author may have intended. Then we will rejoin the Main Room, and each group will explain the other team's bug. Don't just say "the list was empty, and element 0 was requested, producing IndexError"; you'll want to explain exactly how the program's operation led to that circumstance.
# Your results will be based on your own discussion groups.
# In case you missed discussion, here's another challenge for practice...
"""Module backpack with classes for a BackPack type and various BackPackItems"""
# MCS 275 Week 5 Problem 5
# J Vaccaro
# I wrote this code myself.
class BackPack():
"""Class representing a BackPack, with a color and containing items"""
def __init__(self, color, items):
"""Save the color and items attributes"""
self.color = color
self.items = items
def __add__(self, other):
"""Create a new BackPack with current items and new item"""
if isinstance(self, BackPackItem):
items = self.items # Copy the list over
self.append(other)
return BackPack(self.color, items)
else:
return NotImplemented
def __radd__(self, other):
"""Call the original add operator"""
return self + other
def __str__(self):
"""Print out the BackPack color and contents"""
s = "Backpack: "+self.color+ " with items..."
for i in self.items:
s+= "\n * "+str(i) # Prints out a bulleted list of items
return s
def __repr__(self):
"""Call the str function"""
return str(self)
class BackPackItem():
"""Base class for items that go inside the BackPack"""
def __init__(self, name):
"""Save the name attribute"""
self.name = name
def __str__(self):
"""Print out the item's name"""
return self.name
def __repr__(self):
"""Call the str function"""
return str(self)
class Book(BackPackItem):
"""Represents a book, subclasses BackPackItem"""
def __init__(self, title):
"""Calls the superclass constructor with the title (a string)"""
super().__init__("Book: "+title)
class Pencil(BackPackItem):
"""Represents a pencil, subclasses BackPackItem"""
def __init__(self, color):
"""Calls the superclass constructor with a color (a string)"""
super().__init__("Pencil: "+color)
class Sandwich(BackPackItem):
"""Represents a sandwich, subclasses BackPackItem"""
def __init__(self, recipe):
"""Calls the superclass constructor with a recipe (a string)"""
super().__init__("Sandwich: "+recipe)
# Test code, don't run when imported
if __name__=="__main__":
pink_pencil = Pencil("pink")
bp = BackPack("blue", [pink_pencil])
print(bp)
blt_sandwich = Sandwich("BLT")
seuss_book = Book("The Cat in the Hat")
# TODO: Test the add/radd operators
bp = bp + blt_sandwich
print(bp)
bp = seuss_book + bp
print(bp)
If you're working on this extra challenge, the questions to ask yourself are: