Jesteś na zaawansowanej międzygalaktycznej stacji kosmicznej. Twój przyjaciel, który pracuje w Studium Grawitacji, właśnie stworzył grę, która polega na użyciu mikrograwitacji jako sposobu na poruszanie piłką.

Podaje ci małego kontrolera z czterema strzałkami kierunkowymi i labiryntową strukturą z piłką siedzącą po lewej stronie. Zaczyna wyjaśniać, jak działa gra.

• Masz 2 przyciski kierunkowe, lewy <i prawy >.
• Masz również 2 przyciski grawitacji, w górę ^i w dół v(przynajmniej z poziomu odniesienia)
• Za pomocą tych przycisków strzałek możesz poruszać piłką po ekranie.

„Teraz należy przestrzegać kilku zasad”. ona mówi

1. Przed dojściem do pucharu wszystkie platformy muszą przejść \ /
2. Strzałki < > ^ vzostaną wykorzystane do określenia ruchu piłki
3. Grawitacja to ^ v(góra i dół). To przesuwa piłkę do następnej platformy w tym kierunku. (Odległość nie jest obliczana dla wzlotów i upadków)
4. Zgubienie piłki jest złe! Nie spadaj poza krawędź i nie zmieniaj grawitacji zbyt wcześnie, aby Twoja piłka nigdy nie osiągnęła platformy
5. Ruch jest liczony w krokach co < >
6. Piłka może wejść do kubka z dowolnego kierunku, o ile przestrzegana jest reguła 1
7. Musisz określić kierunek grawitacji, aby twoja piłka nie odpłynęła
8. Ruch może być losowy, o ile przestrzegana jest reguła 1 i reguła 4
9. W przypadkach, których nie można rozwiązać, należy wpisać False lub Invalid

Prosty przykład piłki, platformy i kubka:

v
o
---\ /

v>

 o
---\ /

v>>

  o
---\ /

v>>>

   o
---\ /

v>>>>


---\o/

Przykład ponownego przejścia przez tę samą platformę.

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

Przykład przełączania grawitacji

v
   --/ \

o
----

v>
   --/ \

 o
----

v>>
   --/ \

  o
----

v>>>
   --/ \

   o
----

v>>>^
   --/ \
   o

----

v>>>^>
   --/ \
    o

----

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

----

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


----

Zadanie

Twoim zadaniem jest stworzenie programu, który pobierze reprezentację kursu ASCII jako dane wejściowe. I wyślij ciąg strzałek <>^vprzedstawiających kierunek i siłę grawitacji, aby przenieść piłkę w opoprzek platformsdo kubka.

Obowiązują standardowe zasady gry w golfa

Przypadki testowe

Wejście (sytuacja, w której przełączana jest grawitacja)

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

  ------    -----

Wydajność

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

Wejście (sytuacja, w której zmienia się kierunek)

       ---
o   
----
    ---

     -----  

    --\ /

Wydajność

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

Wejście (sytuacja, w której musisz dwukrotnie przejść przez tę samą platformę)

 o
 ------

  ------

 ------ 

\ /------

Wydajność

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

Złe przypadki, program powinien wypisać dla nich Falsy

Piłka nie może dostać się na następną platformę

o
--- ---

Piłka odpłynie w kosmos

---
o
   ---

Sytuacja, w której piłka dostaje się do kubka, ale wszystkie platformy się nie przechodzą.

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

Pyth, 431 bajtów

To jest mój pierwszy program w języku Pyth (tak naprawdę to mój pierwszy program w dowolnym języku golfowym), co oznacza, że ​​prawdopodobnie można go jeszcze ulepszyć.

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

Wypróbuj tutaj (ostatnia walizka testowa wymaga zbyt dużo czasu, należy ją przetestować przy użyciu lokalnej instalacji Pyth).

Zrzut szesnastkowy kodu (użyj xxd -r <filename>do dekodowania):

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

Wyjaśnienie

Główną ideą tego programu było użycie wyrażeń regularnych do modyfikacji danych wejściowych. Aby zaoszczędzić miejsce, wszystkie te wyrażenia regularne są zawarte w skompresowanym ciągu. Pierwszym krokiem w programie jest dekompresja ciągu i podzielenie go na pojedyncze wyrażenie regularne i odpowiadające im ciągi zastępujące.

            .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

Zawartość zmiennej Jto:

[[['\\\\ /', '=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

Funkcja rstosuje podstawienia wyrażeń regularnych z listy przechowywanej w Jindeksie Gdo wszystkich ciągów na liście H. Zwraca się, gdy tylko jeden z ciągów zostanie zmieniony.

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

Funkcja ijest podobna do funkcji rz 2 różnicami. Stosuje podstawienia na liście transponowanej (pionowej zamiast poziomej). Powoduje także wielokrotne podstawienia, o ile cokolwiek się zmieni.

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

Funkcja gsprawdza, czy wyrażenie regularne z listy przechowywanej w Jindeksie Gmożna znaleźć w dowolnym ciągu na liście 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

Reszta kodu zawiera logikę programu. Przeprowadza pierwsze wyszukiwanie możliwych ruchów, aż do znalezienia rozwiązania. Pozycja w drzewie wyszukiwania jest jednoznacznie określona przez kierunek grawitacji i zmodyfikowaną kopię danych wejściowych programu. Aby uniknąć ponownego przetwarzania tej samej pozycji, przetworzone pozycje są zapisywane na liście globalnej K. Pozycje, które należy jeszcze przetworzyć, są przechowywane razem z odpowiednią częścią rozwiązania na liście Y.

Modyfikacja danych wejściowych oraz inicjalizacja Ki Ysą wykonywane przez następujący kod:

           .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

Modyfikacja danych wejściowych działa w następujący sposób. Dane wejściowe:

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

  ------    -----

przekształca się w:

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

Wartości mają następujące znaczenie:

• - Platforma, którą należy jeszcze odwiedzić
• = Platforma, której nie trzeba już odwiedzać
• M Puchar, do którego można wprowadzić grawitację ustawioną na „dół”
• W Puchar, do którego można wprowadzić grawitację ustawioną na „górę”
• V Można bezpiecznie przenieść się do tego miejsca z grawitacją ustawioną na „dół”
• A Można bezpiecznie przenieść się w to miejsce z ustawioną grawitacją
• X Można bezpiecznie przenieść się w to miejsce niezależnie od ustawienia grawitacji
• 6 Piłka na miejscu oznaczonym jako V
• 9 Piłka na miejscu oznaczonym jako A
• 0 Piłka na miejscu oznaczonym jako X

Logika używa wyrażeń regularnych do wykonywania ruchów. W powyższym przykładzie, jeśli grawitacja byłaby ustawiona na „w górę”, możemy zastąpić „9A” „A9” wyrażeniem regularnym, aby przesunąć piłkę w prawo. Oznacza to, że próbując zastosować wyrażenie regularne, możemy znaleźć wszystkie możliwe ruchy.

Funkcja XWykonuje ruchy pionowe kulkowe oparte na aktualnym ustawieniem grawitacyjnego, zapisuje wynik na światowych listach Ki Y, i sprawdza, czy rozwiązanie zostało znalezione.

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

Funkcja (realizuje kontrole dla 4 przycisków kierunkowych / grawitacyjnych. Przyciski grawitacji można nacisnąć tylko wtedy, gdy zmienia się bieżąca grawitacja i jeśli piłka znajduje się w bezpiecznym miejscu, aby zmienić grawitację. Przyciski kierunkowe można nacisnąć tylko wtedy, gdy można bezpiecznie przenieść się w odpowiednie miejsce.

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

Wreszcie główna pętla. Pierwszy element Yjest usuwany wielokrotnie i wykonywane są sprawdzenia wszystkich możliwych ruchów.

#                                                        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)