Interactive Maze Solver

13

4

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.

Maltysen

Posted 2019-04-25T23:18:15.090

Reputation: 25 023

I was writing a comment about how it would be nice if this could use a black-box function instead of I/O for navigating the maze, but then I realized that not only would that black-box function need to be implemented for every maze for every language that tries to use it, but it would need to be implemented statefully... so interactivity being the only option is probably best. – Unrelated String – 2019-04-25T23:48:50.060

1It’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. – Nick Kennedy – 2019-04-26T06:26:24.997

3Do we get a solved when outputting no exit? If so please state so in the rules, not only in the test cases! – wastl – 2019-04-26T09:50:15.413

Oops.. deleted my wrong comment, so here again: is there a maximum size for the maze, of can it be infinitely long. Or to be more concrete: can I create a matrix variable with pre-defined dimensions if my language isn't able to dynamically change the dimensions along the way? – Kevin Cruijssen – 2019-04-26T10:47:36.670

1"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? – Kevin Cruijssen – 2019-04-26T19:09:17.517

1

start="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)?
    • – Kevin Cruijssen – 2019-04-26T19:10:06.193

    @KevinCruijssen I think the sequence up (ok); up (wall); left (wall); down (ok); is invalid. If you go back where you came from before all other directions were tested, you cannot enforce the penultimate rule (your program is not allowed to move in the same direction from the same square twice). – Arnauld – 2019-04-27T06:00:18.857

    @Arnauld Hmm, in that case my answer is invalid as I feared it might be after I posted the comments above, since I travel in a random direction which isn't the same as the previous.. :( If what you say is correct, and both my comments above are invalid, it means you always have to check all directions in the priority order: not visited yet; visited already but not a wall; reverse move since no more paths are available. So we'll have to keep track of where we came from, where the walls are, and which cells we've already visited if I understand correctly? Am I forgetting something? – Kevin Cruijssen – 2019-04-27T08:21:22.267

    1@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). – Arnauld – 2019-04-27T08:44:37.593

    @Arnauld Ah, yeah, that's a better approach. :) I'm gonna wait for OP to confirm what we've concluded before I change anyway, so will leave things as they are for now. Apart from what I sketched in my two comments above, my current program works as intended and will be able to reach either the state from input solved or output no exit. It's not the most efficient however. ;p As mentioned in my answer, I suck at matrix/path-finding challenges.. Even though they're usually great challenges. – Kevin Cruijssen – 2019-04-27T09:06:09.900

    @KevinCruijssen yeah, Arnauld's interpretation is correct. You have to dfs fully into all the other directions before backtracking out. Also, the maze is finite but could be arbitrarily large. – Maltysen – 2019-04-27T12:43:31.343

    @Maltysen Was afraid you might say that. Will delete my answer and fix if I have some time. Although it will probably require a new approach from scratch to fix the arbitrarily large size, using ArrayLists instead of fixed-size arrays and adding a leading/trailing columns to each row in a loop.. So not sure if it will be undeleted anytime soon, if at all. Ah well. Regardless, nice challenge. Even if my answer is invalid, I had fun (and slight frustration for some parts) when making it. ;) – Kevin Cruijssen – 2019-04-27T12:50:39.570

    Can the maximum maze size be my language's integer datatype's maximum? – Embodiment of Ignorance – 2019-04-28T03:37:58.857

    @EmbodimentofIgnorance yeah, sure. – Maltysen – 2019-04-28T16:54:58.293

    Answers

    7

    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)

    Arnauld

    Posted 2019-04-25T23:18:15.090

    Reputation: 111 334

    Asked: 2019-04-25T23:18:15.090

    Viewed: 393 times

    Active: 2019-04-29T14:07:59.250