13
\$\begingroup\$

Bob got kidnapped and is stuck in a maze. Your job is to help him find a way out. But since it is a very dark and scary maze, he can't see anything. He can only feel walls when he runs in to it, and knows when he has found the exit, but doesn't know anything more that.

Since he has to run your program by memory, it has to be as short as possible.

Note: I took this problem from http://acmgnyr.org/year2016/problems.shtml, but adapted it slightly, and wrote the judge program/test cases myself.

Specification

  • This is an interactive problem, so you program will output moves to stdout, and take in responses from stdin.
  • Your program can output one of the moves right, left, down, up.
  • It will then get as input one of the following:
    • wall - this means that Bob has hit a wall. Bob will stay in the same place.
    • solved - Bob has found the exit! Your program should now also exit without printing anything else.
    • ok - Bob was able to move in the given direction.
  • If the maze has no exit, your program should output no exit to let Bob know that he should give up. Your program should then exit without printing anything else.
  • Since Bob is in a hurry to get out, your program should not make any extraneous moves. In other words, your program is not allowed to move in the same direction from the same square twice.
  • This is , so shortest program wins!

Examples

In the following examples, S is the starting square, X is the exit, # is a wall, and spaces are valid squares. Since there is no single correct answer, these are just example runs of a solution. Also note that the drawings of the maze are just there for you to see, and your program will not get them as input.

########
#S     #
###### #
     # #
     #X#

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              solved

#####
# S #
#####

right
              ok
right
              wall
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              wall
right
              ok
no exit
              solved

###############################
#S                            #
##############       ###      #
             #       #X#      #
             #                #
             ##################

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              wall
down
              ok
left
              wall
down
              ok
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              solved

Checker Program

  • I have written a solution checker in Python. You can find it at https://gist.github.com/Maltysen/f0186019b3aa3812d812f8bb984fee19.
  • Run it like python mazechecker.py ./mazesolver.
  • It will test your program on all the mazes in a folder called mazes.
  • The mazes are in separate files in the same format from above.
  • It checks all the conditions listed above, and notifies you if your solution violates any.
  • You can have it print additional diagnostic info with python mazechecker.py -d ./mazesolver.
  • You can find a zipped mazes folder here. You can also add your own to it if you want.
\$\endgroup\$
  • 1
    \$\begingroup\$ It’s probably worth explicitly stating that the problem was released under a CC-BY-NA-SA license, and so your remix is necessarily under the same licence. \$\endgroup\$ – Nick Kennedy Apr 26 at 6:26
  • 3
    \$\begingroup\$ Do we get a solved when outputting no exit? If so please state so in the rules, not only in the test cases! \$\endgroup\$ – wastl Apr 26 at 9:50
  • 1
    \$\begingroup\$ "your program is not allowed to move in the same direction from the same square twice." Two questions regarding this: 1. Let's say I'm at position x,y and go up, with respond wall, then right with again respond wall, may I then try up again, or are only left and down still available since I haven't moved from this square yet? \$\endgroup\$ – Kevin Cruijssen Apr 26 at 19:09
  • 1
    \$\begingroup\$ 2. Let's say I have this maze. With this flow: right (ok); right (ok); right (wall); up (ok); up (ok); up (wall); left (wall); down (ok); down (ok); down (ok); down (ok); down (wall); right (wall); up (ok); up (ok); Am I now again allowed to go up even though I already did from that specific square before (at the bold one)? \$\endgroup\$ – Kevin Cruijssen Apr 26 at 19:10
  • 1
    \$\begingroup\$ @KevinCruijssen I don't explicitly keep track of where I came from in my answer. Instead, I keep track of all directions that were processed on each square and I try unvisited squares first. When all unvisited squares have been tried, the only remaining legal move is where I came from (already visited, but not in this direction). \$\endgroup\$ – Arnauld Apr 27 at 8:44
7
\$\begingroup\$

JavaScript (ES6),  180  174 bytes

Uses prompt() to output the direction and retrieve the result.

_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])

Try it online! (with automated I/O)

Interactive snippet

WARNING: this code will display a prompt() dialog until 'solved' is entered or the function figures out that there's no exit at all.

(
_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])
)()

Commented

_ => (                      // anonymous function taking no argument
  g = p =>                  // g = recursive function taking the current position p = [x, y]
    [ ...'0123',            // i<4  : try to move on squares that haven't been visited yet
      ...'0123',            // 3<i<8: try to go back to where we initially came from
      ...'4'                // i=8  : if everything failed, there must be no exit
    ].some((d, i) =>        // for each direction d at index i:
      g[p] >> d & 1         //   if this direction was already tried at this position
      | i < 4 &             //   or i is less than 4 and
      g[P = [               //   the square at the new position P = [X, Y] with:
        p[0] + (d - 2) % 2, //     X = x + dx[d]
        p[1] + ~-d % 2      //     Y = y + dy[d]
      ]] > 0 ?              //   was already visited:
        0                   //     abort
      : (                   //   else:
        r = prompt(         //     output the direction:
          [ 'up',           //       0 = up
            'left',         //       1 = left
            'down',         //       2 = down
            'right',        //       3 = right
            'no exit'       //       4 = no exit
          ][                //
            g[p] |= 1 << d, //       mark this direction as used
            d               //       d = actual index of the string to output
          ]                 //     r = result of prompt()
        )                   //
      ) < 's' ?             //     if r = 'ok':
        g(P)                //       do a recursive call at the new position
      :                     //     else:
        r < 't'             //       yield true if r = 'solved' or false if r = 'wall'
    )                       // end of some()
)([0, 0])                   // initial call to g at (0, 0)
\$\endgroup\$

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.