Pecahkan labirin panah terbalik

14

Ini adalah "labirin panah":

  v      < 
>     v    
      >  ^ 
>         v
^ <       *

The *menandai tempat di mana Anda akan menyelesaikan. Tujuan Anda adalah untuk menemukan di mana maze dimulai (karenanya, maze terbalik). Dalam hal ini, ini adalah yang pertama >di baris kedua.

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

Perhatikan bahwa semua panah harus digunakan. Perhatikan juga bahwa Anda dapat mengasumsikan garis akan diisi dengan spasi dengan panjang yang sama.

Program Anda harus memasukkan maze dengan cara yang masuk akal (stdin, dari file, kotak pesan, dll.), Namun maze harus benar-benar utuh. Misalnya, Anda tidak dapat memasukkan garis yang dipisahkan oleh koma; input harus persis labirin.

Anda harus menampilkan awal maze dengan cara yang masuk akal. Misalnya, Anda bisa

  • output koordinat awal
  • output seluruh labirin dengan panah mulai diganti dengan S
  • Keluarkan seluruh labirin dengan semua panah kecuali panah awal dihapus (whitespace intact!)
  • dll.

Selama Anda bisa tahu dari output Anda panah mana yang merupakan panah awal, maka tidak apa-apa. Misalnya, output dari

"0"
"2"

tidak apa-apa, terlepas dari baris baru dan kutipan, karena Anda masih dapat mengetahui di mana awal itu.

Ini adalah kode-golf , jadi kode terpendek dalam byte akan menang.

code-golf Gagang pintu
sumber
Apakah masuk akal untuk mengasumsikan bahwa setiap anak panah hanya memiliki satu anak panah lainnya yang menunjuk padanya? Tidak akan ada contoh di mana ada beberapa titik awal, kan?
Danny
Apakah "permulaan maze" adalah panah tempat satu sama lain dikunjungi satu kali? Dengan kata lain pertanyaan Danny + asumsi tidak ada loop.
shiona
3
"Anda tidak dapat memasukkan garis yang dipisahkan oleh koma; input harus persis labirin." Ini tampaknya seperti pembatasan yang tidak perlu, karena "tepatnya labirin" sudah secara de facto dibatasi oleh baris baru di antara baris. Mengapa memprioritaskan satu pembatas di atas yang lain?
Jonathan Van Matre
1
@ Doorknob Itu masuk akal, karena orang secara teoritis bisa menyandikan seluruh solusi terkompresi dalam "pembatas". Namun, saya curiga bahwa pembatasan tersebut menimbulkan bias linguistik tertentu terhadap bahasa tertentu. Bagaimana jika aturannya adalah "Baris input dapat dibatasi oleh salah satu karakter pilihan Anda. Semua baris harus dibatasi oleh karakter yang sama ."? Saya pikir batas atas berguna karena membuat domain tempat program Anda harus bekerja.
Jonathan Van Matre
1
@ Peter Itu hanya berarti bahwa, misalnya, di >v^dalam >menunjuk ke v, bukan ^. Saya akan mengedit lebih banyak barang ketika saya pulang ke komputer hari ini.
Gagang Pintu

Jawaban:

4

GolfScript, 55 byte

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

Demo online

Asumsikan bahwa semua jalur input diisi dengan spasi dengan panjang yang sama dan dipisahkan oleh baris baru. Output byte offset dari panah mulai dari awal string input (misalnya 12untuk labirin contoh dalam tantangan).

Secara khusus, program ini menemukan offset byte dari semua panah yang tidak memiliki panah yang menunjuk ke mereka (dengan asumsi bahwa semua panah menunjuk ke panah atau tujuan; perilaku aneh dapat terjadi jika ini tidak benar). Secara default, jika ada beberapa panah seperti itu (yang, per spec, seharusnya tidak dimungkinkan dalam input yang valid), offset mereka hanya akan digabungkan dalam output. Jika mau, Anda dapat menambahkan n*ke program agar dipisahkan oleh baris baru.

Versi de-golf dengan komentar:

:&                     # 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
Ilmari Karonen
sumber
1
Anda dapat menyimpan 3 karakter jika Anda sebaris w.
Howard
@ Howard: Hah, jadi saya bisa. Terima kasih! Harus mengubah nama zuntuk &menghindari membutuhkan ruang tambahan, meskipun. OTOH, ?~.~)membuat senyum yang cukup bagus. :-)
Ilmari Karonen
5

GolfScript ( 101 100 bytes)

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

Output dalam bentuk di [[x y]]mana koordinat keduanya berbasis 0.

Demo online

Pemrosesan ada dalam dua fase: fase pertama mengubah labirin menjadi array [x y dx dy]tupel; fase kedua memetakan setiap panah / tanda bintang ke tanda panah / tanda bintang yang ditunjukkannya. (Tanda bintang dianggap menunjuk pada diri mereka sendiri). Dengan definisi masalah, ada tepat satu panah yang tidak ada dalam hasil peta ini, dan itu adalah solusinya.

Peter Taylor
sumber
Saya baru saja menempel jawaban saya saat Anda memposting ini. Kami memiliki ide yang sama, tetapi Anda berhasil membuatnya sukses. Yang bagus!
Vereos
@PeterTaylor Aku tidak bisa melihat bahwa itu menangani titik melalui kasus benar yang disebutkan dalam komentar.
Howard
@ Howard, saya tidak tahu kasus apa itu. Akan meminta klarifikasi.
Peter Taylor
Bisakah Anda memposting contoh input dan output Anda?
DavidC
@ DavidCarraher, lihat demo online. ;'STUFF'mensimulasikan memasok STUFFmelalui stdin.
Peter Taylor
2

Mathematica 491 323

Tidak dikoleksi dengan komentar

Prosedur dimulai dari selesai ("*"), menemukan panah yang mengarah ke sana, dan seterusnya hingga mencapai awal.

Fungsinya, 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 *)

prekursor [{Ratakan [{atasMe [loc, a], belowMe [loc, a], rightOfMe [loc, a], leftOfMe [loc, a]}, 2], a, Prepend [daftar, loc]}]]

(* return the path through the maze from start to finish *)
f[maze_]:= precursor[{final[maze[[1]]],maze[[1]]}]

Golf

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

Contoh

Labirin. Setiap pasangan yang dipesan berisi baris dan kolom sel. Misalnya {2, 3} menunjukkan sel pada baris 2, kolom 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} -> "<",{_, _} -> " "}]]

labirin

Memasukkan

f[maze]

Output : Jalur dari awal hingga selesai.

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

DavidC
sumber
Format input Anda salah - "input harus persis labirin".
Gagang Pintu
Input sekarang adalah labirin itu sendiri.
DavidC
Saya belum mengikuti kode, tetapi cara Anda memecahkan "input sekarang maze" itu lucu! +1 ... jumlah orang percaya di "STDIN itu universal" sangat mengejutkan.
Dr. belisarius
Saya senang Anda menghargai solusi untuk masalah input.
DavidC
1

Saya pikir saya menemukan cara yang baik untuk menyelesaikan ini, tetapi saya kebetulan mengisap golf itu. Saya kira ini bisa jadi WAY lebih pendek, jadi saya akan menjelaskan ide saya sehingga orang lain dapat menggunakannya jika mereka merasa baik.

Jika setiap panah harus digunakan, maka semua panah akan diarahkan oleh panah lain, kecuali satu, itu adalah solusi kami.

Ini berarti kita tidak benar-benar harus memainkan labirin mundur, tetapi, mulai dari yang kiri atas, kita hanya perlu memeriksa panah yang dapat ditunjukkan terdekat untuk masing-masing. Ini adalah penghilang rasa sakit yang nyata untuk labirin yang lebih besar (karena Anda tidak perlu memeriksa keempat arah, tetapi hanya satu).

Inilah solusi saya:

PHP, 622 byte

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

Tidak Disatukan:

$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;
            }
        }
    }
}
Vereos
sumber
1

PHP - 492 byte

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

Solusi ini mengandaikan bahwa peta dapat ditemukan dalam variabel lokal $m. Metode terpendek yang saya miliki untuk melewati itu adalah melalui $_GET: $m=$_GET['m'];pada 14 byte. Versi ungolfed dengan peta dalam variabel disediakan di bawah ini untuk kejelasan membaca.

$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";
Yoda
sumber
1

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

Ini versi yang lebih awal dan tidak dikoleksi

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

Mengembalikan titik awal x ydengan 0 indeks berbasis.

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

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

Input ada dalam file bernama m.txt. Outputnya adalah (x, y)tetapi jika Anda mengubah pernyataan cetak terakhir ke print g, output akan menjadi daftar seperti [(x, y), (x, y), ...]dengan semua langkah untuk mendapatkan dari ujung ke awal.

gcq
sumber