Anda berada di stasiun ruang angkasa intergalaksi canggih. Seorang teman Anda yang sedang belajar di Gravitasi Studi baru saja menciptakan sebuah permainan yang melibatkan menggunakan gayaberat mikro sebagai cara untuk memindahkan bola di sekitar.

Dia memberi Anda controller kecil dengan empat panah arah di atasnya dan struktur seperti labirin dengan bola duduk di sebelah kiri. Dia mulai menjelaskan cara kerja gim.

• Anda memiliki 2 tombol arah, kiri <dan kanan >.
• Anda juga memiliki 2 tombol gravitasi, naik ^dan turun v(setidaknya dari kerangka referensi Anda)
• Anda akan menggunakan tombol panah ini untuk menggerakkan bola di layar Anda.

"Sekarang ada beberapa aturan yang perlu diikuti." dia berkata

1. Semua platform harus dilalui sebelum sampai ke piala \ /
2. Panah < > ^ vakan digunakan untuk menentukan pergerakan bola
3. Gravitasi adalah ^ v(naik & turun). Ini menggerakkan bola sampai ke platform berikutnya ke arah itu. (Jarak tidak dihitung untuk naik turun)
4. Kehilangan bola itu buruk! Jangan jatuh ke tepian, dan jangan beralih gravitasi terlalu cepat sehingga bola Anda tidak pernah mencapai platform
5. Gerakan dihitung dalam langkah-langkah < >
6. Bola dapat memasuki cawan dari arah mana pun selama Aturan 1 diikuti
7. Anda harus menentukan arah gravitasi agar bola Anda tidak melayang
8. Gerakan mungkin acak selama Aturan 1 dan Aturan 4 diikuti
9. Untuk kasus yang tidak dapat diselesaikan, output False atau Invalid

Contoh sederhana bola, platform, dan piala:

v
o
---\ /

v>

 o
---\ /

v>>

  o
---\ /

v>>>

   o
---\ /

v>>>>


---\o/

Contoh melintasi lagi di platform yang sama.

v    

 o
 ----

\ /-------

v>   

  o
 ----

\ /-------

v>>

   o
 ----

\ /-------

v>>>

    o
 ----

\ /-------

v>>>>


 ----
     o
\ /-------

v>>>>>


 ----
      o
\ /-------

v>>>>>>


 ----
       o
\ /-------

v>>>>>>>


 ----
        o
\ /-------

v>>>>>>>>


 ----
         o
\ /-------

v>>>>>>>><<<<<<<< # move all the way to the left to get to the cup


 ----

\o/-------

Contoh beralih gravitasi

v
   --/ \

o
----

v>
   --/ \

 o
----

v>>
   --/ \

  o
----

v>>>
   --/ \

   o
----

v>>>^
   --/ \
   o

----

v>>>^>
   --/ \
    o

----

v>>>^>>
   --/ \
     o

----

v>>>^>>>
   --/o\


----

Tugas

Tugas Anda adalah membuat program yang akan mengambil representasi ASCII dari kursus sebagai input. Dan menghasilkan serangkaian panah yang <>^vmewakili arah dan tarikan gravitasi untuk memindahkan bola omelintasi semua platformske dalam cangkir.

Aturan golf kode standar berlaku

Uji Kasus

Input (Situasi di mana gravitasi sedang diaktifkan)

         ----   --/ \
---    --
o

  ------    -----

Keluaran

^>>v>>>>>^>>>>>v>>>>^>>>

Input (Situasi di mana arah dialihkan)

       ---
o   
----
    ---

     -----  

    --\ /

Keluaran

v>>>>>>^>>>v<<<<<v>>>

Input (Situasi di mana Anda harus melintasi platform yang sama dua kali)

 o
 ------

  ------

 ------ 

\ /------

Keluaran

v>>>>>><<<<<<>>>>>>><<<<<<

Kasus Buruk, Program harus menampilkan Falsy untuk ini

Tidak mungkin bola bisa sampai ke platform berikutnya

o
--- ---

Bola akan melayang ke angkasa

---
o
   ---

Situasi di mana bola sampai ke piala, tetapi semua platform tidak dilewati.

o
----
    ----
        \ /----

Pyth, 431 byte

Ini adalah program Pyth pertama saya (sebenarnya ini adalah program pertama saya dalam bahasa kode-golf), yang artinya mungkin masih dapat ditingkatkan.

Jmmck\:cd\%c.Z"xÚU±Ã@DÅ W,J áDPáÒ­V`ýüw{g$ÍÀÞÇr§o.÷å8èÝÇr{øºy{~1åõ:noßÃú/.yçíäÂ'ëL¢êF¸èÆ\ka´QÒnÒ@tãÒÁµÆ¾õö»bÍH¥¦$¨%5Eyîÿ}ó§ûrh³oÄåËÄqõ XÔHû"\_KYDrGHFN@JGIn=bm:d.*NHHRb)RHDiNTR.turNG.tT;M:jH)hh@JG0DXGHN=Ti+3qG\^HI!},GTK aK,GT aY+eKNI&!g5T}\EjT)N.q;D(GHNT)INIqHhT=ZrGhtTInZhtTXHZ+eTN))).?I&nHhTgGhtTXHhtT+eTH; aK,di2i1r0.z aY+eKk#=N.(Y0(6\vkN)(7\^kN)(8\v\<N)(9\v\>N)(10\^\<N)(11\^\>N

Coba di sini (testcase terakhir terlalu lama, harus diuji dengan instalasi Pyth lokal).

Hex dump kode (gunakan xxd -r <filename>untuk memecahkan kode):

00000000: 4a6d 6d63 6b5c 3a63 645c 2563 2e5a 2278  Jmmck\:cd\%c.Z"x
00000010: da55 8eb1 8ac3 400c 447f c58d 2057 2c99  [email protected]... W,.
00000020: 4aa0 e144 50e1 d2ad 5660 87fd 84fc 7f77  J..DP...V`.....w
00000030: 7b67 1f24 cdc0 8319 de1c c772 a76f 2ef7  {g.$.......r.o..
00000040: e538 e8dd c772 7bf8 9eba 797b 7e31 e5f5  .8...r{...y{~1..
00000050: 8e3a 6e8f 6fdf c3fa 2f2e 0c79 e717 ede4  .:n.o.../..y....
00000060: c21f 27eb 8395 189a 4c15 140b a28d ea82  ..'.....L.......
00000070: 46b8 e8c6 5c05 1b6b 1d61 b490 0251 d28c  F...\..k.a...Q..
00000080: 6ed2 4087 74e3 1ad2 c1b5 c6be f5f6 1cbb  [email protected]...........
00000090: 6286 cd48 a5a6 24a8 2535 4579 eeff 7df3  b..H..$.%5Ey..}.
000000a0: 8a8a 1613 a7fb 7204 68b3 6fc4 e51b 160c  ......r.h.o.....
000000b0: 1304 cbc4 8a71 f57f 2058 d448 fb22 5c5f  .....q.. X.H."\_
000000c0: 4b59 4472 4748 464e 404a 4749 6e3d 626d  KYDrGHFN@JGIn=bm
000000d0: 3a64 2e2a 4e48 4852 6229 5248 4469 4e54  :d.*NHHRb)RHDiNT
000000e0: 522e 7475 724e 472e 7454 3b4d 3a6a 4829  R.turNG.tT;M:jH)
000000f0: 6868 404a 4730 4458 4748 4e3d 5469 2b33  hh@JG0DXGHN=Ti+3
00000100: 7147 5c5e 4849 217d 2c47 544b 2061 4b2c  qG\^HI!},GTK aK,
00000110: 4754 2061 592b 654b 4e49 2621 6735 547d  GT aY+eKNI&!g5T}
00000120: 5c45 6a54 294e 2e71 3b44 2847 484e 5429  \EjT)N.q;D(GHNT)
00000130: 494e 4971 4868 543d 5a72 4768 7454 496e  INIqHhT=ZrGhtTIn
00000140: 5a68 7454 5848 5a2b 6554 4e29 2929 2e3f  ZhtTXHZ+eTN))).?
00000150: 4926 6e48 6854 6747 6874 5458 4868 7454  I&nHhTgGhtTXHhtT
00000160: 2b65 5448 3b20 614b 2c64 6932 6931 7230  +eTH; aK,di2i1r0
00000170: 2e7a 2061 592b 654b 6b23 3d4e 2e28 5930  .z aY+eKk#=N.(Y0
00000180: 2836 5c76 6b4e 2928 375c 5e6b 4e29 2838  (6\vkN)(7\^kN)(8
00000190: 5c76 5c3c 4e29 2839 5c76 5c3e 4e29 2831  \v\<N)(9\v\>N)(1
000001a0: 305c 5e5c 3c4e 2928 3131 5c5e 5c3e 4e    0\^\<N)(11\^\>N

Penjelasan

Gagasan utama untuk program ini adalah menggunakan ekspresi reguler untuk memodifikasi input. Untuk menghemat ruang, semua ekspresi reguler ini terkandung dalam string terkompresi. Langkah pertama dalam program ini adalah mendekompresi string dan membaginya menjadi ekspresi reguler tunggal dan string pengganti yang sesuai.

            .Z"..."     Decompress the string
           c       \_   Split the result into pieces (separator is "_")
  m    cd\%             Split all pieces (separator is "%")
 m ck\:                 Split all sub-pieces (separator is ":")
J                       Assign the result to variable J

Isi variabel Jadalah:

[[['\\\\ /', '=M='], ['/ \\\\', '=W=']],
 [[' (?=[V6M=-])', 'V'], ['o(?=[V6M=-])', '6']],
 [['(?<=[A9W=-]) ', 'A'], ['(?<=[A9W=-])o', '9'], ['(?<=[X0W=-])V', 'X'], ['(?<=[X0W=-])6', '0']],
 [['6V', 'V6'], ['0X', 'X0'], ['6-', '6='], ['0-', '0='], ['6M', 'VE'], ['0M', 'XE']],
 [['A9', '9A'], ['X0', '0X'], ['-9', '=9'], ['-0', '=0'], ['W9', 'EA'], ['W0', 'EX']],
 [['[MW-]']],
 [['[60]']],
 [['[90]']],
 [['V6', '6V'], ['V0', '6X'], ['X6', '0V'], ['X0', '0X']],
 [['6V', 'V6'], ['0V', 'X6'], ['6X', 'V0'], ['0X', 'X0']],
 [['A9', '9A'], ['A0', '9X'], ['X9', '0A'], ['X0', '0X']],
 [['9A', 'A9'], ['0A', 'X9'], ['9X', 'A0'], ['0X', 'X0']]]

KY   Set the variable K to an empty list

Fungsi ini rmenerapkan penggantian regex dari daftar yang disimpan di Jdalam indeks Gke semua string dalam daftar H. Ini kembali segera setelah salah satu string diubah.

DrGH                         Define the function r(G,H)
    FN@JG              )     Loop for all entries in J[G]
             m:d.*NH         Regex substitution, replace N[0] with N[1] in all strings in list H
           =b                Store the result in variable b
         In         HRb      If b != H return b
                        RH   Return H

Fungsi iini mirip dengan fungsi rdengan 2 perbedaan. Ini menerapkan substitusi pada daftar yang dialihkan (vertikal, bukan horizontal). Itu juga melakukan penggantian berulang kali selama ada yang berubah.

DiNT          ;   Define the function i(N,T)
           .tT    Transpose the list T
       urNG       Apply r(N,...) repeatedly as long as something changes
    R.t           Transpose the result back and return it

Fungsi gmemeriksa apakah regex dari daftar yang disimpan di Jdalam indeks Gdapat ditemukan di string mana pun dalam daftar H.

M             Define the function g(G,H)
     hh@JG    Get the single regex stored in J[G]
  jH)         Join all strings in H
 :        0   Check if the regex is found anywhere in the joined string

Sisa kode berisi logika program yang sebenarnya. Ini melakukan pencarian luas pertama untuk gerakan yang mungkin sampai solusi ditemukan. Posisi di pohon pencarian secara unik ditentukan oleh arah gravitasi dan salinan input program yang dimodifikasi. Untuk menghindari pemrosesan posisi yang sama berulang-ulang, posisi yang diproses disimpan dalam daftar global K. Posisi yang masih harus diproses disimpan bersama dengan bagian yang sesuai dari solusi dalam daftar Y.

Modifikasi input dan inisialisasi dari Kdan Ydilakukan oleh kode berikut:

           .z          Get all input as a line list
     i2i1r0            Apply the regular expressions stored in J[0] horizontally, and the the ones from J[1] and J[2] vertically
   ,d                  Create a list with " " (represents "no gravity set") and the modifed input
 aK                    Append the result to the list K
                 eK    Retrieve the appended list again
                +  k   Append "" to the list (represents the empty starting solution)
              aY       Append the result to the list Y

Modifikasi input melakukan sesuatu seperti berikut ini. Input:

         ----   --/ \
---    --
o

  ------    -----

ditransformasikan menjadi:

VVVVVVVVV----VVV--=W=
---VVVV--AAAXVVVXAAAA
9AXVVVVXAAAAXVVVXAAAA
AAXVVVVXAAAAXVVVXAAAA
AA------AAAA-----AAAA

Nilai-nilai memiliki arti sebagai berikut:

• - Platform yang harus tetap dikunjungi
• = Platform yang tidak perlu dikunjungi lagi
• M Piala yang bisa dimasukkan dengan gravitasi diatur ke "turun"
• W Piala yang dapat dimasuki dengan gravitasi diatur ke "atas"
• V Aman untuk pindah ke tempat ini dengan gravitasi diatur ke "turun"
• A Aman untuk pindah ke tempat ini dengan gravitasi diatur ke "atas"
• X Aman untuk pindah ke tempat ini terlepas dari pengaturan gravitasi
• 6 Bola di tempat yang akan ditandai sebagai V
• 9 Bola di tempat yang akan ditandai sebagai A
• 0 Bola di tempat yang akan ditandai sebagai X

Logikanya menggunakan ekspresi reguler untuk melakukan gerakan. Pada contoh di atas, jika gravitasi diatur ke "atas", kita dapat mengganti "9A" dengan "A9" dengan regex untuk memindahkan bola ke kanan. Ini berarti dengan mencoba menerapkan regex kita dapat menemukan semua gerakan yang mungkin.

Fungsi Xmelakukan gerakan bola vertikal berdasarkan pengaturan gravitasi saat ini, menyimpan hasilnya dalam daftar global Kdan Y, dan memeriksa apakah solusi ditemukan.

DXGHN                                             ;   Define the function X(G,H,N)
        +3qG\^                                        Select the correct set of regular expressions based on the current gravity setting G (3 for "v" and 4 for "^")
     =Ti      H                                       Apply i(...,H) and store the result in T 
               I!},GTK                                If [G,T] not in K
                       aK,GT                          Store [G,T] in K 
                             aY+eKN                   Store [G,T,N] in Y 
                                   I&!g5T}\EjT)       If J[5] not found in T and T contains "E" (all platforms visited and ball in cup)
                                               N.q    Print N and exit

Fungsi (mengimplementasikan pemeriksaan untuk 4 arah / gravitasi tombol. Tombol gravitasi dapat ditekan hanya jika gravitasi saat ini akan berubah dan jika bola berada di tempat yang aman untuk mengubah gravitasi. Tombol arah dapat ditekan hanya jika aman untuk pindah ke tempat yang sesuai.

D(GHNT)                                                    ;   Define the function ( (G,H,N,T)
       IN                           )                          If N is not empty (contains either "<" or ">" representing directional buttons)
         IqHhT                     )                           If H (gravity setting for which this test is performed) is equal T[0] (the current gravity)
              =ZrGhtT                                          Apply r(G,T[1]) and store the result in Z (G is the appropriate regex index for the combination of gravity and directional button, T[1] is the current modified input) 
                     InZhtT       )                            If Z != T[1] (the regex operation changed something, meaning we found a valid move)
                           XHZ+eTN                             Call X(H,Z,[T[2],N]) 
                                     .?                        Else (gravity button pressed)
                                       I                       If ...
                                         nHhT                  H (new gravity setting) is not equal T[0] (current gravity setting) 
                                        &                      ... and ...
                                             gGhtT             J[G] found in T[1] (ball is in an appropriate place to switch gravity) 
                                                  XHhtT+eTH    Call X(H,T[1],[T[2],H])

Akhirnya loop utama. Elemen pertama Ydihapus berulang kali, dan memeriksa semua gerakan yang mungkin dilakukan.

#                                                        Loop until error (Y empty)
 =N.(Y0                                                  Pop first element of Y and store it in the variable N
       (6\vkN)                                           Call ( (6,"v","",N)
              (7\^kN)                                    Call ( (7,"^","",N)
                     (8\v\<N)                            Call ( (8,"v","<",N)
                             (9\v\>N)                    Call ( (9,"v",">",N)
                                     (10\^\<N)           Call ( (10,"^","<",N)
                                              (11\^\>N   Call ( (11,"^",">",N)