microgravedad bola

33

Estás en una estación espacial intergaláctica avanzada. Un amigo tuyo que se está especializando en el Estudio de la gravedad acaba de crear un juego que implica usar la microgravedad como una forma de mover una pelota.

Te entrega un pequeño controlador con cuatro flechas direccionales y una estructura tipo laberinto con una pelota a la izquierda. Ella comienza a explicar cómo funciona el juego.

  • Tienes 2 botones direccionales, izquierdo <y derecho >.
  • También tiene 2 botones de gravedad, arriba ^y abajo v(al menos desde su marco de referencia)
  • Utilizará estos botones de flecha para mover la bola en su pantalla.

"Ahora hay algunas reglas que deben seguirse". ella dice

  1. Todas las plataformas deben atravesarse antes de llegar a la copa. \ /
  2. Las flechas < > ^ vse usarán para especificar el movimiento de la pelota.
  3. La gravedad es ^ v(arriba y abajo). Esto mueve la pelota hasta la siguiente plataforma en esa dirección. (La distancia no se calcula para arriba y abajo)
  4. ¡Perder la pelota es malo! No caigas por el borde y no cambies la gravedad demasiado pronto para que tu pelota nunca llegue a una plataforma
  5. El movimiento se cuenta en pasos de < >
  6. La pelota puede entrar en la copa desde cualquier dirección siempre que se siga la Regla 1
  7. Debes especificar la dirección de la gravedad para que tu bola no se aleje flotando
  8. El movimiento puede ser aleatorio siempre que se sigan las reglas 1 y 4
  9. Para casos que no se pueden resolver, salida Falso o Inválido

Ejemplo simple de una pelota, plataforma y copa:

v
o
---\ /

v>

 o
---\ /

v>>

  o
---\ /

v>>>

   o
---\ /

v>>>>


---\o/

Ejemplo de atravesar nuevamente la misma plataforma.

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

Ejemplo de cambio de gravedad

v
   --/ \

o
----

v>
   --/ \

 o
----

v>>
   --/ \

  o
----

v>>>
   --/ \

   o
----

v>>>^
   --/ \
   o

----

v>>>^>
   --/ \
    o

----

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

----

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


----

Tarea

Su tarea es crear un programa que tome una representación ASCII de un curso como entrada. Y genera una serie de flechas que <>^vrepresentan la dirección y la atracción gravitacional para mover una bola a otravés de platformsuna taza.

Aplican reglas estándar de golf de código

Casos de prueba

Entrada (una situación en la que se cambia la gravedad)

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

  ------    -----

Salida

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

ingrese la descripción de la imagen aquí


Entrada (una situación donde se cambia la dirección)

       ---
o   
----
    ---

     -----  

    --\ /

Salida

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

ingrese la descripción de la imagen aquí


Entrada (una situación en la que necesita atravesar la misma plataforma dos veces)

 o
 ------

  ------

 ------ 

\ /------

Salida

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

ingrese la descripción de la imagen aquí


Casos incorrectos, el programa debería generar Falsy para estos

No hay forma de que la pelota llegue a la siguiente plataforma

o
--- ---

La bola flotaría en el espacio

---
o
   ---

Una situación en la que la pelota llega a la copa, pero no se atraviesan todas las plataformas.

o
----
    ----
        \ /----
tisaconundrum
fuente
44
La regla 1 hace que esto sea bastante desafiante ... hmmm ...
JungHwan Min
¿El rompecabezas siempre será solucionable? Además, creo que debería incluir un caso de prueba que requiera retroceder.
FryAmTheEggman
Sí, los rompecabezas siempre deben poder resolverse. Los huecos o saltos que pierden la pelota o las situaciones que hacen que el laberinto sea insoluble no se harán.
tisaconundrum
44
@JungHwanMin La regla 1 es exactamente por qué esto es un desafío y no trivial.
Erik the Outgolfer
2
Nunca me he sentido tan lejos por una madriguera de conejo en una pregunta de
codegolf

Respuestas:

11

Pyth, 431 bytes

Este es mi primer programa Pyth (en realidad este es mi primer programa en cualquier lenguaje de código de golf), lo que significa que probablemente todavía se puede mejorar.

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

Pruébelo aquí (el último caso de prueba necesita demasiado tiempo, debe probarse con una instalación local de Pyth).

Volcado hexadecimal del código (usar xxd -r <filename>para decodificar):

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

Explicación

La idea principal de este programa era usar expresiones regulares para modificar la entrada. Para ahorrar espacio, todas estas expresiones regulares están contenidas en una cadena comprimida. El primer paso en el programa es descomprimir la cadena y dividirla en una sola expresión regular y las cadenas de reemplazo correspondientes.

            .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

Los contenidos de la variable Json entonces:

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

La función raplica sustituciones de expresiones regulares de la lista almacenada en Jel índice Ga todas las cadenas de la lista H. Regresa tan pronto como se cambie cualquiera de las cadenas.

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

La función ies similar a la función rcon 2 diferencias. Aplica las sustituciones en una lista transpuesta (vertical en lugar de horizontal). También realiza las sustituciones repetidamente siempre que se cambie algo.

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

La función gverifica si la expresión regular de la lista almacenada en Jel índice Gpuede encontrarse en cualquier cadena de la lista 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

El resto del código contiene la lógica real del programa. Realiza una búsqueda amplia de los posibles movimientos hasta encontrar una solución. La posición en el árbol de búsqueda se define únicamente por la dirección de la gravedad y una copia modificada de la entrada del programa. Para evitar el procesamiento de la misma posición una y otra vez, las posiciones procesadas se almacenan en la lista global K. Las posiciones que aún deben procesarse se almacenan junto con la parte correspondiente de la solución en la lista Y.

La modificación de la entrada e inicialización de Ky Yse realiza mediante el siguiente código:

           .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

La modificación de entrada hace algo como lo siguiente. La entrada:

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

  ------    -----

se transforma en:

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

Los valores tienen el siguiente significado:

  • - Plataforma que aún debe visitarse
  • = Plataforma que ya no necesita ser visitada
  • M Copa que se puede ingresar con la gravedad ajustada a "abajo"
  • W Copa que se puede ingresar con la gravedad configurada en "arriba"
  • V Es seguro mudarse a este lugar con la gravedad configurada en "abajo"
  • A Es seguro mudarse a este lugar con la gravedad configurada en "arriba"
  • X Es seguro moverse a este lugar independientemente de la configuración de gravedad
  • 6 Bola en un lugar que se marcaría como V
  • 9 Bola en un lugar que se marcaría como A
  • 0 Bola en un lugar que se marcaría como X

La lógica es usar expresiones regulares para realizar los movimientos. En el ejemplo anterior, si la gravedad se configurara como "arriba", podemos reemplazar "9A" con "A9" con una expresión regular para mover la pelota hacia la derecha. Esto significa que al intentar aplicar la expresión regular podemos encontrar todos los movimientos posibles.


La función Xrealiza movimientos verticales de bolas en base a la configuración de la gravedad actual, almacena el resultado en las listas globales Ky Y, y comprueba si se ha encontrado una solución.

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

La función (implementa controles para los 4 botones direccionales / de gravedad. Los botones de gravedad se pueden presionar solo si la gravedad actual cambiaría y si la pelota está en un lugar seguro para cambiar la gravedad. Los botones de dirección solo se pueden presionar si es seguro moverse al lugar correspondiente.

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

Finalmente el bucle principal. El primer elemento de Yse elimina repetidamente y se realizan comprobaciones de todos los movimientos posibles.

#                                                        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
fuente
¿Estoy en lo cierto al pensar que asumes que cada entrada es solucionable? Debido a que la pregunta aún dice que se deben detectar entradas insolubles, los comentarios, sin embargo, sugieren que cada entrada será solucionable. No estoy seguro de cuál es el caso, aunque creo que su código no detecta insolubilidad.
Jonathan Frech
@ JonathanFrech Si la entrada no tiene solución, no habrá salida. Cuando se verificaron todas las posibilidades, la Ylista estará vacía, la ventana emergente arrojará un error y el #ciclo finalizará.
Sleafar
1
Cuando retira la copa de la entrada (`/ \`), el rompecabezas se vuelve insoluble (ya que no puede alcanzar la copa) pero su programa aún genera una salida.
Jonathan Frech
No quise decir lo que hace su programa, menciono que esta entrada de rompecabezas sin solución genera una salida.
Jonathan Frech
@ JonathanFrech Tienes razón. Solo estoy tratando de arreglarlo, pero tengo problemas de codificación con la cadena comprimida.
Sleafar