Dr. Probot is a famous inventor, known for many creations, his most recent being "Bot".

Bot is the very first working robot, he has 3 very basic instructions:

  • Left
  • Right
  • Self Destruct

Left: Rotate 90° left, move forward one space.
Right: Rotate 90° right, move forward one space.
Self Destruct: Destroy itself for all eternity, leave no traces.

Bots are preprogrammed to pick a random left/right movement. They will also self-destruct if they bump into another bot, or leave the grid.

Each turn all the bots move at once.

The bots are programmed to stop if they are the last one left.

Imagine an $n\times n$ grid full of bots, all facing in one direction. Is there a general strategy to determine if eventually, there will be 1 bot standing, and in how many turns? If there is, what is it? If there isn't, explain why not.

  • $\begingroup$ Though I suppose the question is if there will ever be just one bot, one can note that a single bot will almost surely (i.e. with probability $1$) walk off the grid (<profound>since being dead is the only absorbing state </profound>) - meaning, if we wait long enough, all the bots will blow up. $\endgroup$ – Milo Brandt Feb 14 '15 at 3:38
  • $\begingroup$ Do all bots move in a common direction or does each one make an individual decision ? $\endgroup$ – The Dragonista Feb 14 '15 at 3:55
  • $\begingroup$ @The Dragonista Individual. $\endgroup$ – warspyking Feb 14 '15 at 9:57
  • 6
    $\begingroup$ My problem with tasks like this is that they're not actually puzzles. You made up some rules and ask to analyze the behavior of the system (how many turns). Very likely, there's nothing better to do than write code to simulate it. No clever solution, no aha's, no elegance. Good puzzles are crafted with their solution in mind. $\endgroup$ – xnor Feb 14 '15 at 16:30
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because the main question is unlikely to be solvable as a puzzle, and is more apt as a programming exercise. $\endgroup$ – xnor Feb 19 '15 at 3:43

No, there's not.

If it's 1x1

Ends immediately.

If it's 2x2

There is 1 guy left after two moves if everyone moves in the same direction. There is no one left if NW and SW turn left and NE and SE turn right.

If it's nxn

Imagine a 3x3 grid, and the bots are all facing north. They turn left and 3 go off the west end. Then they either have to go north or south. I'll choose north, but the result in the other direction is identical. They go north, and two more bots fall off. Then you have 4 bots left in a 2x2 square in the northwest corner of the grid. They can now continually turn right. Obviously there will eventually be 1 left if they all go W then N then W then N then W then N etc..

  • $\begingroup$ You are sure this is possible no matter what n is? $\endgroup$ – warspyking Feb 14 '15 at 3:46
  • $\begingroup$ If the bots just all follow a pattern like: West-North-West-South-West-North-West-South-West... then, for any $n>2$, they will run off the grid, never leaving one bot alone - which generalizes the pattern. $\endgroup$ – Milo Brandt Feb 14 '15 at 3:51
  • $\begingroup$ Yeah, corrected myself. 1x1 and 2x2 have to be handled separately, but there is not a general solution. $\endgroup$ – Millie Smith Feb 14 '15 at 3:52
  • $\begingroup$ 2x2 could end with no one, they could all move right, then all move right again. $\endgroup$ – warspyking Feb 14 '15 at 3:53
  • $\begingroup$ I'll wait to see if there's more answers before accepting by the way. $\endgroup$ – warspyking Feb 14 '15 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.