The Cleaning Robot Puzzle: Four New Rules

Ask the cleaning robot for the fewest commands, take away its map, give it a dock that empties its bag, then add a second robot that must not collide with it.

Part 1 and Part 2 kept the robot’s world simple: it knew the map, it worked alone, and any complete route was good enough. This part takes those comforts away one at a time. Each question changes a single rule, and each change turns the puzzle into a different classic problem.

It builds on Part 1’s depth-first walk and on Part 2’s dirty rooms, pickup rules and helpers. The same approach as Part 2 applies throughout. Where the best answer is hard to find, there is a fast solver and an exact one. Every answer is replayed by a simulator that enforces the rules, and on rooms small enough, brute force acts as the referee.

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

Fewest commands

The question

The rules are Part 1’s: clean every floor field and finish anywhere. But now the answer should use as few commands as possible.

Part 1’s walk spends a lot of commands walking back. Trimming the final walk home helps, but it’s the walking back in the middle that really costs.

The corridor. The robot starts one field from the right end:

Part 1 walks <<<<<>>>>>>< (12 commands), and trimmed it’s <<<<<>>>>>> (11). The best route is ><<<<<<: step right first, then walk left to the end. That’s 7 commands. Leave the longest branch for last.

Example 2 (5×5, start in the middle): Part 1 needs 48 commands, and trimmed 29. The best needs 24, exactly one command per new field. The fast solver finds ^^<<v>v<vv>^>v>>^<^>^^<v.

How short can a route possibly be?

Three simple facts give a lower bound. A route that reaches it is proven to be the best.

• One new field per command. With N floor fields, every route needs at least N − 1 commands.
• Checkerboard colours. Colour the floor like a chessboard. Every command steps onto the other colour, so the route alternates colours. If S fields share the start’s colour and O fields have the other colour, the route needs at least 2S − 2 commands and at least 2O − 1.
• Dead ends. Leaving a dead end (a field with only one neighbour) means stepping back onto a field already visited. Only one dead end can be the last field, so D dead ends force at least N − 1 + (D − 1) commands.

“Visit the farthest branch last” is not the whole story

If the floor is a tree (a maze with no loops), the best route is easy to describe. Every corridor has to be walked in and back out, except the ones on the path to where the robot finishes. So the best is 2(N − 1) − (distance to the farthest field), and “visit the farthest branch last” achieves it.

For any room, the best route that follows some spanning tree is 2(N − 1) − L, where L is the longest simple path from the start. It’s tempting to think that’s the answer. It isn’t:

Here N = 7 and the longest simple path is L = 3, so the tree formula says 9. But v>^<^<v cleans all seven fields in 7. It goes around the bottom loop, back through the start, and around the top loop. Loops let the robot come back without retracing its steps. The checkerboard bound proves that 7 can’t be beaten: four fields have the other colour, so the route needs at least 2 × 4 − 1 = 7.

The true question is: in which order should the robot visit the fields, if it walks the shortest way between consecutive ones? That is a travelling-salesman path on grid distances. Deciding whether N − 1 commands are enough is the Hamiltonian path problem, which is NP-complete even on grid graphs. Itai, Papadimitriou and Szwarcfiter proved that in 1982 for a path between two given fields, and Brunner and colleagues in 2023 for the robot’s case, a given start and a free end.

Brute force also turned up rooms where neither the formula nor the lower bound is reached:

The tree formula gives 9 and the lower bound 7, and the true best is 8 (^v<v>^>>).

The fast solver

It builds several candidate routes and keeps the shortest. It stops as soon as one reaches the lower bound.

1. Tree route. Grow Part 1’s depth-first tree, then visit it in preorder with the deepest branch last, walking the shortest path from each field to the next. This is never longer than Part 1’s trimmed walk, and it is exactly the best on mazes.
2. The same, with Warnsdorff’s rule. When growing the tree, step to the neighbour with the fewest ways onward. This rule, famous from the knight’s tour puzzle, tends to produce long snakes that don’t leave stranded fields behind.
3. Greedy walks. Walk by Warnsdorff’s rule directly, preferring to keep going straight on ties and breaking remaining ties at random. When stuck, walk to the nearest uncleaned field. This is repeated with 10 different random choices.

def route_lower_bound(start, targets, walkable):
    """No route from start that visits every target (walking inside walkable) is shorter than this.

    - Each command reaches at most one new target: n - 1.
    - Steps alternate colours on a checkerboard, so the route needs enough steps of each colour.
    - Leaving a dead end means stepping back onto a visited field, except at the very end.
    """
    targets = set(targets) | {start}
    n = len(targets)
    same = sum((r + c) % 2 == (start[0] + start[1]) % 2 for r, c in targets)
    other = n - same
    dead_ends = sum(1 for cell in targets
                    if cell != start and sum(1 for _ in steps(cell, walkable)) == 1)
    return max(n - 1, 2 * same - 2, 2 * other - 1, n - 1 + max(0, dead_ends - 1))


def tree_route(start, targets, walkable, choose):
    """Grow a depth-first tree over the targets, then visit it in preorder with the deepest
    branch last, so the route never walks back from its far end."""
    parent, children, found = {start: None}, {start: []}, [start]
    stack = [start]
    while stack:
        options = [n for n, _ in steps(stack[-1], targets) if n not in parent]
        if not options:
            stack.pop()
            continue
        n = choose(options, parent, targets)
        parent[n], children[n] = stack[-1], []
        children[stack[-1]].append(n)
        found.append(n)
        stack.append(n)

    height = dict.fromkeys(found, 0)
    for cell in reversed(found[1:]):
        height[parent[cell]] = max(height[parent[cell]], height[cell] + 1)
    order, stack = [], [start]
    while stack:
        cell = stack.pop()
        order.append(cell)
        stack.extend(sorted(children[cell], key=lambda k: -height[k]))   # deepest is popped last
    order += [cell for cell in targets if cell not in parent]            # targets the tree missed
    return follow(start, order, walkable)


def best_route(start, targets, walkable, runs=10, seed=0):
    """Shortest of several routes that visit every target; stops as soon as one is provably best."""
    targets = set(targets) | {start}
    bound = route_lower_bound(start, targets, walkable)
    rng = random.Random(seed)
    makers = [lambda: tree_route(start, targets, walkable, first_option),
              lambda: tree_route(start, targets, walkable, fewest_exits)]
    makers += [lambda: greedy_route(start, targets, walkable, rng)] * runs
    best = None
    for make in makers:
        route = make()
        if best is None or len(route) < len(best):
            best = route
        if len(best) <= bound:
            break
    return best

The listing leaves out the small helpers, which are in shortest_route_fast.py: steps(cell, allowed) yields each neighbour inside allowed with the command that reaches it, follow walks to each field of an order in turn by a shortest path and skips any it has already crossed, first_option and fewest_exits choose the next field while the tree grows (the second by Warnsdorff’s rule), and greedy_route builds candidate 3.

The functions take a set of targets and a separate set of walkable fields for a reason: the two-robots solution later reuses them to cover just one robot’s share of the room.

The exact solver

A breadth-first search over (robot’s field, set of cleaned fields), with two tricks to keep it small:

• It only looks for routes shorter than the fast one.
• It drops a state if even an ideal finish can’t beat the fast route. From the current field, the next steps alternate colours starting with the other colour. So with same uncleaned fields of the current colour and other of the other colour, at least max(same + other, 2 * same, 2 * other - 1) more commands are needed.

def solution(room, max_states=1_000_000):
    fast = shortest_route_fast.solution(room)
    if len(fast) <= lower_bound(room):
        return fast                             # the fast route is already proven shortest

    start, floor = parse(room)
    cells = sorted(floor)
    index = {cell: i for i, cell in enumerate(cells)}
    full = (1 << len(cells)) - 1
    black = sum(1 << i for i, (r, c) in enumerate(cells) if (r + c) % 2 == 0)
    moves = [[(index[(r + dr, c + dc)], go) for dr, dc, go in DIRS if (r + dr, c + dc) in index]
             for r, c in cells]

    first = (index[start], 1 << index[start])
    parent = {first: None}
    layer = [first]
    for k in range(1, len(fast)):               # only routes shorter than the fast one matter
        nxt = []
        for state in layer:
            i, mask = state
            for j, go in moves[i]:
                new = (j, mask | 1 << j)
                if new in parent:
                    continue
                left = full & ~new[1]
                same = bin(left & (black if black >> j & 1 else ~black)).count('1')
                other = bin(left).count('1') - same
                # the next steps alternate colours starting from the other colour
                if k + max(same + other, 2 * same, 2 * other - 1) >= len(fast):
                    continue
                parent[new] = (state, go)
                if new[1] == full:
                    return rebuild(parent, new)
                nxt.append(new)
        if len(parent) > max_states:
            return None
        layer = nxt
    return fast                                 # nothing shorter exists

parse, DIRS and lower_bound come from the fast solver: parse returns the start and the set of floor fields, DIRS is the direction table, and lower_bound(room) is route_lower_bound over the whole floor. rebuild follows the parent links back from the finished state to read off the commands. The whole search is in shortest_route_exact.py.

It returns None when the search grows past max_states, rather than running for hours. The report counts those cases instead of hiding them.

Results

On three 40×40 rooms with a random start:

On big furnished rooms the gap to the lower bound stays wide. The bound is weak there, and nobody knows how far from the best the fast routes really are.

Blind robot

The question

There is no map any more. The robot has one sense: robot.move(d) either moves one field and returns True, or bumps into something, stays put and returns False. It must still clean every field it can reach. It doesn’t know how big the room is or where it started.

Walking and bumping are counted separately: moves are the successful steps, and bumps are the failed ones.

Building its own map

The robot calls its starting field (0, 0) and keeps a dictionary known of what it has learned: True for floor it has stood on, False for walls. Then it runs Part 1’s depth-first search, with walls discovered by bumping:

• Probe the directions around the current field, skipping anything already known.
• A failed probe marks a wall. A successful one is a step forward, and the field it came from goes on the trail.
• When nothing around the field is unknown, walk back one step along the trail.

def explore(robot, order, trim, shortcuts):
    pos, heading = (0, 0), None
    known = {pos: True}                     # True: floor the robot has stood on, False: wall
    trail = []                              # fields the robot came from, newest last
    unknown = {shift(pos, d) for d in STEP}  # unprobed cells next to visited floor
    while True:
        for d in order(heading):
            n = shift(pos, d)
            if n in known:                  # never probe a known wall or a visited field
                continue
            unknown.discard(n)
            if robot.move(d):
                known[n] = True
                trail.append(pos)
                pos, heading = n, d
                unknown.update(m for m in (shift(n, e) for e in STEP) if m not in known)
                break
            known[n] = False
        else:                               # everything around this field is known
            if not trail or (trim and not unknown):
                return sum(known.values())
            last = walk_shortcut(robot, pos, trail, known) if shortcuts else None
            if last:
                pos, heading = trail.pop(), last
                continue
            back = trail.pop()
            heading = next(d for d in STEP if shift(pos, d) == back)
            robot.move(heading)
            pos = back

STEP maps each command to its step, and shift(cell, d) is the field one step from cell in direction d. order(heading) gives the directions to probe, trim switches on the first improvement below, and walk_shortcut is the second. The whole robot, with both probing orders, is in blind_robot.py.

With the map order ^ v < > and no extras, the blind robot’s steps are exactly Part 1’s commands, one for one. It makes the same decisions; it just learns about each wall by bumping into it.

What every blind robot has to pay

Bumps can’t be avoided. A robot that is certain it’s done must have bumped every wall touching the floor. Any wall it never touched could have been a doorway to more room. This robot never probes a known cell, so it bumps each such wall exactly once. No blind robot can bump less.

Walking costs at most double. The walk uses at most 2(N − 1) moves, while even a robot with the map needs at least N − 1. So it never walks more than twice the best route. Research on exploring grid rooms without a map studies the closed-tour version of this problem. It shows that with obstacles, no strategy can guarantee better than a factor of 2. Without obstacles, a smarter depth-first search guarantees 4/3 (Icking, Kamphans, Klein and Langetepe, 2005; longer version on arXiv; a newer lower bound).

Three improvements

1. Stop when nothing is left to probe. Keep the set of unprobed cells next to visited floor, and stop the moment it is empty, even halfway back along the trail.
2. Take shortcuts. When walking back, skip trail fields with nothing left to probe, and walk the shortest way through known floor to the next one that has something.
3. Probe in left-hand order. Try left, straight, right, then back, relative to the robot’s last move, the way you might follow a wall in the dark.

Watching it think

In these logs, x marks a bump.

The 2×2 room (8 walls touching the floor):

• Map order: ^x v vx <x > ^ ^x >x v vx >x < ^ <x. It walks v>^v<^, 6 moves, going all the way home just to bump the start’s left wall.
• Left-hand order: <x ^x > ^x >x v >x vx < vx <x. It walks >v<, 3 moves, as good as the best route with a map.

A ring around a pillar: map order walks 14 moves (vv>>^^<>vv<<^^), left-hand order 7 (>>vv<<^), the same as the best with a map. Both bump 13 times.

No order wins everywhere. In a corridor lying on its side with the start at one end, map order walks 4 moves and left-hand order 8. Stand the same corridor on end and it’s the other way round: 8 moves for map order, 7 for left-hand. The bumps are 12 in both cases, as they must be.

Results

On 3,000 random rooms up to 40×40, every variant cleaned everything and bumped every wall exactly once (0.51 bumps per field on average). The plain walk matched Part 1 command for command. Padding the room with extra walls on the top and left gave identical logs, which confirms the robot never uses coordinates it shouldn’t know.

All five variants together take at most 233 ms on a 40×40 room.

Next, the robot gets its bag back.

Emptying the bag

The question

Part 2’s dirty room is back, but the bag is small now. The robot’s start field is a dock: whenever the robot stands on it, the bag empties. The robot must clean every dirty field using as few moves as possible, finishing anywhere. C costs nothing, and the capacity is at least 5, so every field fits on its own. Both of Part 2’s pickup rules get a solution.

The 50,000-command limit can’t hold here. A 40×40 room full of 5s with capacity 5 needs one trip per field, and that costs 106,782 moves however cleverly it’s planned. So instead of that limit, the checks use an upper bound that every answer must stay under.

Examples (capacity 5)

Filling each trip is a trap.

Filling each trip until the next field doesn’t fit gives trips of 3, then 3 + 2, then 2: 2 + 6 + 4 = 12 moves. The best plan is 3, then 3, then 2 + 2: 2 + 4 + 4 = 10 (><>><<>>>> under take all). Spare room in a trip near the dock is cheap; the far trip is the one that should be full.

The pickup rule matters.

• Pick cells: drive over the 1 and clean the 5 on its own (>>C<<), then collect the 1 and the 4 together (>C>>C): 7 moves.
• Take all: the robot can’t reach the 5 without scooping up the 1, and 1 + 5 doesn’t fit. So it’s >< for the 1, >><< for the 5 and >>> for the 4: 9 moves.

Nothing to optimise.

Every trip carries a single 5, so both rules need 15 moves. That is the most any plan can need and the fewest possible.

How good can a plan be?

• Upper bound: one field per trip, farthest trip last. That’s 2 × (sum of distances from the dock) − (the farthest distance). Every answer must stay at or under it.
• Lower bound, from distance. A closed trip costs at least twice the distance to its farthest field, and weighting fields by their dirt gives at least ⌈2 × Σ(dirt × distance) / capacity⌉ − farthest distance.
• Lower bound, from steps. Every dirty field needs a step onto it, and every trip except the last ends with a step onto the dock. That’s at least (dirty fields) + ⌈total dirt / capacity⌉ − 1.

One long tour, cut in the best places

The plan is built in two steps: first choose an order for all the dirty fields, then decide where to cut that order into trips.

Once the order is fixed, the best cut is a small dynamic program, a classic trick from vehicle routing. best[j] is the fewest moves to finish the first j fields, trying every possible start for the last trip: go out to its first field, follow the order to field j, and come home. With running sums and a sliding-window minimum over the trips that still fit in the bag, the whole cut takes O(n) time.

def split(weights, d0, gaps, capacity):
    """Cut fields 0..n-1 (in this order) into consecutive trips with the fewest moves.

    A closed trip over fields a..b costs d0[a] + gaps a..b + d0[b]; the last trip doesn't come
    back. gaps[k] is the walk from field k to field k+1. Returns (moves, trips as index lists).
    Uses a sliding-window minimum, so it runs in O(n)."""
    n = len(weights)
    if n == 0:
        return 0, []
    load, walked = [0] * (n + 1), [0] * n       # prefix sums of weights and of gaps
    for k in range(n):
        load[k + 1] = load[k] + weights[k]
        if k:
            walked[k] = walked[k - 1] + gaps[k - 1]
    best = [0] * (n + 1)                        # best[t]: fewest moves to finish fields 0..t-1
    came_from = [0] * (n + 1)
    key = [0] * n                               # cost of a trip starting at a, minus its gaps so far
    window = deque()
    for b in range(n):
        key[b] = best[b] + d0[b] - walked[b]
        while window and key[window[-1]] >= key[b]:
            window.pop()
        window.append(b)
        while load[b + 1] - load[window[0]] > capacity:
            window.popleft()
        a = window[0]
        best[b + 1] = key[a] + walked[b] + d0[b]
        came_from[b + 1] = a
    a = window[0]                               # the open last trip ends at field n-1
    trips, t = [list(range(a, n))], a
    while t > 0:
        s = came_from[t]
        trips.append(list(range(s, t)))
        t = s
    return key[a] + walked[n - 1], trips[::-1]

Which order? Start with the preorder of a breadth-first tree grown from the dock, visiting the child that leads deepest last. This order has a useful property: every field comes after its parent in the tree. Under take all, that makes every cut legal. The way out to a trip’s first field runs through its ancestors, which are already clean, and so does the way home.

Pick cells: improve the order

With brushes up, the robot can drive anywhere, so the order can be improved freely.

• A distance table. Run a breadth-first search from every field and store the results in compact 16-bit arrays: 1,444 × 1,444 distances in about 4 MB, taking 0.7 seconds on a 40×40 room. Each search also records that field’s 8 nearest dirty fields.
• Local search. Try putting a field right next to one of its 8 nearest fields, either by moving it or by reversing the stretch in between. Re-cut the order after each change, which is cheap because the cut is O(n). Keep any change that saves moves, and stop after 2 seconds.

def changes(order, x, y):
    """New orders that put field x right next to its nearby field y."""
    i, j = order.index(x), order.index(y)
    without = order[:i] + order[i + 1:]
    k = without.index(y)
    yield without[:k + 1] + [x] + without[k + 1:]           # move x to just after y
    yield without[:k] + [x] + without[k:]                   # move x to just before y
    if i < j:
        yield order[:i + 1] + order[i + 1:j + 1][::-1] + order[j + 1:]   # reverse so y follows x
    else:
        yield order[:j] + order[j:i][::-1] + order[i:]                   # reverse so y precedes x

In #*154#, the tree order is 1, 5, 4, which cuts into 9 moves. Moving the 5 in front of the 1 gives the trips 5 | 1 + 4: 7 moves.

Take all: the clean area has to stay connected

Under take all, the robot can’t take shortcuts across dirty floor: it would scoop up dirt early and might overflow. So the walk from one field to the next may only cross fields that are already clean, plus the target itself. The order can’t be rearranged freely either, so instead the solver tries 30 different breadth-first trees, with random neighbour order and random tie-breaks. It cuts each one in the best places and keeps the cheapest plan, stopping early if a plan reaches the lower bound.

def clean_path(a, b, cleaned, dirt):
    """Fields along a shortest path from a to b that never enters an uncleaned field before b."""
    def open_to(n):
        return n == b or n in cleaned or dirt.get(n) == 0

    parent, queue = {a: None}, deque([a])
    while b not in parent:
        cell = queue.popleft()
        for dr, dc, _, _ in MOVES:
            n = (cell[0] + dr, cell[1] + dc)
            if n in dirt and n not in parent and open_to(n):
                parent[n] = cell
                queue.append(n)
    path = []
    while b != a:
        path.append(b)
        b = parent[b]
    return path[::-1]


def plan(dock, dirt, capacity, rng):
    """One tree: its order, the walk between consecutive fields, and the best cut into trips."""
    dist, parent = bfs_tree(dock, dirt, rng)
    order = tree_order(dock, dirt, dist, parent, rng)
    cleaned, gaps = {dock}, []
    for k in range(len(order) - 1):
        cleaned.add(order[k])
        gaps.append(len(clean_path(order[k], order[k + 1], cleaned, dirt)))
    moves, trips = split([dirt[f] for f in order], [dist[f] for f in order], gaps, capacity)
    return moves, [[order[i] for i in trip] for trip in trips], parent

bfs_tree and tree_order build the breadth-first tree and the order described above. They live in dock_common.py with split and the code that turns trips into commands, and MOVES is Part 2’s direction table. The rest of the take-all solver is in take_all_dock.py, and the pick-cells one, with its distance table and local search, in pick_cells_dock.py.

The exact solver and the referee

dock_exact.py runs a 0-1 breadth-first search over (field, cleaned fields, bag load). A move costs 1, C costs 0, and stepping onto the dock empties the load. Pick cells also gets an independent referee: the cheapest single trip for every set of fields (Held–Karp), then the best way to split all the fields into closed trips plus one open trip. The two must always agree.

Results

Part 2’s running example shows where the fast solvers lose a little:

Pick cells found the best plan every time. Take all, which can’t reorder freely, missed by 2 moves with the larger bags.

Last, a second robot joins in.

Two robots

The question

Two robots share the room. Robot A starts on * and robot B on @. At every step both run their next command at the same time, and a robot whose commands have run out stays where it is. The floor is clean once every field has been visited by one of them. The goal is to finish as soon as possible, so the time is the length of the longer command string.

And they must not collide:

• they may never stand on the same field after a step;
• they may never swap places in one step;
• a robot may move into the field the other one is just leaving, as when following it down a corridor;
• the command . makes a robot wait.

Examples

The corridor.

Each robot first steps inward to clean a field between them, then runs to its own end. A runs ><<<<< and B runs <>>>>>, which takes 6 steps. The lower bound (below) is 5, and brute force confirms that 6 is the best.

The plus-shaped room.

If sharing were allowed, both robots would step into the centre and then go different ways: 2 steps. Without collisions, one of them has to wait: B runs <^, A runs .>v and follows B through the centre, taking 3 steps.

Following is allowed.

B runs >> while A runs >^, stepping into the field B has just left. That takes 2 steps; if following were banned, it would take 3.

The open room.

Twelve fields, two already clean: at least ⌈10 / 2⌉ = 5 steps. Two snakes, vv>^^ and ^^<vv, achieve exactly that.

A lower bound

• Two new fields per step at most. With N fields and both starts already clean, at least ⌈(N − 2) / 2⌉ steps are needed.
• Distance. Some field is at least max over all fields of min(distance from A, distance from B) away from both robots.

Step 1: split the work, ignoring collisions

The solver builds several plans and keeps the fastest:

1. Split into regions. Each field goes to whichever robot reaches it first when B starts delay steps late, which keeps both regions connected. A binary search finds the delay where the two routes balance. Each robot’s route comes from the fewest-commands solver, run on just its own region while walking anywhere on the floor. Then border fields move from the longer region to the shorter one for as long as that helps.
2. Cut one shared walk. Build a single route from A over the whole floor that ends on B’s start. A walks the front part and B walks the back part in reverse, and the cut goes where the longer part is shortest. On the open room, one snake cut in half beats two separate regions.
3. Give everything to one robot, in case the other one is badly placed.

def shared_walk(a, b, floor):
    """One route from a over the whole floor, extended to end on b. A walks its front part and B
    walks its back part in reverse, cut where the longer of the two parts is shortest."""
    commands = best_route(a, floor - {b}, floor)
    end = positions(a, commands)[-1]
    if end != b:
        commands += ''.join(go for go, _ in shortest_path(end, b, floor))
    cells = positions(a, commands)
    n = len(commands)
    first, last = {}, {}
    for k, cell in enumerate(cells):
        first.setdefault(cell, k)
        last[cell] = k
    starts_at = [[] for _ in range(n + 1)]
    for cell, k in first.items():
        starts_at[k].append(cell)
    # need[i]: the latest index where B's part may begin if A's part ends at index i
    need, latest = [0] * (n + 1), n
    for i in range(n, -1, -1):
        need[i] = latest
        latest = min([latest] + [last[cell] for cell in starts_at[i]])
    i = min(range(n + 1), key=lambda i: (max(i, n - need[i]), i + n - need[i]))
    j = need[i]
    return commands[:i], ''.join(BACK[go] for go in reversed(commands[j:]))

positions(start, commands) lists the field the robot stands on after each command, shortest_path is the breadth-first path from shortest_route_fast.py, and BACK maps each command to its reverse. The region split and the rest of step 1 are in two_robots.py.

Step 2: stay out of each other’s way

If the plan from step 1 happens to be collision-free, it’s the answer. Otherwise:

• One robot keeps its route. At every step it “reserves” the field it will stand on, and it holds its final field for good.
• The other plans around it in space and time. It visits the fields it still has to clean in the same order as before, but plans each leg with a breadth-first search over (field, time). It may move or wait, but never onto a reserved field and never through the other robot. After its last field it parks somewhere the first robot never passes again.
• Both ways round. Each robot gets a turn at keeping its route, and the faster plan wins.

def timed_path(pos, t, goal, kept_at, end, floor):
    """Earliest sequence of moves or waits from (pos, t) to a (field, time) that meets goal, never
    sharing a field with the kept robot and never swapping with it. None if impossible."""
    if goal(pos, t):
        return []
    options = [(0, 0, '.')] + DIRS
    first = (pos, min(t, end))
    parent = {first: None}
    queue = deque([(pos, t)])
    while queue:
        cell, time = queue.popleft()
        here = kept_at(time)
        there = kept_at(time + 1)
        for dr, dc, go in options:
            n = (cell[0] + dr, cell[1] + dc)
            if n not in floor or n == there or (n == here and there == cell):
                continue
            state = (n, min(time + 1, end))
            if state in parent:
                continue
            parent[state] = ((cell, min(time, end)), go, time)
            if goal(n, time + 1):
                path = []
                while parent[state]:
                    prev, go, _ = parent[state]
                    path.append((go, state[0]))
                    state = prev
                return path[::-1]
            queue.append((n, time + 1))
    return None

Once the kept robot has finished, time no longer matters, so the search stores time as min(time, end) and always terminates.

kept_at(t) is the kept robot’s field at time t, and goal(cell, time) says when a leg is done: standing on the next field to clean or, for the last leg, on a field the kept robot never stands on again. DIRS is the fewest-commands solver’s direction table. The whole replanner, with the plan that always works, is in two_robots_no_collide.py.

A plan that always works. A cleans everything it can reach without passing B, and comes home while B waits. Then B cleans everything it can reach without passing A. Why does that cover every field? Take any field and a shortest path to it from A. Either the path avoids B’s start, so A cleans the field, or it passes B’s start and never comes back to A’s, so B cleans it. This plan is slow, but it guarantees there is always an answer.

The exact solver and the referee

two_robots_exact.py is a breadth-first search over (A’s field, B’s field, cleaned fields). Each robot moves or waits, and the collision rules can be switched on or off. The sharing rules also get an independent referee. For each robot alone, it finds the fewest steps to visit at least each set of fields, then tries every way of dividing the fields between the robots.

Results

Two robots in a random room rarely want the same field at the same moment, so avoiding collisions almost never costs time. When it does, it can cost a lot: the plus-shaped room needs 3 steps instead of 2, which is 1.5×.

Testing Part 3

Each problem has its own test script, built the same way as Part 2’s: a simulator that knows every rule, rooms designed to cause trouble, and brute force as the referee.

The referees earned their keep. They found the rooms where the tree formula fails, and the rooms where even the lower bound can’t be reached. One report once claimed that avoiding collisions made the robots faster on average. That’s impossible, and the impossible number led straight to a bug in the report itself: rooms with nothing to clean were counted as costing zero.

What Part 3 teaches

• A lower bound is half an answer. One new field per command and the checkerboard colouring proved most fewest-commands routes optimal. “Every wall touching the floor must be bumped” proved the blind robot’s bumps can’t be reduced.
• Trees are easy; loops are where the difficulty hides. On mazes, “visit the farthest branch last” is exactly right. Loops let a route come back without retracing, and suddenly the problem is a travelling-salesman path.
• Order first, then cut. Emptying the bag split into two problems. Finding the best order is hard and left to heuristics. Cutting a given order into trips is solved exactly by an O(n) dynamic program.
• Measure the cost of not knowing. In the worst case, exploring without a map can cost twice the walking. On random rooms, with shortcuts and a left-hand order, it cost 1.16×.
• Always keep a plan that can’t fail. The blind robot’s depth-first walk, the dock’s one-field-per-trip bound and the two robots’ last-resort plan each guarantee an answer. That frees the clever parts to try things.
• Brute force keeps you honest, even about your own reports.

Part 4 keeps the square fields and glues the room’s edges together, and the floor stops being flat.