Lakukan backflip untuk ais523!

16

Tantangan ini adalah hadiah untuk ais523 untuk memenangkan para " Rookie of the Year " kategori dalam " Best of PPCG 2016 ". Selamat!


BackFlip adalah bahasa pemrograman esoterik yang dibuat oleh pengguna ais523 , yang telah menciptakan lebih dari 30 esolangs menarik lainnya .

BackFlip adalah bahasa 2D seperti Befunge atau > <> di mana penunjuk instruksi melintasi kotak teks (program), bergerak ke atas, ke bawah, ke kiri, dan ke kanan, mengubah arah tergantung pada karakter yang aktif. Secara kritis, kisi-kisi dalam program BackFlip berubah saat sedang dilalui, sedikit mirip dengan Langton's Ant .

Untuk tantangan ini, Anda dapat mengasumsikan bahwa program BackFlip selalu berupa kisi-kisi teks persegi panjang (semua garis memiliki panjang yang sama), ukuran minimal 1 × 1, hanya berisi karakter ./\<>^V. ( .digunakan untuk visibilitas daripada ruang.) Semantik BackFlip yang akan kami gunakan di sini identik dengan spesifikasi asli .

Instruksi penunjuk (IP) di BackFlip selalu dimulai tepat di kiri atas sudut kiri program, menuju ke kanan. Ada tiga jenis perintah itu dapat menemukan:

  1. .adalah no-op. IP melanjutkan ke arah yang sedang terjadi. No-op tetap no-op.

  2. /dan \merupakan cermin. Mereka memantulkan IP ke arah yang ditunjukkan oleh sudut mereka, kemudian mereka berubah menjadi jenis cermin lainnya .

    • Misalnya, jika kepala IP dibiarkan menjadi \, mulai bergerak ke atas, bukan ke kiri dan \menjadi /.
  3. <, >, ^, Dan Vadalah anak panah. Mereka mengarahkan IP ke arah yang mereka tuju, kemudian mereka berubah menjadi panah yang menunjuk ke arah IP berasal (berlawanan dengan arah IP bergerak) .

    • Sebagai contoh, jika IP mengarah ke bawah >, ia mulai bergerak ke kanan, bukan ke bawah dan >menjadi ^karena itu adalah arah IP berasal.

Program BackFlip berakhir ketika IP bergerak keluar dari batas, yaitu keluar dari grid. Ternyata semua program BackFlip akhirnya berakhir karena loop tak terbatas tidak mungkin. (Anda mungkin menganggap ini benar.)

Tujuan Anda dalam tantangan ini adalah untuk menulis program atau fungsi yang mengambil dalam program BackFlip dan menampilkan jumlah gerakan yang dilakukan oleh penunjuk instruksi sebelum program berakhir. Yaitu, berapa banyak langkah yang diambil IP dalam menjalankan program? Ini termasuk langkah awal ke grid dan langkah terakhir darinya.

Misalnya, penunjuk instruksi mengambil 5 langkah di kotak sepele ....:

 ....  <- empty 4×1 grid
012345 <- step number of the IP

Jadi hasilnya ....adalah 5.

Dalam lebih kompleks 4 × 2 kotak

\...
\.><

IP keluar dari kotak pada langkah 9, sehingga output adalah 9:

step  grid  IP position (@)
0     \...  @....
      \.><   ....

1     \...   @...
      \.><   ....

2     /...   ....
      \.><   @...

3     /...   ....
      /.><   .@..

4     /...   ....
      /.><   ..@.

5     /...   ....
      /.<<   ...@

6     /...   ....
      /.<<   ..@.

7     /...   ....
      /.><   .@..

8     /...   ....
      /.><   @...

9     /...   ....
      \.><   ....
             @

Kode terpendek dalam byte menang.

Anda dapat mengambil input sebagai array garis atau matriks karakter, bukan string multiline jika diinginkan, tetapi Anda harus menggunakan karakter ./\<>^V(bukan opcode integer). Anda dapat menggunakan ruang alih-alih .jika lebih disukai. Tidak apa-apa jika karakter seperti \perlu melarikan diri dalam input. Output selalu integer lebih dari satu.

Uji Kasus

....
5

\...
\.><
9

.
2

..
3

.
.
2

\
2

^
2

.^.
3

<.
2

\\
\/
7

>V
^<
6

>\
>/
6

\><
2

\><
\><
7

\><
\><
\><
12

\.V.
\.\<
5

\.V.
\./<
9

V./\
V./\
>./<
..\/
14

\V..
.^..
\/><
.V..
.^..
20

\.V.V.
\./.\<
.>\<..
..^.^.
31

\.V.V.V.
\./>/.\<
.>\>\<..
..^.^.^.
69

\.V.V.V.V.
\./>/>/.\<
.>\>\>\<..
..^.^.^.^.
145

\.V.V.V.V.V.V.V.V.V.V.
\./>/>/>/>/>/>/>/>/.\<
.>\>\>\>\>\>\>\>\>\<..
..^.^.^.^.^.^.^.^.^.^.
9721
Hobi Calvin
sumber
1
Sangat memalukan bahwa Anda tidak dapat membuat solusi BackFlip untuk ini ...
HyperNeutrino
Bingung tentang mirror ... apakah / membalik arah sebagai kiri => atas dan atas => kiri ,?
officialaimm
1
@officialaimm Menuju dari kiri ke kanan /akan membuat IP naik dan menuju ke atas /akan membuat IP kanan, seolah-olah itu adalah bola yang memantul ke dinding. (Tapi ingat /perubahan backslash setelah IP menyentuhnya.)
Calvin Hobi
mengapa '\\' <LF> '\ /' adalah 7 bukannya 6?
TSH

Jawaban:

3

JavaScript (ES6), 158 byte

f=(a,x=0,y=0,d=3)=>a[x]&&(c=a[x][y])?(a[x][y]=c=='.'?c:c=='/'?(d^=3,'\\'):c=='\\'?(d^=1,'/'):'v>^<'[d][d='^<v>'.search(c),0],f(a,d<3?x+d-1:x,d?y+d-2:y,d)+1):1

Dikembangkan secara independen dari jawaban @ tsh meskipun sangat mirip.

Pemetaan arah ^<v>ke bilangan bulat 0-3 diatur oleh fakta bahwa .search('^')mengembalikan 0 karena ^adalah metacharacter regexp.

Neil
sumber
Saya merasa sangat terpukul. Saya cukup bingung pada akhirnya sampai saya menyadari x dan y terbalik dibandingkan dengan yang saya harapkan.
Ørjan Johansen
@ ØrjanJohansen Itu poin bagus; mungkin saya harus menukar x dengan y di mana-mana untuk membuatnya lebih mudah dimengerti.
Neil
2

Haskell , 333 325 byte

EDIT:

  • -8 byte: Dibuat fpointfree dan digabung menjadi b.

bmengambil daftar Strings dan mengembalikan sebuah Integer.

data C a=C{c::a->(a,C a)}
b g=[0,0]#([0,1],map(maybe(C$m 1)C.(`lookup`zip"./^>V<"[n,m(-1),a[-1,0],a[0,1],a[1,0],a[0,-1]]))<$>g)
[y,x]#(d,g)|g&y||g!!0&x=1|n@([f,e],_)<-(($d).c)?x?y$g=1+[y+f,x+e]#n
l&i=i<0||i>=length l
(f?i)l|(p,a:r)<-splitAt i l=(p++).(:r)<$>f a
n d=(d,C n)
a v d=(v,C$a$(0-)<$>d)
m s[d,e]=([s*e,s*d],C$m(-s))

Cobalah online!

Bagaimana itu bekerja

  • C aadalah tipe data yang digunakan karena Haskell tidak akan mengizinkan suatu tipe menjadi rekursif tanpa menyatakannya secara eksplisit. Cjuga merupakan konstruktor pembungkus dan cmerupakan fungsi buka bungkusnya yang sesuai. Hanya digunakan dengan a=[Int].
    • Tipe C [Int]mewakili perintah sel, sebagai fungsi yang mengambil [Int]argumen direction ( ), dan mengembalikan sepasang arah baru, dan C [Int]nilai baru .
  • badalah fungsi utama. Itu mengkonversi setiap karakter menjadi Cnilai, lalu itu panggilan #.
    • g adalah kisi sebagai daftar string.
    • Karena \perlu untuk melarikan diri dan karakter terpanjang yang disebutkan, hasilnya malah digunakan sebagai nilai default untuk pencarian daftar.
  • #menjalankan simulasi utama, memeriksa batas dengan &dan menghasilkan grid baru dengan ?. [y,x]adalah posisi saat ini, darah saat ini, dan gkisi saat ini. [f,e]adalah arah berikutnya, dan nmerupakan pasangan dari itu dan kotak berikutnya.
  • l&imemeriksa apakah indeks di iluar batas untuk daftar l. (Ini kembali Truekeluar dari batas, karena itu menghindari kondisi penjaga boneka #.)
  • Kapan f(l!!i)==(d,x), di (f?i)l==(d,m)mana mdaftar ldengan ielemen th diganti dengan x.
    • Secara teknis (?i)adalah lensa yang lebih umum, dengan fokus pada elemen ke-10 dari daftar, dalam hal ini digunakan dengan (,) [Int]instance functor.
  • n adalah fungsi yang mewakili sebuah titik.
  • a vadalah fungsi yang mewakili panah ke arah v.
  • m sadalah fungsi yang mewakili cermin; s==1untuk \\dan s==-1untuk /.
Ørjan Johansen
sumber
1

JavaScript, 172 byte

f=(a,d=3,x=0,y=0,n=1)=>(p=a[y]||[],q=p[x])?(p[x]=~(t='^<V>'.indexOf(q))?'^<V>'[d^2]:q=='/'?(t=3-d,'\\'):q=='\\'?(t=d^1,'/'):(t=d,q),f(a,t,x+(t&1&&t-2),y+(~t&1&&t-1),n+1)):n

Tetapi saya tidak dapat menguji testcase terakhir karena saya mendapat stack overflow pada mesin saya. (harus bekerja jika ada mesin dengan ram lebih besar)

Kami menggunakan nomor untuk arah:

  • 0: ^
  • 1: <
  • 2: V
  • 3:>

Biarkan dmenjadi nomor arah ...

  • jika kita bertemu '/', kita perlu d = 3 - d;
  • jika kita bertemu dengan '\' kita perlu d = d ^ 1;
  • jika kita bertemu '^ <V>' kita perlu d = '^ <V>' .indexOf (catatan)

Membiarkan (x, y)menjadi posisi saat ini, posisi berikutnya adalah: x+(t&1&&t-2),y+(~t&1&&t-1)

catatan:

Fungsi ini mengambil satu paramter dengan format berikut:

[ [ '\\', '.', 'V', '.', 'V', '.', 'V', '.', 'V', '.' ],
  [ '\\', '.', '/', '>', '/', '>', '/', '.', '\\', '<' ],
  [ '.', '>', '\\', '>', '\\', '>', '\\', '<', '.', '.' ],
  [ '.', '.', '^', '.', '^', '.', '^', '.', '^', '.' ] ]

Uji di sini

f=(a,d=3,x=0,y=0,n=1)=>(p=a[y]||[],q=p[x])?(p[x]=~(t='^<V>'.indexOf(q))?'^<V>'[d^2]:q=='/'?(t=3-d,'\\'):q=='\\'?(t=d^1,'/'):(t=d,q),f(a,t,x+(t&1&&t-2),y+(~t&1&&t-1),n+1)):n

    ;k=x=>x.split('\n').map(t=>t.split(''));
<textarea id=v>\.V.V.V.V.
\./>/>/.\<
.>\>\>\<..
..^.^.^.^.</textarea><br/><button onclick="r.textContent=f(k(v.value))">Solve</button>
<p>Result: <output id=r></output></p>

tsh
sumber
Hanya untuk mendokumentasikan, saya mendapatkan Uncaught RangeError: Maximum call stack size exceededdengan 16GB RAM.
Zeb McCorkle
1
@ZebMcCorkle aha, cari tahu bahwa "gunakan ketat" dan beberapa vardeklarasi membuatnya lulus testcase terakhir (penerjemah js melakukan optimasi panggilan ekor dalam mode ketat)
tsh
1

C, 232 221 byte

d,n,t,m[4]={1,-1};char*w="><^V/\\.",*P;main(o,v)char**v;{for(P=v[1],m[2]=-(m[3]=strchr(P,10)-P+1);P>=v[1]&&P<strchr(v[1],0)&&*P^10;++n)*P=w[((o=d,t=strchr(w,*P)-w)<4)?d=t,o^1:(t<6)?d^=t-2,9-t:6],P+=m[d];printf("%d",n+1);}

Mengambil input dalam argumen pertama, mencetak hasil. Membutuhkan input yang mengandung setidaknya 1 baris baru (jadi jika hanya ada 1 baris, harus diakhiri dengan baris baru)

Contoh penggunaan:

./backflip '....
';

Kerusakan:

d,                                          // Direction
n,                                          // Step counter
t,
m[4]={1,-1};                                // Movement offsets
char*w="><^V/\\.",                          // Command lookup
*P;                                         // Cursor location
main(o,v)char**v;{
    for(P=v[1],                             // Begin at 0,0
        m[2]=-(m[3]=strchr(P,10)-P+1);      // Find width of grid
        P>=v[1]&&P<strchr(v[1],0)&&*P^10;   // While inside grid:
        ++n)                                //  Increment step
        *P=w[                               //  Update the current cell
            ((o=d,t=strchr(w,*P)-w)         //  (store current direction & command)
              <4)?d=t,o^1:                  //   If <>^V, write backflip & set dir
            (t<6)?d^=t-2,9-t:               //   If / or \, write flip & bounce
            6],                             //   If ., write unchanged & continue
        P+=m[d];                            //  Move
    printf("%d",n+1);                       // Print result
}
Dave
sumber
1

Python 3 , 286 byte

[f () mengambil input dalam bentuk {(0,0):'/',(0,1):'.'}jadi saya juga menulis fungsi g () untuk mengonversi array baris ke bentuk itu]

def f(r):
 x=y=0;d='>';s=1
 while 1:
  try:c=r[y,x];m='>^<V'.find(d)
  except:break
  if(c=="\\"):d='V<^>'[m];r[y,x]="/"
  elif(c=="/"):d='^>V<'[m];r[y,x]="\\"
  elif(c!="."):r[y,x]='<V>^'[m];d=c
  x+=1if(d=='>')else-1if(d=='<')else 0;y+=1if(d=='V')else-1if(d=='^')else 0;s+=1
 return s

Cobalah online!

officialaimm
sumber