The Column Sweep

Work columns, not cubes

You could hunt cubes one at a time, scanning the drawing for likely candidates. It fails under time pressure for two reasons: you lose track of which cubes you have already judged, and you never reach the cubes you cannot see.

Sweep column by column instead. Take a column, run up it from the table to its top cube, write down a number for each cube, and move to the next column. Columns do not overlap, and the height map lists every one of them, so when the last column is done every cube in the pile has been counted exactly once.

The rule

The previous topic established the identity this rests on: a cube's painted count is the number of its faces meeting open air among the top and the four sides. Read that off a height map and it becomes arithmetic.

Pick a cube and note which level of its column it sits at. Look at the four columns touching that column edge to edge, and count how many of them have a cube at that same level. Call that number L.

If the cube is the top of its column, its painted count is 5 − L.

If another cube sits on top of it, its painted count is 4 − L.

The two lines are one rule. A cube starts with five faces in play. Its top face survives unless a cube covers it, which is what separates the two lines; each of the four side faces survives unless a neighbouring column is standing at that level, which is what L subtracts. A slot outside the footprint, or an empty slot inside it, is a column of height zero and is never standing at any level, so edge columns simply have a smaller L.

The only thing the rule reads is the height map. Once you have the heights written down you never look at the picture again, which is exactly what makes the method survive a pile you cannot fully see.

Sweep a pile

Here is a nine-cube pile. Its five columns are labeled A through E, and every cube that shows a face wears its painted count.

Nine cubes in five columns, A through E; the seven cubes that show a face carry their painted counts.

Seven badges, nine cubes. Work the columns one at a time and watch the arithmetic produce all nine numbers, including the two the drawing has no way to show you.

Showing column A.

Column A: one cube, painted count 3.

A is 1 cube tall. Two of its four neighbouring slots hold columns of height 2; the other two are empty. Its single cube tops the column, and both standing neighbours reach that level, so L is 2: 5 − 2 = 3.

The cubes you cannot see come free

Nine numbers came out of five columns, and two of them belong to cubes the drawing never renders: the lower cube of B and the bottom cube of D. Nothing special happened when the sweep reached them — they are cubes in a column with heights on four sides, and the rule needed nothing else. Visual scanning can only reach cubes that are drawn; a column sweep reaches every cube the height map claims.

One consequence is worth keeping as a check. The cube at the top of a column always has at least one painted face: nothing covers its top, so its count is 5 minus L, and L can be at most 4. If a sweep ever hands you a zero for a column's top cube, you have made an arithmetic slip.

A bigger pile

Nothing about the rule changes as piles grow. There is just more of it.

Seventeen cubes in ten columns, badged the same way.

Ten columns, seventeen cubes, fourteen badges. Take the one column here whose four neighbouring slots are all occupied: it stands 3 cubes high, with columns of 2, 1, 1 and 3 packed around it. Its bottom cube is covered above and has all four neighbours standing at that level, so 4 − 4 = 0 — a cube with no painted face at all. Its middle cube keeps only the columns of 2 and 3 as company that high, giving 4 − 2 = 2. Its top cube has nothing above it and only the column of 3 still standing beside it, giving 5 − 1 = 4.

The sweep just reported a cube with no painted face at all, in a pile whose drawing shows nothing of the kind, using the same subtraction it used on a one-cube column. Work the remaining nine columns the same way and every cube has a number. Turning that heap of numbers into an answer is the next topic's job.

Run sweeps on fresh piles in the cube counting practice generator until the arithmetic stops feeling like arithmetic.

The takeaway

Take one column at a time, bottom to top, and give every cube in it a number before moving on. At each level, count how many of the four touching columns have a cube at that same level: the count is 5 minus that number for the cube topping the column, and 4 minus it for every cube underneath. The height map is the only input, so the sweep reaches buried cubes as easily as visible ones, and a column's top cube can never come out below one.

The Column Sweep

Summary

Practice Questions

AI Tutor