Module assignment: budget planner in Python

The brief

A small shop runs a budget tool on a tablet at the till. The tool answers four questions for the shop owner, and each question is a dynamic programming problem you have now met in this module. The owner wants one program that reads a request, works out the answer, and prints one number. You are the developer who builds that program.

The four questions are these.

1. Coins. A customer must pay an exact amount using coins from the till's list of coin values. What is the fewest number of coins needed, or -1 if the exact amount cannot be paid?
2. Knapsack. The shop can pack a delivery van with items of different weights and values. Each item is either loaded or left behind. What is the largest total value the van can carry without going over its weight limit?
3. Longest increasing run. The shop tracks the price of one product each day. What is the length of the longest subsequence of days on which the price rose on every step? Days may be skipped, but the order must be kept.
4. Edit distance. A customer types a product name with a spelling mistake. How many single-letter changes turn the typed word into the correct product name?

Each request arrives as text, in one of four formats. The first word of the input names the task, and the rest of the input gives the data. The program must print exactly one number for each request.

This is a module assignment, so it uses everything in the module. You will write a function for each problem, use one-dimensional and two-dimensional tables, use the loop directions you learned, and handle the edge cases. You will also make the program read its input correctly, which is a skill that many beginners find harder than the algorithms.

The input format

The input starts with one word on its own, which is the task name. The task name is one of COINS, KNAPSACK, LIS or EDIT, written in capital letters. The rest of the input depends on the task.

For COINS, the next line holds the number of coin values k. The line after that holds the k coin values, separated by spaces. The last line holds the amount to pay. Every coin value is at least 1. The amount is between 0 and 1000.

For KNAPSACK, the next line holds two numbers: the number of items n and the capacity of the van. Then come n lines, each with the weight and the value of one item. Weights and values are whole numbers from 1 to 100. The capacity is between 0 and 500. The number of items is between 0 and 100.

For LIS, the next line holds the number of days n, and the line after that holds the n prices, separated by spaces. The number of days is between 1 and 2000, and each price is an integer from 1 to 10000.

For EDIT, the next two words are the typed name and the correct name. Each word has 1 to 30 letters and contains no spaces. The two words are on separate lines, but they are read the same way as the other tokens.

The output is a single integer on a single line for every task. For COINS, print -1 when the amount cannot be paid exactly. For KNAPSACK, print 0 when the capacity is 0. For LIS, print the length of the longest increasing subsequence. For EDIT, print the edit distance.

Reading the input

Python can read the whole input at once and cut it into words. The line sys.stdin.read().split() returns every word and number in the input as a list of strings, in order, whatever the line breaks look like. A program then reads the list one position at a time with a counter called pos. Each read moves the counter forward by the number of tokens it used. This is the method the reference solution uses. It works the same way for every task, so no task can leave numbers behind for the next one.

The alternative is input(), which reads one line at a time. It works here too, but a program that reads one line too many or too few gets the wrong numbers without any warning. The token method avoids that, because the count of tokens follows the format exactly.

Worked examples

The owner's tool has been tested on the examples below. Your program must print exactly these outputs. Each example is a complete input, and the output follows it.

Example 1, coins: the till has coins 1, 3 and 4, and the customer must pay 6. Input:

COINS
3
1 3 4
6

Output:

2

Two coins of value 3 pay the amount exactly. A greedy method that takes the largest coin first would pay with 4, 1 and 1, which is three coins, so the table is needed.

Example 2, knapsack: the van has capacity 7, and there are four items. Input:

KNAPSACK
4 7
1 1
3 4
4 5
5 7

Output:

9

The best choice is the items of weight 3 and 4, worth 4 and 5. Together they weigh 7 and are worth 9.

Example 3, longest increasing run: the price list is 10, 9, 2, 5, 3, 7, 101, 18. Input:

LIS
8
10 9 2 5 3 7 101 18

Output:

4

One run of length 4 is 2, 3, 7, 101. Another is 2, 5, 7, 18.

Example 4, edit distance: the customer types horse and the correct name is ros. Input:

EDIT
horse
ros

Output:

3

These four examples are the first tests your program must pass. The grader also runs hidden tests, which use other values and edge cases. You must not hard-code the outputs for the examples. The program must compute every answer from the input.

Requirements checklist

Work through this list before you submit. Each line is one requirement that the grader checks. Tick a box only after you have run the program and seen the correct output.

• The program reads the task name first, and it chooses the right function from that name.
• The COINS task prints the fewest coins for the examples, and prints -1 for an amount that cannot be paid.
• The COINS task handles an amount of 0 and prints 0.
• The KNAPSACK task loops the capacity downward so each item is used at most once.
• The KNAPSACK task prints 0 when the capacity is 0 and when no item fits.
• The LIS task returns the maximum of the table, not the last cell.
• The LIS task handles a list of one price, which must print 1.
• The EDIT task uses the three options (replace, delete and insert) and fills the base row and column with i and j, not zeros.
• The EDIT task prints 0 for two identical words. The format says each word has at least one letter, so an empty word does not occur, but the function still returns the length of the other word if one is empty.
• Every function computes its answer from its input, and no output is typed in as a constant.
• The program prints exactly one number on one line, with no extra text, labels or blank lines.
• The program does not crash on any of the four examples above.

Each task has its own function. Keep the functions separate from the reading code, so that you can test one function at a time. This habit is what the rubric rewards most.

Grading rubric

The grader scores the program out of 100, using the hidden tests. The three levels below describe what each score looks like in practice, so you can judge your own work before you submit.

60 percent: the program runs and handles some tasks. The program runs on the four examples. It answers at least two of the four tasks correctly on the examples, and it may fail on other inputs. A solution at this level usually has the right recurrence for one or two tasks, but it reads input in the wrong order for another task, or it leaves out the edge cases. Expect the grader to find a wrong answer on a hidden test for at least one task.

80 percent: all four tasks are correct on normal inputs. The program prints the right answer for every example and for typical hidden tests with moderate sizes. The coin, knapsack, LIS and edit distance functions each use the correct recurrence and fill order. The program may still fail on edge cases, such as an amount of 0, a capacity of 0, a single-price list, or a pair of identical words. The grader will see a few failures on the edge-case tests.

100 percent: all four tasks are correct on every test, including the edge cases. Every hidden test passes. The program handles the empty amount, the impossible amount, the zero capacity, the single item, the single day, and the identical words in the edit distance test. The code is readable: each function has a clear name, the table sizes are right, and the program does not crash on any input that the statement allows. A 100 percent solution also reads input the same way for every task, so no task is broken by leftover tokens from another.

To move from 60 to 80, test each function on its own with a small input before you combine them. To move from 80 to 100, go through the edge cases in the checklist one by one, and check each by hand.

A suggested order of work

Do not write the whole program at once. Build it in this order, testing after each step.

First, write the reading code only. Make the program read the task name and print it back. Then add the COINS branch and test Example 1. Next add the KNAPSACK branch with Example 2. The LIS and EDIT branches come last. Testing one branch at a time means that when something fails, you know where the bug is.

Second, for each function, write the state in one sentence before you write any Python. For coins, the state is "the fewest coins that make amount i". For the knapsack, it is "the best value using the first i items with capacity w", but the one-dimensional version only needs "the best value with capacity w". For LIS, it is "the longest run that ends at index i". For edit distance, it is "the edit distance between the first i letters and the first j letters". If a sentence is hard to write, the function is not ready.

Third, test the edge cases with a pencil. Write the answer for an amount of 0, a capacity of 0, a list of one price, and two identical words. Then run the program on those inputs and compare.

Fourth, check the input reading. Many failed submissions in this kind of assignment read the wrong number of tokens. Count the lines in the examples, and make sure your program reads exactly that many numbers for each task. A program that reads too many numbers stops with an IndexError when the input runs out, and a program that reads too few gives shifted numbers, so every later answer is wrong.

Hints

Try the hints in order. Read one, try the code, and open the next only when you are stuck.

Hint 1: reading the task name. Read the tokens once with sys.stdin.read().split(), and take the first one as the task. Then use if and elif to pick the branch. In Python, == compares the letters of two strings, so task == "COINS" is the right test.

Hint 2: the coins function. Copy the coin change function from the second lesson. Set every cell to amount + 1 first, set dp[0] = 0, and then loop the amount upward and each coin inside it. Return -1 when the last cell is still larger than the amount.

Hint 3: the knapsack function. Use the one-dimensional list of length capacity + 1. The item loop is the outer loop. The capacity loop is the inner loop, and it counts down from capacity to wt, using range(capacity, wt - 1, -1). If the capacity is 0, the loop body never runs and the answer is dp[0], which is 0.

Hint 4: the LIS function. Use the O(n squared) table from the second lesson. Start every cell at 1, compare each earlier price with the current one, and keep a running maximum called best. Return best, which is correct even when the longest run ends early.

Hint 5: the edit distance function. Use the two-dimensional list with m + 1 rows and n + 1 columns. The first column is 0, 1, 2, ... and the first row is 0, 1, 2, .... When the letters match, copy the diagonal cell. When they differ, take one plus the smallest of the diagonal, the cell above and the cell to the left. Python's min takes all three in one call.

Hint 6: why the program can print the wrong answer on one task only. If a function gives the right answer when you call it directly, but the program prints a wrong number or crashes, check the reading code. The most common cause is a number of tokens that does not match the input format. For example, a loop that reads n - 1 items instead of n leaves one number unread, and every value after it is shifted, so the answer is wrong.

Reference solution

Try to finish your own version before you open this. The reference below is correct on every example in this lesson, and it follows the rules of the module. Read it after you have compared your program with the rubric, and note any differences in how you handled the edge cases. Its functions use the same names as the hints, so you can compare them line by line.

Show the reference solution

import sys
 
 
def min_coins(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    return -1 if dp[amount] > amount else dp[amount]
 
 
def best_value(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]
 
 
def lis(prices):
    dp = [0] * len(prices)
    best = 0
    for i in range(len(prices)):
        dp[i] = 1
        for j in range(i):
            if prices[j] < prices[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
        best = max(best, dp[i])
    return best
 
 
def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
 
 
def main():
    tokens = sys.stdin.read().split()
    pos = 0
    task = tokens[pos]
    pos += 1
    if task == "COINS":
        k = int(tokens[pos])
        pos += 1
        coins = [int(t) for t in tokens[pos:pos + k]]
        pos += k
        amount = int(tokens[pos])
        print(min_coins(coins, amount))
    elif task == "KNAPSACK":
        n = int(tokens[pos])
        capacity = int(tokens[pos + 1])
        pos += 2
        weights = []
        values = []
        for _ in range(n):
            weights.append(int(tokens[pos]))
            values.append(int(tokens[pos + 1]))
            pos += 2
        print(best_value(weights, values, capacity))
    elif task == "LIS":
        n = int(tokens[pos])
        pos += 1
        prices = [int(t) for t in tokens[pos:pos + n]]
        print(lis(prices))
    elif task == "EDIT":
        a = tokens[pos]
        b = tokens[pos + 1]
        print(edit_distance(a, b))
 
 
main()

The reference reads each task with exactly the number of tokens its format specifies. That is why no task affects another. The EDIT branch reads two words, which is possible only because the statement promises no spaces inside a word. If you were told that a word could be empty, you would need to read the lines one at a time with input() and keep the empty line, as the fourth lesson showed.

What to submit

Submit one file named main.py that contains the whole program. Do not split the program into several files, because the grader runs one file. Run it on all four examples before you submit. Then run it on the edge cases from the checklist. Keep a short note of each test you ran, with the input and the output you expected and got. The note is the evidence that you checked the program, and the grader does not need it, but a good note helps you find a bug quickly if one appears later.

Reflection questions

Answer these in writing, in your own words. They are not graded for a particular answer. They ask you to explain the choices in your program, which is the skill interviewers test most.

1. Why does the coin function use amount + 1 as the marker for impossible amounts, and not a very large number such as float("inf")?
2. Why does the knapsack capacity loop go downward, and what would change if it went upward?
3. Why does the LIS function return the maximum of the table rather than the last cell?
4. For edit distance, why are the base cases i and j, and not zero?
5. Which of the four tasks would you convert to a two-variable version to save memory, and why?

What you now know

• A dynamic programming solution is a state, a recurrence, base cases, a fill order and an answer.
• Each of the four tasks in this assignment uses one of the patterns from the module.
• A program that reads several request formats must read exactly the tokens each format promises.
• Testing one function at a time, then the edge cases, finds most bugs before the grader does.