Which Pattern?

Every module so far has had its technique in the title. You knew a stack was wanted because the module was called Stacks. Outside a course, a problem arrives with no title. It is a paragraph about parcels or timetables, and choosing the tool is part of the work, often the larger part. This module teaches no new technique. It teaches a way of working that gets you from an unfamiliar paragraph to a fast answer you can trust.

Before this, you can: use a stack, a queue, a dictionary of what has been seen, two positions, halving and a window; remember answers or fill a table; write asserts, and choose the cases that matter.

By the end you will be able to find the detail in a problem that points at a pattern, write the slow answer first and say what it costs, check a fast answer against the slow one, say what a pattern needs to be true before relying on it, and state the promise of a loop before writing it.

Before you read on, decide what this prints:

def longest_calm(readings, limit):
    longest = 0
    for start in range(len(readings)):
        total = 0
        for end in range(start, len(readings)):
            total = total + readings[end]
            if total <= limit and end - start + 1 > longest:
                longest = end - start + 1
    return longest

print(longest_calm([2, 1, 3, 1, 1], 5))
print(longest_calm([-1, 4, -3], 2))

3
3

This tries every stretch and keeps the longest whose total is within the limit. It is slow, and it is right for any numbers at all. In the second list the whole of it counts: −1, 4 and −3 come to 0, which is within 2. Hold on to that list. You will see a faster function get it wrong.

The problem does not say

A problem never says "use a window". It says something like the longest stretch of days on which the total rainfall stayed within the budget. The pattern has to be read out of the wording. That sounds like guesswork and is not. A handful of details do nearly all the pointing, and you have met every one of them.

The detail that decides

The problem says	Think of	Because
a stretch, a run, neighbouring items, consecutive days	a window, or running totals	neighbours share almost all their items
the list is sorted, or could be sorted without losing anything	two positions, or halving	order lets one comparison rule out many items
a pair that adds up, matches, or was seen before	a dictionary or set of what has been seen	"have I met its partner?" is one look-up
the most recent unfinished thing; undo; things that cancel their neighbour	a stack	the last in is the first out
the fewest moves, steps or presses	a queue, searching in rings	the first time a place is reached is the shortest way
how many ways; the best total over a chain of choices	remember the answer, or a table	the same smaller questions come up again and again
the smallest or largest value that is still enough	halving the range of answers	if one value is enough, so is every larger one

None of these is a rule. Each is a reason to try one thing first. "Sorted" may mean two positions or halving, and you find out which by asking what one comparison lets you throw away. "Best" may mean a table, or may be answered by a single pass with a best-so-far.

Read the problem twice. The second time, look only for these details, and for the awkward ones: can numbers be negative, can the list be empty, are repeats allowed, is "fewest" wanted or just "any"?

The slow answer first

Before reaching for a pattern, write the answer that needs no cleverness: try every pair, every stretch, every choice. longest_calm above is one.

It may seem a waste to write something you intend to replace. It is the most useful thing you will write.

It makes you understand the problem. You cannot try every stretch without deciding what a stretch is, whether an empty one counts, and what to return when nothing fits.
It is almost certainly right, because it has no trick in it to get wrong.
It gives a cost to beat. Two loops over n items is about n × n / 2 steps: fine for a hundred items, hopeless for a hundred thousand. That number tells you whether you need anything faster at all. Often you do not.
It checks the fast answer, which is the next section.

Check the fast against the slow

A fast function has more ways of being wrong than a slow one, and they hide in inputs you would not think to try. So do not think of them. Make the computer try all the small ones, and compare.

def fast_calm(readings, limit):
    left = 0
    total = 0
    longest = 0
    for right in range(len(readings)):
        total = total + readings[right]
        while total > limit:
            total = total - readings[left]
            left = left + 1
        if right - left + 1 > longest:
            longest = right - left + 1
    return longest

def first_difference(low, high, limit):
    for a in range(low, high + 1):
        for b in range(low, high + 1):
            for c in range(low, high + 1):
                readings = [a, b, c]
                if fast_calm(readings, limit) != longest_calm(readings, limit):
                    return readings
    return None

print(first_difference(0, 4, 5))
print(first_difference(-3, 4, 2))

None
[-1, 4, -3]

fast_calm is the growing-and-shrinking window from Sliding Windows. On every list of three readings from 0 to 4, which is 125 lists, it agrees with the slow answer. Allow negative readings and the check finds a disagreement: the list from the top of this lesson.

A disagreement found this way is small: three numbers. You can work it through by hand in a minute. A wrong answer on a list of ten thousand tells you nothing.

Three things make the check worth having.

Use small inputs and small values. Bugs that need a long list are rare. Bugs that need a repeat, a zero, a negative or an empty list are common, and small values produce those constantly.
Try every input up to some size if you can, as above. If there are too many, try a few thousand made by a formula.
When it reports nothing, that is evidence and not proof. It has not tried a long input, and it cannot tell you that the fast function is fast.

What the pattern needs

Why did the window fail? Follow it on −1, 4, −3 with a limit of 2. It takes in −1, then 4: the total is 3, over the limit, so it shrinks. Letting go of the −1 makes the total larger, 4, so it lets go of the 4 as well, and the window is empty. Then it takes in −3, and reports a longest stretch of 1. The slow answer is 3, the whole list, because the −3 at the end pays for the 4.

The window threw away the −1 and the 4 on the grounds that a stretch already over the limit can only get worse by growing. That is true when every number is positive. It is the thing the pattern needs, and Sliding Windows said so: a longer window must only make the rule harder to keep. With a negative number in the list it is false, and the pattern gives wrong answers with no error at all.

Every pattern has something of this kind.

Pattern	What it needs to be true
a window that grows and shrinks	making the window longer only ever moves it one way against the rule
two positions moving inward; halving	the list is sorted, by the thing being compared
halving a range of answers	if one answer is enough, every answer on one side of it is too
searching in rings for the fewest moves	every move counts the same
a memo or a table	the answer depends only on the key, not on how you arrived

Before relying on a pattern, find its row and ask whether the problem really promises it. When it does not, either the problem has to be looked at another way (running totals in a dictionary handle stretches with negative numbers, as you will find in the lab) or the slow answer is the answer.

Say the promise

The last habit is the one that stops most mistakes before they are typed. Before writing the loop, write one sentence that will be true every time round. You met these in each module: "the stack holds the days still waiting, coldest on top"; "if the target is in the list, its position is from low to high"; "the window is the longest valid one ending here"; "this cell holds the best total for the first i nights".

The sentence does three jobs. It tells you what to set up before the loop, because it has to be true before the first turn. It tells you what each line inside may and may not do. And at the end it hands you the answer, because the sentence, true at the last turn, says what you wanted to know.

If you cannot write the sentence, you do not yet know what your loop is for, and no amount of typing will help.

A routine

Put together, this is a way through a problem you have not seen.

Restate it in your own words, with one small example worked by hand.
Find the details: sorted, neighbouring, fewest, how many ways, most recent, still enough. And the awkward ones: negative, empty, repeats.
Write the slow answer, and note its cost.
Choose a pattern from the details, and check what it needs against what the problem promises.
Say the promise of the loop in a sentence, as a comment.
Write the fast answer.
Check it against the slow one on every small input, and then try one large input for speed.

Steps 1 to 3 are worth doing even when you already think you know the pattern. They are quick, and they are where a wrong guess gets caught.

In the lab

You will pick out the deciding detail in three short problems and cost a slow answer. You will write a fast answer to a problem about times a set distance apart, with the slow one given. You will watch a check find a mistake that hand-picked tests missed, and write the closest gap between two sorted lists. You will see a window fail on a negative number and count stretches that come to a target another way. You will choose the promise of a halving loop, and find the slowest speed that still arrives. Four assignments follow with no pattern named: steps that cancel, the fewest presses, trees with no three together, and a fast function that disagrees with its slow one.