Cara da gravidade pode fazer isso?

27

Gravity Guy é um jogo em que a única entrada do usuário é uma única tecla que muda a direção da gravidade. Dado um nível artístico ASCII, determine se é possível que o Gravity Guy chegue ao fim.


Regras

  • A direção inicial da gravidade está baixa .
  • A primeira coluna da entrada sempre conterá apenas uma # , na qual o Gravity Guy inicia .
  • Cada iteração, ele se move para o personagem diretamente à sua direita .
  • Se o caminho dele estiver bloqueado e ele entrar em um #, o jogador perde .
  • Depois de se mover, o jogador pode opcionalmente mudar a gravidade de baixo para cima ou de cima para baixo.
  • O Gravity Guy então cai para o próximo# (na direção atual da gravidade).
  • Se não houver #alguém para cair e ele cair fora da grade , o jogador perde .
  • Se o Gravity Guy se mover do lado direito da grade de entrada, o jogador vence .

Exemplo

Se essa era a grade de entrada:

  ### 

#  # #
 ###  

O Gravity Guy começaria nas xposições e estar nessas posições após cada iteração. ^= alternar a gravidade para cima e v= alternar a gravidade para baixo.

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

Como você pode ver, alternando a gravidade nesses momentos, o Gravity Guy chega ao fim, para que essa entrada retorne um valor verdadeiro.

Especificações

  • A grade de entrada pode estar em qualquer formato de "grade" apropriado (cadeia de linhas múltiplas preenchida com espaços, matriz de cadeias de linhas, matriz de matriz de caracteres, etc.).
  • Se for possível ao jogador vencer o nível, produza um truthyvalor. Caso contrário, imprima um falseyvalor.
  • A largura e a altura da grade terão 50no máximo caracteres.
  • Este é o , que o código mais curto em bytes vença!

Casos de teste

(cada caso separado por ----------, qualquer linha em branco também deve ser preenchida com espaços)

Verdade

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

----------


###

----------

   #####

####    

----------

 #####
 # # #

# # # 
 #####

----------

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

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

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

----------

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

----------

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


----------

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

----------

  ### 

#  # #
 ###  

----------

  ###  ###

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

----------

  #        
     #   # 
       #   
#   #     #
        #  
   #       
      #    
 #         

----------

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

----------

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

Falso

 ###
   #
####

----------


### ###

----------

    #   
 ### ###

#### ###
    #   

----------

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

----------

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

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

----------

 ########################### 
 #   #   #   #  #  #   #   # 
 # # # #   #   # #   #   # # 
 # # # ######### ########### 
 # # # #  #       #     #  # 
   # # # ## ##### ### #      
## #   #    #          ## ###
 # ##### #### ###########  # 
 # #     #  #     #     ## # 
 # # #####  ### # # # # #  # 
 #              #   # #   ## 
 ########################### 
user81655
fonte
A grade é permitida no formato colunar?
Neil
@ Neil Você quer dizer uma matriz transposta / girada? Vou dizer não, pois está alterando a entrada. Mas se o seu idioma tiver um columntipo especial , seria bom usá-lo, eu acho.
user81655
É possível que a #primeira coluna esteja na primeira linha?
precisa saber é
@feersum Não, você pode assumir a grade irá incluir espaço para a cara gravidade "estar" no.
user81655
Vergonha; a transposição aumenta minha contagem de bytes em 20%.
Neil

Respostas:

19

Caracóis , 15 bytes

Experimente online?

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

0 ^é uma opção que requer que o padrão inicie no canto superior esquerdo.

  1. \ ​: corresponder espaço

  2. n: Gire 90 graus em qualquer direção

  3. \ ,​: corresponde ao espaço zero ou mais vezes

  4. =\#verifique se há um #na nossa frente

  5. r: defina a direção para a direita

  6. }+: faça todas as uma ou mais vezes anteriores

  7. ~ corresponde a uma célula que está fora dos limites da grade

feersum
fonte
Isso dá a 0 para a maioria dos casos de teste Verdadeiros
Bassdrop Cumberwubwubwub
@ Bas Você acolchoou as linhas vazias com espaços?
Martin Ender
@ MartinBüttner Copiei diretamente algumas das entradas, removendo alguns dos espaços. Ele funciona de fato após espaços acrescentando
Bassdrop Cumberwubwubwub
5
Como ninguém disse ainda: Isso é incrível!
DLosc
9

Perl, 93 89 81 77 76 75 74 bytes

Inclui +2 para -0p

Execute com o padrão de entrada (com todas as linhas de espaço preenchidas no mesmo comprimento) em 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

Esta versão baseada em arquivo precisa da nova linha final, ou seja, é de 75 bytes. Mas a versão baseada em linha de comando não precisa dessa nova linha extra, portanto conta como 74 bytes:

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

Explicação:

Isso construirá uma string com um wem cada posição que a gravidade pode alcançar. Portanto, para o penúltimo exemplo de verdade, ele construirá:

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

Então, o cara da gravidade pode fazê-lo se e somente se houver um w na última coluna. A sequência será construída substituindo um espaço acessível por wcada rodada.

Cada substituição terá o formato

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

que exigirá que o espaço seja precedido por prefixo e seguido pelo postfix, mas substitua apenas o espaço por w sem a necessidade de muitos agrupamentos avançados.

Suponha que $ncontenha uma regex que progredirá apenas o suficiente para que os lados esquerdo e direito estejam exatamente abaixo um do outro. As regexes relevantes são:

/^( $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

Com isso fora do caminho, o programa é fácil:

#!/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
Ton Hospel
fonte
3

JavaScript (ES6), 174 bytes

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

Toma uma matriz horizontal de seqüências de caracteres e retorna o número de pontos de saída. Transpor a matriz custa 29 bytes. 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;
}
Neil
fonte
3

Pip , 85 68 62 59 + 1 = 60 bytes

Usa a -rbandeira para ler todas as linhas de stdin.

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

Experimente online!

Breve explicação

A estratégia é essencialmente uma busca pela primeira vez. Transpomos a entrada e fazemos um loop pelas linhas (colunas), mantendo uma lista das posições em y que o jogador pode alcançar nessa coluna. A saída após a última coluna é uma lista não-vazia, se o jogador puder vencer, ou uma lista vazia (que imprime apenas como uma nova linha à direita), se o jogador perder.

Explicação completa

Built-in variáveis utilizadas neste programa: i == 0, l == [], s == " ".

A -rbandeira coloca uma lista das linhas de entrada g. FcZg{...}fecha ge fecha sobre cada coluna c. (Unário Z, quando aplicado a uma lista de iteráveis, age como Python zip(*g), transpondo ordenadamente uma matriz 2D.) Observe que cserá uma lista, não uma string.

Dentro do loop da coluna, redefinimos ya lista vazia por Yanking l. Fxidá uma volta i. Nas iterações posteriores, ihaverá uma lista das coordenadas y que o jogador conseguiu alcançar na coluna anterior. Na primeira vez, queremos começar com apenas 0(canto superior esquerdo). A variável é pré-inicializada para um escalar 0, não para uma lista[0] , mas o Pip faz uma iteração muito boa de qualquer maneira.

Para cada uma das posições válidas na última coluna, Ic@xQsverifica se há um espaço nessa posição na coluna atual. Caso contrário, o jogador simplesmente colidiu contra uma parede e tentamos a próxima possibilidade. Nesse caso, queremos encontrar as posições nas quais o jogador cairá nesta coluna para cada direção da gravidade e adicioná-las à lista yusando o PushB operador ack.

Gravidade subindo (esquerda, na versão transposta):

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

Gravidade diminuindo (à direita, na versão transposta):

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

Se o jogador cair da grade em uma direção específica, a @?operação respectiva não encontrará #ae dará zero. Este não é um índice válido e irá gerar alguns avisos na próxima iteração - que, no entanto, não são visíveis sem o-w sinalizador. Para nossos propósitos, esses casos são essencialmente eliminados de consideração.

Após o loop interno, i:UQypega a lista yde posições que construímos, elimina duplicatas e as atribui i. (A eliminação de duplicatas é necessária porque, caso contrário, a lista aumenta exponencialmente.) Em seguida, vamos para a próxima coluna. Quando percorrermos todas as colunas, se houver um caminho válido, ihaverá uma lista não vazia de posições (verdade); caso contrário, será uma lista vazia (falsey).

DLosc
fonte