Debugging lab: greedy bugs

Why this matters

A greedy program is short. It sorts the input once, walks through it, and makes one choice at each step. Because it is short, a small mistake can make the whole answer wrong, and the program still runs without any error message. The output looks like a number, so it is easy to trust a wrong number.

The lessons in this module showed how the greedy methods work when they are written correctly. This lesson is the other side. You are given greedy code that is wrong, and your job is to find out why. The three bugs in this lab are common in greedy code.

1. A sort on the wrong key, so the greedy step picks items in a poor order.
2. A tie broken the wrong way, so two equal-looking choices give different answers.
3. A comparison that is strict where it should be loose, or loose where it should be strict. One version rejects a pair that exactly fits, and another breaks the rules that std::sort needs.

Each program is short and has one bug. You will predict what the program should print, run it, read the output, explain the bug in plain words, and then fix it. The method is the same for each lab. Predict first, run second, and change one thing at a time.

Setting up the lab

Create a folder for the lab files. Each program below goes in its own file. Compile each file with the same command, changing only the file name and the program name.

g++ -std=c++20 -Wall -o truck_wrong truck_wrong.cpp

The flags have these meanings. -std=c++20 tells the compiler to use the C++20 rules, which include std::ranges::sort. -Wall turns on the usual warnings. -o truck_wrong sets the name of the program file that the compiler writes. The last part names the source file.

Run each program with a time limit. A time limit stops the program after a set number of seconds, so a program that never ends does not hang the terminal. The timeout command does this. The echo "exit $?" part prints the exit code, which is the number a program returns when it finishes. Zero means success. Other numbers mean something went wrong.

timeout 10 ./truck_wrong; echo "exit $?"

Some bugs show up only when extra checks are on. The flag -D_GLIBCXX_DEBUG turns on checks in the C++ standard library. It makes the program slower, so use it only while you are debugging. Lab 3 uses it.

Lab 1: the sort on the wrong key

A sort key is the value the sort uses to decide the order. std::greater{} makes the sort put the largest key first. Sorting by the wrong key puts items in a poor order, even when the rest of the code is correct.

The problem is a truck. A truck can carry a fixed number of boxes. Each box type has a number of boxes and a number of units in each box. The goal is to fill the truck so that the total number of units is as large as possible. A unit here just means one item inside a box.

Take this example. The truck holds 5 boxes. There are two box types:

• Type A: 5 boxes, and each box holds 3 units.
• Type B: 1 box, and that box holds 10 units.

The best choice is clear to a person. Take the one box of type B, which gives 10 units. Then take 4 boxes of type A, which give 12 more units. The total is 22.

The greedy rule is to take the boxes that hold the most units first. The sort key must be the units per box. The program below uses the number of boxes as the sort key instead. Save it as truck_wrong.cpp.

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
 
struct BoxType {
    int boxes;         // how many boxes of this type exist
    int unitsPerBox;   // how many units each box holds
};
 
// BUG: sorts by the number of boxes, not by units per box
int maxUnitsWrong(std::vector<BoxType> types, int truckSize) {
    std::ranges::sort(types, std::greater{}, &BoxType::boxes);
    int total = 0;
    for (const BoxType& t : types) {
        int take = std::min(t.boxes, truckSize);
        total += take * t.unitsPerBox;
        truckSize -= take;
    }
    return total;
}
 
// Fixed: take the boxes that hold the most units first
int maxUnits(std::vector<BoxType> types, int truckSize) {
    std::ranges::sort(types, std::greater{}, &BoxType::unitsPerBox);
    int total = 0;
    for (const BoxType& t : types) {
        int take = std::min(t.boxes, truckSize);
        total += take * t.unitsPerBox;
        truckSize -= take;
    }
    return total;
}
 
int main() {
    std::vector<BoxType> types = {{5, 3}, {1, 10}};
    std::cout << "wrong sort key: " << maxUnitsWrong(types, 5) << '\n';
    std::cout << "fixed:          " << maxUnits(types, 5) << '\n';
}

Predict

Before you run the program, write down the answer you expect for each line. The correct total is 22. Write down what you think the buggy version prints.

Run

g++ -std=c++20 -Wall -o truck_wrong truck_wrong.cpp
timeout 10 ./truck_wrong; echo "exit $?"

The program prints:

wrong sort key: 15
fixed:          22
exit 0

Read

The program runs and exits with 0, so nothing looks broken. The number is different, though. The buggy version gives 15 and the fixed version gives 22.

Look at what the buggy sort does. It puts type A first, because 5 boxes is more than 1 box. The greedy loop then takes all 5 boxes of type A, which gives 5 times 3, or 15 units. The truck is full, and the single box of 10 units never gets a place. The sort looked at the count of boxes, and the count is not what the truck cares about.

Fix

The fixed function sorts by unitsPerBox, so the box with 10 units comes first. The greedy loop takes 1 box of type B for 10 units. Then it takes 4 boxes of type A for 12 units. The total is 22.

A quick check for any greedy program: write the value you are trying to maximize, and ask whether the sort key puts the best choice first. If the sort key is anything else, the greedy choice is wrong.

Lab 2: the tie that goes the wrong way

A tie happens when two candidates have the same value on the key you are comparing. The bug in this lab is about choosing among tied candidates. The code walks through a list and keeps the best one seen so far. The problem asks for the earliest candidate when there is a tie, but the code keeps the last one.

The program looks for the cheapest fuel station on a road. The station order matters, because the driver reaches the stations in that order. When two stations cost the same, the rule is to pick the earlier one, since it is reached sooner. Save the program as tie_station.cpp.

#include <cstddef>
#include <iostream>
#include <vector>
 
// Return the index of the cheapest price. On a tie, return the earliest index.
std::size_t cheapest_buggy(const std::vector<int>& prices) {
    std::size_t best = 0;
    for (std::size_t i = 1; i < prices.size(); ++i) {
        if (prices[i] <= prices[best]) best = i;  // BUG: <= moves to a later tie
    }
    return best;
}
 
std::size_t cheapest_fixed(const std::vector<int>& prices) {
    std::size_t best = 0;
    for (std::size_t i = 1; i < prices.size(); ++i) {
        if (prices[i] < prices[best]) best = i;   // strict: keep the earliest tie
    }
    return best;
}
 
int main() {
    std::vector<int> prices = {4, 2, 7, 2, 9};
    std::cout << "buggy index: " << cheapest_buggy(prices) << '\n';
    std::cout << "fixed index: " << cheapest_fixed(prices) << '\n';
}

Predict

The prices are 4, 2, 7, 2 and 9. The cheapest price is 2, and it appears at index 1 and index 3. The rule says to return index 1. Write down what each function should print.

Run

g++ -std=c++20 -Wall -o tie_station tie_station.cpp
timeout 10 ./tie_station; echo "exit $?"

The program prints:

buggy index: 3
fixed index: 1
exit 0

Read

Walk through the buggy loop by hand. The variable best starts at index 0, which has price 4. At index 1, the price 2 is less than 4, so best becomes 1. At index 2, the price 7 is not less than 2, so nothing changes. At index 3, the price is 2, and the test prices[3] <= prices[1] is 2 <= 2, which is true. So best moves to 3.

The <= test accepts a tie. Every later tie replaces the earlier choice. The result is the last cheapest station, not the first one.

Fix

Use < instead. A strict comparison only replaces best when the new price is really cheaper. A tie keeps the earlier index. The fixed function prints index 1.

Why this is easy to miss

Ties are rare in random test data. A test with prices 4, 1, 9 gives index 1 from both functions, so the test passes. The bug shows up only when two equal values are the best. Good tests include ties on purpose. Use inputs where the best value appears more than once, and check which index the problem asks for.

Lab 3: the exact fit and the loose comparison

A comparison is a test that says whether one value is less than, equal to or greater than another. Greedy code uses comparisons in two places: to decide whether an item fits, and inside the comparator that the sort uses.

A comparator is a function that takes two items and returns true when the first should come before the second. The C++ sort functions need the comparator to follow strict rules. The short version of the rule is this: an item must never be before itself. A comparator that returns true for two equal items breaks that rule. The sort can then read past the ends of its data.

This lab has two parts. Part A is a boat problem where the code rejects a pair that exactly fits. Part B is a sort whose comparator is loose, and it breaks only in a checked build.

Part A: the pair that exactly fits

The boat problem is this. Each person has a weight. A boat can carry at most a fixed weight limit. Each boat holds one or two people. The greedy method sorts the people by weight, then pairs the heaviest person with the lightest one if they fit together. If they do not fit, the heaviest person goes alone.

The rule is "fit within the limit," which means the total can be equal to the limit. The buggy version uses a strict test and rejects a total that equals the limit. Save the program as boats_strict.cpp.

#include <algorithm>
#include <iostream>
#include <vector>
 
// People are sorted by weight. Pair the heaviest with the lightest when they fit.
int boats_buggy(std::vector<int> people, int limit) {
    std::ranges::sort(people);
    int lo = 0;
    int hi = static_cast<int>(people.size()) - 1;
    int count = 0;
    while (lo <= hi) {
        if (people[lo] + people[hi] < limit) ++lo;  // BUG: a pair that exactly fits is rejected
        --hi;
        ++count;
    }
    return count;
}
 
int boats_fixed(std::vector<int> people, int limit) {
    std::ranges::sort(people);
    int lo = 0;
    int hi = static_cast<int>(people.size()) - 1;
    int count = 0;
    while (lo <= hi) {
        if (people[lo] + people[hi] <= limit) ++lo;
        --hi;
        ++count;
    }
    return count;
}
 
int main() {
    std::vector<int> people = {1, 2};
    std::cout << "buggy boats: " << boats_buggy(people, 3) << '\n';
    std::cout << "fixed boats: " << boats_fixed(people, 3) << '\n';
}

The variable lo points at the lightest person who is not yet in a boat. The variable hi points at the heaviest person who is not yet in a boat. Each loop run sends one boat. When the pair fits, both people leave, so lo moves up. The heaviest person always leaves, so hi moves down.

Predict

Two people weigh 1 and 2. The limit is 3. Together they weigh exactly 3, so they can share one boat. Write down the number of boats you expect from each function.

Run

g++ -std=c++20 -Wall -o boats_strict boats_strict.cpp
timeout 10 ./boats_strict; echo "exit $?"

The program prints:

buggy boats: 2
fixed boats: 1
exit 0

Read

The buggy version uses <. The sum is 3 and the limit is 3, so 3 < 3 is false. The pair is rejected, and lo stays at 0. The heaviest person leaves alone, which is one boat. Then lo is still 0 and hi is also 0. The loop runs once more and sends the lightest person alone. That is a second boat, which is more than needed.

The bug is not a crash. The answer is just too large. A wrong answer like this is easy to miss unless a test has a total that exactly equals the limit.

Fix

Use <=. The pair fits when the total is at most the limit, and an exact fit is allowed. The fixed version prints 1.

Part B: the loose comparator

The next program sorts 40 values that are all equal. Its comparator uses <=, which is a loose comparison. The [](int a, int b) { ... } part is a lambda, a small function written in place. Save it as sort_loose.cpp.

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> values(40, 5);  // many equal values
    // BUG: <= is not a strict weak ordering; equal items must not compare as less
    std::ranges::sort(values, [](int a, int b) { return a <= b; });
    std::cout << "sorted " << values.size() << " values\n";
}

A strict weak ordering is the name for the rules a comparator must follow. The main rule is that a < a must be false for every item a. The comparator a <= b breaks this rule, because a <= a is true. Equal items look like they should come before each other.

Run it normally

g++ -std=c++20 -Wall -o sort_loose sort_loose.cpp
timeout 10 ./sort_loose; echo "exit $?"

The program prints:

sorted 40 values
exit 0

The output looks correct, and the exit code is 0. The bug is still there. The standard library is allowed to assume the rule holds, so a broken comparator can make it read outside its data. In this run, the broken case caused no visible failure.

Run it with the checks on

g++ -std=c++20 -Wall -g -D_GLIBCXX_DEBUG -o sort_loose_dbg sort_loose.cpp
timeout 10 ./sort_loose_dbg; echo "exit $?"

The checked build stops and prints a message. The output begins with the file in the standard library that caught the problem, with its line number (both depend on your compiler version), and then it gives this line:

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

The exit code is 134. The message names the rule that the comparator breaks. "Irreflexive" is the name for the rule that nothing is less than itself. The fix is to use < in the comparator:

std::ranges::sort(values, [](int a, int b) { return a < b; });

The < version passes the checked build and prints the same line as before, with exit code 0.

Common mistakes

Reading only the last line

The last line of output is often a total, and it can look right. Read every line. In Lab 1, the first line was the wrong answer, and the second line was the correct one. The difference between the two lines is the bug.

Testing only with inputs that have no ties

A test with all values different hides tie bugs. Add inputs where the best value appears two or three times, and check which index or which item the problem asks for.

Testing only with a total that is far from the limit

A test where the pair is far under the limit hides the exact-fit bug. Add one test where the total equals the limit, and one where it is one more than the limit.

Changing several things at once

When an output is wrong, change one line, compile, and run again. If you change the sort key, the comparison and the loop in one step, you cannot tell which change fixed the output, or whether another change broke something else.

Trusting a fast run

A program that finishes quickly with exit code 0 can still be wrong. The sort in Part B finished and exited normally. The checked build found the problem. For code that uses a comparator, compile once with -D_GLIBCXX_DEBUG before you trust the result.

Practice

Exercise 1

The truck holds 4 boxes. Type A has 2 boxes with 4 units each. Type B has 3 boxes with 4 units each. Type C has 1 box with 9 units. What total does maxUnits return? Explain why types A and B give the same result in either order.

Show the answer

The total is 21. The sort puts the 9-unit box first, so the loop takes 1 box for 9 units. Next it takes 2 boxes of type A for 8 units, and then 1 box of type B for 4 units. The truck holds 4 boxes in total, so the sum is 9 + 8 + 4 = 21. Types A and B are worth the same per box, so the order between them does not change the answer.

Exercise 2

Change cheapest_fixed so that it returns the index of the cheapest price, and on a tie returns the latest index. What single character changes, and what does the program print for the prices 4, 2, 7, 2, 9?

Show the answer

The comparison changes from < to <=, so the test becomes prices[i] <= prices[best]. One character is added, the =. For the prices 4, 2, 7, 2, 9, the program prints index 3. This is the same as the buggy version in Lab 2. The result is correct only if the problem asks for the latest tie.

Exercise 3

Two people weigh 3 and 3. The limit is 6. What do boats_buggy and boats_fixed print? Explain the result of the buggy version step by step.

Show the answer

boats_fixed prints 1, because the pair fits exactly. boats_buggy prints 2. The first loop run rejects the pair, since 3 + 3 < 6 is false. The heavier person leaves alone and hi moves to 0. The second loop run has lo and hi both at index 0, so the test compares that person with themselves, 3 + 3 < 6 is again false, and the second boat is counted. The buggy answer is one boat too many.

Exercise 4

Write a comparator that sorts people by height from tallest to shortest, and when two people have the same height, puts them in name order from A to Z. Use the struct Pet with the fields name and height. Show the comparator, and say which rule of the strict weak ordering it respects.

Show the answer

std::ranges::sort(pets, [](const Pet& a, const Pet& b) {
    if (a.height != b.height) return a.height > b.height;
    return a.name < b.name;
});

For the input bo 5, al 5 and cy 7, the sorted output is cy 7, al 5, bo 5. The comparator never returns true for an item compared with itself. Two items with the same height are ordered by name, and two items with the same name and height compare as equal, not as less. This respects the strict rule.

Exercise 5

Your team's greedy code gives correct answers on all the tests except one. The failing test has two items with the same best value. Name the bug you would check first, and say what test you would add to prove the fix.

Show the answer

Check the comparison that updates the best choice, and the comparator if the code sorts first. A loose comparison such as <= or >= in the update step picks a later tie, and the wrong choice would appear only when two values match. Add a test where the best value appears twice and the problem asks for a specific one of them. Assert that the output is the expected index or item, and run the test on the fixed code.

Summary

• A greedy result is only as good as its sort key, so write down what you are maximizing and sort by that value.
• A tie is a case where two candidates have the same key, so decide which one the problem wants and test it on purpose.
• Use <= to accept an exact fit, such as a total equal to a limit, and use < only when the rule says strictly less.
• A comparator must never be true for an item compared with itself, so use < and not <= in a sort comparator.
• Compile with -D_GLIBCXX_DEBUG while you test code that sorts with a comparator, and read every line of output.