Thinking ahead and thinking logically

Inputs, outputs and preconditions, caching and reuse, decisions and conditions, and solving logic problems.

A2.7Recursion and computational thinkingA level25 min

Good programmers solve a lot of a problem before writing a line. Thinking ahead is working out, in advance, what a solution will need: its inputs and outputs, the conditions it relies on, what can be stored and reused. Thinking logically is working out where the decisions are and exactly what conditions control them. Both are how you write an algorithm that works first time, and how you argue that it does.

Inputs, outputs and preconditions

Before designing a solution, identify:

• the inputs: what data the solution is given, in what form and range;
• the outputs: exactly what it must produce;
• the preconditions: what must already be true for the solution to work.

A precondition is part of the contract of a subroutine. Binary search has the precondition that the list is sorted; a function that works out a mean has the precondition that the list is not empty. Stating preconditions has two benefits: the subroutine can be simpler, because it does not have to cope with every possible input, and anyone reusing it knows what they must guarantee. A precondition can be checked inside the subroutine, raising an error when it is broken, or left to the caller and written in the documentation.

def mean(readings):
    """Precondition: readings is a list of at least one number."""
    if len(readings) == 0:
        raise ValueError("mean needs at least one reading")
    return sum(readings) / len(readings)

print(mean([30, 40, 50]))
try:
    print(mean([]))
except ValueError as error:
    print("refused:", error)

Run this in the simulator

Caching

Caching is storing the result of work so that the next time the same result is needed it can be fetched instead of worked out again. It appears at every level of computing: the processor's cache keeps recently used data close by, a web browser keeps copies of pages it has downloaded, and a program can keep answers it has already calculated.

In the last lessons, fib_rec(20) made 21,891 calls because it worked out the same values over and over. A dictionary of answers already found removes the repetition. This is called memoisation:

cache = {}
calls = 0

def fib(n):
    global calls
    calls = calls + 1
    if n in cache:
        return cache[n]                 # fetched, not worked out
    if n < 2:
        answer = n
    else:
        answer = fib(n - 1) + fib(n - 2)
    cache[n] = answer                   # stored for next time
    return answer

print(fib(20), "in", calls, "calls")

Run this in the simulator

39 calls instead of 21,891, and still recursive.

Reusable components

A reusable program component is a subroutine, module, class or library written once, tested, and used in many programs. Thinking ahead includes spotting what will be needed more than once, and writing it so it can be reused: clear inputs and outputs, stated preconditions, no dependence on global variables.

Reuse saves development time, and a component that has been used and tested many times is more reliable than new code. The drawbacks: a general component may be slower or larger than code written for one job, it may not do quite what is needed, and a fault in it affects every program that uses it.

Thinking logically

Thinking logically means:

• identifying the points in a solution where a decision has to be taken;
• determining the logical conditions that affect the outcome of each decision;
• determining how the decisions affect the flow through the program.

For a robot that parks, the decisions might be: is the wall closer than 30 cm? If so, is it closer than 10 cm? The conditions are comparisons on distance(), and each outcome sends the program down a different branch or ends a loop. Getting a condition exactly right matters: < or <= decides what happens at the boundary.

Logic puzzles train the same skill. A problem with a small number of possibilities can be solved by testing every possibility against every condition, and the solution can then be checked by confirming it satisfies each condition and that no other possibility does.

# One of three robots bumped the wall. Exactly one of them is telling the truth.
# Ada says "Bolt did it". Bolt says "I did not". Cog says "I did not".
for culprit in ["Ada", "Bolt", "Cog"]:
    ada = culprit == "Bolt"
    bolt = culprit != "Bolt"
    cog = culprit != "Cog"
    truths = [ada, bolt, cog].count(True)
    print(culprit, "did it:", truths, "telling the truth")
    if truths == 1:
        print("  this fits every clue")

Run this in the simulator

Only Cog fits, and because every possibility was tested, the answer is proved to be the only one. That is an argument for correctness by logical reasoning, which is what exam questions mean when they ask you to justify a solution.

Following and writing algorithms

An algorithm is a sequence of steps that can be followed to complete a task, and that always terminates. Any algorithm can be written with four constructs: sequence, assignment, selection and iteration. You should be able to write one in pseudocode, hand-trace it, convert it to program code, and explain why it is correct (logical reasoning and test data) and efficient.

Task: routes with a cache

The robot moves on a grid, only ever one cell right or one cell up. routes(right_steps, up_steps) is the number of different routes from one corner to a cell that many steps right and up. Both parameters are whole numbers. If either is 0 there is exactly 1 route (a straight line); otherwise every route arrives either from the cell to the left or from the cell below, so routes(r, u) = routes(r - 1, u) + routes(r, u - 1).

• Write routes recursively, with a dictionary cache so no pair is ever worked out twice.
• Count every call of routes in a global calls, including calls answered from the cache.
• Precondition: both parameters must be 0 or more. At the start of routes, if either is negative, raise ValueError with a message of your choice.

Then print, in this order:

1. routes(3, 2) = <answer>;
2. routes(16, 16) = <answer>, with calls set back to 0 just before this call;
3. calls: <n>, the calls made by that one call (without a cache this would be over a billion);
4. refused: <message>, by calling routes(-1, 4) inside try and printing the error's message in except ValueError.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

cache = {}
calls = 0

def routes(right_steps, up_steps):
    if right_steps == 0 or up_steps == 0:
        return 1
    return routes(right_steps - 1, up_steps) + routes(right_steps, up_steps - 1)

print("routes(3, 2) =", routes(3, 2))

Task: who won the race?

Four robots, Ada, Bolt, Cog and Dot, ran a race and finished in four different places. These are the only clues:

1. Ada finished ahead of Dot.
2. Cog finished ahead of Ada.
3. Dot and Bolt finished next to each other.
4. Bolt did not finish third.

Find the order by testing every possible finishing order against every clue. permutations from itertools gives every order of a list. Print:

• order: <first> <second> <third> <fourth>, the names of the order that fits;
• solutions: <n>, how many orders fit every clue (checking there is only one);
• checked: <n>, how many orders you tested.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

from itertools import permutations

robots = ["Ada", "Bolt", "Cog", "Dot"]

Challenges

1. Remove the cache from routes and time routes(12, 12). Then work out roughly how long routes(16, 16) would take.
2. A robot caches its map of the room. Give one situation where the cache helps and one where it causes a crash.
3. Remove clue 4 from the race. How many orders fit now, and what does that tell you about checking a solution?