Gravity Guy - игра, в которой единственным пользовательским вводом является одиночная клавиша, которая меняет направление гравитации. Учитывая художественный уровень ASCII, определите, возможно ли Gravity Guy достичь конца.

правила

• Начальное направление гравитации вниз .
• Первый столбец ввода всегда будет содержать только один # , над которым начинается Gravity Guy .
• На каждой итерации он перемещается к персонажу прямо справа от него .
• Если его путь заблокирован, и он входит в #, игрок проигрывает .
• После перемещения игрок может при желании переключать гравитацию вниз или вверх или вниз.
• Гравитационный парень затем падает на следующий# (в текущем направлении гравитации).
• Если нет #возможности упасть, и он падает с сетки , игрок проигрывает .
• Если Gravity Guy смещается с правой стороны входной сетки, игрок выигрывает .

пример

Если это была входная сетка:

  ### 

#  # #
 ###  

Гравитационный парень начинал с xэтих позиций после каждой итерации. ^= переключить гравитацию вверх и v= переключить гравитацию вниз.

v                        ^                               v
-------------------------------------------------------------
  ###   |    ###   |    ###   |    ###   |    ###   |    ### 
x       |          |    x     |     x    |      x   |        
#  #    |  #x #    |  #  #    |  #  #    |  #  #    |  #  # x
 ### #  |   ### #  |   ### #  |   ### #  |   ### #  |   ### #

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

Характеристики

• Входная сетка может иметь любой подходящий формат «сетки» (многострочная строка, дополненная пробелами, массив строк, массив символов и т. Д.).
• Если это возможно для игрока , чтобы выиграть уровень, выводить truthyзначение. Если нет, выведите falseyзначение.
• Ширина и высота сетки будут не более 50символов.
• Это код-гольф , пусть победит самый короткий код в байтах!

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

(каждый случай, разделенный ----------пробелами, также должен быть дополнен пробелами)

Правда

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

----------


###

----------

   #####

####    

----------

 #####
 # # #

# # # 
 #####

----------

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

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

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

----------

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

----------

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


----------

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

----------

  ### 

#  # #
 ###  

----------

  ###  ###

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

----------

  #        
     #   # 
       #   
#   #     #
        #  
   #       
      #    
 #         

----------

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

----------

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

Ложь

 ###
   #
####

----------


### ###

----------

    #   
 ### ###

#### ###
    #   

----------

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

----------

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

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

----------

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

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

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

^
\ n\ ,=\#r}+~

0 ^это опция, которая требует запуска шаблона в верхнем левом углу.

1. \ ​: совпадать пространство

2. n: Поворот на 90 градусов в любом направлении

3. \ ,​: совпадать с пробелом ноль или более раз

4. =\#проверьте, что #перед нами

5. r: установите направление вправо

6. }+: сделать все предыдущие один или несколько раз

7. ~ сопоставить ячейку, находящуюся за пределами сетки

Perl, 93 89 81 77 76 75 74 байта

Включает +2 для -0p

Запустите с шаблоном ввода (со всеми пробелами на одной и той же длине) в STDIN:

gravity.pl < gravity.txt

gravity.pl:

#!/usr/bin/perl -0p
/
/;$n=".{@-}";s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es&&redo;$_=m;w

Эта файловая версия нуждается в последнем переводе строки, так что на самом деле это 75 байт. Но версия для командной строки не нуждается в этой дополнительной новой строке, поэтому она считается 74 байтами:

perl -0pe '/
/;$n=".{@-}";s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es&&redo;$_=m;w' < gravity.txt

Объяснение:

Это создаст нить wв каждой позиции, которой может достичь гравитационный парень. Так что для второго до последнего правдивого примера он построит:

     #########   
    ##### ####   
   #wwwww#wwww#  
  #w  # #w ##ww# 
wwwww wwwwwww#ww#
#####  ####  w#ww
     wwwwwwwwww# 
     #########   

Так что гравитационный парень может сделать это, если и только если есть w в последнем столбце. Строка будет построена путем замены одного доступного пространства на wкаждый раунд.

Каждая замена будет иметь вид

s/prefix \K space postfix/ w | $& /e

который потребует, чтобы перед пробелом стоял префикс, а за ним следовал постфикс, но заменил только пробел w без необходимости в расширенной группировке.

Предположим, $nсодержит регулярное выражение, которое будет прогрессировать настолько, что левая и правая стороны будут точно друг под другом. Тогда соответствующие регулярные выражения:

/^( $n)*\K $n#/       From the first position drop down as long as you
                      encounter spaces until you encounter a #. 
                      This puts gravity guy on his starting platform

/#$n\K( $n)*\b /      A space immediately below a # and if you (optionally)
                      go down further from there (as as the descent is
                      over spaces) you get to a space that follows a word
                      boundary. The only way to get a word boundary is if 
                      there is a w in front of that space. This selects the
                      position gravity guy ends up on if starting from that
                      w and gravity is up
/w([w ]$n)*\K $n#/    A w followed by a space (or w) and if you go down from
                      there as long as it is over spaces (or w) you finally
                      end up on a space directly above a #. This handles the
                      gravity down case. The test uses "space or w" instead
                      of just space to handle this case:

                       #
                      ww
                      #x  
                       #

                      Position x is currently a space and must be replaced by a
                      w but the gravity up regex has already put a w directly
                      after the w gravity guy takes off from. So for gravity
                      down we must handle w as if it is still a space. This
                      is not needed for gravity up because regex always matches
                      starting at the earliest possible character, so 
                      gravity up matches before gravity down

С этим легко справиться с программой:

#!/usr/bin/perl -0p   Slurp all of STDIN into $_, at the end print $_

/\n/                  Match the first newline (needed to measure the row
                      length)
$n=".{@-}"            $n effectively becomes rowlength-1 times ".". This
                      will be the regex that goes one step down a column

s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es

                     This is the 3 regexes shown above combined. The s 
                     modifier is needed so the . in $n also matches newline

    &&redo           Keep looping as long as w's keep getting added

$_=m;w\n;            Check if the last column contains a w: He made it!
                     The \n; at the end is not written. These 2 bytes sneakily
                     come from the -p option for the ; and the -e option
                     for the \n

JavaScript (ES6), 174 байта

a=>[...a[0]].map((_,i)=>[...t].map(x=>s[x]<'#'&&g(s.indexOf('#',x),-1)&&g(s.lastIndexOf('#',x),1),s=a.map(s=>s[i]),t=new Set),t=new Set([0]),g=(i,d)=>i<0||t.add(i+d))&&t.size

Принимает горизонтальный массив строк и возвращает количество точек выхода. Транспонирование массива стоит мне 29 байт. Ungolfed:

function gravity(array) {
    var set = new Set;
    set.add(0); // starting point
    for (var i = 0; i < array[0].length; i++) {
        var s = array.map(s => s[i]); // transpose array
        var old = set;
        set = new Set;
        for (var x of old) {
            if (s[x] == '#') continue; // hit wall
            var j = s.indexOf('#', x); // try downward gravity
            if (j >= 0) set.add(j - 1);
            j = s.lastIndexOf('#', x); // try upward gravity
            if (j >= 0) set.add(j + 1);
        }
    }
    return set.size;
}

Пип , 85 68 62 59 + 1 = 60 байт

Использует -rфлаг для чтения всех строк стандартного ввода.

FcZg{YlFxiIc@xQsyPB(Jc@<x@?`# *$`)+1PB(c@>x@?'#)+x-1i:UQy}i

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

Краткое объяснение

Стратегия - это поиск в ширину. Мы транспонируем ввод и зацикливаем строки (столбцы), сохраняя список y-позиций, которые игрок может достичь в этом столбце. Вывод после последнего столбца представляет собой непустой список, если игрок может выиграть, или пустой список (который печатается как только завершающий перевод строки), если игрок проигрывает.

Полное объяснение

Встроенные переменные , используемые в этой программе: i == 0, l == [], s == " ".

-rФлаг помещает список линий ввода в g. FcZg{...}молнии gи петли над каждым столбцом c. (Унарный Z, когда применяется к списку итераций, действует как Python zip(*g), аккуратно перемещая двумерный массив.) Обратите внимание, что cэто будет список, а не строка.

Внутри цикла столбцов мы возвращаемся yк пустому списку с помощью Yanking l. Fxiперебирает i. В последующих итерациях iбудет представлен список y-координат, которые игрок смог достичь в предыдущем столбце. В первый раз, мы хотим начать с просто 0(верхний левый угол). Переменная инициализируется в Scalar 0, а не в List [0], но Pip выполняет итерацию в любом случае.

Для каждой из допустимых позиций в последнем столбце Ic@xQsпроверяется, есть ли пробел в этой позиции в текущем столбце. Если нет, игрок просто врезался в стену, и мы продолжаем пробовать следующую возможность. Если это так, то мы хотим найти позиции, в которые игрок попадет в этот столбец для каждого направления силы тяжести, и добавить их в список yс помощью оператора Push Back.

Повышение силы тяжести (слева, в транспонированной версии):

(Jc@<x@?`# *$`)+1
  c@<x             Slice everything left of x in the column
 J                 Join into a string so we can do a regex search on it
      @?`# *$`     Find index of the last # in this string
(             )+1  The player's index is the space below/to the right of this #

Снижение силы тяжести (справа, в транспонированной версии):

(c@>x@?'#)+x-1
 c@>x              Slice everything right of x in the column
     @?'#          Find index of the first # in this list (no need to join into string)
(        )+x       Translate to index number in entire column
            -1     The player's index is the space above/to the left of this #

Если игрок падает с сетки в определенном направлении, соответствующая @?операция не найдет #и даст ноль. Это недопустимый индекс, и он будет генерировать некоторые предупреждения на следующей итерации, которые, однако, не видны без -wфлага. Для наших целей эти случаи по существу исключены из рассмотрения.

После внутреннего цикла i:UQyберет список yсозданных нами позиций, удаляет дубликаты и присваивает его i. (Устранение дубликатов необходимо, потому что в противном случае список расширяется экспоненциально.) Затем мы переходим к следующему столбцу. Когда мы прошли через все столбцы, если был правильный путь, iбудет непустой список позиций (правда); если нет, то это будет пустой список (фальси).