Programming & program design

Keep one unfinished run and a list of finished runs. For testing, write a decoder independently and check both reconstruction and maximality.

Start with an empty output. For each x, append (x,1) if the output is empty or the last value differs; otherwise replace the final pair by (x,lastCount+1). Before each iteration, decoding the output yields exactly the processed prefix, each count is positive, and adjacent output values differ. This invariant establishes the postcondition at the end; the empty list encodes as [].

Useful properties are decode(encode(xs))=xs, the sum of counts equals len(xs), and adjacent encoded values differ. Reconstruction on [2,3,2] detects an implementation that incorrectly groups all equal values, while maximality detects [(2,1),(2,1)] for input [2,2]. Neither total counts nor membership alone is sufficient.

The first pipeline filters to [2], then maps to [3]. The second maps to [2,3,4], then filters to [2,4]. The expressions are not equivalent. A valid transformation can use a predicate composed with f when the original specification calls for testing transformed values; side effects, exceptions, and evaluation order also need explicit treatment.

Check your reasoning

• State an invariant strong enough to prove reconstruction and maximal runs.
• Include empty, singleton, alternating, and repeated-value tests.
• Calculate both pipelines before proposing any rewrite.

The right branch must exclude the midpoint already shown too small. Use interval length as the measure.

For a=[1], target=2, the buggy call [0,1) chooses m=0 and repeats [0,1) forever. The corrected right branch is [m+1,hi). Return an absent sentinel when lo==hi before reading a[m]. Require a nondecreasing array and 0≤lo≤hi≤len(a). The result is either an index in the original interval whose value equals target or an absent sentinel exactly when none exists there. No promise of the first duplicate is made.

The measure hi−lo is a nonnegative integer and strictly decreases on both recursive branches. Sorted order excludes m and everything to its left when a[m]<target, and excludes m and everything to its right when target<a[m]. Thus the remaining interval contains every possible match from the original interval. An empty interval has no match, proving the absent case.

For length 8 with target above all values, the intervals are [0,8),[5,8),[7,8),[8,8). Midpoints are 4,6,7; the final call performs no array access. A first-occurrence contract needs different logic and cannot be inferred from this proof.

Check your reasoning

• Demonstrate an actual nonshrinking recursive call.
• Distinguish any matching duplicate from the first duplicate.
• Prove both interval preservation and strict size reduction.

Copying an outer list copies references to its elements. The two occurrences of row are two references to one object.

row becomes [0,7]. Both elements of a refer to that same row, so a displays [[0,7],[0,7]]. b is a distinct outer list but its first two elements also refer to row; appending changes only b, which displays [[0,7],[0,7],[9,9]]. There are three list objects before the append: row, a, and b. The literal appended list creates a fourth.

Use [[0 for _ in range(2)] for _ in range(3)] to create three independent row lists. Integers are immutable, so sharing references to the integer 0 does not create a mutation problem. [[0,0]]*3 would reuse one row list.

Copying each row with r[:] is sufficient for independent row structure when cells are immutable. If a cell contains another mutable list, both copies still reference that nested list. A deep-copy policy, immutable cell values, or explicit ownership rule must be chosen. The correct answer depends on the declared data model; indiscriminate copying can also break intentional shared identity.

Check your reasoning

• Track object identity separately from equal printed values.
• Explain why append and nested assignment affect different objects.
• State the promised depth of independence instead of calling a copy simply safe.

The logical front is at the end of outgoing. Write the abstract queue as reversed(outgoing) followed by incoming.

The queue contract is: enqueue(x) appends x to the abstract sequence; dequeue() removes and returns its first element, or raises an EmptyQueue error without mutation when the queue is empty; size() returns the number of stored elements without mutation. With two lists, size() is len(incoming)+len(outgoing).

The abstract sequence is reverse(outgoing)+incoming. After enqueuing A,B, incoming=[A,B],outgoing=[]. The first dequeue transfers to outgoing=[B,A], then returns A, leaving [B]. Enqueue C gives incoming=[C],outgoing=[B]. The next dequeue returns B without transferring; the last transfers and returns C.

When outgoing is empty, repeatedly popping incoming reverses its order in outgoing. Reversing outgoing in the abstraction function restores the original incoming order, so transfer changes representation without changing the abstract queue. Every element crosses lists at most once before removal, giving constant amortized operations even though one dequeue may perform a linear transfer.

If enqueue promises to retain every accepted element until dequeued, silently discarding the oldest violates that postcondition. A bounded API can return Full without mutation, block under a stated policy, or explicitly advertise drop-oldest semantics with a returned eviction. Each is a different contract. Inheritance does not by itself establish substitutability.

Check your reasoning

• Give an abstraction function, not only a successful trace.
• Separate amortized operation cost from the worst individual call.
• Identify the exact postcondition broken by silent eviction.

Validation and publication are separate stages. A temporary output can delay replacing the destination until the new result is complete.

Open the input with a context manager, parse each stripped line with an explicit nonempty check, reject negative values, and accumulate using a type whose range satisfies the contract. Python integers support the very-large-integer case within resource limits. Only after successful parsing create a temporary file beside the destination, write the final value and close it, then replace the destination using a same-filesystem operation with documented semantics. On failure, preserve the original destination where the API permits and remove the temporary file.

Use a preexisting sentinel output in the malformed-middle-line test and assert it is unchanged. Empty input must produce 0. Inject a write exception instead of depending on a machine-specific permission accident. Assert resources close and temporary files are handled. Directly overwriting the destination before validation loses the old result even if parsing later fails.

Atomic replacement concerns which name-to-file state other observers can see. Durability across power loss additionally depends on flush operations, directory persistence, filesystem behavior, and hardware. A classroom implementation should state which guarantee it tests; successful close and rename alone are not a universal durability proof.

Check your reasoning

• Keep malformed input from publishing a partial result.
• Test failures deterministically and check cleanup.
• Distinguish atomic visibility, durable storage, and arithmetic range.