To jest „labirynt strzałkowy”:

  v      < 
>     v    
      >  ^ 
>         v
^ <       *

Te *znaki w miejscu, gdzie można zakończyć. Twoim celem jest znalezienie miejsca, w którym zaczyna się labirynt (stąd labirynt odwrócony). W tym przypadku jest to pierwszy >w drugiej linii.

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

Pamiętaj, że należy użyć wszystkich strzałek. Pamiętaj również, że możesz założyć, że linie zostaną wypełnione spacjami do równej długości.

Twój program musi wprowadzić labirynt w dowolny rozsądny sposób (standardowe, z pliku, okna komunikatu itp.), Jednak labirynt musi być całkowicie nienaruszony. Na przykład nie można wprowadzić wierszy oddzielonych przecinkami; wejście musi być dokładnie labiryntem.

Musisz wyprowadzić początek labiryntu w dowolny rozsądny sposób. Na przykład możesz

• wyprowadzić współrzędne początku
• wypisz cały labirynt ze strzałką początkową zastąpioną przez S
• wypisuje cały labirynt ze usuniętymi wszystkimi strzałkami oprócz strzałki początkowej (białe znaki nienaruszone!)
• itp.

Tak długo, jak na podstawie danych wyjściowych można stwierdzić, która strzałka jest strzałką początkową, jest w porządku. Na przykład wyjście

"0"
"2"

jest w porządku, bez względu na nowe wiersze i cytaty, ponieważ nadal możesz powiedzieć, gdzie był początek.

To jest code-golf , więc wygra najkrótszy kod w bajtach.

GolfScript, 55 bajtów

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

Demo online

Zakłada, że ​​wszystkie linie wejściowe są wypełnione spacjami na tej samej długości i oddzielone znakami nowej linii. Zwraca bajtowe przesunięcie początkowej strzałki od początku ciągu wejściowego (np. 12Dla przykładowego labiryntu w wyzwaniu).

W szczególności ten program znajduje przesunięcia bajtów wszystkich strzałek, do których nie prowadzi żadna inna strzałka (zakładając, że wszystkie strzałki wskazują na strzałkę lub cel; może wystąpić dziwne zachowanie, jeśli nie jest to prawda). Domyślnie, jeśli istnieje kilka takich strzałek (które zgodnie ze specyfikacją nie powinny być możliwe przy prawidłowym wprowadzeniu), ich przesunięcia zostaną po prostu połączone w danych wyjściowych. Jeśli chcesz, możesz dołączyćn* do programu, aby zamiast tego były oddzielone znakami nowej linii.

Wersja bez golfa z komentarzami:

:&                     # 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

GolfScript ( 101 100 bajtów)

n/:g,,{:&g=:r,,{&1$r='^v<>*'?70429 3base 2/=++}/}%{,4=},.{2<}%:&\{2/~\{[~2$~@+(@@+(\]&1$?)!}do\;}%^`

Dane wyjściowe mają postać, w [[x y]]której współrzędne są oparte na 0.

Demo online

Przetwarzanie odbywa się w dwóch fazach: pierwsza faza zamienia labirynt w szereg [x y dx dy]krotek; druga faza odwzorowuje każdą strzałkę / gwiazdkę na strzałkę / gwiazdkę, na którą wskazuje. (Uważa się, że gwiazdki wskazują na siebie). Według definicji problemu istnieje dokładnie jedna strzałka, która nie jest wynikiem tej mapy, i to jest rozwiązanie.

Mathematica 491 323

Niegolfowany z komentarzami

Procedura rozpoczyna się od końca („*”), znajduje strzałkę do niej wskazującą i tak dalej, aż do początku.

Funkcja f [labirynt].

(* 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]]}]

Grał w golfa

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

Przykład

Labirynt. Każda uporządkowana para zawiera wiersz i kolumnę komórki. Np. {2, 3} oznacza komórkę w wierszu 2, kolumnie 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} -> "<",{_, _} -> " "}]]

Wejście

f[maze]

Wyjście : ścieżka od początku do końca.

{{2, 1}, {2, 3}, {3, 3}, {3, 5}, {1, 5}, {1, 2}, {5, 2}, {5, 1}, { 4, 1}, {4, 5}, {5, 5}}

Wydaje mi się, że znalazłem dobry sposób na rozwiązanie tego problemu, ale zdarzyło mi się ssać golfa. Myślę, że może to być DROGA krótsza, więc wyjaśnię mój pomysł, aby inni mogli go wykorzystać, jeśli uznają go za dobry.

Jeśli każda strzała musi być użyta, wszystkie strzałki będą wskazywane przez inną strzałkę, z wyjątkiem jednej, to jest nasze rozwiązanie.

Oznacza to, że tak naprawdę nie musimy grać w labirynt do tyłu, ale zaczynając od lewego górnego rogu, musimy po prostu sprawdzić najbliższą wskazaną strzałkę dla każdego z nich. To prawdziwy ból dla większych labiryntów (ponieważ nie musisz sprawdzać wszystkich czterech kierunków, ale tylko jeden).

Oto moje rozwiązanie:

PHP, 622 bajty

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

Nie golfowany:

$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 bajtów

$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";

To rozwiązanie zakłada, że ​​mapę można znaleźć w zmiennej lokalnej $m. Najkrótsza metoda, jaką mam do przekazania, to $_GET: $m=$_GET['m'];14 bajtów. Wersja bez golfa z mapą w zmiennej znajduje się poniżej dla przejrzystości odczytu.

$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, 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]}

Oto wcześniejsza, nie golfowa wersja

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

Zwraca punkt początkowy, jak w x yprzypadku indeksów opartych na 0.

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

Dane wejściowe znajdują się w pliku o nazwie m.txt. Dane wyjściowe są, (x, y)ale jeśli zmienisz ostatnią instrukcję drukowania na print g, wynik będzie listą, podobnie jak [(x, y), (x, y), ...]wszystkie kroki, które należy wykonać od końca do początku.