В мире искусства ASCII есть вода, хэш-стены и буквенные механизмы.

Вы находитесь в комнате, состоящей из хеш-стен ( #знаков):

#######
#     #
#     #
#     #
# ### #
#     #
#######

Вы устанавливаете источник воды S ( Sзнак) и бак для воды E ( Eзнак), который может получать воду из любого направления, но у вас есть только один источник S и один бак E.

#######
#  S  #
#     #
#     #
# ### #
#  E  #
#######

Таким образом, вы должны мудро выбрать, где разместить источник. Вот где вы получаете свои навыки игры в гольф .

Задание

Вы получаете вход, состоящий из строки, представляющей комнату с источником и резервуаром:

#######
#  S  #
#     #
#     #
# ### #
#  E  #
#######

Вы должны выяснить, достигает ли вода в конечном итоге резервуар. Вода стекает вниз, если возможно, влево и вправо, если это возможно. Вода не накапливается, потому что она не идет вверх.

Итак, для вышеприведенного ввода, результат:

#######
#  *  #
#  *  #
#*****#
#*###*#
#**O**#
#######

Вода благополучно достигает резервуара, поэтому вы должны вывести истинное значение.

Но если вода не достигает резервуара:

#######
#S    #
#     #
#  E  #
# ### #
#     #
#######

#######
#*    #
#*    #
#* X  #
#*### #
#*****#
#######

Тогда вы должны вывести ложное значение.

Напишите программу, чтобы решить, достигнет ли вода воды в баке. Ваш код должен быть максимально коротким.

Предположения

• Предположим, что входные данные всегда действительны (вся комната представляет собой закрытую прямоугольную область с S и E).

• Предположим, что в качестве входных данных используется только одна комната.

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

Ваша программа должна вернуть истинное значение для следующих тестовых случаев:

#######
#  S  #
#     #
#     #
# ### #
#  E  #
#######

#######
#  S  #
#     #
#  E  #
#     #
#     #
#######

#######
#     #
#     #
# SE  #
# ### #
#     #
#######

###############################################
#                      S                      #
#                                             #
#                                             #
#                                             #
#               ###############               #
#                                             #
#  ##################     ##################  #
#                                             #
#                                             #
#                    #####                    #
#                      E                      #
###############################################

#######
#  S  #
#     #
#     #
# ### #
#   # #
### ###
## E ##
#     #
#######

Но ложное значение для следующих тестовых случаев:

#######
#S    #
#     #
#  E  #
# ### #
#     #
#######

#######
#     #
# SE  #
#     #
#     #
#     #
#######

#######
#     #
#  E  #
#     #
#  S  #
#     #
#######

####################################
#                                  #
#                                  #
#                                  #
#S             #                  E#
####################################

Комната со второй по последнюю в категории «Истина» и последняя комната в категории «Ложь» были бесстыдно украдены, позаимствованные у Кота: Прыгай и беги , Ману (который удалил пост песочницы).

Последняя комната в категории «Истина» взята из ответа Мартина Буттнера в «Retina» .

Улитки , 20 байт

\S{d(=\#n)?^#},!(t\E

Печать 0для значения falsey и 1для значения truthy.

Попробуйте онлайн!

• \Sматчи Sв начале
• d устанавливает направление вниз
• {...}, соответствует материал в скобках 0 или более раз
• =\#является утверждением, которое успешно выполняется, если #перед улиткой есть символ, но не перемещает его
• n поворачивается на 90 градусов в любом направлении
• (...)? соответствует шаблону в скобках 0 или 1 раз
• \ ​ соответствует пробелу и перемещает улитку на него
• !(... это негативное утверждение
• t телепортируется на любой непревзойденный квадрат в сетке
• \E Матчи E

Slip , 20 + 2 = 22 байта

S>( ^4|^4(?|`#)^T)*E

Так что Слип все так же сломлен, как и раньше, но на этот раз это был вызов, который он действительно мог сделать. Хотя он никогда не создавался таким образом, чтобы играть в гольф, поэтому он никогда не победит Улитки: P

Требуется rфлаг (без повторяющихся ячеек) для завершения.

Попробуйте онлайн . Выход - путь, выбранный для правды, пустой для ложного.

S                 Match S
>                 Rotate pointer downward
(                 Either...
 <space>^4          Match a space and point downwards
 |                  or
 ^4                 Point downwards
 (?|`#)             Match # below then reset pointer
 ^T                 Either turn left or right
)*                ... 0+ times
E                 Match E

Сетчатка , 87 байт

Количество байтов предполагает кодировку ISO 8859-1.

+mT`E `S`(?<=^(?(1)!)(?<-1>.)*S.*¶(.)*)[E ]|.?S(?=(.)*¶.*#(?<-2>.)*(?(2)!)$)[E ]?
M`E
0

Попробуйте онлайн!

Столько, сколько возможна обработка 2D строк в Retina (или в регулярных выражениях .NET), это не совсем кратко ...

объяснение

+mT`E `S`(?<=^(?(1)!)(?<-1>.)*S.*¶(.)*)[E ]|.?S(?=(.)*¶.*#(?<-2>.)*(?(2)!)$)[E ]?

Это заливка, которая отмечает все клетки, которые достигаются водой S. Это делается путем сопоставления символов, которые могут быть достигнуты, а затем транслитерации их Sс T-mode. Эта заливка проходит через оба пространства и E. В +начале это повторяется до тех пор, пока выход не перестанет изменяться.

Что касается фактического регулярного выражения, содержит два отдельных случая:

(?<=^(?(1)!)(?<-1>.)*S.*¶(.)*)[E ]

Это соответствует пробелу или Eкоторый точно на одну клетку ниже S. Вертикальное соответствие выполняется путем подсчета префикса в текущей строке с использованием групп балансировки, чтобы мы могли убедиться, что горизонтальное положение одинаково. Этот заботится о падении воды.

.?S(?=(.)*¶.*#(?<-2>.)*(?(2)!)$)[E ]?

Это очень похоже: он соответствует Sи, если доступно, символу до и после него, при условии, что символ непосредственно под символом Sa #. Это заботится о распространении воды по земле.

Когда мы закончим, очень легко определить, достигла ли вода E. Если это так, то Eон был удален из строки в заливке, а если нет, то Eвсе еще там. Итак, давайте посчитаем количество Eс:

M`E

Но теперь это 0(что я бы назвал фальшивкой) для тестов на правдивость и 1(что я бы назвал правдивыми) для тестов на ложь. Мы можем очень легко инвертировать это, посчитав число 0s в этом результате:

0

Выполнено.