The arrow maze escape

14

2

Question

You have a 50 by 50 character array. Each cell has an arrow pointing in any one of four directions. No cell is empty. On entering a cell, you must exit it in the direction specified by the arrow. The arrow may also point in the same direction you came from, resulting in a dead end.

You may start from any cell on the outermost border of the maze and find a path that takes you in the maze, and causes you to exit at some other cell. Input will be given as an array containing <, >, ^ and v. Output will be a single digit (Boolean, integer or character, anything will do) as 0 (indicating that the task is impossible) or 1 (indicating that you have achieved the task).

Example (actual array will be bigger than this)

^ v < >
> < v <
v > v ^

Output will be

1
as you can enter from the < on the right, which will cause you to exit from the bottom v by the path "< v v"

The task is to write the shortest possible code that will receive the maze as input, and determine where there exists a path in it as specified in the rules and output a single digit 0 or 1

Outputing TRUE and FALSE instead of actual digits is also allowed.

ghosts_in_the_code

Posted 2015-10-31T05:23:50.153

Reputation: 2 907

6It would be nice to have some actual test cases to work with – Liam – 2015-10-31T06:44:07.553

Is the input a one dimensional array or a two dimensional? And can you only enter on the right by a < or can you also enter by a ^ ? – bobbel – 2015-10-31T08:54:49.473

@bobbel Input can be given as a 1 or a 2 dimensional array, whichever is required for a shorter code. Even arrows can be entered as 1 2 3 4 instead of < > ^ v if that can shorten the code. And yes, you can enter via the ^ also. – ghosts_in_the_code – 2015-10-31T10:29:56.957

@ LiamNoronha It's not that hard to randomly generate test cases. – ghosts_in_the_code – 2015-10-31T10:32:27.327

You mention the possible output in several parts of the challenge, but I'm still not quite sure what exactly is permitted. My answer currently prints 1 if there exists a path and 0 if not. Could it also print 0 if there exists a path and 1 if not? – Dennis – 2015-10-31T15:13:07.183

@Dennis No, it should print TRUE or 1 if there exists a path. – ghosts_in_the_code – 2015-10-31T15:25:36.277

Oh, I may return the Boolean, integer or character 0. Now I get it. – Dennis – 2015-10-31T15:27:11.433

1The likelihood that a random, 50 by 50, array will not have a solution is just about 0. It would be better if you required that the solution have at least a certain number of steps or that the user specified the solution path. – DavidC – 2015-10-31T16:44:05.483

Could I enter the bottom through a v? – DanTheMan – 2015-10-31T22:15:36.627

@DanTheMan Nope. – ghosts_in_the_code – 2015-11-01T13:26:06.763

1This should have been called "An arrow escape"... Still pondering a solution. – beaker – 2015-11-03T20:09:33.713

Answers

6

CJam, 89 81 bytes

q~"><v^":A2/{f{\*}z}/sA[1W52-52]er:T,,{[52md]51f%0e=1=},:E{[2704{__T=+}*]\-E&},,g

Try it online in the CJam interpreter.

How it works

q~        e# Read and evaluate all input. This pushes an array of strings.
"><v^":A  e# Push that string and save it in A.
2/        e# Split it into ["><" "v^"].
{         e# For each chunk:
  f{      e#   For each input string, push the string and the chunk; then:
    \*    e#     Join the chunk, using the string as separator.
  }       e#
  z       e#   Transpose rows and columns.
}/        e#
s         e# Flatten the resulting array of strings.
A         e# Push "><v^".
[1W52-52] e# Push [1 -1 52 -52].
er        e# Perform transliteration.
:T        e# Save the result in T.
,,        e# Push [0 ... 2703].
{         e# Filter; for each integer I in [0 ... 2703]:
  [52md]  e#   Push [I/52 I%52].
  51f%    e#   Take both integers modulo 51 to map 51 to 0.
  0e=     e#   Count the number of resulting zeroes.
  1=      e#   Check if the count is 1.
},        e# If it is, keep I.
:E        e# Save the filtered array in E.
{         e# For each integer I in E:
  [2704{  e#   Do 2704 times:
    __    e#     Push two copies of the integer on the stack.
    T=    e#     Select the corresponding element from T.
    +     e#     Add it to the first copy.
  }*]     e#   Collect all results in an array.
  \-      e#   Remove I from that array.
  E&      e#   Intersect with E.
},        e# If the intersection is non-empty, keep the integer.
,g        e# Push the sign of the length of the filtered array.

Dennis

Posted 2015-10-31T05:23:50.153

Reputation: 196 637