14
\$\begingroup\$

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.

\$\endgroup\$
  • 6
    \$\begingroup\$ It would be nice to have some actual test cases to work with \$\endgroup\$ – Liam Oct 31 '15 at 6:44
  • \$\begingroup\$ 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 ^ ? \$\endgroup\$ – bobbel Oct 31 '15 at 8:54
  • \$\begingroup\$ @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. \$\endgroup\$ – ghosts_in_the_code Oct 31 '15 at 10:29
  • 1
    \$\begingroup\$ The 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. \$\endgroup\$ – DavidC Oct 31 '15 at 16:44
  • 1
    \$\begingroup\$ This should have been called "An arrow escape"... Still pondering a solution. \$\endgroup\$ – beaker Nov 3 '15 at 20:09
6
\$\begingroup\$

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.
\$\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.