¿Puede Gravity Guy hacerlo?

27

Gravity Guy es un juego en el que la única entrada del usuario es una sola tecla que invierte la dirección de la gravedad. Dado un nivel de arte ASCII, determine si es posible que Gravity Guy llegue al final.


Reglas

  • La dirección inicial de la gravedad es hacia abajo .
  • La primera columna de la entrada siempre contendrá solo una # , sobre la cual Gravity Guy comienza .
  • Cada iteración, se mueve al personaje directamente a su derecha .
  • Si su camino está bloqueado y se mueve hacia a #, el jugador pierde .
  • Después de moverse, el jugador puede cambiar opcionalmente la gravedad de abajo hacia arriba o de arriba hacia abajo.
  • Gravity Guy luego pasa a la siguiente# (en la dirección de gravedad actual).
  • Si no hay #que caer y él se cae de la red , el jugador pierde .
  • Si Gravity Guy se mueve del lado derecho de la cuadrícula de entrada, el jugador gana .

Ejemplo

Si esta fue la cuadrícula de entrada:

  ### 

#  # #
 ###  

Gravity Guy comenzaría en el xy el estar en estas posiciones después de cada iteración. ^= cambiar la gravedad a arriba y v= cambiar la gravedad a abajo.

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

Como puede ver, al cambiar la gravedad en estos momentos, Gravity Guy llega al final, por lo que esta entrada devolvería un valor verdadero.

Presupuesto

  • La cuadrícula de entrada puede estar en cualquier formato de "cuadrícula" apropiado (cadena multilínea rellenada con espacios, matriz de cadenas de línea, matriz de matriz de caracteres, etc.).
  • Si es posible que el jugador gane el nivel, genera un truthyvalor. Si no, emite un falseyvalor.
  • El ancho y la altura de la cuadrícula serán 50caracteres como máximo.
  • Este es el , ¡que gane el código más corto en bytes!

Casos de prueba

(cada caso separado por ----------, cualquier línea en blanco también debe rellenarse con espacios)

Cierto

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

----------


###

----------

   #####

####    

----------

 #####
 # # #

# # # 
 #####

----------

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

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

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

----------

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

----------

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


----------

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

----------

  ### 

#  # #
 ###  

----------

  ###  ###

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

----------

  #        
     #   # 
       #   
#   #     #
        #  
   #       
      #    
 #         

----------

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

----------

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

Falso

 ###
   #
####

----------


### ###

----------

    #   
 ### ###

#### ###
    #   

----------

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

----------

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

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

----------

 ########################### 
 #   #   #   #  #  #   #   # 
 # # # #   #   # #   #   # # 
 # # # ######### ########### 
 # # # #  #       #     #  # 
   # # # ## ##### ### #      
## #   #    #          ## ###
 # ##### #### ###########  # 
 # #     #  #     #     ## # 
 # # #####  ### # # # # #  # 
 #              #   # #   ## 
 ########################### 
usuario81655
fuente
¿Se nos permite la cuadrícula en formato de columnas?
Neil
@Neil ¿Te refieres a una matriz transpuesta / rotada? Voy a decir que no, ya que está alterando la entrada. Pero si su idioma tiene un columntipo especial , estaría bien usar, supongo.
user81655
¿Es posible que #en la primera columna esté en la primera fila?
feersum
@feersum No, puede suponer la red incluirá espacio para el tipo gravedad a "stand" en.
user81655
Vergüenza; la transposición aumenta mi recuento de bytes en un 20%.
Neil

Respuestas:

19

Caracoles , 15 bytes

Pruébalo en línea?

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

0. ^es una opción que requiere que el patrón comience en la esquina superior izquierda.

  1. \ ​: espacio de partido

  2. n: Gire 90 grados en cualquier dirección

  3. \ ,​: coincide con el espacio cero o más veces

  4. =\#compruebe que hay un #frente de nosotros

  5. r: establecer la dirección a la derecha

  6. }+: hacer todo lo anterior una o más veces

  7. ~ coincidir con una celda que está fuera de los límites de la cuadrícula

Feersum
fuente
Esto da 0 para la mayoría de los casos de prueba True
Bassdrop Cumberwubwubwub
@Bas ¿Has rellenado las líneas vacías con espacios?
Martin Ender
@ MartinBüttner Copié directamente algunas de las entradas y, de hecho, eliminé algunos de los espacios. Funciona de hecho después de agregar espacios
Bassdrop Cumberwubwubwub
55
Como nadie lo ha dicho todavía: ¡Esto es impresionante!
DLosc
9

Perl, 93 89 81 77 76 75 74 bytes

Incluye +2 para -0p

Ejecute con el patrón de entrada (con todas las líneas espaciadas en la misma longitud) en 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 versión basada en archivo necesita la nueva línea final, por lo que en realidad son 75 bytes. Pero la versión basada en la línea de comandos no necesita esa nueva línea adicional, por lo que cuenta como 74 bytes:

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

Explicación:

Esto construirá una cadena con una wen cada posición que el tipo de gravedad puede alcanzar. Entonces, para el penúltimo ejemplo de verdad construirá:

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

Entonces, el tipo de gravedad puede hacerlo si y solo si hay un wen la última columna. La cadena se construirá reemplazando un espacio accesible por wen cada ronda.

Cada reemplazo será de la forma

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

lo que exigirá que el espacio esté precedido por un prefijo y seguido de postfix, pero reemplace solo el espacio wsin necesidad de mucha agrupación avanzada.

Suponga que $ncontiene una expresión regular que progresará lo suficiente como para que los lados izquierdo y derecho estén exactamente uno debajo del otro. Entonces las expresiones regulares relevantes son:

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

Con eso fuera del camino, el programa es 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
fuente
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 una matriz horizontal de cadenas y devuelve el número de puntos de salida. La transposición de la matriz me cuesta 29 bytes. Sin golf:

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
fuente
3

Pip , 85 68 62 59 + 1 = 60 bytes

Utiliza la -rbandera para leer todas las líneas de stdin.

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

Pruébalo en línea!

Breve explicacion

La estrategia es esencialmente una búsqueda de amplitud. Transponemos la entrada y el bucle sobre las líneas (columnas), manteniendo una lista de las posiciones y que el jugador podría alcanzar en esa columna. La salida después de la última columna es una lista no vacía si el jugador puede ganar, o una lista vacía (que se imprime como una nueva línea final) si el jugador pierde.

Explicación completa

Una función de las variables utilizadas en este programa: i == 0, l == [], s == " ".

La -rbandera pone una lista de las líneas de entrada g. FcZg{...}cremalleras gy bucles sobre cada columna c. (Unary Z, cuando se aplica a una lista de iterables, actúa como Python zip(*g), transponiendo perfectamente una matriz 2D). Tenga en cuenta que cserá una lista, no una cadena.

Dentro del bucle de la columna, restablecemos yla lista vacía Yanking l. Fxibucles más i. En iteraciones posteriores, ihabrá una lista de las coordenadas y que el jugador pudo alcanzar en la columna anterior. La primera vez, queremos comenzar con solo 0(esquina superior izquierda). La variable se preinicializa en un escalar 0, no en una lista [0], pero Pip lo repite de cualquier manera.

Para cada una de las posiciones válidas en la última columna, Ic@xQsverifica si hay un espacio en esa posición en la columna actual. Si no, el jugador simplemente se topó con una pared y seguimos probando la siguiente posibilidad. Si es así, entonces queremos encontrar las posiciones a las que caerá el jugador en esta columna para cada dirección de gravedad, y agregarlas a la lista yusando el operador Push Back.

Gravedad hacia arriba (izquierda, en la versión transpuesta):

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

Gravedad bajando (derecha, en la versión transpuesta):

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

Si el jugador se cae de la cuadrícula en una dirección particular, la @?operación respectiva no encontrará un #y dará cero. Este no es un índice válido y generará algunas advertencias en la próxima iteración, que, sin embargo, no son visibles sin la -wbandera. Para nuestros propósitos, estos casos se eliminan esencialmente de la consideración.

Después del ciclo interno, i:UQytoma la lista yde posiciones que hemos construido, elimina duplicados y se la asigna i. (Es necesario eliminar los duplicados porque, de lo contrario, la lista se hincha exponencialmente). Luego pasamos a la siguiente columna. Cuando hayamos recorrido todas las columnas, si hubiera una ruta válida, ihabrá una lista de posiciones no vacía (verdad); si no, será una lista vacía (falsey).

DLosc
fuente