# The cleaning robot puzzle: the code The Python behind the posts on slow-is-smooth.io. Parts 1 to 7 use only the standard library. From Part 8 on, the solvers written from scratch still do, but the big rooms are solved with HiGHS through its Python package (`pip install highspy`); without it those checks and reports are skipped, and say so. The figure checkers in docs/ need Playwright. Run each script from this folder, for example `python test_dirt.py`. ## Part 1: /blog/the-cleaning-robot-puzzle/ - cleaning_robot.py: the depth-first walk, the same walk without the trip home, and a version without recursion - test_cleaning_robot.py: the simulator, the example rooms, 3,000 random rooms and the empty 40x40 rooms ## Part 2: /blog/the-cleaning-robot-puzzle-dirt-capacity-and-a-battery/ - dirt_common.py: reading a room, the walk, routes and subset sum, shared by the solutions below - pick_cells.py: pick cells, always the best answer - take_all_fast.py: take all, with random spanning trees and the tree dynamic program - take_all_exact.py: take all, searching every connected group that could still win - pick_cells_battery.py: pick cells with a battery, a heuristic - take_all_battery.py: take all with a battery, a heuristic - test_dirt.py: the simulator, the brute-force referees and the comparison report ## Part 3: /blog/the-cleaning-robot-puzzle-four-new-rules/ - shortest_route_fast.py, shortest_route_exact.py: the fewest commands - blind_robot.py: exploring without a map - dock_common.py, pick_cells_dock.py, take_all_dock.py, dock_exact.py: emptying the bag at the dock - two_robots.py, two_robots_no_collide.py, two_robots_exact.py: two robots - test_shortest_route.py, test_blind_robot.py, test_dock.py, test_two_robots.py: simulators, referees and reports ## Parts 4 to 7: floors that are not flat - surface.py: square fields glued edge to edge, the robot's frame, its moves, Part 1's walk on any surface, a simulator, and the builders for every floor below; test_surface.py checks it ### Part 4: /blog/the-cleaning-robot-puzzle-a-room-that-wraps-around/ - torus.py: the room that wraps around, Part 1's walk on it, random rooms and a robot for the blind tests - periods.py: the labelled spanning tree, the room's periods and the Hermite normal form - blind_torus.py: a blind robot with a dock it can recognise, exploring frontier first with a doubling radius - two_colour.py: a checkerboard colouring, or an odd loop that proves there isn't one - route_exact.py: fewest commands on any surface, the checkerboard pruning optional - test_torus.py: the checks and the report ### Part 5: /blog/the-cleaning-robot-puzzle-a-floor-with-a-twist/ - mobius.py: the Mobius room, the walk in the robot's own directions and in the map's - parity_dsu.py: union-find with parity - blind_twist.py: the blind robot with an arrow on its dock, learning the room's symmetry group - test_mobius.py: the checks and the report ### Part 6: /blog/the-cleaning-robot-puzzle-cleaning-a-box/ - box.py: the walk on a box, "drive k, turn left", and the turns loops leave the robot with - group_dsu.py: union-find with labels from any group - unfold.py: shortest straight routes over a box by unfolding, and a check that pulls the string tight - test_box.py: the checks and the report ### Part 7: /blog/the-cleaning-robot-puzzle-five-squares-at-every-corner/ - hyperbolic.py: the floor with five squares at every corner, built exactly ring by ring, and from floating-point coordinates for comparison - growth.py: the transfer matrix, fast powers and the growth rate - berlekamp_massey.py: the shortest linear recurrence behind a sequence - bidirectional.py: breadth-first search from one end and from both - test_hyperbolic.py: the checks and the report (`--slow` adds the float comparison to ring 15) ## Part 8: /blog/the-cleaning-robot-puzzle-a-lower-bound-from-a-linear-program/ - simplex.py: the simplex method in exact fractions (two phases, Bland's rule), with dual prices and a check of the certificate they make - maxflow.py: maximum flow and minimum cut, by Edmonds and Karp - route_lp.py: the fewest-commands question as a linear program, the search for broken rules with minimum cuts, and the cutting-plane loop, on the exact solver or on HiGHS - test_route_lp.py: the checks and the report ## Part 9: /blog/the-cleaning-robot-puzzle-the-shortest-route-exactly/ - branch_cut.py: the integer program (Part 8's with parity and whole numbers), branch and bound with the cutting-plane loop at every node and Gomory's cuts at the root, in exact fractions; Hierholzer's algorithm, which turns the answer into a route - route_ip.py: the same program in HiGHS for big rooms, with a single-commodity flow as well as Part 8's connected rules, and Part 3's fast route as the first answer - test_branch_cut.py: the checks and the report (the 40x40 rooms take 15 minutes each) ## Part 10: /blog/the-cleaning-robot-puzzle-planning-the-trips/ - column_gen.py: emptying the bag (pick cells) as a choice of trips: column generation with the master in HiGHS or in simplex.py, pricing by labels and dominance on ng-routes, a completion bound over q-routes, and the enumeration of every trip within the gap that proves the best plan - test_column_gen.py: the checks and the report ## The figures - docs/figure_data.py: writes the site's data/cleaning_robot.json from the solutions' own output - docs/check_figures.py: builds the site and checks the robot players in Chromium - docs/check_theory_figures.py: does the same for the twelve figures in Parts 2 and 3's theory boxes, comparing every number they compute with the solutions and oracles above - docs/check_surface_figures.py: does the same for the figures in Parts 4 to 7 - docs/or_figure_data.py: writes the site's data/cleaning_robot_or.json, which Part 8's figures and cover read, from route_lp's own output - docs/ip_figure_data.py: writes data/cleaning_robot_ip.json, which Part 9's figures and cover read - docs/cg_figure_data.py: writes data/cleaning_robot_cg.json, which Part 10's figures and cover read - docs/check_or_figures.py: builds the site and checks the figures of Part 8 onwards in Chromium The checkers need the site's source, which is not public, so they are here as a record of how the figures were checked.