5
$\begingroup$

Inspired by Maze Solving Robot and the related one on code golf SE. Also Is progress possible in an infinite maze?

Rules

  1. Two people start in the same cell in an orthogonal grid of infinite size.

  2. Each cell has four edges, and hence, a maximum of four ways to enter or exit it.

  3. Every edge in the grid is either a wall or not a wall.

  4. Each person will choose to execute a series of moves, which will consist of 'north', 'south', 'east' and 'west' instructions.

  5. If a wall exists in a direction your instruction indicates, the instruction will be skipped.

  6. You can assume that there are an infinite number of cells that are accessible from the starting cell; i.e. walls do not box you into some non-infinite subset of cells.

  7. The two persons can reside on the same cell or cross each other; their movement ignores each other's existence.

The Challenge

Find a pair of sequences of instructions (of minimum possible total length) - the first to be executed by the first person and the second to be executed by the second person, such that no matter the details of the maze, you can guarantee that atleast one of the two persons doesn't end up at the starting cell, once execution completes.

P.S. I'm not sure this can be done; if it can't, prove that.

Improve this question
$\endgroup$
3
  • $\begingroup$ P.S. Turns out the solution is extremely easy. If I get down-voted, I'll delete the post. $\endgroup$
    – ghosts_in_the_code
    Commented Jan 30, 2017 at 14:51
  • $\begingroup$ What do you mean you'll delete it if it gets downvoted? SE doesn't work that way, downvotes might mean people don't like the question, but it's not something against you personally, not at all. $\endgroup$
    – Buffer Over Read
    Commented Jan 30, 2017 at 20:35
  • $\begingroup$ @CipherRiddle I know that, but downvotes indicate that the puzzle is too boring, and hence is not an asset to the site. I read a meta post once that said it was fine to delete posts that had negative score. $\endgroup$
    – ghosts_in_the_code
    Commented Jan 31, 2017 at 3:51

2 Answers 2

Reset to default
8
$\begingroup$

I can do it in just four instructions:

Person 1: up, left; person 2: down, right.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You are correct. Didn't think of that. $\endgroup$
    – ghosts_in_the_code
    Commented Jan 30, 2017 at 14:51
5
$\begingroup$

If I'm understanding the question correctly, then

Person 1: (North, East)
Person 2: (South, West)

should work.

At least one of them must move, and neither can loop back to the start.

Improve this answer
$\endgroup$
1
  • $\begingroup$ OK damn, you are right. Wish I thought of it. $\endgroup$
    – ghosts_in_the_code
    Commented Jan 30, 2017 at 14:51

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