Вы находитесь на передовой межгалактической космической станции. Ваш друг, который работает в «Изучении гравитации», только что создал игру, в которой микрогравитация используется для перемещения мяча.

Она вручает вам маленький контроллер с четырьмя стрелками на нем и лабиринтную конструкцию с мячом, сидящим слева. Она начинает объяснять, как работает игра.

• У вас есть 2 кнопки со стрелками, слева <и справа >.
• У вас также есть 2 кнопки гравитации, вверх ^и вниз v(по крайней мере, от вашей системы отсчета)
• Вы будете использовать эти кнопки со стрелками для перемещения мяча на экране.

«Теперь есть некоторые правила, которые необходимо соблюдать». она говорит

1. Все платформы должны быть пройдены, прежде чем добраться до чашки \ /
2. Стрелки < > ^ vбудут использоваться для указания движения мяча
3. Гравитация есть ^ v(вверх и вниз). Это перемещает мяч до следующей платформы в этом направлении. (Расстояние не рассчитывается для вверх и вниз)
4. Потерять мяч - это плохо! Не падайте через край и не переключайте гравитацию слишком рано, чтобы ваш мяч никогда не достиг платформы
5. Движение считается по шагам < >
6. Мяч может войти в чашку с любого направления, если следовать правилу 1
7. Вы должны указать направление гравитации, чтобы ваш шар не уплыл
8. Движение может быть случайным, если следовать правилу 1 и 4
9. Для случаев, которые не могут быть решены, выведите False или Invalid

Простой пример мяча, платформы и чашки:

v
o
---\ /

v>

 o
---\ /

v>>

  o
---\ /

v>>>

   o
---\ /

v>>>>


---\o/

Пример обхода через ту же платформу снова.

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

Пример переключения гравитации

v
   --/ \

o
----

v>
   --/ \

 o
----

v>>
   --/ \

  o
----

v>>>
   --/ \

   o
----

v>>>^
   --/ \
   o

----

v>>>^>
   --/ \
    o

----

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

----

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


----

задача

Ваша задача - создать программу, которая будет использовать ASCII-представление курса в качестве входных данных. И выведите ряд стрелок, <>^vпредставляющих направление и гравитационное притяжение, чтобы переместить шар oчерез все platformsв чашку.

Применяются стандартные правила игры в гольф

Тестовые случаи

Ввод (ситуация, когда гравитация переключается)

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

  ------    -----

Выход

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

Вход (ситуация, когда направление переключается)

       ---
o   
----
    ---

     -----  

    --\ /

Выход

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

Ввод (ситуация, когда вам нужно пройти через одну и ту же платформу дважды)

 o
 ------

  ------

 ------ 

\ /------

Выход

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

Bad Cases, программа должна выводить Falsy для этих

У мяча нет возможности добраться до следующей платформы

o
--- ---

Мяч упал бы в космос

---
o
   ---

Ситуация, когда мяч попадает в кубок, но все платформы не пересекаются.

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

Pyth, 431 байт

Это моя первая программа Pyth (на самом деле это моя первая программа на любом языке кода-гольфа), что означает, что ее, вероятно, еще можно улучшить.

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

Попробуйте это здесь (последний тестовый сценарий требует слишком много времени, он должен быть протестирован с локальной установкой Pyth).

Шестнадцатеричный дамп кода (используйте xxd -r <filename>для декодирования):

00000000: 4a6d 6d63 6b5c 3a63 645c 2563 2e5a 2278  Jmmck\:cd\%c.Z"x
00000010: da55 8eb1 8ac3 400c 447f c58d 2057 2c99  .U....@.D... 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  n.@.t...........
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

объяснение

Основной идеей этой программы было использование регулярных выражений для изменения ввода. Для экономии места все эти регулярные выражения содержатся в сжатой строке. Первый шаг в программе - распаковать строку и разделить ее на одно регулярное выражение и соответствующие замещающие строки.

            .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

Содержимое переменной Jтогда:

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

Функция rприменяет подстановки регулярных выражений из списка, сохраненного в Jиндексе, Gко всем строкам в списке H. Он возвращается, как только любая из строк была изменена.

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

Функция iпохожа на функцию rс двумя отличиями. Он применяет замены в транспонированном списке (вместо вертикального вместо горизонтального). Он также выполняет замены многократно, пока что-либо изменяется.

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

Функция gпроверяет, можно ли найти регулярное выражение из списка, хранящегося в Jиндексе G, в любой строке списка 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

Остальная часть кода содержит реальную логику программы. Он выполняет поиск возможных движений в ширину, пока не будет найдено решение. Положение в дереве поиска однозначно определяется направлением силы тяжести и измененной копией входных данных программы. Чтобы избежать обработки одной и той же позиции снова и снова, обработанные позиции сохраняются в глобальном списке K. Позиции, которые еще предстоит обработать, сохраняются вместе с соответствующей частью решения в списке Y.

Модификация ввода и инициализация Kи Yвыполняется следующим кодом:

           .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

Модификация ввода делает что-то вроде следующего. Вход:

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

  ------    -----

трансформируется в:

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

Значения имеют следующее значение:

• - Платформа, которую еще нужно посетить
• = Платформа, которую больше не нужно посещать
• M Чашка, в которую можно ввести гравитацию, установленную на «вниз»
• W Чашка, в которую можно ввести гравитацию, установленную на «вверх»
• V Безопасно перемещаться в это место с гравитацией, установленной на «вниз»
• A Безопасно перемещаться в это место с гравитацией, установленной на «вверх»
• X Безопасно перемещаться в это место независимо от настроек гравитации
• 6 Мяч на месте, которое будет помечено как V
• 9 Мяч на месте, которое будет помечено как A
• 0 Мяч на месте, которое будет помечено как X

Логика использует регулярные выражения для выполнения движений. В приведенном выше примере, если сила тяжести будет установлена ​​на «вверх», мы можем заменить «9A» на «A9» с помощью регулярного выражения, чтобы переместить шар вправо. Это означает, что, пытаясь применить регулярное выражение, мы можем найти все возможные движения.

Функция Xвыполняет вертикальные движения шарика на основе текущего значения силы тяжести, сохраняют результат в глобальных списках Kи Y, и проверяет , если решение было найдено.

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

Функция (реализует проверки для 4 кнопок направления / гравитации. Кнопки гравитации можно нажимать только в том случае, если текущая сила тяжести изменится, и если мяч находится в безопасном месте, чтобы изменить гравитацию. Кнопки со стрелками можно нажимать только в том случае, если безопасно перейти в соответствующее место.

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

Наконец основной цикл. Первый элемент Yудаляется неоднократно, и проверяются все возможные ходы.

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