5
$\begingroup$

A former colleague and a friend of his have gotten themselves lost in a storage room in some abandoned building, so having nothing better to do you head out to try and rescue them. As you reach the storage room in question, you notice a small map scribbled on the wall, which looks like this:

Maze Map

Unfortunately, it seems the two of them didn't see the map, as they can only tell you that they're sitting at two different T-junctions

Your niece's boyfriend suggested throwing pumpkins at them to get their location, but you have a much saner plan: You will call out to the two lost ones and tell them to go down a specific path (either the right, left, or middle path from the junction), until they reach another intersection. Based on how long they walk, you will know how far each individual travels. You won't know whether or where they turn while they travel

You can only give one direction at a time, which both individuals will follow. You can't give directions while they are between intersections, and the directions can only state which of the three paths they should go down (i.e. no special conditions based on what they did previously). They will tell you if they end up at the same intersection or if either one is at a four-way intersection. You must get both of them to the exit at the bottom of the map

What instructions can you give to guarantee that both of the two lost in the maze can make it to the exit?

$\endgroup$
9
  • $\begingroup$ Are directions absolute (NSEW) or relative (turn left/right, go forward/backward)? $\endgroup$
    – fljx
    Jun 29, 2023 at 20:22
  • $\begingroup$ @fljx Relative to the individual $\endgroup$ Jun 29, 2023 at 20:24
  • 1
    $\begingroup$ Do we know which way they are facing initially? (So that we know whether their options are left/forward/back vs left/right/back vs right/forward/back). And are we allowed to give them directions that will have one of them walking into a wall (e.g. where one can turn left but the other can't)? $\endgroup$
    – fljx
    Jun 29, 2023 at 21:13
  • 1
    $\begingroup$ Can a direction be relative to the wall at a T junction? (so the first instruction might be "take the middle path, the one opposite the wall where you currently are")? Can it be contingent on something else ("If you can turn left, do so; otherwise, go right")? What happens if it's not possible to follow the direction (e.g. you say "go straight" and they're facing a wall)? $\endgroup$
    – Deusovi
    Jun 29, 2023 at 21:13
  • 2
    $\begingroup$ This still doesn't answer the question of what happens if they can't follow a direction. $\endgroup$
    – Deusovi
    Jun 30, 2023 at 0:56

2 Answers 2

2
$\begingroup$

Employ the following pattern:

LLMMRMMRR
The reason is: It's the pattern to get from intersection #2 (at (10,4) on the map) facing north, to the exit. This pattern also turns people standing in other places to eventually hit place 2 facing north in the initial phase. So, each implementation would let a kid who ended up there facing a wall to directly get to the exit.
However, after 8 or so repeats a person could get stuck in the lower left loop, facing east. So use "MRMRR" to get them off and stop bothering. This seems to work regardless of whether ordering any of those dumbheads to go into a wall makes them turn towards that wall or not.

$\endgroup$
2
$\begingroup$

There are almost certainly quicker ways to get them both out, but the following is the simplest I could find.
This method doesn't care if the two meet up or encounter a four-way intersection, and ignores the distances except for a few special cases to avoid endless loops:

For reference, I've labelled the intersections in red, and the distances between them in blue:

enter image description here

Start by getting them to both repeatedly go Left, Left, Right.

This is always relative to their direction of approach and means take the leftmost or rightmost path. At a crossroads, left and right are 90-degree turns (we never use straight-on). At a T-junction there are always two exits that do not involve a U-turn; they are the left and right paths, even if one of them is physically straight on. This means directions can always be followed, at any intersection.

Note the distances, but don't do anything unless you hear one of the following patterns from either of them:

11, 11, 11 :

  • Someone has just gone round the loop from 16 three times. (The 11 distance here is not unique, but this is the only place you can hit three in a row on an L,L,R pattern.)
  • Immediately go Right, Left, Right and that person will be out of the maze.
  • Now go back to the L,L,R pattern and continue for the other person.

    1, 15, 1 or 1, 15, 15, 1 :
  • Someone has just gone round the loop from 4 once or twice and then down to 6.
  • Immediately go Left, Left, Left, Left and that person will be out of the maze.
  • Now go back to the L,L,R pattern and continue for the other person.

  • How this works:

    The L,L,R pattern takes us on one of several paths through the maze. Most of them eventually get to 21 with the correct turn to exit.
    A few get stuck in endless loops through 4 or 16, and need the special cases above to escape the loop.

    For each possible starting position and orientation, following the L,L,R pattern takes you through the following locations (just listing the location before the first L for brevity):
    All of the following get to the exit:

  • 21N - 14N - 12N - 2E - 5S - 3E - 7S - 1N - 3N - 5W - 9E - 12W - 14E - 13W - 19E - 16S - 9N - 5N - 2W - 1S - 7W - 13E - 14S - 21E - 20W - 17N - 18E - 8E - 4E - 6S - 10W - 18N - 17E - 11N - 21W - Out
  • 16N - 19N - 13N - 7E - 3S - 1E - 2N - 12S - 9S - 16W - Out
  • 15N - 11W - 17W - 20E - 10E - 6W - 15S - Out

    The following hit an endless loop from 4 or 16 but can all be identified by a unique pattern of distances:
  • 4N - 8S - 4N
  • 4W - 8N - 18S - 10N - 20S - 21S - 11E - 15E - 6N - 4W
  • 16E - 19W - 16E

  • $\endgroup$
    7
    • $\begingroup$ There's also a pattern 7-3-11 indicating a loop 1-2-3-1. Please update. $\endgroup$
      – Vesper
      Jul 5, 2023 at 12:48
    • $\begingroup$ @Vesper a 1-2-3-1-... repeating loop is all left turns. A left, left, right pattern does not get stuck there. $\endgroup$
      – fljx
      Jul 5, 2023 at 13:57
    • $\begingroup$ Oh, the "relative to the wall" was just a suggestion, I first read that as a condition. But there is still a loop with LLR pattern, since OP said if there's a wall on the right, ordering right won't let the person move (reported 0), same for left. If the person is at 9 facing east (arrived from 8), LLR following would make him do: 6-8-12-13-wall-11-10-wall-15-9-8-wall-6-wall-4-4 (walked 12)-6-wall-8-wall-9 (looped with same facing). I have asked whether ordering to wallbash would change facing, the loop is calculated on expectation of a yes. If not, checking further (IIRC seen another) $\endgroup$
      – Vesper
      Jul 5, 2023 at 14:21
    • $\begingroup$ Yep, if ordering to wallbash does not alter facing, there is a loop when a person arrives to 5 from 1, any phase. R would not change a thing, LR would make him go 7-wall-2-1-wall-5 (in phase), LLR would make him go 7-2-3-1-wall-5 (same phase). $\endgroup$
      – Vesper
      Jul 5, 2023 at 14:33
    • 1
      $\begingroup$ @justhalf I've edited to clarify the directions. That set of three consecutive 11's happens when someone approaches 16 heading west when they are about to make a right turn. They turn right (north), go round the loop back to 16 heading east. Then they turn left (north) and go round the loop back to 16 heading east. Then they turn left and go round again, giving you the three 11's. For completeness, they then turn right (south) to 19. Left from there goes to 21, and the next left takes you back to 16 heading west ready to turn right and repeat the whole loop. $\endgroup$
      – fljx
      Jul 5, 2023 at 17:09

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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