A document from MCS 275 Spring 2021, instructor Emily Dumas. You can also get the notebook file.

Worksheet 5 Solutions

MCS 275 Spring 2021 - Emily Dumas

Solutions by Jennifer Vaccaro

1. Broken vending machine

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.

First solution: Minimal change

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.15

evaluates 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.)

In [3]:
"""Patched vending machine simulator"""
# MCS 275 Spring 2021 Week 5 Problem 1
# Jennifer Vaccaro
# This code was fixed from an example by Emily 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)
CREDIT: $0.00
>q
CREDIT: $0.25
>q
CREDIT: $0.50
>q
CREDIT: $0.75
>q
CREDIT: $1.00
>d
CREDIT: $1.10
>d
CREDIT: $1.20
>n
CREDIT: $1.25
>4
VEND: Dehydrated garlic slices
RETURN: dime
RETURN: nickel
CREDIT: $0.00
>exit

Second solution: Use integers everywhere

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.

In [2]:
"""Patched vending machine simulator"""
# MCS 275 Spring 2021 Week 5 Problem 1
# Emily 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)
CREDIT: $0.00
>q
CREDIT: $0.25
>q
CREDIT: $0.50
>q
CREDIT: $0.75
>q
CREDIT: $1.00
>d
CREDIT: $1.10
>d
CREDIT: $1.20
>n
CREDIT: $1.25
>4
VEND: Dehydrated garlic slices
RETURN: dime
RETURN: nickel
CREDIT: $0.00
>exit

2. Misbehaving function

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.

In [5]:
"""Histogram example for debugging"""
# MCS 275 Spring 2021 - Emily 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?
Histogram of 'first line example':
{'f': 1, 'i': 2, 'r': 1, 's': 1, 't': 1, 'l': 2, 'n': 1, 'e': 3, 'x': 1, 'a': 1, 'm': 1, 'p': 1}
Histogram of previous line and 'renewed interest in debugging':
{'f': 1, 'i': 5, 'r': 3, 's': 2, 't': 3, 'l': 2, 'n': 5, 'e': 9, 'x': 1, 'a': 1, 'm': 1, 'p': 1, 'w': 1, 'd': 2, 'b': 1, 'u': 1, 'g': 3}
Histogram of the word 'Mississippi':
{'f': 1, 'i': 9, 'r': 3, 's': 6, 't': 3, 'l': 2, 'n': 5, 'e': 9, 'x': 1, 'a': 1, 'm': 1, 'p': 3, 'w': 1, 'd': 2, 'b': 1, 'u': 1, 'g': 3, 'M': 1}
In [1]:
"""Fixed histogram example"""
# MCS 275 Week 5 Problem 2
# Jennifer Vaccaro
# This code was adapted from starter code by Emily 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!
Histogram of 'first line example':
{'f': 1, 'i': 2, 'r': 1, 's': 1, 't': 1, 'l': 2, 'n': 1, 'e': 3, 'x': 1, 'a': 1, 'm': 1, 'p': 1}
Histogram of previous line and 'renewed interest in debugging':
{'f': 1, 'i': 5, 'r': 3, 's': 2, 't': 3, 'l': 2, 'n': 5, 'e': 9, 'x': 1, 'a': 1, 'm': 1, 'p': 1, 'w': 1, 'd': 2, 'b': 1, 'u': 1, 'g': 3}
Histogram of the word 'Mississippi':
{'M': 1, 'i': 4, 's': 4, 'p': 2}

Discussion

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:

In [6]:
# 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()
2
2
2
In [7]:
# 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()
['aha']
['aha', 'aha']
['aha', 'aha', 'aha']

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.

3. Tic-tac-toe too easily won

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
In [3]:
"""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 Emily 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
Tic-tac-toe: enter moves by coordinates (e.g. A1 or B3)

  A|B|C
1  | | 
---+-+-
2  | | 
---+-+-
3  | | 

It is X's turn.

  A|B|C
1 X| | 
---+-+-
2  | | 
---+-+-
3  | | 

It is O's turn.

  A|B|C
1 X| | 
---+-+-
2 O| | 
---+-+-
3  | | 

It is X's turn.

  A|B|C
1 X|X| 
---+-+-
2 O| | 
---+-+-
3  | | 

It is O's turn.

  A|B|C
1 X|X| 
---+-+-
2 O|O| 
---+-+-
3  | | 

It is X's turn.

  A|B|C
1 X|X| 
---+-+-
2 O|O| 
---+-+-
3  |X| 

It is O's turn.

  A|B|C
1 X|X| 
---+-+-
2 O|O|O
---+-+-
3  |X| 

+----------------+
| Player O wins! |
+----------------+

Discussion

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.

4. A semi-chaotic sequence

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:

  1. When 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?
  2. The first time the function reducer is called, what is the value of t in the main program?
  3. What is the first four-digit number printed by the program?
    1. This will take so many iterations that you won't want to do it by hand. Instead, I suggest adding a check for a four-digit answer to the program that raises an Exception when one is found. Then use pdb to do post mortem analysis on that exception.
    2. Which of the two return statements in function reducer is executed when calculating that term in the sequence?

Some exploration with the debugger reveals the answers:

  1. The sum of indices -1 and 0
  2. 1.401649343059023
    1. 1024
    2. The second return statement (y is 1028, which is not a multiple of 3)

5. Unexpected exception competition

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:

  • Do not use any web searches!
  • The program must be completely contained in one .py file, and not depend on any modules other than the Python standard library.
  • The program should not modify any files on the computer where it is run.

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.

In [4]:
# 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)
Backpack: blue with items...
 * Pencil: pink
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-a8fe434e510b> in <module>
     85 
     86     # TODO: Test the add/radd operators
---> 87     bp = bp + blt_sandwich
     88     print(bp)
     89     bp = seuss_book + bp

TypeError: unsupported operand type(s) for +: 'BackPack' and 'Sandwich'

Reminder

If you're working on this extra challenge, the questions to ask yourself are:

  • Why might you expect this program to work? (The error isn't surprising unless you've read the code and believe you understand what the program is trying to do.)
  • What is the program actually doing that is different from your expectation?