Module assignment: Trip planning helper

Why this assignment

The five lessons in this module each taught one family of DP problems. This assignment asks you to put them together in a single program, the way a real tool would. The tool reads a list of questions, answers each one, and prints the answers in order. Each question type is solved by a different DP method from the lessons, so you will use memoization or tabulation, a one-dimensional table, and a two-dimensional table, all in one file.

The program is a small planning helper for a trip. It answers three kinds of question. A question about stairs asks how many ways a walker can climb a flight of steps. A question about coins asks for the fewest coins that pay an exact amount. A question about two words asks how much of them is shared in order. None of these is hard on its own. The challenge is to write them cleanly, test them, and make the program read its input correctly.

You are expected to write the code yourself. The hints are there when you are stuck, and the reference solution is there to check your answer after you have tried. Try each step before you open a hint.

The specification

Your program reads from standard input. The first line holds a single integer q, the number of queries. Each of the next q lines is one query. A query starts with one of three command words, followed by its data.

steps n asks for the number of ways to climb n steps, taking 1 or 2 steps at a time. Use the same definition as lesson 1: there is exactly one way to climb zero steps. Here 0 <= n <= 45. Print the count as a long long.

change T k c1 c2 ... ck asks for the fewest coins that add up to exactly T. There are k coin values, which are c1 through ck, and you may use as many coins of each value as you need. Here 0 <= T <= 10000, 1 <= k <= 20, and each coin value is between 1 and 1000. Print the fewest coins, or -1 when the amount cannot be made. An amount of 0 needs 0 coins.

common s t asks for the length of the longest common subsequence of the two words s and t. Each word has between 1 and 300 lowercase letters and no spaces. A subsequence keeps the order of the letters but may skip them.

Print exactly one line for each query, in the same order as the input. Print nothing else. Unknown commands are not part of the test data, so you do not need to handle them.

An example

Here is an input file with four queries.

4
steps 5
change 11 3 1 2 5
change 3 1 2
common abcbdab bdcaba

Your program must print this output.

Check each line by hand before you trust the program. The stairs answer for 5 steps is 8, the same as the Fibonacci table in lesson 2. The coins 1, 2 and 5 pay 11 with 5 + 5 + 1, which is three coins. The coin 2 cannot pay 3, so the answer is -1. The longest common subsequence of abcbdab and bdcaba is 4, as in lesson 4.

Requirements checklist

Copy this list into your notes and tick each item when it is true. The checklist is also how a marker decides between the rubric levels below.

Grading rubric

The grade depends on how many of the requirements your program meets and how well it meets them. The three levels below describe what a typical solution looks like at each grade.

60 percent. The program compiles and reads the input. Two of the three commands give correct answers on the sample and on small tests. The third command may be missing or may give wrong answers in some cases. Output may contain extra spaces or blank lines. The code is in one long main function, and the state of each DP is not explained.

80 percent. All three commands are implemented and give correct answers on the sample and on small tests, including the -1 cases for change. Each command has its own function. The state of each DP is written in a comment. The program fails at most one of the larger hidden tests, usually because of a limit that was not checked, such as an amount larger than the table or a word longer than expected.

100 percent. All three commands give correct answers on the sample, on small tests and on the largest inputs the specification allows. That means steps 45, change with an amount of 10000 and 20 coins, and common with two words of 300 letters, all within a second. The steps function uses constant extra space. The change function uses a marker that is never confused with a real answer. Every function has a comment that states its complexity, and the code is clear enough that another student could follow each DP without help.

Markers also look at how you test. A solution that has been checked on the edge cases in the next section is much more likely to reach the top grade than one that only passes the sample.

A suggested order of work

Do the work in small steps, and test each step before you move on. Trying to write the whole program at once makes bugs hard to find.

First, read the input. Write the loop that reads q and prints the command word of each query. The starter below does exactly that, and it prints a line that shows what it read. Once the reading is right, you know the next step will get the right data.

Second, write the steps function. You have seen this exact pattern in lesson 2. Test it with steps 5, which should print 8, and then steps 0, which should print 1.

Third, write the change function. It is the coin change table from lesson 3, with a marker that is not zero. Test it with change 11 3 1 2 5 and change 3 1 2.

Fourth, write the common function. It is the LCS table from lesson 4. Test it with common abcbdab bdcaba and then with two words that share no letters, which should print 0.

Fifth, join the parts. Replace the placeholder output with calls to your three functions, and run the full sample. Only then should you test the larger inputs.

Step 1: reading the input

The starter reads the input and prints a summary of each query. It does not solve anything yet, but it shows how the three command formats differ. Note that the change query has a variable number of coins, so the code must read k first and then read exactly k numbers. A common mistake is to read the coins with a fixed count, which makes every later query start at the wrong place.

C++ · editable

#include <iostream>
#include <string>
using namespace std;

int main() {
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        string command;
        cin >> command;  // steps, change or common
        if (command == "steps") {
            int n;
            cin >> n;
            cout << "query " << i << ": steps with n = " << n << "\n";
        } else if (command == "change") {
            int T, k;
            cin >> T >> k;      // the amount, then how many coins follow
            for (int j = 0; j < k; j++) {
                int coin;
                cin >> coin;    // read every coin so the next query starts in the right place
            }
            cout << "query " << i << ": change with T = " << T << "\n";
        } else if (command == "common") {
            string s, t;
            cin >> s >> t;
            cout << "query " << i << ": common of " << s << " and " << t << "\n";
        } else {
            cout << "query " << i << ": unknown command\n";
        }
    }
}

Type the sample input into the Input box, with the first line 4 and then the four query lines, and press Run.

Output:

query 1: steps with n = 5
query 2: change with T = 11
query 3: change with T = 3
query 4: common of abcbdab and bdcaba

Look at the change branch. The variable coin is read and then not used. That is intentional for now. Once you have the solver, you will store the coins in a vector and pass them to the function. The point of this step is to check that the query count and the coin count move the input pointer correctly. If the second change line printed the wrong T, the first query would have read too few or too many numbers.

Step 2: the solvers

The next program holds the steps and change solvers, with a short test in main. It is the code you should start from, and you may change it. The comments state the state and the complexity, which the checklist asks for.

C++ · editable

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// State: n, the number of steps. Time O(n), space O(1).
long long countSteps(int n) {
    if (n == 0) return 1;
    long long prev2 = 1, prev1 = 1;  // ways(0), ways(1)
    for (int i = 2; i <= n; i++) {
        long long cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

// State: amount a, dp[a] = fewest coins that add up to a, or INF.
// Time O(T times k), space O(T).
int fewestCoins(int T, const vector<int>& coins) {
    const int INF = 1000000000;
    vector<int> dp(T + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= T; a++)
        for (int c : coins)
            if (c <= a && dp[a - c] != INF) dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[T] == INF ? -1 : dp[T];
}

int main() {
    cout << countSteps(5) << "\n";
    cout << countSteps(0) << "\n";
    cout << fewestCoins(11, {1, 2, 5}) << "\n";
    cout << fewestCoins(3, {2}) << "\n";
    cout << fewestCoins(0, {2}) << "\n";
}

Output:

The five lines test the easy cases the checklist asks for. countSteps(0) must return 1, which is the base case. fewestCoins(0, {2}) must return 0, not -1, because the amount zero is always made with no coins. Keep these checks in your final program, because they catch the common mistakes at the edges.

Step 3: the two-word solver

The last solver counts the longest common subsequence. The table has one extra row and column for the empty prefix, as in lesson 4. The program below tests it on the two example words, and on two words with no shared letters.

C++ · editable

Output:

4
0
1

The three tests cover the shared case, the empty case and the single-letter case. A solver that passes all three is close to correct. The next section shows how to test the rest.

Testing your work

A marker runs your program on many inputs, and most of them are not the sample. You should do the same. The table below lists the cases that catch the most common mistakes. For each one, predict the output on paper, run your program, and compare.

Query	What it tests	Expected output
`steps 0`	the base case	1
`steps 1`	the smallest non-trivial case	1
`steps 45`	the largest allowed `n`, and overflow	1836311903
`change 0 1 7`	amount zero	0
`change 3 1 2`	an impossible amount	-1
`change 10000 3 1 3 7`	a large amount, within time	check with your own run
`common a a`	two identical letters	1
`common abc xyz`	no shared letters	0
`common abcd dcba`	a shared letter, out of order	1

Check the steps 45 answer by working it out from the rule: each value is the sum of the two before it, starting from 1 and 1. The value must fit in a long long, and a plain int would overflow long before 45. For change 10000, the program should finish in well under a second. If it is slow, check that you have one table of size T + 1, and not a new table for each coin.

Make a file with 20 queries that mixes all three types, and check that the output has exactly 20 lines. A common failure is a line that is missing because a query read too few coins, or an extra line because a debugging print was left in.

Practice

These exercises extend the planner. Try each one in a copy of your program, so the graded version stays unchanged.

Easy. Change steps so a move may be 1, 2 or 3 steps. Predict steps 4 before you run it.

Solution

Add a third term, so ways(n) = ways(n - 1) + ways(n - 2) + ways(n - 3) with ways(0) = 1, ways(1) = 1 and ways(2) = 2. The answer for steps 4 is 7.

Easy. Work out change 6 2 3 4 by hand, then check it. Which two coins make 6?

Solution

The query lists the coins 3 and 4. Two coins of value 3 make 6, so the answer is 2. The coin 4 alone cannot make 6, and no single coin does either.

Easy. Find common aaaa aa by hand. Then explain why the answer is not 4.

Solution

The table gives 2, because aa is the longest common subsequence. The answer is not 4 because the second word has only two letters, so no common subsequence can be longer than 2.

Medium. Add a query reach T k c1 ... ck that prints 1 when the amount can be made and 0 when it cannot. Use a table of true or false values, as in lesson 3.

Solution

Make a vector<bool> with can[0] = true, loop over the coins outside and the amounts inside going downwards, and print can[T]. This is the subset sum idea, applied to amounts.

Medium. Change change so it also prints one set of coins that achieves the minimum. Keep an extra array that records the coin used at each amount, and walk back from T.

Solution

Store lastCoin[a] when the minimum improves. Start at T and repeatedly take lastCoin, subtracting it from the amount, until you reach 0.

Medium. Write a test plan of five queries that would catch a missing base case in steps. Predict the output of each.

Solution

Use steps 0 (expected 1), steps 1 (expected 1), steps 2 (expected 2), steps 3 (expected 3) and steps 45 (expected 1836311903). A missing base case shows at once on the first two.

Medium. Write the first two rows of the LCS table for ab and ba by hand, and find the answer from the table.

Solution

Columns are the empty prefix, b and ba. Row 1, for the letter a, is 0, 0, 1. Row 2, for ab, is 0, 1, 1. The bottom right cell is 1, so the LCS is 1, which is the letter a or the letter b.

Hard. The steps answer for 91 still fits in a long long, but the answer for 92 does not. Explain why, using the fact that the answer for n steps is the Fibonacci number fib(n + 1).

Solution

The answer for n steps is fib(n + 1), and fib(92) is 7540113804746346429, the largest Fibonacci value a signed 64-bit integer holds. So steps 91 gives fib(92) and fits, and steps 92 gives fib(93), which overflows.

Hints

Try the steps first. Each hint below unlocks only the next step, so you can check your own progress. Open them one at a time.

Hints

Read q with cin, then use a for loop that runs exactly q times. Each pass reads one command word.
Use an if and else if chain on the command word. Read the data for that command before you print anything.
For change, read T and k, then read exactly k coin values into a vector<int>. Pass that vector to your solver.
For steps, copy the two-variable loop from lesson 2, and handle n equal to 0 before the loop.
For change, the table starts with a marker. Only dp[0] is zero. Check the marker before you add 1, and print -1 when the last cell still holds it.
For common, copy the LCS table from lesson 4. Remember that dp[i][j] uses the letters s[i - 1] and t[j - 1].
Print each answer followed by a newline. Do not print any labels, because the output must match the sample exactly.

Reference solution

Read this only after you have tried the assignment. It is one correct program, not the only one. Yours may be shaped differently and still be correct.

Reference solution

C++ · editable

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// steps: ways to climb n steps taking 1 or 2 at a time. Time O(n), space O(1).
long long countSteps(int n) {
    if (n == 0) return 1;
    long long prev2 = 1, prev1 = 1;  // ways(0), ways(1)
    for (int i = 2; i <= n; i++) {
        long long cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

// change: fewest coins that add up to T, or -1. Time O(T times k), space O(T).
int fewestCoins(int T, const vector<int>& coins) {
    const int INF = 1000000000;  // a marker that no real answer can reach
    vector<int> dp(T + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= T; a++)
        for (int c : coins)
            if (c <= a && dp[a - c] != INF) dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[T] == INF ? -1 : dp[T];
}

// common: length of the longest common subsequence. Time O(n times m), space O(n times m).
int lcsLength(const string& s, const string& t) {
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = s[i - 1] == t[j - 1] ? dp[i - 1][j - 1] + 1
                                            : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[n][m];
}

int main() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string command;
        cin >> command;
        if (command == "steps") {
            int n;
            cin >> n;
            cout << countSteps(n) << "\n";
        } else if (command == "change") {
            int T, k;
            cin >> T >> k;
            vector<int> coins(k);
            for (int j = 0; j < k; j++) cin >> coins[j];
            cout << fewestCoins(T, coins) << "\n";
        } else if (command == "common") {
            string s, t;
            cin >> s >> t;
            cout << lcsLength(s, t) << "\n";
        }
    }
}

Type the sample input from the specification into the Input box, with 4 on the first line and the four query lines after it, then press Run.

Output:

Explaining your solution

After you have a correct program, write a short note of four to six sentences in a comment at the top of the file. Say what each of the three functions computes, which DP method it uses, and why its loop order is correct. This note is what you would say in an interview, and it proves you understand the method, not only the code.

Include one sentence on the limits. For example, say that countSteps uses long long because the answer for 45 steps is too large for an int, and that fewestCoins uses a marker of one billion because no real answer can reach it with at most 10000 coins of value 1. That is the kind of detail that separates a solution that happens to pass from one you can defend.

What this assignment checks

The assignment brings together every idea in the module, and each part is a skill you will need in interviews. The steps function tests the recurrence and the base cases from lesson 2. The change function tests the marker and the loop logic from lesson 3. The common function tests the two-dimensional table, the index shift and the loop order from lesson 4. Reading the input in the right order tests the discipline of careful input handling, which matters in every program you will write. Testing edge cases tests your habit of checking small inputs by hand before you trust a large one.

If you reach the 100 percent level, you have shown that you can take a set of DP problems, implement each one cleanly, test it, and explain it. That is the ability this module set out to build.

Module assignment: Trip planning helper

Why this assignment

The specification

An example

Requirements checklist

Grading rubric

A suggested order of work

Step 1: reading the input

Step 2: the solvers

Step 3: the two-word solver

Testing your work

Practice

Hints

Reference solution

Explaining your solution

What this assignment checks

Stuck? Ask the tutor