"""Checks and a comparison report for two robots (Part 3). Run from this folder: python test_two_robots.py """ import random import time import two_robots import two_robots_exact import two_robots_no_collide from shortest_route_fast import DIRS, steps from test_cleaning_robot import random_room from two_robots import lower_bound, parse_two STEP = {go: (dr, dc) for dr, dc, go in DIRS} CORRIDOR = ['##############', '#....*..@....#', '##############'] PLUS = ['#####', '##.##', '#*.@#', '##.##', '#####'] T_JUNCTION = ['######', '##.###', '#*@..#', '######'] OPEN = ['######', '#*...#', '#....#', '#...@#', '######'] def simulate_two(room, a_moves, b_moves, collide): """Replay both robots step by step and return the finishing time; fail on any broken rule.""" a, b, floor = parse_two(room) for moves in (a_moves, b_moves): assert set(moves) <= set(STEP) | {'.'}, f'unexpected command in {moves!r}' assert not moves.endswith('.'), 'trailing wait' pa, pb, seen = a, b, {a, b} for t in range(max(len(a_moves), len(b_moves))): na = step(pa, a_moves, t) nb = step(pb, b_moves, t) assert na in floor and nb in floor, f'walked into a wall at step {t + 1}' if collide: assert na != nb, f'both robots on {na} after step {t + 1}' assert not (na == pb and nb == pa), f'robots swapped places at step {t + 1}' pa, pb = na, nb seen |= {pa, pb} assert seen == floor, 'fields left dirty' finish = max(len(a_moves), len(b_moves)) assert finish >= lower_bound(room) return finish def step(pos, moves, t): if t >= len(moves) or moves[t] == '.': return pos return pos[0] + STEP[moves[t]][0], pos[1] + STEP[moves[t]][1] def oracle_sharing(room): """Independent answer for the sharing rules: for each robot alone, the fewest steps to have visited at least a given set of fields; then the best way to divide the fields.""" a, b, floor = parse_two(room) cells = sorted(floor) bit = {cell: 1 << i for i, cell in enumerate(cells)} full = (1 << len(cells)) - 1 inf = float('inf') def alone(start): best = [inf] * (full + 1) first = (start, bit[start]) seen, layer, k = {first}, [first], 0 best[bit[start]] = 0 while layer: k += 1 nxt = [] for pos, mask in layer: for n, _ in steps(pos, floor): state = (n, mask | bit[n]) if state not in seen: seen.add(state) nxt.append(state) best[state[1]] = min(best[state[1]], k) layer = nxt for i in range(len(cells)): # visiting more also covers less for mask in range(full + 1): if not mask >> i & 1: best[mask] = min(best[mask], best[mask | 1 << i]) return best ga, gb = alone(a), alone(b) return min(max(ga[mask], gb[full & ~mask]) for mask in range(full + 1)) def expect(name, got, wanted): assert got == wanted, f'{name}: got {got}, expected {wanted}' def rooms_from_post(): for name, room, share, apart in (('corridor', CORRIDOR, 6, 6), ('plus', PLUS, 2, 3), ('T-junction', T_JUNCTION, 2, 2), ('open 3x4', OPEN, 5, 5)): expect(f'{name} exact sharing', simulate_two(room, *two_robots_exact.solution(room, False), False), share) expect(f'{name} exact no collisions', simulate_two(room, *two_robots_exact.solution(room, True), True), apart) fast_share = simulate_two(room, *two_robots.solution(room), False) fast_apart = simulate_two(room, *two_robots_no_collide.solution(room), True) print(f' {name:<10} lower bound {lower_bound(room)}; sharing: exact {share}, fast {fast_share}; ' f'no collisions: exact {apart}, fast {fast_apart}') print('rooms from the post ..... ok') def two_start_room(rng, R, C, wall_p): room = [list(row) for row in random_room(rng, R, C, wall_p)] free = [(r, c) for r, row in enumerate(room) for c, ch in enumerate(row) if ch == '.'] if not free: return None r, c = rng.choice(free) room[r][c] = '@' return [''.join(row) for row in room] def tiny_rooms(rng, count=500, max_fields=12): checked = 0 stats = {'sharing': [0, 0], 'no collisions': [0, 0]} price = [] while checked < count: room = two_start_room(rng, rng.randint(3, 6), rng.randint(3, 6), rng.choice([0, 0.2, 0.4])) if room is None or len(parse_two(room)[2]) > max_fields: continue share = simulate_two(room, *two_robots_exact.solution(room, False), False) apart = simulate_two(room, *two_robots_exact.solution(room, True), True) expect(f'sharing oracle {room}', oracle_sharing(room), share) assert share <= apart for rule, exact, fast in (('sharing', share, simulate_two(room, *two_robots.solution(room, 0.2), False)), ('no collisions', apart, simulate_two(room, *two_robots_no_collide.solution(room, 0.2), True))): assert fast >= exact stats[rule][0] += fast == exact stats[rule][1] = max(stats[rule][1], fast - exact) if share: # rooms with nothing to clean have no price price.append(apart / share) checked += 1 print(f'tiny rooms (<= {max_fields} fields) {checked} rooms: exact search = independent sharing oracle on every room') for rule, (best, gap) in stats.items(): print(f' {rule:<22} best on {best}/{checked}, worst gap {gap}') print(f' price of no collisions exact times {sum(price) / len(price):.2f}x on average, {max(price):.1f}x at worst') def bigger_rooms(rng, sizes=((12, 12, 20), (40, 40, 10))): for R, C, count in sizes: ratios, price, worst = [], [], 0.0 done = 0 while done < count: room = two_start_room(rng, R, C, rng.choice([0, 0.15, 0.3])) if room is None: continue t = time.perf_counter() share = simulate_two(room, *two_robots.solution(room), False) apart = simulate_two(room, *two_robots_no_collide.solution(room), True) worst = max(worst, time.perf_counter() - t) ratios.append(apart / lower_bound(room)) price.append(apart / share) done += 1 print(f'{R}x{C} rooms ............ {count} rooms: no collisions {sum(ratios) / count:.2f}x the lower bound ' f'on average, {sum(price) / count:.2f}x the sharing time; {worst:.1f} s at worst') def main(): rng = random.Random(2026) rooms_from_post() tiny_rooms(rng) bigger_rooms(rng) print('all checks passed') if __name__ == '__main__': main()