"""Checks for surface.py, the square fields that Parts 4-7 glue together. Run from this folder: python test_surface.py """ import random from cleaning_robot import solution_iterative from surface import (box, corner_counts, cross, cylinder, depth_first, euler_characteristic, angle_defects, flat, frames_reachable, klein, mobius, simulate, torus) from test_cleaning_robot import EXAMPLES, random_room def check_glue(s): """Every gluing is symmetric, and crossing an edge and crossing back restores the frame.""" for f in s.floor: for side in range(4): g = s.glue[f][side] if g is None: continue h, t, flipped = g assert s.glue[h][t] == (f, side, flipped) for frame in [(u, m) for u in range(4) for m in (False, True)]: h2, fr2 = cross(s, f, frame, side) assert h2 == h # Back through side t, the robot is where it started, in the frame it had. assert cross(s, h, fr2, t) == (f, frame) def random_floor(rng, R, C, wall_p): """Random furniture; unlike Part 1's rooms, no wall round the edge.""" return [''.join('#' if rng.random() < wall_p else '.' for _ in range(C)) for _ in range(R)] def test_flat_matches_part1(): """On a flat floor, the general walk is Part 1's walk, command for command.""" rng = random.Random(1) rooms = [room for room, _ in EXAMPLES] rooms += [random_room(rng, rng.randint(3, 12), rng.randint(3, 12), rng.random() * 0.4) for _ in range(500)] for room in rooms: s, start = flat(room) check_glue(s) cmds = depth_first(s, start) assert cmds == solution_iterative(room) cleaned, _, frame = simulate(s, start, cmds) assert cleaned == reach(s, start) assert frame == (0, False) # a flat floor never turns or mirrors the robot print(f'flat rooms .............. ok ({len(rooms)} rooms, same commands as Part 1)') def reach(s, start): seen, todo = {start}, [start] while todo: f = todo.pop() for g in s.glue[f]: if g is not None and g[0] not in seen: seen.add(g[0]) todo.append(g[0]) return seen def test_topology(): """Euler characteristic, squares per corner and Descartes' total for every kind of room.""" rng = random.Random(2) empty = ['.' * 7] * 5 cases = [ ('flat', flat(['*' + '.' * 6] + ['.' * 7] * 4)[0], 1), ('cylinder', cylinder(empty)[0], 0), ('torus', torus(empty)[0], 0), ('mobius', mobius(empty)[0], 0), ('klein', klein(empty)[0], 0), ('box 3x3x3', box(3, 3, 3), 2), ('box 2x5x4', box(2, 5, 4), 2), ('pool 4x3x2', box(4, 3, 2, open_top=True), 1), ] for name, s, chi in cases: check_glue(s) assert euler_characteristic(s) == chi, (name, euler_characteristic(s)) assert angle_defects(s) == 360 * chi, (name, angle_defects(s)) # Squares at each corner: 4 inside a flat-looking floor, 3 at the eight corners of a box. for name, s, _ in cases: inside = [n for n, arcs in corner_counts(s).values() if not arcs] if name.startswith('box'): assert sorted(inside).count(3) == 8 and set(inside) == {3, 4}, name elif name in ('torus', 'klein'): assert set(inside) == {4}, name # A closed box's corners are 90 degrees short each, whatever its size: 8 x 90 = 720. for a, b, c in [(1, 1, 1), (1, 2, 3), (4, 4, 4), (7, 2, 5)]: s = box(a, b, c) short = sum(360 - 90 * n for n, _ in corner_counts(s).values()) assert short == 720 # Furniture punches holes: each hole in a flat floor lowers the characteristic by one. s, _ = flat(['.....', '.#.#.', '.....']) assert euler_characteristic(s) == -1 and angle_defects(s) == -360 for _ in range(200): room = random_floor(rng, rng.randint(3, 8), rng.randint(3, 8), rng.random() * 0.5) for build in (flat, cylinder, torus, mobius, klein): s = build(room)[0] check_glue(s) assert angle_defects(s) == 360 * euler_characteristic(s) print(f'topology ................ ok ({len(cases)} named surfaces, 1,000 random floors)') def test_frames(): """Where the robot can be facing: one way on a torus, two on a Mobius strip, four on a box.""" empty = ['.' * 7] * 5 s = torus(empty)[0] assert {fr for _, fr in frames_reachable(s, 0)} == {(0, False)} s = mobius(empty)[0] frames = frames_reachable(s, 0) assert len(frames) == 2 * len(s.floor) # every field, both ways round s = box(3, 3, 3) frames = frames_reachable(s, 0) assert len(frames) == 4 * len(s.floor) # every field, turned all four ways assert all(not m for _, (_, m) in frames) # but never mirrored: a box has two sides # The Mobius strip: '>' seven times along a 5-row strip from the middle row comes back to # the same field, mirrored. s, _ = mobius(empty) start = s.index[(2, 3)] _, field, frame = simulate(s, start, '>' * 7) assert field == start and frame == (2, True) # From any other row it lands on the mirror-image row. start = s.index[(0, 3)] _, field, _ = simulate(s, start, '>' * 7) assert s.names[field] == (4, 3) print('frames .................. ok') def test_walk_everywhere(): """Part 1's walk cleans every reachable field on every kind of surface.""" rng = random.Random(3) count = 0 for _ in range(300): room = random_floor(rng, rng.randint(3, 9), rng.randint(3, 9), rng.random() * 0.45) cells = [(r, c) for r, row in enumerate(room) for c, ch in enumerate(row) if ch == '.'] if not cells: continue r, c = rng.choice(cells) room[r] = room[r][:c] + '*' + room[r][c + 1:] for build in (flat, cylinder, torus, mobius, klein): s, start = build(room) frame = (rng.randrange(4), rng.random() < 0.5) cmds = depth_first(s, start, frame) cleaned, _, _ = simulate(s, start, cmds, frame) assert cleaned == reach(s, start) assert len(cmds) == 2 * (len(cleaned) - 1) count += 1 for a, b, c in [(1, 1, 1), (2, 3, 4), (5, 5, 5)]: for open_top in (False, True): s = box(a, b, c, open_top) cmds = depth_first(s, 0) assert simulate(s, 0, cmds)[0] == set(s.floor) count += 1 print(f'the walk everywhere ..... ok ({count} surfaces)') if __name__ == '__main__': test_flat_matches_part1() test_topology() test_frames() test_walk_everywhere()