The Cleaning Robot Puzzle: A Floor with a Twist

Give the cleaning robot’s floor a half twist, like a Möbius strip, and after one lap round the room its up is the map’s down, and the commands that cleaned every flat room walk it into the walls.

This is Part 5 of the cleaning robot puzzle. Part 4 glued the room’s edges into a torus, and the robot lost its ability to name fields by counting moves. This part glues two edges with a twist, and the robot loses something it never knew it had: a compass. On every floor so far, ^ meant the same direction everywhere. Here it doesn’t.

The new algorithms this time:

• tracking a frame, so that a plan made on the map can be told to a robot that only knows its own directions;
• union-find with parity, a disjoint-set structure in which every element also remembers one bit about how it relates to the others, so that “does this floor have a loop that turns the robot over?” can be answered after every change in near-constant time;
• learning a symmetry group from examples, with Schreier’s lemma and Part 4’s Hermite normal form, so that the blind robot can fold its map when it comes home mirrored.

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

A floor with a twist

Take a strip of paper, give one end a half turn, and tape the ends together. You have a Möbius strip, the surface Johann Benedict Listing and August Möbius each found in 1858 (Listing first, in July; Möbius in September). Run a pencil along the middle and you come back to where you started having drawn on “both sides”: the strip has only one.

Engineers have used that. In 1949 Owen Harris patented an abrasive belt with a half twist, so that both faces wear and the belt lasts longer (US 2,479,929), and in 1957 B. F. Goodrich patented a twisted conveyor belt for hot material, whose faces take turns carrying the load and cooling off (US 2,784,834).

The robot’s floor is the same thing, made of square fields. The room is still a list of strings, and its right edge is glued to its left edge upside down: walking off the right end of row r brings the robot back on the left end of row H − 1 − r, the mirror-image row of a room H rows high. The top and bottom rows run along the strip’s two edges, which work like walls. There is no other wall round the room.

The arrows say how the edges are glued: the left edge’s arrow points up and the right edge’s points down, so gluing arrow to arrow needs the half twist.

The robot has no compass

On every earlier floor, ^ meant “up the map”, and nobody needed to say what “up” was, because it was the same everywhere. A real robot has no map-up. It has its own front and its own left, painted on its body, and it carries them wherever it goes. If it drives in the four directions without ever turning, as this one does, then ^ means “towards the way my arrow points”.

On a flat floor or a torus those are the same thing. On the Möbius strip, they part company at the seam. Drive the robot below across the seam and watch its arrow:

When it leaves the right edge of row 2 of a 5-row strip, it comes back on the left edge of row 2 again (the middle row is its own mirror image), still moving right. But everything across the seam is upside down, so the robot’s arrow, which still points to its up, now points to the map’s down. Its left and right hands are still its left and right, but relative to the map it has been reflected.

Home, upside down

The cleanest way to see it is a lap. From the middle field of the 5×7 strip above, > seven times brings the robot back to the field it started on. On a torus it would come back exactly as it left. Here it comes back mirrored: its ^ now takes it down the map and its v up. From any other row, > seven times lands it on the mirror-image row instead: ^ then seven > from the middle ends one row below the middle.

Two things are worth separating.

Which command strings bring the robot home? Exactly the same ones as on a flat floor, as long as nothing is in the way. The robot’s position, counted in its own directions, changes by the same amount for every command it carries out, twist or no twist, so a string that adds up to zero on the flat floor adds up to zero here. (The strip adds strings that come home too, like > fourteen times, but none are lost.)

How does it come home? That is what the twist changes. A loop can return the robot to its starting field mirrored. On a flat floor, every loop brings the robot back as it left; on the Möbius strip, a loop that goes round the strip an odd number of times flips it over.

Part 1’s commands walk into walls

Part 1’s walk writes its commands in the map’s directions: to step into the field above, write ^. Planned on the Möbius strip’s map, with wrapped neighbours, the walk is still a correct walk on the map. But the robot reads each command in its own directions. Until the walk first crosses the seam, the two agree. After that, until it crosses back, every ^ and v the map asks for moves the robot the wrong way.

Here is a room where it happens early:

The map’s walk and the robot’s-own-directions walk agree on their first ten commands, v<^^^<vvv<. The tenth, <, crosses the seam from the left edge to the right. It arrives mirrored, on the top row. The map’s next command is v, down the map. For the mirrored robot, v means up, and up from the top row is the strip’s edge. The robot’s-own-directions version says ^ instead.

Replay the two side by side:

On 500 random Möbius rooms, from 1 to 9 rows high and 3 to 12 fields long with up to 40% furniture, the map’s walk went wrong, into a wall or into the wrong field, on 362 of the 459 rooms whose floor reaches the seam. On the other 97 it never happened to ask for ^ or v while the robot was mirrored, for instance on strips a single row high. On the 41 rooms whose floor never reaches the seam it never went wrong, as it shouldn’t.

Tracking the frame

The fix is to plan on the map and translate as you go. Keep track of the robot’s frame on the field it stands on: which side of the field its ^ points through, and whether its clockwise runs the same way as the field’s. That is two numbers, (up, mirrored). A map direction then becomes a robot direction with one line:

def robot_dir(frame, side):
    """The robot's direction (0-3) that points through the given side: the inverse of side_of."""
    up, mirrored = frame
    return (up - side) % 4 if mirrored else (side - up) % 4

The robot’s directions are numbered clockwise from its own up, ^ > v <, and so are each field’s sides. If the robot isn’t mirrored, its direction d points through side up + d; if it is, through side up − d.

The only other thing to know is how the frame changes when the robot crosses an edge. Entering field g through its side t, the robot keeps moving the same way, towards g’s side t + 2, and every direction along the edge stays the same direction. Those two facts fix the answer:

def cross(surface, field, frame, side):
    step = surface.glue[field][side]
    if step is None:
        return None
    g, t, flipped = step
    up, mirrored = frame
    if flipped:
        return g, ((side + t + 2 - up) % 4, not mirrored)
    return g, ((up + t + 2 - side) % 4, mirrored)

Across an ordinary edge the frame turns by t + 2 − side quarter turns, which is zero on a flat floor, where the right side (1) of one field meets the left side (3) of the next. Across the twist it reflects. Part 6 will need the turning case; this part needs the reflection.

With that, Part 1’s walk works on any surface. Its only other trick was stepping back, and stepping back needs no translation at all: the robot doesn’t turn, so it arrives moving in the direction it set off in, and the way back is the opposite of the way it came, in its own directions:

def depth_first(surface, start, frame=(0, False), order=PART1_ORDER):
    seen = {start}
    moves = []
    trail = []                      # (command that undoes the step, field, frame)
    field = start
    while True:
        for side in order:
            step = cross(surface, field, frame, side)
            if step is not None and step[0] not in seen:
                d = robot_dir(frame, side)
                seen.add(step[0])
                moves.append(DIRS[d])
                trail.append((DIRS[(d + 2) % 4], field, frame))
                field, frame = step
                break
        else:
            if not trail:
                return ''.join(moves)
            back, field, frame = trail.pop()
            moves.append(back)

On a flat floor this produces Part 1’s commands exactly, character for character: test_surface.py checks that on Part 1’s five example rooms and 500 random ones. On the same 500 Möbius rooms, and on tori, Klein bottles and flat floors with the robot starting in a random frame, the simulator accepted every walk: every reachable field cleaned in exactly 2(N − 1) commands.

Two ways round every field

Where can the robot be? Not just which field, but which field and which way round. A breadth-first search over pairs (field, mirrored) answers it. On a flat floor or a torus every pair it reaches has mirrored = false: N pairs for N fields. On the empty Möbius strip it reaches every field both ways round, 2N pairs.

Those pairs form a surface of their own, twice the size, with no twist: the orientation double cover. For the Möbius strip it is a cylinder of twice the length, which you can make by cutting a paper Möbius strip down the middle: you get one loop twice as long, with four half-twists, not two loops. The robot on the strip is exactly a robot on that cylinder, with its “mirrored” bit saying which half it is on. The figure above draws it underneath the strip.

With furniture, the answer depends on the floor. The robot can reach both ways round exactly when the floor contains a loop that goes round the strip an odd number of times. Floor that never crosses the seam, or crosses and comes back the way it came, behaves like a flat floor. On 600 random rooms (Möbius strips, Klein bottles, tori and flat floors), 391 were orientable and 209 had a loop that mirrors the robot, and on every one the breadth-first search found exactly N or exactly 2N pairs, as it should.

A floor with a mirroring loop needs different handling everywhere a robot’s frame matters: a robot that remembers “the charger is to my left” is wrong half the time. So it is worth being able to answer “does this floor have a loop that turns the robot over?” quickly, and, as the next section shows, over and over as the floor changes.

Union-find with parity

Suppose the floor isn’t fixed. Furniture is taken out of the room one piece at a time, and after each piece we want to know whether the floor now has a loop that turns the robot over. A breadth-first search after every change answers it, at a cost proportional to the whole floor each time: quadratic over a whole sequence of changes.

There is a much faster way, and it is a small extension of one of the most useful data structures there is.

Union-find

Union-find (also called a disjoint-set forest) keeps a collection of items split into groups, and supports two operations: find(x), which names x’s group, and union(a, b), which merges two groups. Every item points at a parent, and following parents leads to a root that names the group. Two items are in one group exactly when their roots are the same.

Two tricks make it fast:

• Union by size: when merging, hang the smaller tree under the root of the larger, so trees stay shallow.
• Path compression: after a find, point every item it passed straight at the root, so the next find is quick.

With both, a sequence of m operations on n items takes O(m α(n)) time, where α is the inverse of Ackermann’s function. α grows so slowly that, in Jeff Erickson’s words, α(n) ≤ 3 “for all even remotely imaginable values of n” (his notes on union-find): in practice, constant time per operation.

One more bit

For the twist, each item gets one extra bit: its parity, whether it is mirrored relative to its parent. Adding up the bits on the way to the root (exclusive or) says whether an item is mirrored relative to its root, and two items in one group are mirrored relative to each other exactly when those answers differ.

union(a, b, p) records “b is mirrored relative to a” when p is 1. If a and b are in different groups, it joins them and sets the new link’s bit so that the claim holds. If they are already in one group, it checks the claim against what it knows instead. A claim that disagrees means a loop through the new edge with an odd number of mirrorings: a loop that turns the robot over.

From parity_dsu.py:

class ParityDSU:
    def __init__(self):
        self.parent = {}
        self.bit = {}                   # mirrored relative to the parent?
        self.size = {}
        self.consistent = True          # no loop has contradicted a claim yet

    def add(self, x):
        if x not in self.parent:
            self.parent[x], self.bit[x], self.size[x] = x, 0, 1

    def find(self, x):
        """(root, parity of x relative to the root), compressing the path on the way back."""
        path = []
        while self.parent[x] != x:
            path.append(x)
            x = self.parent[x]
        root, parity = x, 0
        for y in reversed(path):        # nearest the root first
            parity ^= self.bit[y]
            self.parent[y], self.bit[y] = root, parity
        return root, (self.bit[path[0]] if path else 0)

    def union(self, a, b, p):
        ra, pa = self.find(a)
        rb, pb = self.find(b)
        if ra == rb:
            if pa ^ pb == p:
                return 'agrees'
            self.consistent = False
            return 'contradicts'
        if self.size[ra] < self.size[rb]:
            ra, rb, pa, pb = rb, ra, pb, pa
        self.parent[rb] = ra
        self.bit[rb] = pa ^ pb ^ p      # so that parity(b) = parity(a) ^ p holds through ra
        self.size[ra] += self.size[rb]
        return 'joined'

The only subtle line is the last bit. After the join, b’s parity relative to the new root is pb, its parity relative to its old root, plus the new link’s bit. We want that to equal a’s parity pa plus p, so the link’s bit must be pa ^ pb ^ p. Path compression keeps every bit meaning the same thing: when an item is re-pointed at the root, its bit becomes its whole path’s parity.

A worked example

Take a strip 3 rows high and 6 fields long, full of furniture, and lay its floor one field at a time in a shuffled order. Every new field is joined to the floor neighbours already there: bit 0 for an ordinary edge, bit 1 for an edge across the twist, which joins row r at the right end to row 2 − r at the left.

• The first five fields, (1, 5), (1, 3), (0, 0), (2, 4) and (0, 2), touch nothing already laid. Five groups of one.
• (2, 3) arrives next to (1, 3) and (2, 4): two joins, with bit 0, and three groups become one. Four groups.
• (1, 4) arrives next to (1, 5), (2, 4) and (1, 3). The first two join it to their groups. By the third, (1, 4) and (1, 3) are already in one group, with the same parity, and the claim “same way round” agrees: the four fields round the corner between them make an ordinary loop. Three groups.
• (0, 3), (0, 5) and then (2, 5) join more fields in. The last of these sits at the right end of row 2, so its neighbour across the twist is (0, 0) at the left end of row 0, and that join has bit 1: (0, 0) now belongs to the big group, marked as mirrored relative to (2, 5). One group.
• (2, 2) and (1, 0) arrive. (1, 0) sits at the left end of the middle row, whose neighbour across the twist is (1, 5), the middle row’s right end. The forest already knows (1, 0)’s parity through (0, 0), and it agrees with the new bit 1.
• (1, 1), then (1, 2). The last of (1, 2)’s joins is with (1, 1), bit 0: “same way round”. But the forest already connects them through the twist, and following the parities round that way says they are mirrored. The claim contradicts what the forest knows. The loop through the new edge goes round the strip once and turns the robot over, found at the 14th field of 18.

The figure below replays exactly that order.

Step through it, and watch the trees flatten as path compression points field after field straight at the root:

When does the first mirroring loop appear?

Now the question from the start of the section. Take an n × n Möbius strip, full of furniture, and remove the pieces one at a time in random order. After each, join the new floor field to its floor neighbours, with bit 1 across the twist. The first 'contradicts' is the first moment the floor has a loop that turns the robot over. Record what fraction of the floor was there by then:

The fractions are falling towards a famous number. A loop that turns the robot over must go round the strip, so it needs a path of floor all the way along it, and that is a percolation question: when does a random set of open sites first connect across a large region? For site percolation on the square grid the answer, in the limit of large regions, is p_c = 0.59274621…, measured to eight digits by Mark Newman and Robert Ziff in 2000 with exactly this kind of union-find (Newman and Ziff, 2000). Part 6 comes back to it with a torus, from the other side.

A search after every new field gets the same answers, and the test checks that on twenty 32 × 32 strips. It is just much slower: on one 64 × 64 strip, in one run on this machine, union-find took 27 ms and the searches 1,647 ms, finding the same first contradiction at the 2,583rd field. The search re-examines every field it can reach each time; union-find only ever walks short paths to roots.

The same class answers Part 4’s question online too. Give every step between neighbours the bit 1, “different colour”, and the first contradiction is the first odd loop: a floor built piece by piece stops being two-colourable at that moment. Union-find with parity is, in the end, an online two-colouring.

The blind robot needs an arrow

Part 4’s blind robot finished on any torus because it could recognise its dock. Whenever it stood on the dock at a counted position p other than (0, 0), p was a period of the room, a shift that carries the room’s copy on the unrolled plane onto itself, and it folded its map by that shift.

On a Möbius strip, that reasoning breaks. After one lap the robot is back on its dock, at counted position (0, 7) say, but mirrored. The copy of the room it has walked into on its unrolled plane is not a shifted copy but a mirror image of the first one, shifted. Folding the map by the shift glues each field to the wrong one, the field in the mirror-image row. On 150 random Möbius rooms, Part 4’s robot with a plain round dock stopped with the right number of fields on 26. On the other 124 its map contradicted itself: a field it had marked as floor turned out, after folding, to be the same field as one it had marked as furniture.

What the robot can see on the dock

The fix is to make the dock tell the robot more. Paint an arrow on it, or better a letter F, a shape that looks different in a mirror. Standing on the dock, the robot reads the arrow in its own directions: for each of its directions ^ > v <, which side of the dock that direction points through. In surface.py the robot’s on_dock() now returns exactly that, or None off the dock.

It reads the arrow once at the start and again every time it comes back. Comparing the two readings tells it how its directions now relate to what they were: unchanged, turned, or mirrored. Together with the counted position p, that is a whole symmetry of its unrolled plane: a map v ↦ Mv + p, where M is one of the eight ways to turn or reflect a square, that carries the copy of the room it started in onto the copy it is standing in now:

def symmetry(self, p, reading):
    """The symmetry that carries the start onto counted position p with the arrow looking
    like `reading`: direction d at the start matches the direction that now points through
    the same dock side."""
    now = {side: d for d, side in enumerate(reading)}
    return matrix([now[self.first[d]] for d in range(4)]), p

Learning the room’s symmetries

Every symmetry found this way belongs to one group: the symmetries of the unrolled floor. Compose two of them and you get a third, and so on. To name fields, the robot needs, for any counted position, one canonical representative of everything the group can carry it to. In Part 4 the group was a lattice of shifts, and the Hermite normal form did it.

Now the group has reflections in it. But it has a simple shape. Every symmetry is a shift after one of at most eight turns and reflections, and the shifts in the group form a lattice, exactly Part 4’s kind. So the robot stores:

• one representative symmetry for each turn-or-reflection that occurs, and
• the lattice of shifts, in Hermite normal form.

To name a position q, it applies each representative to q, reduces the result modulo the lattice, and keeps the smallest. Every symmetry in the group is a lattice shift after some representative, so that minimum is the same for every position in q’s orbit and different for positions in different orbits.

Which shifts belong in the lattice? Schreier’s lemma says: for every representative r and every symmetry s the robot has found, s after r is a shift away from the representative for its own turn-or-reflection, and those leftover shifts generate the lattice. The robot recomputes this closure each time it learns a new symmetry, which happens only a handful of times:

def learn(self, p, reading):
    g = self.symmetry(p, reading)
    if self.contains(g):
        return False
    self.found.append(g)
    gens = self.found + [inverse(x) for x in self.found]
    reps, shifts, todo = {IDENTITY: (IDENTITY, (0, 0))}, [], [IDENTITY]
    while todo:                                 # Schreier: close up the representatives
        r = reps[todo.pop()]
        for s in gens:
            sr = compose(s, r)
            if sr[0] not in reps:
                reps[sr[0]] = sr
                todo.append(sr[0])
            else:
                shifts.append(compose(sr, inverse(reps[sr[0]]))[1])
    self.reps, self.basis = reps, hermite(shifts)
    return True

def canon(self, p):
    return min(reduce(compose(r, (IDENTITY, p))[1], self.basis) for r in self.reps.values())

Everything else is Part 4’s frontier explorer with its doubling radius, unchanged: it only ever asks the group for canon and learn. For a Möbius floor with a loop round the strip the group ends up with two representatives, “as you were” and “mirrored”, and a lattice with one shift, two laps’ worth. For a Klein bottle it has a second, ordinary shift as well.

Results

On 120 random rooms each of Möbius strips, Klein bottles, tori and flat floors (3 to 8 rows, 3 to 9 columns, up to 40% furniture, a random starting frame), the robot with an arrow on its dock cleaned every reachable field and stopped every time. It found a mirroring symmetry exactly on the rooms whose floor has a loop that turns the robot over. Moves per field, as in Part 4 (moves divided by N − 1):

The flat floors cost least, since there is nothing to discover. The others pay for the laps the robot has to take before it learns what the room is.

The Klein bottle

Glue the Möbius room’s top and bottom edges together too, plainly, as a torus glues them, and the room becomes a Klein bottle: no edge anywhere, and a twist one way round.

Everything in this part works on it unchanged. Part 1’s walk, tracking the frame, cleans it. The breadth-first search over (field, mirrored) reaches every field both ways round. Union-find with parity finds the twist. The blind robot with an arrow on its dock learns what the room is, and what it learns is worth looking at, because it shows the difference between the two floors exactly.

On the empty 5 × 7 Möbius strip above, the robot ends with two representatives and a lattice with one shift:

• “as you were”, and a glide reflection: flip the rows over, then move seven columns along. That is one lap round the strip, which brings the robot home mirrored.
• the shift (0, 14): two laps, which bring it home the right way round, fourteen columns along.

On the empty 5 × 7 Klein bottle it ends with a glide reflection again, now combined with a shift of five rows as well, and a lattice with two shifts, (5, 0) and (0, 14). The (5, 0) is the plain loop from top to bottom, and (0, 14) is still two laps round the twisted way. The Möbius strip’s symmetries repeat in one direction only, because the strip has edges; the Klein bottle’s repeat in two, because it doesn’t.

Its orientation double cover, the (field, mirrored) pairs, is a torus, twice as long as the room. That is the Klein bottle’s version of the cylinder the Möbius strip unrolled into, and it is why a robot that tracks its frame can think of the Klein bottle as a torus in which each field appears twice, once each way round.

One more gluing is left: both pairs of edges with a twist. That surface, the projective plane, can’t be built this way at all, because it would need 360° of curvature somewhere, and every corner in these rooms has exactly four squares round it. Where the curvature comes from, and what it does to the robot, is Part 6.

Testing Part 5

test_mobius.py produces every number above:

Underneath, test_surface.py checks the model: crossing an edge and crossing back restores every frame on every surface, and > seven times from the middle of the strip comes home as (2, mirrored).

What Part 5 teaches

• Some assumptions are invisible until they fail. Nobody thought “^ means the same thing everywhere” was an assumption. It was the compass every earlier part relied on.
• Plan in one frame, act in another, and translate. Tracking two numbers, the robot’s up and whether it is mirrored, makes every earlier algorithm work on the twisted floor.
• One bit per link turns connectivity into consistency. Union-find with parity answers “is this floor orientable?” and “is this graph two-colourable?” online, in near-constant time per edge.
• Measure the thing, then find its name. The first mirroring loop arrives at around 60% of the floor, falling with size: percolation’s threshold, with a union-find algorithm behind its best measurement.
• A landmark has to carry enough information. A round dock tells the robot where it is; an arrow also tells it which way round, and on a twisted floor that is the difference between a correct map and a contradiction.
• Groups are data structures too. A lattice for the shifts plus a handful of representatives for the turns and mirrors, glued by Schreier’s lemma, gives every position a canonical name.

Part 6 takes the robot up the walls of a box, where turning a corner turns the robot too.