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

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.