The Cleaning Robot Puzzle: Cleaning a Box

Send the cleaning robot up the walls of a swimming pool and it finds that driving forward and turning left three times can bring it back to where it started.

This is Part 6 of the cleaning robot puzzle. Part 4 glued the room into a torus and Part 5 gave it a twist, but both floors were still flat: at every corner, four squares met, exactly as on a tiled kitchen floor. This part folds the floor round the corners of a box, where only three squares meet. That one missing square changes what “turning left” means, rules out a compass on the whole surface, and breaks the checkerboard again.

The new algorithms and ideas:

• union-find with labels from any group, the general form of Part 5’s parity structure, here with quarter turns, and with shifts for a famous result about tori;
• shortest paths by unfolding, Henry Dudeney’s spider and fly, solved by trying every way to lay the box’s faces out flat;
• an invariant as a test oracle: Descartes’ theorem, which says how many degrees any closed box is short at its corners, whatever its size, and so checks every box the code builds.

Every file behind all the parts is listed in the code’s README.

The walls of a box

Robotic pool cleaners already do this. Many of the Dolphin robots from Maytronics, a company founded at Kibbutz Yizre’el, scrub a pool’s floor, its walls and the waterline, driving up from the floor onto a wall and back down. Window robots such as Ecovacs’ Winbot hold on to the glass with suction and work their way across a pane. For a robot, the floor is simply whatever surface it is standing on, and the walls of a box are one connected surface.

So the room is now the surface of a box, a × b × c fields, cut into square fields: all six faces for a closed box, or five for a pool, whose missing top leaves a rim along the waterline that works as a wall. The robot drives over the edges between faces as if they weren’t there, down one face and up the next, and every field still has four neighbours: on a flat part of a face, the usual four; along an edge of the box, three on its own face and one on the next. As in Part 5, the robot’s commands are its own directions, ^ > v <, and it never turns, so its directions are carried over each edge.

In surface.py a box is built from its fields’ corners, which are points in space. A field on the front face and a field on the top face that meet along the box’s edge share two corners, so the same code that glued the torus and the Möbius strip glues the box, and the same cross works out how the robot’s frame changes going over the edge. Nothing about the robot is new, and neither is Part 1’s walk: on 400 random boxes and pools up to 6 × 6 × 6 with furniture, it cleaned every reachable field in exactly 2(N − 1) commands.

Drive the robot over a box yourself. Its arrow is its ^ and the short bar marks its >; turn the box to follow it round:

What is new is the corners. Almost everywhere on the box, four fields meet at each corner point, as on a flat floor. At the box’s own eight corners, three meet: one on each of the three faces. That is all the geometry there is, and it is enough.

Three left turns

Here is the experiment that shows it. Drive k fields forward, turn left, and repeat. The robot can’t turn, but “turn left” just means “use my next direction anticlockwise”, ^ then < then v then >. On a flat floor this draws a square and closes after four stretches, every time.

On the walls of a box it doesn’t. Start on one of the three fields round a corner of the box and drive one field at a time: after three stretches the robot is home. Here is the count for every starting field and every starting direction on cubes of side 2, 3, 4 and 6, driving one field per stretch:

• exactly 24 of them close after three stretches: three fields round each of the eight corners, each in one direction;
• every other one closes after four, as on a flat floor.

With longer stretches the same happens whenever the square is centred on a corner. From the field a stretch of k away, with k odd, 24 loops close after three stretches, and with k even none do. The rest close after four stretches, or, if they pass a corner off centre, after twelve. Every loop on every cube tested closed after 3, 4 or 12 stretches.

The reason is the missing square. Round a flat corner, four squares’ worth of 90° corners add up to 360°. Round a box’s corner there are three, 270°. A robot circling that corner turns left at each of three corners of its path, 90° each, and three turns plus the 90° the corner itself is missing make the 360° that bring it home. On a flat floor the four turns supply all of it.

And twelve? Four stretches that pass a box’s corner off centre don’t close. They end on the field you get by turning the start a quarter of the way round the corner: on the box, the same field on the next face, with the three faces at that corner taking turns. Round a point with only 270° available, a quarter turn has to be made three times to come back to the start, so three rounds of four stretches, twelve in all, close the loop. (The test checks this on a 6 × 6 × 6 cube: the fields reached after four and eight stretches are the start’s images under the corner’s three-fold symmetry.)

Every corner is 90 degrees short

Carry the robot round a loop and compare its frame at the end with its frame at the start. On a flat floor they always agree. Round one corner of the box the frame comes back turned a quarter turn: in the experiment above, the robot arrives home with its ^ pointing through a different side of its field than when it left. Round two corners it comes back turned half a turn. Round the belt of four side faces, which goes round four corners, it comes back turned a full turn, which is no turn at all. In each case the turn is 90° for every corner of the box inside the loop.

That 90° is the corner’s angle defect: 360° minus the angles of the squares that meet there. It is a measure of curvature concentrated at a point. A flat floor has defect 0 everywhere. A box has 90° at each of its eight corners and 0 everywhere else, 720° in all, and so does a cube of any size, a long thin box, or any other closed box. That total is not a coincidence:

An invariant as a test

That line is also a test. test_surface.py and test_box.py compute the Euler characteristic and the defects of every surface the code builds, and check them against the topology each should have: 2 and 720° for every closed box from 1 × 1 × 1 to 5 × 5 × 5, all 125 of them; 1 and 360° for every pool; 0 for a torus, a cylinder, a Möbius strip and a Klein bottle; 1 for a flat floor, less one for every hole the furniture punches in it. A mistake in the gluing, such as a face turned the wrong way or an edge glued twice, shows up as a wrong characteristic.

This kind of test is worth knowing about. The code under test builds something complicated, and nobody wants to check it field by field. But a global quantity of the result is known exactly in advance, for every size, without running anything. Checking it catches most mistakes a single example would miss.

No compass fits the box

On the flat floor, the torus and even the Möbius strip away from the seam, “up” was a direction you could paint on every field. On the box, can you? Choose, for every field, which of its sides is “north”, so that a robot that drives from field to field without turning always finds north on the same side of itself as before.

No. If such a choice existed, carrying the robot round any loop would bring it back with north on the same side as when it started, a turn of zero. But carrying it round one corner of the box turns it a quarter turn. So no choice works: there is no compass on a box. It isn’t a matter of finding a clever one. A compass needs every loop to turn the robot by zero, and the box’s corners forbid it.

This is the grid version of a famous result. The hairy ball theorem says that you can’t comb the hair on a ball flat without leaving a cowlick somewhere: every continuous field of arrows on a sphere has a point where the arrow vanishes. A compass is exactly such a field of arrows, and a box is a sphere with its curvature gathered into eight corners.

The pool

A pool is a box without its lid, and the missing lid changes the counts in an instructive way. Take a pool 10 fields long, 5 wide and 2 deep: a floor of 50 fields and four walls of 20, 20, 10 and 10, 110 fields in all. Part 1’s walk cleans it in 218 commands, 2 × (110 − 1), climbing from the floor onto each wall and back as it goes.

Its corners come in three kinds:

So all the curvature sits in the four bottom corners: 4 × 90° = 360°. A closed box had 720°. The pool’s missing lid took the other 360° with it, and in exchange the pool has a boundary, the rim, which Gauss–Bonnet counts on the other side of the equation. The pool’s Euler characteristic is 1, a disc, and 360° × 1 = 360°.

For the robot, the pool is as uncompassable as the box: a loop round one bottom corner turns it a quarter, and on this pool every quarter turn is possible. What the rim changes is only that the robot has a wall at the waterline, which surface.py gets for free: the fields along the rim have one side glued to nothing.

Union-find with labels from any group

How much can a loop turn the robot? On a closed box, every quarter turn is possible. On the belt of four side faces alone (block off the top and bottom), no loop turns it at all: the belt is a cylinder, flat, and its only loops go round four corners. On a floor of just the three fields round one corner, every turn is possible again, because the loop round that corner turns a quarter and repeating it gives the rest.

Answering that for any floor, with furniture, is the same kind of question Part 5 answered with union-find with parity. There, each item stored one bit, whether it was mirrored relative to its parent, and a contradiction meant a loop that flips the robot. Nothing in that structure depended on the labels being bits. It needed three things: a way to combine two labels (exclusive or), a way to undo one (exclusive or again), and a label meaning “no change” (0). Any group supplies those three things. So the same code, given the group of quarter turns, {0, 1, 2, 3} under addition modulo 4, tracks how much the robot’s frame turns between any two fields:

class GroupDSU:
    def __init__(self, compose, inverse, identity):
        self.compose, self.inverse, self.identity = compose, inverse, identity
        self.parent, self.rel, self.size = {}, {}, {}

    def find(self, x):
        """(root, value of x relative to the root), compressing the path."""
        path = []
        while self.parent[x] != x:
            path.append(x)
            x = self.parent[x]
        root, acc = x, self.identity
        for y in reversed(path):                    # nearest the root first
            acc = self.compose(acc, self.rel[y])
            self.parent[y], self.rel[y] = root, acc
        return root, (self.rel[path[0]] if path else self.identity)

    def union(self, a, b, g):
        """Record value(b) = value(a) * g. Returns ('joined', None), or ('loop', h) when a and b
        were already joined, with h the loop's leftover: the identity if the claim agrees."""
        ra, va = self.find(a)
        rb, vb = self.find(b)
        through = self.compose(va, g)               # value(b) by way of this edge
        if ra == rb:
            return 'loop', self.compose(through, self.inverse(vb))
        if self.size[ra] >= self.size[rb]:
            self.parent[rb], self.rel[rb] = ra, self.compose(through, self.inverse(vb))
            self.size[ra] += self.size[rb]
        else:
            # value(a) = value(b) * g^-1, so hang ra under rb the other way round.
            self.parent[ra] = rb
            self.rel[ra] = self.compose(self.compose(vb, self.inverse(g)), self.inverse(va))
            self.size[rb] += self.size[ra]
        return 'joined', None


PARITY = (lambda a, b: a ^ b, lambda a: a, 0)
TURNS = (lambda a, b: (a + b) % 4, lambda a: -a % 4, 0)
SHIFTS = (lambda a, b: (a[0] + b[0], a[1] + b[1]), lambda a: (-a[0], -a[1]), (0, 0))

The only change from Part 5 is what a “contradiction” returns. With parity there was one possible disagreement. With a bigger group, the leftover, value(a) · g · value(b)⁻¹, says how the loop through the new edge disagrees: here, by how many quarter turns it turns the robot. (The order of composition is written so that it also works for groups where order matters, such as the eight symmetries of a square, though turns and shifts don’t need it.)

The label on each edge is the turn the robot’s frame makes crossing it, which Part 5’s cross already computes: t + 2 − s quarter turns from side s of one field into side t of the next. Zero on a flat face, a quarter turn one way or the other over some edges of the box. Join every pair of neighbouring floor fields with that label, collect the leftovers of the loops, and the turns a loop can leave the robot with are all their sums.

The test compares that with a breadth-first search over (field, frame), which simply finds every frame the robot can have on its starting field. On 400 random boxes and pools with furniture they agreed every time. 16 floors allowed no turn at all, 12 only half turns, and 372 all four.

Shifts, and where a torus first wraps

The same class with a different group answers Part 4’s question incrementally. Label each step on a torus with how far it moves the robot on the unrolled plane, (−1, 0) for ^ and so on, and the leftover of a loop is its period. Lay a torus’s floor one field at a time in random order, and the first leftover other than (0, 0) is the first moment a loop goes round the torus. This is exactly how Mark Newman and Robert Ziff detect clusters that wrap round a torus in percolation simulations: each union-find link stores the displacement from an item to its parent (Newman and Ziff, 2001, crediting the idea to Machta and co-authors, 1996).

(400 runs each up to n = 64, 60 for the two largest.) The fractions rise towards the square grid’s percolation threshold, 59.27%, from below, while Part 5’s first mirroring loop on a Möbius strip approached it from above. One likely reason: a torus offers a cluster more ways to wrap, across, down or diagonally, while a loop that mirrors the robot on a Möbius strip needs a cluster that spans its length. Either way, both converge on the same number as the grid grows. The shift labels also say which way each torus wrapped, which parity bits couldn’t: across, down or diagonally.

The checkerboard fails at every corner

The three fields round a corner of the box touch each other in pairs, along the box’s three edges. They form a loop of three, an odd loop, and Part 4 showed that one odd loop rules out a checkerboard colouring. So on a box, Part 3’s checkerboard bound can’t even be stated. two_colour.py, run on every box from 1 × 1 × 1 to 5 × 5 × 5, returned an odd loop every time, and on a 4 × 4 × 4 box the first one it found has exactly three fields: a corner.

The exact solver from Part 4 works without a colouring. On the small boxes and pools it can handle, the fewest commands always turned out to be N − 1, a perfect route visiting a new field with every command, and the search, pruned only by “one new field per command”, agreed with a brute force that prunes nothing:

A checkerboard bound wouldn’t have been tight here anyway: with odd loops available, a route can reach fields of either colour when it needs to.

The spider and the fly

So far the robot has driven in steps from field to field. A real robot drives in straight lines at any angle, and on a box a “straight line” goes over edges from face to face. What is the shortest way from one point on the walls to another?

Henry Dudeney posed the famous version in the Weekly Dispatch on 14 June 1903 and included it as puzzle 75 of The Canterbury Puzzles in 1907 (Project Gutenberg). A room is 30 feet long and 12 feet wide and high. A spider sits in the middle of one end wall, a foot below the ceiling; a fly sits in the middle of the other end wall, a foot above the floor. The obvious route, up a foot, 30 feet across the ceiling, and 11 feet down, is 42 feet. The shortest is 40, and in Dudeney’s words the spider “passes along five of the six sides”.

Unfolding

The idea that solves it: cut the box open along its edges and lay a chain of faces out flat, each one folded down next to the one before it. A path over the box that crosses those faces in that order becomes a path on the flat chain, with the same length. On a flat sheet the shortest path is a straight line. So the shortest path over the box is a straight line on some unfolding: try every chain of faces from the start’s face to the goal’s, draw the straight line on each, keep the ones where the line really stays inside the chain, crossing each shared edge in order, and take the shortest.

def shortest(L, W, H, a, b):
    fs, edges = shared_edges(L, W, H)
    fa = next(i for i, f in enumerate(fs) if on_face(f, a))
    fb = [i for i, f in enumerate(fs) if on_face(f, b)]
    best = None
    for goal in fb:
        for chain in chains(fs, edges, fa, goal):
            pos = [(1, 0, False)]
            for i, j in zip(chain, chain[1:]):
                pos.append(unfold_next(fs, edges, i, pos[-1], j))
            s = place(pos[0])(local(fs[fa], a))
            t = place(pos[-1])(local(fs[goal], b))
            lams = []
            for k, (i, j) in enumerate(zip(chain, chain[1:])):
                p3, q3 = edges[i, j]
                f = place(pos[k])
                lam = crosses(s, t, f(local(fs[i], p3)), f(local(fs[i], q3)))
                if lam is None:
                    break
                lams.append(lam)
            else:
                if lams == sorted(lams):
                    length = abs(t - s)
                    if best is None or length < best[0] - 1e-9:
                        best = (length, [fs[i][0] for i in chain])
    return best

Positions on the flat sheet are complex numbers, which makes laying a face flat a one-liner: a placement is a map w ↦ αw + β, or αw̄ + β when the face is laid down mirrored, with |α| = 1. unfold_next finds the placement that puts the shared edge where the previous face left it and the new face on the far side of that edge. crosses checks where the straight segment meets each shared edge, and the fractions along the segment must come in order.

A box has six faces, so no chain is longer than six faces and there are only a few hundred of them: brute force is perfectly good. For general polyhedra the same idea needs cleverness to avoid exploring exponentially many chains. Micha Sharir and Amir Schorr gave the first polynomial algorithm for convex polyhedra in 1986, and one of their observations is that a shortest path on a convex polyhedron never passes through a corner, except at its ends (Sharir and Schorr, 1986). Round a corner with a 90° defect there is always a shortcut. crosses rejects a segment that meets an edge exactly at its end for the same reason.

For Dudeney’s room the search finds 40 feet over five faces, end wall, ceiling, side wall, floor, end wall, as he said. Try other chains:

Checked without unfolding

Unfolding is geometry, and geometry code is easy to get subtly wrong: a face laid down mirrored, an edge matched the wrong way round. So unfold.py has a second answer that never unfolds anything. For each chain it puts one point on every shared edge and slides them, one at a time, to wherever makes the path shortest in three dimensions, measuring the straight segments between consecutive points. Each segment lies within one face, the length is a convex function of each point’s position, so golden-section search finds the best spot, and repeated sweeps converge to the tightest path through that chain: a string pulled tight over the box. The shortest over all chains must equal the unfolding answer. For Dudeney’s room both give 40, and on 12 random boxes with random pairs of points they agreed to within a millionth.

A robot that drives in steps

The spider drives straight. What about the cleaning robot, which drives in grid steps? Cut Dudeney’s room into one-foot fields, 30 × 12 × 12, and put the robot on the field of the near end wall that holds the spider, in the top row, and its goal on the field of the far wall that holds the fly, in the bottom row. Breadth-first search over the surface gives the answer: 42 steps, exactly the “obvious” route’s length.

The five-face route gains nothing here, because a grid robot pays for distance differently. On the flat unfolding, the obvious route is a straight line 42 feet long along the grid, 42 steps. The five-face route is a line 40 feet long, but it runs 32 feet one way and 24 the other, diagonally across the grid, and a robot that can only drive along the grid needs 32 + 24 = 56 steps to follow it. Measured in grid steps, the Manhattan distance, the shortcut is a detour.

The spider’s puzzle is a fact about straight lines, and the cleaning robot’s routes are about steps. It is the same box with a different ruler, and the answer to “which way is shortest?” changes with the ruler. Real robots mostly drive straight, which is why the spider’s version is the one that matters for a pool cleaner.

How often does the shortest route need many faces? For 2,000 random pairs of points on the two end walls of Dudeney’s room, the shortest route crossed three faces 993 times, four 958 times and five 49 times. The five-face routes are rare, but they exist, and a robot that only tried the “obvious” chains would drive further than it needs to.

Testing Part 6

test_box.py produces every number above:

What Part 6 teaches

• Curvature is a count of missing corners. A box is flat everywhere except at eight points, each 90° short, and that alone makes three left turns close a loop and forbids a compass.
• A global invariant is a strong test. Descartes’ 720° and the Euler characteristic are known for every box in advance; checking them catches gluing mistakes no single example would.
• Generalise the data structure, not the problem. Part 5’s union-find stored bits. Given any group, the same forty lines track turns on a box, or where a torus first wraps, or which way a floor is coloured.
• Straight lines on the flat hide in unfoldings. The shortest route over a box is a straight line on some chain of faces, and with six faces, trying every chain is cheap.
• Check geometry with different geometry. Pulling a string tight in three dimensions and drawing a line on an unfolding share no code, and they agree.

Part 7 goes the other way: a floor with five squares at every corner, curved the opposite way everywhere, where the number of fields within reach grows exponentially.