Debugging lab: greedy bugs in Python

Why this matters

A greedy program can be wrong in a quiet way. It runs, it prints a number, and the number is too small. Nothing crashes, so nothing tells you to look again. The earlier lessons in this module showed the rules. This lesson is about finding the bug when the code does not follow the rule.

Many greedy bugs come from four small places. The sort key is wrong. Two items tie on the key and the code handles the tie badly. The comparison that decides whether an item fits is strict where it should be loose, or the other way round. The sort function gets a comparator that breaks its rules. The code looks right when you read it quickly. The only way to find these bugs is to run small cases by hand, compare with an answer you know is right, and change one thing at a time.

This lesson is a lab. You get one program with four bugs. You will reproduce each bug, find the line that causes it, and fix it. The problem is meetings in one room. The rule behind it is the one the earlier lessons in this module prove, so this lesson does not prove it again.

Words you will need

• Greedy: at each step, take the choice that looks best now, and keep it.
• Meeting: a start time and an end time, both whole numbers. A meeting from 2 to 5 is written [2, 5]. In the lab, a meeting is a small object with two fields, start and end.
• Sort key: the value that sorted compares. You pass it with key=. key=lambda m: m.start means the sort compares start times. A lambda is a short function written on one line with no name. lambda m: m.end takes a meeting m and returns its end time.
• Tie: two items with the same sort key. For example, two meetings that both start at 7.
• Stable sort: a sort that keeps equal items in the order they came in. Python's sorted and list.sort are both stable.
• Comparator: a function that takes two items, a and b, and says which one comes first. It returns a negative number when a comes first, zero when they are equal, and a positive number when b comes first. Python's sort does not take a comparator directly. functools.cmp_to_key turns a comparator into a key.
• Consistent comparator: a comparator whose answers agree with each other. If a comes before b, then b never comes before a. Two equal items must get zero.
• Boolean: a value that is True or False. A comparison such as a.end > b.end gives a boolean. It is not a comparator result.
• Strict comparison: a test that uses > or <, which fails when the two values are equal.
• Loose comparison: a test that uses >= or <=, which passes when the two values are equal.
• Touching: two meetings where one ends at exactly the time the other starts. In this lab, touching meetings can both be used.
• Brute force: trying every possible answer and keeping the best. It is slow, but it is simple enough to trust. You use it only on small inputs.
• Counterexample: a small input where a rule gives the wrong answer. One counterexample is enough to prove a rule is wrong.
• Reproduce: run the same input again and get the same wrong result. A bug you cannot reproduce is hard to fix.
• f-string: a string that starts with f, such as f"[{self.start}, {self.end}]". Each {...} part is replaced by its value when the code runs.

The problem: as many meetings as possible in one room

You have a list of meetings. Two meetings clash when they overlap in time. Choose the largest set of meetings that do not clash.

Touching is allowed. A meeting from 1 to 3 and a meeting from 3 to 5 do not clash, because the first one has ended when the second one starts. Keep that in mind for the strict comparison bug.

The correct rule is this. Sort the meetings by end time, earliest first. Walk through them. Take a meeting when its start is at or after the end of the last meeting you took. Keep a variable last_end for the end of the last meeting taken.

Here is the rule on a small list, by hand. The meetings are [1, 4], [2, 5], [6, 8], [5, 7]. Sorted by end, they are [1, 4], [2, 5], [5, 7], [6, 8].

• Take [1, 4]. The last end is now 4.
• [2, 5] starts at 2, which is before 4. Skip it.
• [5, 7] starts at 5, which is at or after 4. Take it. The last end is now 7.
• [6, 8] starts at 6, which is before 7. Skip it.

The answer is 2. The two meetings taken are [1, 4] and [5, 7].

How to debug a greedy program

Use the same steps every time. They work for any greedy bug.

1. Find a small input that gives the wrong answer. Two or three meetings are often enough.
2. Work the small input by hand with the correct rule. Write the sorted order and the taken meetings in a table.
3. Compare your hand answer with the program. The first line where they differ is the bug.
4. Look at that line only. Ask what its sort key is, what happens on a tie, and whether the comparison is strict or loose.
5. Change one thing. Run again. If the answer is still wrong, change the next thing, not three things at once.

A brute-force checker helps with step 1. It is a second program that tries every subset of the meetings and keeps the largest set that does not clash. It is slow, so use it only on up to about 8 meetings. The lab includes one, later in this lesson.

The lab program

The program below holds the correct rule and five buggy versions of it, which cover the four bugs in this lesson. Read the buggy versions and try to find each bug before you read the explanations.

meeting_lab.py:

The Meeting class is a frozen dataclass. A dataclass is a class that stores its fields for you, and frozen=True means you cannot change a meeting after you make it. __repr__ controls how a meeting prints, so the output shows [1, 10].

pick walks through the sorted list and counts the meetings it takes. last_end starts at float("-inf"), which is smaller than any time, so the first meeting always fits.

Run it from the folder where you saved the file:

python3 meeting_lab.py

The output is:

A [[1, 10], [2, 3], [4, 5]] correct=2 wrongStartKey=1
L [[1, 3], [3, 4], [2, 5]] correct=2 wrongLengthKey=1
B [[1, 3], [3, 5], [5, 7]] correct=3 strictCheck=2
C [[1, 4], [2, 4], [5, 6]] correct=2 badComparator=2
D [[1, 10], [2, 3], [4, 5]] correct=2 boolComparator=1
50 seeds of 200 meetings: badComparator wrong on 0, boolComparator wrong on 50

Each of the first four lines shows the correct answer next to a buggy one. Three of the buggy versions give a smaller number. The comparator version in line C gives the right number on these inputs. Line D shows the boolean comparator, which gives a smaller number on input D. The last line runs 50 seeded random inputs of 200 meetings. The <= comparator was wrong on none of them. The boolean comparator was wrong on all 50. The meetings come from Python's random module. A seed is the starting number for it, so the same seed gives the same meetings on every run. These numbers belong to this exact code.

Bug 1: the wrong sort key, start time

The first buggy version sorts by start time, not end time. Its sort line is ordered = sorted(meetings, key=lambda m: m.start). Look at input A: [1, 10], [2, 3] and [4, 5].

Sorted by start, the order is [1, 10], [2, 3], [4, 5]. The first meeting is [1, 10], which starts at 1. It is taken, and the last end becomes 10. Both other meetings start before 10, so both are skipped. The answer is 1.

The correct order, sorted by end, is [2, 3], [4, 5], [1, 10]. Take [2, 3], then [4, 5] (it starts at 4, which is at or after 3). The meeting [1, 10] is skipped. The answer is 2.

The start-time key picks a long meeting first, and that one blocks the short ones. Ending early is what leaves room for later meetings, so the end time is the key.

A tie inside the wrong key

Ties make the start-time key fail in a second way. Take the input [7, 9], [7, 8] and [8, 9]. Two meetings start at 7. A sort by start time keeps them in input order, because Python's sort is stable. That puts [7, 9] first. Taking it gives a last end of 9, and both other meetings start before 9, so both are skipped. The answer is 1.

Running the same two functions on this input gives correct = 2 and wrong_start_key = 1. The correct order by end is [7, 8], [7, 9], [8, 9]. Taking [7, 8] and then [8, 9] gives 2.

A tie on the correct key is harmless. Take two meetings that both end at 9, such as [3, 9] and [5, 9]. Whichever one you take first, the second one starts before 9, so it clashes and is skipped. The answer is the same either way. So the rule does not need a tie-break when the key is the end time. The danger is a tie on a key that is wrong to begin with.

The fix for bug 1 is to change the key:

ordered = sorted(meetings, key=lambda m: m.end)

Bug 2: the wrong sort key, length

The second buggy version sorts by length, which is end minus start. The key is m.end - m.start. This looks sensible, because short meetings seem like they should go first. It is still wrong.

Take input L: [1, 3], [3, 4] and [2, 5]. The lengths are 2, 1 and 3. Sorted by length, the order is [3, 4], [1, 3], [2, 5].

• Take [3, 4]. The last end is 4.
• [1, 3] starts at 1, which is before 4. Skip it.
• [2, 5] starts at 2, which is before 4. Skip it.

The answer is 1. The correct order by end is [1, 3], [3, 4], [2, 5]. Take [1, 3], then [3, 4] (it starts at 3, which equals the last end, so it fits). The answer is 2.

Length does not tell you what a meeting blocks. The short meeting [3, 4] clashes with [2, 5], but not with [1, 3]. The length key takes it first, so it also skips [1, 3], which would have fit. Only the end time tells you how much room is left after a meeting.

A counterexample like this one is the best kind of evidence. You do not need a proof that a key is wrong. One input where the key gives a smaller answer than the correct rule is enough.

Bug 3: a comparator that breaks the rules

The third and fourth bugs are about the comparison rules. This section has two comparators. Both are wrong, and they fail in different ways.

The comparator that never returns zero

The first one is the comparator from bad_comparator:

def compare(a, b):
    return -1 if a.end <= b.end else 1

The comparator is supposed to answer one question for a pair a and b. Zero means the two are equal. This one never returns zero. When two meetings end at the same time, it returns -1 when a is first. It also returns -1 when the pair is swapped and b is first. So it says each meeting comes before the other. That contradicts itself.

Java's sort can detect this and stop with an error, but only on some inputs. Python does not check. The sort finishes and returns a list in some order, and nothing tells you the order is wrong.

In our runs, this comparator gave the right answer every time. It gave the right answer on input C, on the 50 seeded inputs in the lab, and on the 300 small inputs in the brute-force check below. In a larger check, with 20,000 small inputs and 2,000 seeded inputs, it also gave no wrong answer. The reason is that Python's sort only asks whether the result is less than zero. For two meetings that end at different times, this comparator answers that question correctly. For equal ends it gives a wrong answer, but the end-time rule does not care about the order of equal ends, so the count does not change. Do not rely on this. A comparator that breaks its rules is a bug, even when the output looks right.

Use a key instead. The key version is sorted(meetings, key=lambda m: m.end), the same fix as bug 1. A key gives each item one number, so there is no pair to compare and no tie to get wrong. If you must write a comparator, return -1, 0 or 1 with (a.end > b.end) - (a.end < b.end). In Python, True counts as 1 and False counts as 0, so this gives 1 when a ends later, -1 when a ends earlier and 0 when they are equal.

The comparator that returns True or False

The second comparator is the one from bool_comparator:

def compare(a, b):
    return a.end > b.end

This looks sensible. It says that a comes after b when a ends later. The problem is the return value. True and False are not negative, zero or positive numbers. Python's cmp_to_key checks one thing: is the result less than zero? True and False are never less than zero, so the sort never moves anything. The output stays in input order, and the answer depends on how the input was written.

Python gives no error for this. Line D of the lab output shows the result:

D [[1, 10], [2, 3], [4, 5]] correct=2 boolComparator=1

Input D is the same as input A from bug 1. The boolean comparator leaves [1, 10] first, so it takes that meeting and skips the other two. The answer is 1, and the correct answer is 2. The last line of the lab output shows that the boolean comparator was wrong on all 50 seeded inputs.

The fix is the same as before. Use key=, or return a number as shown above.

Bug 4: the strict comparison that drops touching meetings

The fourth buggy version is in the strict_check function. It calls pick with touching_allowed set to False, so the test becomes m.start > last_end instead of m.start >= last_end.

Take input B: [1, 3], [3, 5] and [5, 7]. Each meeting touches the next one. The correct rule takes all three, because each one starts at exactly the time the last one ended. The correct answer is 3.

The strict version compares 3 > 3, which is false. So [3, 5] is skipped. Then 5 > 3 is true, so [5, 7] is taken. The answer is 2. The lab prints strictCheck=2.

This bug is easy to miss in sparse random inputs, because gaps between meetings mean no two touch. The bug shows up when a meeting starts at exactly the end time of another. Test the edge cases on purpose. Use inputs where the times are equal. In the brute-force check below, the strict version was wrong on 133 of 300 small inputs, because those inputs are dense and many meetings touch.

The fix is the loose test, >=. The lab's correct function uses it through pick(ordered, True).

The brute-force check

A brute-force checker tells you which buggy version is wrong, and how often. The program below tries every subset of up to 8 meetings. It keeps the largest subset where no two meetings clash. It then compares each version against that answer on 300 random small inputs.

Save it in the same folder as meeting_lab.py, because it imports that file.

brute.py:

import random
 
from meeting_lab import Meeting, bad_comparator, bool_comparator, correct, strict_check, wrong_length_key, wrong_start_key
 
 
def compatible(a, b):
    return a.end <= b.start or b.end <= a.start
 
 
def best(meetings):
    n = len(meetings)
    best_count = 0
    for mask in range(1 << n):
        chosen = [meetings[i] for i in range(n) if mask & (1 << i)]
        ok = True
        for i in range(len(chosen)):
            for j in range(i + 1, len(chosen)):
                if not compatible(chosen[i], chosen[j]):
                    ok = False
        if ok and len(chosen) > best_count:
            best_count = len(chosen)
    return best_count
 
 
def main():
    rng = random.Random(7)
    trials = 300
    names = ["wrongStartKey", "wrongLengthKey", "strictCheck", "badComparator", "boolComparator"]
    checks = [wrong_start_key, wrong_length_key, strict_check, bad_comparator, bool_comparator]
    wrong = [0] * len(checks)
    first = [None] * len(checks)
    for _ in range(trials):
        n = 1 + rng.randrange(8)
        ms = []
        for _ in range(n):
            s = rng.randrange(10)
            ms.append(Meeting(s, s + 1 + rng.randrange(4)))
        truth = best(ms)
        if correct(ms) != truth:
            print("CORRECT VERSION WRONG", ms)
        for i, check in enumerate(checks):
            if check(ms) != truth:
                wrong[i] += 1
                if first[i] is None:
                    first[i] = ms
    print(f"trials={trials}")
    for name, count in zip(names, wrong):
        print(f"{name} wrong on {count}")
    for name, example in zip(names, first):
        print(f"first {name} input {example}")
 
 
if __name__ == "__main__":
    main()

Run it:

python3 brute.py

The output is:

trials=300
wrongStartKey wrong on 43
wrongLengthKey wrong on 179
strictCheck wrong on 133
badComparator wrong on 0
boolComparator wrong on 198
first wrongStartKey input [[4, 6], [3, 7], [6, 10], [1, 3]]
first wrongLengthKey input [[2, 6], [0, 1], [8, 9], [5, 6], [8, 10], [0, 1]]
first strictCheck input [[6, 8], [8, 9], [9, 12], [8, 10], [1, 3]]
first badComparator input None
first boolComparator input [[2, 6], [0, 1], [8, 9], [5, 6], [8, 10], [0, 1]]

The counts come from Python's random module, so they belong to this exact code. The CORRECT VERSION WRONG line never printed, so correct matched the brute force on all 300 inputs. The <= comparator was wrong on 0 inputs. It is still a broken comparator, as bug 3 explains, but in this test it never changed an answer. The None in the last badComparator line means the checker never found a wrong answer for that version.

The boolean comparator was wrong on 198 of 300 inputs, the most of any version. Small tests do not prove a program is correct, so use larger tests too.

Common mistakes

Sorting by a key that feels natural. Start time, length and duration all look like they should work. Test each key with a small counterexample before you trust it. The end time is the key that leaves room.

Calling a tie harmless without checking. A tie on the end time is harmless here, because the second meeting always clashes with the first. A tie on any other key is not automatically harmless. Work the tie by hand before you decide.

Returning True or False from a comparator. Python gives no error. The sort does nothing, and the answer is wrong. Use key= for ordering, as in bug 1.

Writing a comparator that returns 1 for equal items. A comparator that breaks its rules can still give correct answers in Python, so a test may not show it. Write the comparison as a key, so the rule cannot break.

Sorting objects with no key. If you write sorted(meetings) with no key=, Python does not know how to order two meetings. It stops with this error:

TypeError: '<' not supported between instances of 'Meeting' and 'Meeting'

Storing the result of list.sort. list.sort sorts the list in place and returns None. If you write ordered = meetings.sort(key=lambda m: m.end) and then loop over ordered, the error appears inside pick:

TypeError: 'NoneType' object is not iterable

Use ordered = sorted(meetings, key=...) to get a new sorted list.

Changing a meeting after you made it. Meetings are frozen, so this fails:

FrozenInstanceError: cannot assign to field 'end'

Make a new Meeting with the new value instead.

Using a strict comparison for touching meetings. The test start > last_end drops meetings that touch. In example B, it gave 2 when the answer is 3. Decide whether touching is allowed before you write the test, and write the test to match.

Testing only with random inputs. Random inputs can miss the edge cases that matter, such as two meetings that touch. A sparse random test may never produce a touching pair. Use both small hand-made inputs and random ones.

Trusting one passing run. A program that passes the sample has passed one input. It has not been checked against the rule. The brute-force checker in this lesson is the stronger test, because it compares against an answer you know is right.

Practice

Exercise 1

The meetings are [1, 10], [2, 3] and [4, 5]. What does wrong_start_key return, and what does correct return?

Show the answer

wrong_start_key returns 1. It sorts [1, 10] first, takes it, and then both other meetings start before 10 and are skipped.

correct returns 2. It sorts by end, so the order is [2, 3], [4, 5], [1, 10]. It takes [2, 3] and [4, 5], and skips [1, 10].

Exercise 2

Meetings [0, 2] and [2, 4]. Does the strict version give the same answer as the correct version? Explain in two sentences.

Show the answer

No. The correct version takes both meetings, because 2 >= 2 is true, while the strict version tests 2 > 2, which is false, so it takes only one and gets 1 instead of 2.

Exercise 3

Explain why a tie on the end time does not change the answer. Use two meetings, [3, 9] and [5, 9].

Show the answer

Whichever one the sort puts first, the rule takes it. Then the second meeting starts before 9, which is when the first one ends. So the second meeting clashes with the first and is skipped. Either order gives one meeting from that pair, so the tie does not change the count.

Exercise 4

The comparator -1 if a.end < b.end else 1 returns 1 for two meetings that end at the same time. Which rule does this break? Write the sorted call that does the same job without a comparator.

Show the answer

It breaks the rule that equal items must return zero. Take two meetings that both end at 9. With a first, the result is 1, which says a comes after b. With b first, the result is also 1, which says b comes after a. In our tests this did not change any answer, because Python only checks whether the result is less than zero. The sort without a comparator is sorted(meetings, key=lambda m: m.end).

Exercise 5

Give a small input where the start-time key returns a smaller answer than the correct end-time key. Show both answers.

Show the answer

Use [0, 100], [1, 2] and [3, 4]. Sorted by start, the first meeting is [0, 100]. It is taken, and the last end becomes 100, so the other two are skipped. The start-time key returns 1. Sorted by end, the order is [1, 2], [3, 4], [0, 100]. Take [1, 2] and [3, 4]. The correct answer is 2.

Summary

• Check the sort key with a small counterexample before you trust it. For meetings, the end time is the key that leaves room.
• A tie on the key is harmless only when the rule still works for either order. Check ties by hand.
• Python does not stop a sort when a comparator breaks its rules. Use key= whenever you can, and never return True or False from a comparator.
• Decide whether touching meetings are allowed, then write the comparison to match. A strict test drops touching meetings silently.
• A brute-force checker on small random inputs finds the bugs that a sample misses, but random inputs can also miss edge cases, so test both kinds of input.