Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Danny Feb 20 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. –  shiona Feb 20 at 13:36
3  
"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? –  Jonathan Van Matre Feb 20 at 14:58
1  
@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. –  Jonathan Van Matre Feb 20 at 16:20
1  
@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 at 18:02

7 Answers 7

up vote 4 down vote accepted

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
share|improve this answer
1  
You can save 3 chars if you inline w. –  Howard Feb 21 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. :-) –  Ilmari Karonen Feb 21 at 15:38

GolfScript (101 100 bytes)

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.

share|improve this answer
    
I was just pasting my answer while you posted this. We had the same idea, but you managed to golf it successfully. Nice one! –  Vereos Feb 20 at 16:59
    
@PeterTaylor I can't see that it handles the point through case correctly which is mentioned in the comments. –  Howard Feb 20 at 17:14
    
@Howard, I have no idea what that case is. Will ask for clarification. –  Peter Taylor Feb 20 at 17:17
    
Would you kindly post an example of your input and output? –  David Carraher Feb 20 at 18:29
    
@DavidCarraher, see the online demo. ;'STUFF' simulates supplying STUFF via stdin. –  Peter Taylor Feb 20 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} -> "<",{_, _} -> " "}]]

maze


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}}

share|improve this answer
    
Your input format is wrong - "the input must be exactly the maze". –  Doorknob Feb 20 at 16:05
    
The input is now the maze itself. –  David Carraher Feb 20 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. –  belisarius Feb 21 at 4:57
    
I'm glad you appreciated the solution to the input problem. –  David Carraher Feb 21 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;
            }
        }
    }
}
share|improve this answer

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";
share|improve this answer

K, 281 277 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
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.