# Solve a reverse arrow maze

This is an "arrow maze":

  v      <
>     v
>  ^
>         v
^ <       *


The * marks the spot where you will finish. Your goal is to find where the maze starts (hence, reverse maze). In this case, it's the first > on the second line.

  v------<
S-+---v  |
|   >--^
>-+-------v
^ <       *


Note that all arrows must be used. Also note that you can assume the lines will be padded with spaces to equal length.

Your program must input the maze in any reasonable way (stdin, from a file, message box, etc.), however the maze must be completely intact. For example, you can't input the lines separated by commas; the input must be exactly the maze.

You must output the start of the maze in any reasonable way. For example, you could

• output the coordinates of the start
• output the entire maze with the start arrow replaced with an S
• output the entire maze with all arrows except the start arrow removed (whitespace intact!)
• etc.

As long as you can tell by your output which arrow is the start arrow, then it's okay. For example, an output of

"0"
"2"


is alright, regardless of the newlines and quotes, because you can still tell where the start was.

This is , so the shortest code in bytes will win.

• Is it reasonable to assume that each arrow has only one other arrow pointing to it? There isn't going to be an instance where there could be multiple starting points is there? Feb 20 '14 at 13:34
• Is "start of the maze" an arrow from which each other arrow is visited once? In other words danny's question + assumption there are no loops. Feb 20 '14 at 13:36
• "you can't input the lines separated by commas; the input must be exactly the maze." This seems like an unnecessary restriction, since "exactly the maze" is already de facto delimited by newlines between the rows. Why prioritize one delimiter over another? Feb 20 '14 at 14:58
• @Doorknob That's reasonable, since one could theoretically encode an entire compressed solution in the "delimiters". However, I do suspect that the restriction introduces a certain linguistic bias against certain languages. What if the rule were "Input rows may be delimited by any one character of your choice. All rows must be delimited by the same character."? I think the upper bound is useful because it establishes a domain within which your program must work. Feb 20 '14 at 16:20
• @Peter That just means that, for example, in >v^ the > is pointing to the v, not the ^. I'll edit more stuff in when I get back home to a computer today.
– Doorknob
Feb 20 '14 at 18:02

# GolfScript, 55 bytes

:&,,{&=42>},.{.&="><^v"?[1-1&n?~.~)]=:d;{d+.&=32=}do}%-


Online demo

Assumes that all input lines are padded with spaces to the same length and separated by newlines. Outputs the byte offset of the starting arrow from the start of the input string (e.g. 12 for the example maze in the challenge).

Specifically, this program finds the byte offsets of all arrows that have no other arrow pointing to them (assuming that all arrows do point to an arrow or a goal; strange behavior may occur if this is not true). By default, if there are several such arrows (which, per spec, should not be possible in valid input), their offsets will simply be concatenated in the output. If you want, you can append n* to the program to have them separated by newlines instead.

De-golfed version with comments:

:&                     # save a copy of the input string in the variable "&"
,, { &= 42> },         # make a list of the byte offsets of all arrows
.                      # duplicate the list and apply the following loop to it:
{
.                    # make a copy of the original offset...
&=                   # ...and get the corresponding character in the input
"><^v" ?             # map the arrow character to integers 0 to 3, and...
[ 1 -1 &n?~ .~) ]=   # ...map these to +1, -1, -len-1 or +len+1, where len is the...
:d;                  # ...length of the first input line, and save result as "d"
{ d+ . &= 32= } do   # add d to the byte offset until another non-space is found
} %
-                      # subtract the resulting list of target offsets from the
# original list of arrow offsets; this should leave exactly
# one offset, which is left on the stack for output

• You can save 3 chars if you inline w. Feb 21 '14 at 14:19
• @Howard: Huh, so I can. Thanks! Had to rename z to & to avoid needing an extra space, though. OTOH, ?~.~) makes a pretty nice smiley. :-) Feb 21 '14 at 15:38

n/:g,,{:&g=:r,,{&1$r='^v<>*'?70429 3base 2/=++}/}%{,4=},.{2<}%:&\{2/~\{[~2$~@+(@@+(\]&1$?)!}do\;}%^  Output is in the form [[x y]] where the co-ordinates are both 0-based. Online demo Processing is in two phases: the first phase turns the maze into an array of [x y dx dy] tuples; the second phase maps each arrow / asterisk to the arrow / asterisk it points to. (Asterisks are considered to point to themselves). By the definition of the problem, there is exactly one arrow which isn't in the result of this map, and that is the solution. • I was just pasting my answer while you posted this. We had the same idea, but you managed to golf it successfully. Nice one! Feb 20 '14 at 16:59 • @PeterTaylor I can't see that it handles the point through case correctly which is mentioned in the comments. Feb 20 '14 at 17:14 • @Howard, I have no idea what that case is. Will ask for clarification. Feb 20 '14 at 17:17 • Would you kindly post an example of your input and output? Feb 20 '14 at 18:29 • @DavidCarraher, see the online demo. ;'STUFF' simulates supplying STUFF via stdin. Feb 20 '14 at 19:21 # Mathematica 491 323 Ungolfed with comments The procedure begins from the finish ("*"), finds the arrow that points to it, and so forth until reaching the start. The function, f[maze]. (* positions of the arrowheads *) aHeads[a_]:=Position[m,#]&/@{"^","v",">","<"} (* position of the final labyrinth exit*) final[a_]:=Position[a,"*"][[1]]; (* find arrowheads that point to the current location at {r,c} *) aboveMe[{r_,c_},a_]:=Cases[aHeads[a][[2]],{r1_,c}/;r1<r] belowMe[{r_,c_},a_]:=Cases[aHeads[a][[1]],{r1_,c}/;r1>r] rightOfMe[{r_,c_},a_]:=Cases[aHeads[a][[4]],{r,c1_}/;c1>c] leftOfMe[{r_,c_},a_]:=Cases[aHeads[a][[3]],{r,c1_}/;c1<c] (*find the precursor arrowhead*) precursor[{loc_,a_,list_:{}}]:= (* end the search when the precursor has already been traversed or when there is no precursor *) Which[MemberQ[list,loc],list, loc=={},list,True, (* otherwise find the next precursor *)  precursor[{Flatten[{aboveMe[loc,a],belowMe[loc,a],rightOfMe[loc,a],leftOfMe[loc,a]},2],a, Prepend[list,loc]}]] (* return the path through the maze from start to finish *) f[maze_]:= precursor[{final[maze[[1]]],maze[[1]]}]  Golfed f@z_:=Module[{p,h,m=z[[1]]},h@a_:=Position[a,#]&/@{"^","v",">","<","*"}; p[{v_,a_,j_:{}}]:=Module[{r,c,x=Cases},{r,c}=v; Which[MemberQ[j,v],j,v=={},j,True, p[{Flatten[{x[h[a][[2]],{r1_,c}/;r1<r],x[h[a][[1]],{r1_,c}/;r1>r], x[h[a][[4]],{r,c1_}/;c1>c],x[h[a][[3]],{r,c1_}/;c1<c]},2],a,Prepend[j,v]}]]]; p[{Position[m,"*"][[1]],m}]]  ## Example The maze. Each ordered pair contains the row and column of a cell. E.g. {2, 3} denotes the cell at row 2, column 3. maze=Grid[Normal@ SparseArray[{{5, 5} -> "*",{1, 2} -> "v", {1, 5} -> "<",{2, 1} -> ">", {2, 3} -> "v",{3, 3} -> ">", {3, 5} -> "^",{4, 1} -> ">", {4, 5} -> "v",{5, 1} -> "^", {5, 2} -> "<",{_, _} -> " "}]]  Input f[maze]  Output: The path from start to finish. {{2, 1}, {2, 3}, {3, 3}, {3, 5}, {1, 5}, {1, 2}, {5, 2}, {5, 1}, {4, 1}, {4, 5}, {5, 5}} • Your input format is wrong - "the input must be exactly the maze". – Doorknob Feb 20 '14 at 16:05 • The input is now the maze itself. Feb 20 '14 at 17:00 • I haven't followed the code, but the way you solved the "the input is now the maze" thing is hilarious! +1 ...the number of believers in "STDIN is universal" is astounding. Feb 21 '14 at 4:57 • I'm glad you appreciated the solution to the input problem. Feb 21 '14 at 5:48 I think I found a good way to solve this, but I happened to suck at golfing it. I guess this could be WAY shorter, so I'm going to explain my idea so others can use it if they find it good. If every arrow must be used, then all the arrows will be pointed by another arrow, except one, that is our solution. This means we don't actually have to play the maze backwards, but, starting from the upper-left one, we just need to check the nearest pointable arrow for each one. This is a real painsaver for larger mazes (since you don't have to check all four directions, but just one). Here's my solution: # PHP, 622 bytes $h=fopen("a.txt","r");$b=0;while(($z=fgets($h))!==false){$l[$b]=str_split($z,1);$b++;}$v=array("^","<","v",">");$s=array();for($i=0;$i<count($l);$i++){for($j=0;$j<count($l[0]);$j++){if(in_array($l[$i][$j],$v)){switch($l[$i][$j]){case"^":$c=$i-1;while($l[$c][$j]==" ")$c--;$s[]=$c.",".$j;break;case"v":$c=$i+1;while($l[$c][$j]==" ")$c++;$s[]=$c.",".$j;break;case"<":$c=$j-1;while($l[$i][$c]==" ")$c--;$s[]=$i.",".$c;break;case">":$c=$j+1;while($l[$i][$c]==" ")$c++;$s[]=$i.",".$c;break;}}}}for($i=0;$i<count($l);$i++){for($j=0;$j<count($l[0]);$j++){if(in_array($l[$i][$j],$v)){if(!in_array($i.",".$j,$s)){echo$i.",".$j;}}}}  Ungolfed: $h=fopen("a.txt","r");
$b=0; while(($z=fgets($h))!==false) {$l[$b]=str_split($z,1);
$b++; } //Input ends here$v = array("^","<","v",">");
$s = array(); //Here i check every arrow, and save every pointed one in$s
for($i=0;$i<count($l);$i++){
for($j=0;$j<count($l[0]);$j++){
if(in_array($l[$i][$j],$v)){
switch($l[$i][$j]) { case "^":$c=$i-1; while ($l[$c][$j]==" ")
$c--;$s[]=$c.",".$j;
break;
case "v":
$c=$i+1;
while ($l[$c][$j]==" ")$c++;
$s[]=$c.",".$j; break; case "<":$c=$j-1; while ($l[$i][$c]==" ")
$c--;$s[]=$i.",".$c;
break;
case">":
$c=$j+1;
while ($l[$i][$c]==" ")$c++;
$s[]=$i.",".$c; break; } } } } //I check if the arrow is in$s. If not, we have a solution.
for($i=0;$i<count($l);$i++){
for($j=0;$j<count($l[0]);$j++){
if (in_array($l[$i][$j],$v)){
if (!in_array($i.",".$j,$s)){ echo$i.",".$j; } } } }  PHP - 492 bytes $r=split("\n",$m);$h=count($r);foreach($r as &$k)$k=str_split($k);$l=count($r[0]);$e=strpos($m,"*")+1-$h;$a=$x=$e%$l;$b=$y=floor(($e-$x)/$l);do{$c=0;for(;--$a>=0;){if($r[$b][$a]==">"){$x=$a;$c++;}if($r[$b][$a]!=" ")break;}$a=$x;for(;--$b>=0;){if($r[$b][$a]=="v"){$y=$b;$c++;}if($r[$b][$a]!=" ")break;}$b=$y;for(;++$a<$l;){if($r[$b][$a]=="<"){$x=$a;$c++;}if($r[$b][$a]!=" ")break;}$a=$x;for(;++$b<$h;){if($r[$b][$a]=="^"){$y=$b;$c++;}if($r[$b][$a]!=" ")break;}$b=$y;}while($c>0);echo "$x-$y";  This solution supposes that the map can be found in local variable $m. The shortest method I have for passing that is via $_GET: $m=$_GET['m']; at 14 bytes. An ungolfed version with map in variable is provided below for clarity of reading. $m=<<<EOT
v      <
>     v
>  ^
>         v
^ <       *
EOT;

$r=split("\n",$m);
$h=count($r);
foreach($r as &$k)
$k=str_split($k);
$l=count($r[0]);

$e=strpos($m,"*")+1-$h;$a=$x=$e%$l;$b=$y=floor(($e-$x)/$l);
do{
$c=0; for(;--$a>=0;)
{
if($r[$b][$a]==">"){$x=$a;$c++;}
if($r[$b][$a]!=" ")break; }$a=$x; for(;--$b>=0;)
{
if($r[$b][$a]=="v") {$y=$b;$c++;
}
if($r[$b][$a]!=" ")break; }$b=$y; for(;++$a<$l;) { if($r[$b][$a]=="<")
{
$x=$a;
$c++; } if($r[$b][$a]!=" ")break;
}
$a=$x;
for(;++$b<$h;)
{
if($r[$b][$a]=="^") {$y=$b;$c++;
}
if($r[$b][$a]!=" ")break; }$b=$y; }while($c>0);
echo "$x-$y";


# K, 281277 258

{{$[&/x in*:'{{~"*"=x 1}{(s;k . s;k;s:*1_w@&(k ./:w:{{x@&x in y}[(*:'{(x[1]@x 0;x 1)}\[x;(z;y)]);i]}[(h!b,b,a,a:#k:x 2)m;(h!(0 1+;0 -1+;1 0+;-1 0+))m:x 1;x 0])in"*",h:"><v^")}\(x;y;z;x)}[*x;y .*x;y];*x;.z.s[1_x]y]}[i@&~(x ./:i::,/(!#x),/:\:!b::#*x)in" *";x]}  Here's an earlier, ungolfed version solve:{[x] //j - indices of all possible starting points //i - every index j::i@&~(x ./:i::,/(!a:#x),/:\:!b:#*x) in " *"; h::">v<^"; //d - dictionary mapping each directional character to // increment/decerement it needs to apply to the x/y axis d::h!((::;1+);(1+;::);(::;-1+);(-1+;::)); //e - dictionary mapping each directional character to // the maximum number of moves it should make in a // given direction e::h!b,a,b,a; //f - function to produce the indices of each point that is // passed once we move in a certain direction from a // certain index f::{{x@&x in y}[(last'{(x[0];x[0]@'x 1)}\[x;(y;z)]);i]}; //g - function that, given a starting and a direction, // moves in that direction until hitting another directional // character. It then moves in the new direction etc. until // it reaches the end point -- * g::{[x;y;z] {[x] q:x 0;m:x 1; k:x 2; w:f[e m;d m;q]; s:*1_w@&(k ./:w)in h,"*"; m:k . s; (s;m;k;s)}\[{~"*"=x 1};(x;y;z;x)]}; // recursive function that starts at the first possible starting point // and plots its way to the end. If all other potential starting points // have been touched in this path, then this is the correct starting point. // else, recursively call the function with the next possible starting point :{$[min "b"\$j in last'g[*x;y . *x;y];*x;.z.s[1_x;y]]}[j;x]
}


Returns the starting point as x y with 0 based indices.

k)maze
"  v      < "
">     v    "
"      >  ^ "
">         v"
"^ <       *"
k)solve maze
1 0


## Python 422

with open("m.txt","r") as f:m=f.read().split("\n")
p=[(v.find("*"),p) for p,v in enumerate(m) if "*" in v][0]
g=[]
def f(a):
x,y=b,c=a
for p,i in enumerate((lambda x:[l[x] for l in m])(x)):
if i in "^>v<" and((p<y and i=="v")or(p>y and i=="^")):return b,p
for p,i in enumerate(m[y]):
if i in "^>v<" and((p<x and i==">")or(p>x and i=="<")):return p,c
while True:
z=f(p)
if z in g:break
else:g.append(z);p=z
print p


The input is in a file called m.txt. The output is (x, y) but if you change the last print statement to print g, the output will be a list like [(x, y), (x, y), ...]` with all the steps to get from the end to the start.