Você está em uma estação espacial intergaláctica avançada. Um amigo seu, que é menor no Study of Gravity, acabou de criar um jogo que envolve o uso da microgravidade como uma maneira de movimentar uma bola.

Ela entrega um pequeno controle com quatro setas direcionais e um labirinto com uma bola à esquerda. Ela começa a explicar como o jogo funciona.

• Você tem 2 botões direcionais, esquerdo <e direito >.
• Você também tem 2 botões de gravidade, para cima ^e para baixo v(pelo menos a partir do seu quadro de referência)
• Você usará esses botões de seta para mover a bola na tela.

"Agora, existem algumas regras que precisam ser seguidas." ela diz

1. Todas as plataformas devem ser atravessadas antes de chegar ao copo \ /
2. As setas < > ^ vserão usadas para especificar o movimento da bola
3. A gravidade é ^ v(para cima e para baixo). Isso move a bola até a próxima plataforma nessa direção. (A distância não é calculada para cima e para baixo)
4. Perder a bola é ruim! Não caia sobre a borda e não mude a gravidade tão cedo que sua bola nunca chega a uma plataforma
5. O movimento é contado em etapas de < >
6. A bola pode entrar no copo de qualquer direção, desde que a Regra 1 seja seguida
7. Você deve especificar a direção da gravidade para que sua bola não flutue
8. O movimento pode ser aleatório, desde que sejam seguidas as Regras 1 e 4
9. Para casos que não podem ser resolvidos, imprima Falso ou Inválido

Exemplo simples de bola, plataforma e copo:

v
o
---\ /

v>

 o
---\ /

v>>

  o
---\ /

v>>>

   o
---\ /

v>>>>


---\o/

Exemplo de atravessar a mesma plataforma novamente.

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

Exemplo de mudança de gravidade

v
   --/ \

o
----

v>
   --/ \

 o
----

v>>
   --/ \

  o
----

v>>>
   --/ \

   o
----

v>>>^
   --/ \
   o

----

v>>>^>
   --/ \
    o

----

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

----

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


----

Tarefa

Sua tarefa é criar um programa que terá como representação uma representação ASCII de um curso. E saída de uma série de setas <>^vque representam a direção ea força gravitacional para mover uma bola oem todos platformsem um copo.

Aplicam-se regras de golfe de código padrão

Casos de teste

Entrada (uma situação em que a gravidade está sendo alterada)

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

  ------    -----

Saída

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

Entrada (uma situação em que a direção está sendo alterada)

       ---
o   
----
    ---

     -----  

    --\ /

Saída

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

Entrada (uma situação em que você precisa atravessar a mesma plataforma duas vezes)

 o
 ------

  ------

 ------ 

\ /------

Saída

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

Casos ruins, o programa deve gerar Falsy para esses

Não há como a bola chegar à próxima plataforma

o
--- ---

A bola flutuaria para o espaço

---
o
   ---

Uma situação em que a bola chega ao copo, mas todas as plataformas não são atravessadas.

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

Pitão, 431 bytes

Este é o meu primeiro programa Pyth (na verdade, este é o meu primeiro programa em qualquer linguagem de código-golfe), o que significa que provavelmente ainda pode ser aprimorado.

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

Experimente aqui (o último caso de teste precisa de muito tempo, deve ser testado com uma instalação local do Pyth).

Despejo hexadecimal do código (use 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

Explicação

A idéia principal desse programa era usar expressões regulares para modificar a entrada. Para economizar espaço, todas essas expressões regulares estão contidas em uma sequência compactada. A primeira etapa do programa é descompactar a string e dividi-la na expressão regular única e nas strings de substituição correspondentes.

            .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

O conteúdo da variável Jé então:

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

A função raplica substituições de expressões regulares da lista armazenada no Jíndice Ga todas as seqüências de caracteres na lista H. Ele retorna assim que qualquer uma das cadeias de caracteres foi alterada.

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

A função ié semelhante à função rcom 2 diferenças. Aplica as substituições em uma lista transposta (vertical em vez de horizontal). Também realiza as substituições repetidamente, desde que alguma coisa seja alterada.

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

A função gverifica se o regex da lista armazenada no Jíndice Gpode ser encontrado em qualquer sequência da 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

O restante do código contém a lógica real do programa. Ele realiza uma pesquisa abrangente dos possíveis movimentos até encontrar uma solução. A posição na árvore de pesquisa é definida exclusivamente pela direção da gravidade e uma cópia modificada da entrada do programa. Para evitar o processamento da mesma posição repetidamente, as posições processadas são armazenadas na lista global K. As posições que ainda precisam ser processadas são armazenadas junto com a parte correspondente da solução na lista Y.

A modificação da entrada e inicialização de Ke Yé realizada pelo seguinte 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

A modificação de entrada faz algo como o seguinte. A entrada:

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

  ------    -----

é transformado em:

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

Os valores têm o seguinte significado:

• - Plataforma que ainda deve ser visitada
• = Plataforma que não precisa mais ser visitada
• M Copo que pode ser inserido com a gravidade ajustada em "para baixo"
• W Copo que pode ser inserido com a gravidade ajustada para "up"
• V É seguro mover-se para este local com a gravidade definida como "para baixo"
• A É seguro mover-se para este local com a gravidade definida como "up"
• X É seguro mover-se para este local, independentemente da configuração da gravidade
• 6 Bola em um local que seria marcado como V
• 9 Bola em um local que seria marcado como A
• 0 Bola em um local que seria marcado como X

A lógica está usando expressões regulares para executar os movimentos. No exemplo acima, se a gravidade for configurada para "up", podemos substituir "9A" por "A9" por um regex para mover a bola para a direita. Isso significa que, ao tentar aplicar a regex, podemos encontrar todos os movimentos possíveis.

A função Xexecuta movimentos da bola verticais com base na definição de gravidade atual, armazena o resultado em listas globais Ke Y, e verifica se uma solução foi encontrada.

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

A função (implementa verificações nos 4 botões direcionais / de gravidade. Os botões de gravidade podem ser pressionados apenas se a gravidade atual mudar e se a bola estiver em um local seguro para alterar a gravidade. Os botões direcionais podem ser pressionados apenas se for seguro mover para o local correspondente.

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, o loop principal. O primeiro elemento de Yé removido repetidamente e são realizadas verificações de todos os movimentos possíveis.

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