Interactive Maze Solver

Question

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 code-golf, 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.

Answer 1

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)

Answer 2

Python3, 408 bytes:

E=enumerate;P=print
def f(m):
 q,d=[(x,y)for x,r in E(m)for y,s in E(r)if'S'==s],{}
 while q:
  x,y=q.pop(0)
  for M,X,Y in[('up',-1,0),('down',1,0),('left',0,-1),('right',0,1)]:
   if 0<=(j:=x+X)<len(m)and 0<=(k:=y+Y)<len(m[0])and(j,k)not in(V:=d.get((x,y),[])):
    C=m[j][k]
    if'X'==C:P(M+' solved');return
    elif'#'==C:P(M+' wall')
    else:print(M+' ok');q+=[(j,k)];d[(x,y)]=V+[(j,k)]
 P('no exit')

Try it online!