The O(n) Club: Robot Bounded in Circle—How to Stop Your Robot From Moonwalking to Infinity

The O(n) Club: Robot Bounded in Circle—How to Stop Your Robot From Moonwalking to Infinity

⚡ TL;DR

Does your robot know when to stop, or is it headed for a starring role in ‘Interstellar 2, Not My Fault’? Fast answer: after one cycle through the instructions, check two things: did the robot return home (0,0), or is it facing a new direction? If either is true, congrats—your robot will spin forever in a lovely fenced-in circle. Otherwise, it’s about to ghost planet Earth.
Here’s a Java one-liner for people who prefer to let the JVM worry:

// After one loop, is it bounded?
public boolean isRobotBounded(String instructions) {
    int x=0, y=0, d=0;
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    for(char c: instructions.toCharArray()){
        if(c=='G') { x += dirs[d][0]; y += dirs[d][1]; }
        else if(c=='L') d = (d+3)%4;
        else d = (d+1)%4;
    }
    return (x==0 && y==0) || d!=0;
}

🧠 How Devs Usually Mess This Up

If you think this problem sounds like you need to simulate the robot until the sun explodes, you’re not alone. Most folks crank out simulation after simulation expecting an epiphany (or a crash). Others think the ONLY way to win is to get back to the origin every cycle, thereby missing the sneaky ‘facing a new direction’ trap. Life pro tip: trust the math, not your panicked instincts.

🔍 What’s Actually Going On

This is less about robots and more about dance choreography. If, after its set of moves, your little automaton is either back where it started, or even just facing a different wall—err, direction—it will eventually draw a loop. Repeat the steps, and it winds itself back, never escaping its own square dance floor. But if it’s still facing North, and not home, it’s got wanderlust—prepare for an endless moonwalk.

Think Roomba: it isn’t smart enough to vacuum your neighbor’s house by accident, unless you tell it to.

🛠️ PseudoCode

• Start at (0,0), facing North (direction=0).
• For every instruction you read:
  • If ‘G’, move forward in your current direction.
  • If ‘L’, turn left: direction = (direction + 3) % 4.
  • If ‘R’, turn right: direction = (direction + 1) % 4.
• After one cycle:
  • If you’re back at (0,0) OR turned away from North, robot is bounded.
  • Otherwise: Bon voyage, little buddy!

💻 The Code

public boolean isRobotBounded(String instructions) {
    int x = 0, y = 0, direction = 0; // 0=N, 1=E, 2=S, 3=W
    int[][] move = new int[][]{ {0,1}, {1,0}, {0,-1}, {-1,0} };
    for(char c : instructions.toCharArray()) {
        if (c == 'G') {
            x += move[direction][0];
            y += move[direction][1];
        } else if (c == 'L') {
            direction = (direction + 3) % 4;
        } else if (c == 'R') {
            direction = (direction + 1) % 4;
        }
    }
    return (x == 0 && y == 0) || direction != 0;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All ‘G’ and no turn? Infinity and beyond—robot keeps going, batteries not included.
• Robot never returns to (0,0)? If it’s not facing North, you’re still safe: next lap, it’ll corner itself.
• The mod-4 dance: direction %= 4 is your fields medal. Forget this math and the robot forgets its directions.
• Complexity? O(n) time, O(1) space—unless you debug-print every move, in which case, enjoy your memory leak.

🧠 Interviewer Brain-Tattoo

“If your robot’s still facing North and nowhere near home, it’s not coming back. Just like your hopes after debugging on Friday night.”