From a real problem to a precise program contract

By UK A Level Computer Science · independent study · myAudience

Original textbook concept plate generated with OpenAI imagegen; labels and states checked against the lesson model. · Generated original teaching artwork; pending operator rights/provenance review before publication.

From a real problem to a precise program contract

A program is an executable description of behaviour; an algorithm is a finite effective method intended to terminate on its stated domain. A request such as “work out how many boxes we need” leaves important facts unstated. What counts as an item? Can a box be partly filled? Is zero allowed? Analysis identifies the required outputs, the accepted inputs and the conditions under which a result is meaningful. A precondition is a condition the caller must satisfy before execution; a postcondition specifies what must hold after successful execution. The domain is the set of allowed inputs, not merely the type names written beside them.

For our original packing problem, items is a nonnegative integer count and capacity is a positive integer count of items per box. The output b is the smallest nonnegative integer satisfying b × capacity ≥ items. Minimality also requires that b=0 or (b−1) × capacity < items. These two inequalities distinguish a correct result from any generous overestimate. A physical box might have length, price or colour, but this representational abstraction omits those properties because the present requirement concerns capacity alone. If breakable items cannot share boxes, that omission becomes invalid and the model must change.

Integer division makes the calculation exact. Write items=q × capacity+r with 0≤r<capacity. When r=0, q boxes suffice; when r>0, one additional box is necessary. Therefore b=q+[r>0], equivalently (items+capacity−1)//capacity for this nonnegative domain. The derivation explains both the offset and the floor division. It is safer than taking a floating-point quotient and rounding, which may lose precision for sufficiently large counts. In Python, // floors toward negative infinity, so we must not silently extend this derivation to arbitrary signed inputs.

The implementation deliberately rejects Boolean values as item counts, even though Python treats bool as a subclass of int. A type is a set of values with permitted operations, while an application domain can be narrower. A type annotation alone does not enforce the domain at runtime. Exceptions separate invalid input from a valid numerical result; returning zero on failure would be indistinguishable from correctly packing no items. The choice to reject rather than coerce is a design decision in this example, not an instruction for every program.

Testing and proof contribute different evidence. Tests for zero, an exact multiple and a remainder inspect important partitions. The quotient-and-remainder argument explains all valid integer inputs. Neither establishes that the physical warehouse model is adequate: user requirements and observations address that question. Decompose the eventual system into input parsing, validated calculation and presentation so that a pure calculation can be tested without a keyboard or file. Preserve the assumptions beside the code rather than hiding them in the interface.

Reading the diagram: The seven trays show six groups of eight components and one group of five. Three outlined places in the last tray are empty, not extra components. The first six trays hold 48, which is insufficient for 53; seven can hold 56. Thus the picture demonstrates both sufficiency and minimality, exactly the two postcondition inequalities, rather than rounding to the nearest tray.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def packs(items, capacity):
"""Nonnegative integer items; positive integer capacity; round up exactly."""
if type(items) is not int or type(capacity) is not int:
raise TypeError('integer domain required')
if items < 0 or capacity <= 0:
raise ValueError('items >= 0 and capacity > 0 required')
return (items + capacity - 1) // capacity
```

Worked example: A workshop has 53 identical components and trays holding 8 each. Explain the result without floating arithmetic.

53=6×8+5, so six full trays leave five components.

The positive remainder requires a seventh tray. Check 7×8=56≥53 and 6×8=48<53.

The implementation evaluates (53+8−1)//8=60//8=7. For zero components it gives 7//8=0.

Answer: 7 trays; three spaces remain. Both sufficiency and minimality have been established.

Check your understanding: 1. Evaluate packs(24,8) and packs(25,8). 2. Explain why capacity=0 must fail. 3. A colleague proposes int(items/capacity+0.5). Give a counterexample and repair the model if every tray must contain exactly eight components.

Answer: 1. The answers are 3 and 4: the second input has a nonzero remainder. 2. Zero capacity cannot hold a positive item and division is undefined. 3. At 25/8 the proposed expression gives 3, leaving one item unpacked. If partial trays are forbidden, no solution exists unless items is divisible by capacity; return an explicit infeasibility outcome or raise a defined exception instead of inventing a tray count.

Why: Rounding to the nearest integer solves a different problem from rounding upward. A sufficient result is not necessarily minimal. A changed physical requirement changes the postcondition, so altering arithmetic without altering the contract is unjustified.