Piłka Microgravity

33

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

wprowadź opis zdjęcia tutaj


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

       ---
o   
----
    ---

     -----  

    --\ /

Wydajność

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

wprowadź opis zdjęcia tutaj


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

 o
 ------

  ------

 ------ 

\ /------

Wydajność

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

wprowadź opis zdjęcia tutaj


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
----
    ----
        \ /----
tisaconundrum
źródło
4
Zasada 1 sprawia, że ​​jest to dość trudne ... hmmm ...
JungHwan Min
Czy łamigłówka zawsze da się rozwiązać? Myślę też, że powinieneś dołączyć przypadek testowy, który wymaga cofnięcia.
FryAmTheEggman
Tak, puzzle powinny zawsze być rozwiązywalne. Luki lub skoki, które tracą piłkę lub sytuacje, które sprawiają, że labirynt jest nierozwiązywalny, nie zostaną wykonane.
tisaconundrum
4
@JungHwanMin Zasada 1 dokładnie wyjaśnia, dlaczego jest to wyzwanie, a nie trywialne.
Erik the Outgolfer
2
Nigdy nie czułem się tak daleko w dół króliczej nory w pytaniu o codegolf
dj0wns

Odpowiedzi:

11

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)
Sleafar
źródło
Czy mam rację sądząc, że zakładasz, że każdy wkład można rozwiązać? Ponieważ pytanie wciąż mówi, że należy wykryć nierozwiązywalne dane wejściowe, komentarze sugerują jednak, że każde dane wejściowe będą możliwe do rozwiązania. Nie jestem pewien, co się dzieje, ale myślę, że twój kod nie wykrywa nierozwiązywalności.
Jonathan Frech,
@JathanathanFrech Jeśli dane wejściowe są nierozwiązywalne, nie będzie danych wyjściowych. Po sprawdzeniu wszystkich możliwości Ylista będzie pusta, pop wyrzuci błąd i #pętla się zakończy.
Sleafar
1
Kiedy wyjmiesz kubek z wejścia (`/ \`), układanka stanie się nierozwiązywalna (ponieważ nie możesz dosięgnąć filiżanki), ale twój program nadal generuje wyjście.
Jonathan Frech,
Nie miałem na myśli tego, co robi twój program, myślę, że to nierozwiązywalne wejście układanki generuje wyjście.
Jonathan Frech,
@JathanathanFrech Masz rację. Próbuję to naprawić, ale mam problemy z kodowaniem skompresowanego ciągu.
Sleafar