Writing down what a function does
A function you write gets called again: further down the same program, in the next problem, or by you a month from now, when you no longer remember its body. Each caller needs to know which arguments the function accepts, what it can return, and which result it gives for each argument. In this lesson we write those answers down, check that the body really keeps to them, and then split a bigger problem into functions you can trust one at a time.
We'll start with a function worth keeping. Rounding a division up takes (a + b - 1) // b: 20 items packed 12 to a box need 2 boxes, and so do 24 items. As a function, the formula becomes ceil_div(a, b), where ceil is short for ceiling, the usual name for rounding up. The name alone doesn't say whether b can be 0 or whether a can be negative, so we write the answers next to the function:
def ceil_div(a, b):
"""Return a divided by b, rounded up to a whole number.
b must be positive.
"""
# Adding b - 1 reaches the next multiple of b only when there is a remainder.
return (a + b - 1) // b
print(ceil_div(20, 12))
print(ceil_div(24, 12))Python details
A string written as the first line of a function's body is its docstring. Python keeps it with the function, so help(ceil_div) prints it.
The docstring is the function's specification. It answers the caller's questions in two parts: what the function returns, which is rounded up, and what the caller has to supply, which is a positive b. A caller who keeps to that can rely on the answer. A caller who passes 0 for b gets no promise at all.
The line starting with # is a comment, a note for people reading the code, which Python ignores. It has a different reader from the docstring. The docstring is for whoever calls the function, and says what it does. The comment is for whoever reads or changes the body, and says why a line works. help(ceil_div) shows the docstring and leaves the comment out.
The specification says what ceil_div returns and leaves out how the body works it out. It is functional abstraction, written down. If you later replace the body with another one that returns the same values, every program that calls ceil_div keeps working, and none of them needs to be reread.
Definition
A function's specification says what the function needs from its caller and what it gives back, without saying how its body works it out.
Inputs the requirements rule out
The requirement in the docstring isn't arbitrary. It rules out exactly the inputs where the body gives a wrong answer or no answer, and you can find them by trying a few. With 0 for b, the division stops the program with ZeroDivisionError. With a negative b, the answer is wrong: , which rounds up to , but ceil_div(7, -3) returns .
A negative a is fine, though. ceil_div(-7, 3) returns , which is rounded up. The formula relies on // rounding down, and Python's // rounds down for negative numbers too. So the docstring asks for a positive b and lets a be any integer.
Checking a function with assert
A specification says what the body should do. To find out whether it does, call the function on inputs whose answers you already know and compare. You have been doing this by eye: print ceil_div(20, 12), see 2, and move on. The program can do the comparing for you.
Python's assert statement takes a condition. When the condition is true it does nothing, and when it is false it stops the program with an error. Each check is a test case: one input together with the answer you expect for it. Here are four for ceil_div:
def ceil_div(a, b):
"""Return a divided by b, rounded up to a whole number.
b must be positive.
"""
return (a + b - 1) // b
assert ceil_div(20, 12) == 2
assert ceil_div(24, 12) == 2
assert ceil_div(0, 5) == 0
assert ceil_div(3, 7) == 1
print("all tests passed")| Test | Kind of input | Expected |
|---|---|---|
ceil_div(20, 12) | an ordinary division with a remainder | 2 |
ceil_div(24, 12) | an exact division, where rounding up must add nothing | 2 |
ceil_div(0, 5) | nothing to divide | 0 |
ceil_div(3, 7) | a smaller than b: 7 does not fit into 3 at all | 1 |
Each test checks a different kind of input, because a wrong body often gets some kinds right and others wrong. One test on its own can easily miss the mistake.
A test that catches a bug
Here is a body for ceil_div that looks right: a // b + 1, divide and then add one to round up. These are the same four tests run on it:
def ceil_div(a, b):
return a // b + 1
assert ceil_div(20, 12) == 2
assert ceil_div(24, 12) == 2
assert ceil_div(0, 5) == 0
assert ceil_div(3, 7) == 1
print("all tests passed")The first test passes, since . The second fails: 12 divides 24 exactly, so the answer should be 2, but the body gives . Python stops at that line with an AssertionError, and the traceback above it names line 5 and shows assert ceil_div(24, 12) == 2.
The two tests after it never run, and all tests passed is not printed. If ceil_div(20, 12) had been the only test, the bug would have gone to the judge, and the judge would have said Wrong Answer without telling you which input.
Asserts in a program you submit
You can leave the asserts in when you submit. Passing asserts print nothing, so the judge sees only your answer. Take out the line that prints all tests passed, though: the judge compares every line your program prints with the expected output, and that extra line turns a correct answer into Wrong Answer. If an assert fails on one of the judge's inputs, the program stops with an error, and the judge reports Runtime Error.
Practice: Duplex Printing
Duplex Printing is practice for writing a function with its tests, since it needs a division rounded up:
Two pages fit on a sheet, so 5 pages need 3 sheets, the last with its back left blank: the number of sheets is rounded up. Put ceil_div and its tests at the top of your program, add a test for each sample, and then read and print the answer.
Deeper read: tests inside the docstring
Python can keep tests right next to the specification. A doctest is an example written inside the docstring the way it would look at Python's interactive prompt: a line starting with >>>, then the value Python would show. The doctest module finds these examples, runs them and compares:
def ceil_div(a, b):
"""Return a divided by b, rounded up to a whole number.
b must be positive.
>>> ceil_div(20, 12)
2
>>> ceil_div(24, 12)
2
"""
return (a + b - 1) // b
doctest.testmod()doctest.testmod() runs every example in the file. It prints nothing when they all pass. When one fails, it prints the example with the value it expected and the value it got: with the a // b + 1 body, the second example reports Expected: 2 and Got: 3. That report goes to the same output as your answer, so on a judge a failing doctest also shows up as Wrong Answer.
Default argument values
ceil_div counts how many boxes you need. A related question asks for an amount instead. Paying 1900 yen in 1000-yen bills means handing over 2000 yen: 1900 rounded up to a multiple of 1000, which is . So a function for it can call ceil_div.
A multiple of what, though? Today it is 1000-yen bills, but the next problem may round to 500 or to 300. Instead of writing round_up_1000, round_up_500 and so on, we give the function a second parameter, step, and one function covers them all. That makes the function more useful, but now every call has to pass the step, even in a program where it is 1000 nearly every time. A default argument solves this: it gives a parameter a value to use whenever a call leaves that argument out.
def ceil_div(a, b):
"""Return a divided by b, rounded up. b must be positive."""
return (a + b - 1) // b
def round_up(n, step=1000):
"""Return the smallest multiple of step that is at least n.
step must be positive.
"""
return ceil_div(n, step) * step
print(round_up(1900))
print(round_up(1900, 300))
print(round_up(3000))Python details
A call can also name the parameter it is passing: round_up(1900, step=300) means the same as round_up(1900, 300), and reads more clearly when a function takes several numbers.
round_up(1900) leaves out step, so step is 1000 and the call returns . round_up(3000) returns 3000 itself, because 3000 is already a multiple of 1000. round_up(1900, 300) passes 300, which is used instead of the default:
The = in step=1000 is not an assignment. In a def line it gives the value step takes when a call leaves it out.
Parameters with defaults come after the ones without. Otherwise, in a call like round_up(1900), nothing would say which parameter 1900 is for.
A value a caller might reasonably want to change, such as the step, belongs in a parameter, with a default when one value is far more common than the rest. A value the problem itself fixes, such as the two pages that fit on a sheet in Duplex Printing, can stay in the body.
Payment is practice for round_up:
You pay yen with as few 1000-yen bills as possible, and the change is the amount handed over minus . Check your program on both samples: 1900 gives 100 back, and 3000, an exact multiple, gives 0 back, not 1000.
Breaking a problem into functions
Each function so far has done one small job that we already knew we needed. A problem, though, arrives as a whole, and part of solving it is finding the small jobs inside it. Splitting a problem into functions this way is called decomposition. Here is a problem to split:
You are painting the four walls of a room. The floor is width metres by length metres, the walls are height metres high, and one can of paint covers coverage square metres. How many cans do you need? (Leave out doors and windows.)
There are two separate questions inside it. The first is how much wall there is. Two walls are width by height and two are length by height, so the wall area is the distance around the floor, its perimeter, times the height. The second is how many cans cover that area: the area divided by the coverage, rounded up, since you can't buy part of a can. That second question is ceil_div, already written and tested, and a perimeter is 2 * (width + length). So the program is four short functions, each with a one-line specification and its own tests:
def ceil_div(a, b):
"""Return a divided by b, rounded up. b must be positive."""
return (a + b - 1) // b
def perimeter(width, length):
"""Return the distance around a width by length rectangle."""
return 2 * (width + length)
def wall_area(width, length, height):
"""Return the area of a room's four walls."""
return perimeter(width, length) * height
def cans_needed(width, length, height, coverage):
"""Return how many cans cover the walls. coverage must be positive."""
return ceil_div(wall_area(width, length, height), coverage)
assert ceil_div(20, 12) == 2
assert ceil_div(24, 12) == 2
assert perimeter(4, 3) == 14
assert wall_area(4, 3, 3) == 42
assert cans_needed(4, 3, 3, 10) == 5
assert cans_needed(3, 2, 3, 10) == 3
assert cans_needed(1, 1, 2, 10) == 1
width, length, height, coverage = map(int, input().split())
print(cans_needed(width, length, height, coverage))The tests come in the same order as the functions, smallest first. A test of one function on its own is called a unit test, and the order pays off when one fails. If perimeter and wall_area pass their tests and a cans_needed test fails, the mistake is in the one line of cans_needed, and you don't need to reread the others. Swapping the two arguments of ceil_div there, for example, makes cans_needed(4, 3, 3, 10) return 1 instead of 5, and only the cans_needed tests fail.
The three cans_needed tests are the kinds of input from the ceil_div table. A 4 by 3 room 3 metres high has 42 square metres of wall, which needs 4.2 cans, so 5. A 3 by 2 room has exactly 30, which needs exactly 3. A 1 by 1 cupboard 2 metres high has 8, less than one can covers, and still needs 1.
Each function also does one job, which is why each has a short name that says what it does. If a function's name needs an "and", such as area_and_cans, the function is doing two jobs and is usually better split in two.
The paint program in an environment diagram
Here is the same program with the specifications, tests and input taken out. Pick a room and step through the calls.
In the first room, cans_needed wants to call ceil_div, but the first argument of that call is itself a call, wall_area(...), so that runs first, and wall_area in turn calls perimeter. At the deepest point three frames are open, f1, f2 and f3, each waiting for the one it called. perimeter returns 14, wall_area returns 42, and only then does ceil_div open its frame, with 42 as a.
The other two rooms are the edge cases from the tests. In the 3 by 2 room the 30 square metres divide exactly, and rounding up adds nothing. In the cupboard, 8 square metres is less than one can covers, and ceil_div still returns 1.
Practice: Golden Coins
Golden Coins is practice for decomposition:
It asks one small question twice: how many coins of one value fit into an amount of yen, first for 500-yen coins and then for 5-yen coins in what is left. Take as many 500-yen coins as fit first, since 500 yen as one coin is worth 1000 points and as a hundred 5-yen coins only . Write the small question as a function and test it, then write the function that adds up the points, and test it on both samples, 1024 and 0.
Common mistakes
Testing only with the sample.
- Where it breaks
- The body that divides and adds 1 passes
ceil_div(20, 12) == 2but returns 3 forceil_div(24, 12), where the answer is 2. On a judge this shows up only as Wrong Answer on a hidden test. - The fix
- Add a test for each kind of input the specification allows: an exact division, an
aof 0, and anasmaller thanb.
Putting a parameter with a default before one without.
- Where it breaks
- Python rejects
def round_up(step=1000, n):withSyntaxError: parameter without a default follows parameter with a default. C++ rejectsint round_up(int step = 1000, int n); clang reportsmissing default argument on parameter 'n'. - The fix
- Put the parameters with defaults last:
round_up(n, step=1000).
Leaving test output in a submission.
- Where it breaks
- The line
all tests passedreaches the judge next to the answer, and the judge reports Wrong Answer although the answer is right. - The fix
- Print only the answer. Asserts print nothing when they pass, so they can stay; delete the line that prints
all tests passedbefore you submit.
Recall Which of these tests catch the body that divides and adds 1: `ceil_div(20, 12) == 2`, `ceil_div(24, 12) == 2`, `ceil_div(0, 5) == 0`?
The second and the third. , not 2, and , not 0. Both are exact divisions, where rounding up should add nothing. The first test passes, since 12 does not divide 20.
Recall In the paint program, the tests of `ceil_div`, `perimeter` and `wall_area` pass, and a test of `cans_needed` fails. Where do you look first?
At the one line of cans_needed. The functions it calls have passed their own tests, so the mistake is most likely in how cans_needed combines them, such as its arguments passed in the wrong order.
Key terms
| Term | Meaning |
|---|---|
| specification | What a function needs from its caller and what it gives back, without how. |
| docstring (Python) | A string on the first line of a function body, holding its specification. |
| comment | Text after # (Python) or // (C++) for people reading the code; the language ignores it. |
| assert | A check that stops the program when its condition is false. |
| test case | One input together with the answer you expect for it. |
| unit test | A test of one function on its own. |
| default argument | A value a parameter takes when a call leaves it out: step=1000. |
| decomposition | Splitting a problem into small functions that each do one job. |
