Mikrogravitationskugel

33

Sie befinden sich auf einer fortgeschrittenen intergalaktischen Raumstation. Ein Freund von Ihnen, der in der Studie der Schwerkraft mitspielt, hat soeben ein Spiel entwickelt, bei dem die Schwerelosigkeit zum Bewegen eines Balls verwendet wird.

Sie gibt Ihnen einen kleinen Controller mit vier Richtungspfeilen und einer labyrinthartigen Struktur, auf der links eine Kugel sitzt. Sie beginnt zu erklären, wie das Spiel funktioniert.

  • Sie haben 2 Richtungstasten, links <und rechts >.
  • Sie haben auch 2 Schwerkrafttasten nach oben ^und unten v(zumindest von Ihrem Bezugsrahmen)
  • Mit diesen Pfeiltasten bewegen Sie den Ball auf Ihrem Bildschirm.

"Nun gibt es einige Regeln, die befolgt werden müssen." Sie sagt

  1. Alle Plattformen müssen vor dem Erreichen des Bechers überquert werden \ /
  2. Pfeile < > ^ vwerden verwendet, um die Bewegung des Balls festzulegen
  3. Die Schwerkraft ist ^ v(auf und ab). Dies bewegt den Ball bis zur nächsten Plattform in dieser Richtung. (Die Entfernung wird nicht für Auf und Ab berechnet.)
  4. Den Ball zu verlieren ist schlecht! Fallen Sie nicht über die Kante und wechseln Sie die Schwerkraft nicht zu früh, sodass Ihr Ball niemals eine Plattform erreicht
  5. Die Bewegung wird in Schritten von gezählt < >
  6. Der Ball kann aus jeder Richtung in den Pokal gelangen, solange Regel 1 befolgt wird
  7. Sie müssen die Richtung der Schwerkraft angeben, damit Ihr Ball nicht wegschwimmt
  8. Die Bewegung kann zufällig sein, solange Regel 1 und Regel 4 befolgt werden
  9. Für Fälle, die nicht gelöst werden können, geben Sie False oder Invalid aus

Einfaches Beispiel für einen Ball, eine Plattform und eine Tasse:

v
o
---\ /

v>

 o
---\ /

v>>

  o
---\ /

v>>>

   o
---\ /

v>>>>


---\o/

Beispiel für ein erneutes Überqueren derselben Plattform.

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

Beispiel für das Umschalten der Schwerkraft

v
   --/ \

o
----

v>
   --/ \

 o
----

v>>
   --/ \

  o
----

v>>>
   --/ \

   o
----

v>>>^
   --/ \
   o

----

v>>>^>
   --/ \
    o

----

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

----

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


----

Aufgabe

Ihre Aufgabe ist es, ein Programm zu erstellen, das eine ASCII-Darstellung eines Kurses als Eingabe verwendet. Geben Sie eine Reihe von Pfeilen aus, <>^vdie die Richtung und die Anziehungskraft darstellen, um einen Ball oüber alle platformsin eine Tasse zu bewegen .

Es gelten die Standard-Code-Golfregeln

Testfälle

Eingabe (Eine Situation, in der die Schwerkraft umgeschaltet wird)

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

  ------    -----

Ausgabe

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

Bildbeschreibung hier eingeben


Eingang (Eine Situation, in der die Richtung gewechselt wird)

       ---
o   
----
    ---

     -----  

    --\ /

Ausgabe

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

Bildbeschreibung hier eingeben


Eingabe (Eine Situation, in der Sie zweimal über dieselbe Plattform fahren müssen)

 o
 ------

  ------

 ------ 

\ /------

Ausgabe

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

Bildbeschreibung hier eingeben


In schlimmen Fällen sollte das Programm für diese Fälle Falsy ausgeben

Keine Möglichkeit für den Ball, zur nächsten Plattform zu gelangen

o
--- ---

Der Ball würde in den Weltraum fliegen

---
o
   ---

Eine Situation, in der der Ball zum Pokal gelangt, aber nicht alle Plattformen überquert werden.

o
----
    ----
        \ /----
tisaconundrum
quelle
4
Regel 1 macht dies zu einer ziemlichen Herausforderung ... hmmm ...
JungHwan Min
Wird das Rätsel immer lösbar sein? Außerdem sollten Sie einen Testfall einbeziehen, der ein Backtracking erfordert.
FryAmTheEggman
Ja, Rätsel sollten immer lösbar sein. Lücken oder Sprünge, die den Ball verlieren, oder Situationen, die das Labyrinth unlösbar machen, werden nicht ausgeführt.
Tisaconundrum
4
@JungHwanMin Regel 1 ist genau deshalb eine Herausforderung und nicht trivial.
Erik der Outgolfer
2
Ich habe mich bei einer Codegolf-Frage noch nie so tief in einem Kaninchenbau gefühlt
dj0wns

Antworten:

11

Pyth, 431 Bytes

Dies ist mein erstes Pyth-Programm (tatsächlich ist dies mein erstes Programm in einer Code-Golf-Sprache), was bedeutet, dass es wahrscheinlich noch verbessert werden kann.

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

Probieren Sie es hier aus (der letzte Testfall dauert zu lange, er muss mit einer lokalen Pyth-Installation getestet werden).

Hex-Dump des Codes ( xxd -r <filename>zum Dekodieren verwenden):

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

Erläuterung

Die Hauptidee für dieses Programm bestand darin, reguläre Ausdrücke zu verwenden, um die Eingabe zu ändern. Aus Platzgründen sind alle diese regulären Ausdrücke in einer komprimierten Zeichenfolge enthalten. Der erste Schritt im Programm besteht darin, die Zeichenfolge zu dekomprimieren und in einzelne reguläre Ausdrücke und die entsprechenden Ersatzzeichenfolgen aufzuteilen.

            .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

Der Inhalt der Variablen Jist dann:

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

Die Funktion rwendet Regex-Ersetzungen aus der im JIndex gespeicherten Liste Gauf alle Zeichenfolgen in der Liste an H. Es wird zurückgegeben, sobald eine der Zeichenfolgen geändert wurde.

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

Die Funktion iähnelt der Funktion rmit 2 Unterschieden. Er wendet die Ersetzungen auf eine transponierte Liste an (vertikal statt horizontal). Es führt die Ersetzungen auch wiederholt durch, solange etwas geändert wird.

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

Die Funktion gprüft, ob der reguläre Ausdruck aus der im JIndex gespeicherten Liste Gin einer beliebigen Zeichenfolge in der Liste gefunden werden kann 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

Der Rest des Codes enthält die eigentliche Programmlogik. Es führt eine Breitensuche nach möglichen Bewegungen durch, bis eine Lösung gefunden wird. Die Position im Suchbaum wird eindeutig durch die Richtung der Schwerkraft und eine geänderte Kopie der Programmeingabe definiert. Um zu vermeiden, dass immer wieder dieselbe Position bearbeitet wird, werden bearbeitete Positionen in der globalen Liste gespeichert K. Positionen, die noch bearbeitet werden müssen, werden zusammen mit dem entsprechenden Teil der Lösung in der Liste gespeichert Y.

Die Änderung der Eingabe und Initialisierung von Kund Ywird mit folgendem Code durchgeführt:

           .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

Die Eingabemodifikation macht ungefähr das Folgende. Die Eingabe:

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

  ------    -----

wird umgewandelt in:

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

Die Werte haben folgende Bedeutung:

  • - Plattform, die noch besucht werden muss
  • = Plattform, die nicht mehr besucht werden muss
  • M Tasse, die mit der Schwerkraft auf "unten" eingegeben werden kann
  • W Tasse, die mit der Schwerkraft auf "up" gestellt werden kann
  • V Sicher, an diesen Ort zu gelangen, wenn die Schwerkraft auf "down" gestellt ist
  • A Sicher, an diesen Ort zu gelangen, wenn die Schwerkraft auf "hoch" eingestellt ist
  • X Sie können sich sicher an diesen Ort bewegen, unabhängig von der Schwerkrafteinstellung
  • 6 Ball an einer Stelle, die als markiert wäre V
  • 9 Ball an einer Stelle, die als markiert wäre A
  • 0 Ball an einer Stelle, die als markiert wäre X

Die Logik verwendet reguläre Ausdrücke, um die Bewegungen auszuführen. Im obigen Beispiel können wir "9A" durch "A9" durch eine Regex ersetzen, um den Ball nach rechts zu bewegen. Das heißt, wenn wir versuchen, die Regex anzuwenden, können wir alle möglichen Bewegungen finden.


Die Funktion Xführt vertikale Kugelbewegungen basierend auf der aktuellen Schwerkrafteinstellung aus, speichert das Ergebnis in globalen Listen Kund Yund prüft, ob eine Lösung gefunden wurde.

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

Die Funktion führt (Überprüfungen für die 4 Richtungs- / Schwerkrafttasten durch. Die Schwerkrafttasten können nur gedrückt werden, wenn sich die aktuelle Schwerkraft ändern würde und wenn sich der Ball an einem sicheren Ort befindet, um die Schwerkraft zu ändern. Die Richtungstasten können nur gedrückt werden, wenn es sicher ist, an die entsprechende Stelle zu gelangen.

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

Endlich die Hauptschleife. Das erste Element von Ywird wiederholt entfernt und es werden alle möglichen Züge überprüft.

#                                                        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
quelle
Habe ich Recht, wenn Sie davon ausgehen, dass jeder Input lösbar ist? Da die Frage weiterhin besagt, dass nicht lösbare Eingaben erkannt werden sollten, deuten die Kommentare jedoch darauf hin, dass jede Eingabe lösbar ist. Ich bin mir nicht sicher, was der Fall ist, obwohl ich glaube, dass Ihr Code keine Unlösbarkeit erkennt.
Jonathan Frech
@JonathanFrech Wenn die Eingabe nicht lösbar ist, erfolgt keine Ausgabe. Wenn alle Möglichkeiten geprüft wurden, ist die YListe leer, der Popup wirft einen Fehler und die #Schleife endet.
Sleafar
1
Wenn Sie die Tasse von der Eingabe entfernen (`/ \`), wird das Rätsel unlösbar (da Sie die Tasse nicht erreichen können), und Ihr Programm generiert dennoch eine Ausgabe.
Jonathan Frech
Ich habe nicht gemeint, was Ihr Programm macht, ich erwähne, dass diese unlösbare Rätseleingabe eine Ausgabe erzeugt.
Jonathan Frech
@ JonathanFrech Sie haben Recht. Ich versuche nur, es zu beheben, aber ich habe Codierungsprobleme mit der komprimierten Zeichenfolge.
Sleafar