Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 5 / a

A flattened Boolean array stores the whole board in $N^2$ entries, with cell $(x,y)$ at position y*N + x. For the pictured board, its bottom-to-top rows are 111111 | 111100 | 111100 | 110000 | 000000 | 000000.

A column-height array uses only $N$ entries: column $x$ contains exactly the cells below height $h(x)$. The pictured board is $h=(4,4,3,3,1,1)$, with 16 occupied cells. The alternatives are essentially different because the first stores every cell and the second encodes the boundary of an order ideal.

For the flattened Boolean array, the abstraction function selects the true cells. A suitable representation invariant requires the occupied cells to form a order ideal: an occupied $(x,y)$ implies occupancy of every $(i,j)$ with $i\le x,j\le y$. Deleting a northeast rectangle preserves that property.

For column heights, the invariant is $N\ge h(0)\ge h(1)\ge \cdots \ge h(N-1)\ge 0$, and the abstraction function is $B=\{(x,y):0\le x<N,0\le y<h(x)\}$. A legal move replaces every $h(i)$ for $i\ge x$ by $\min (h(i),y)$, preserving the invariant. This is an order-ideal board representation.

For a fair comparison, allow either representation a scalar cached token count: Count and Legal then take $O(1)$ in both. Without that cache, counting needs $\Theta (N^2)$ Boolean inspections versus $\Theta (N)$ height additions. A move takes $O(N^2)$ in the worst case in the flattened representation and $O(N)$ with heights. Displaying the full square takes $\Theta (N^2)$ character positions in either. Heights use $\Theta (N)$ array entries rather than $\Theta (N^2)$, so they are superior for the requested operations; their initialization also takes only $\Theta (N)$ time.