Alineación en rejillas triangulares

18

Las cuadrículas hexagonales se han convertido recientemente en un giro bastante popular para los desafíos sobre los datos bidimensionales. Sin embargo, parece que las redes triangulares igualmente interesantes se han descuidado en gran medida hasta ahora. Me gustaría rectificar eso con un desafío bastante simple.

Primero, ¿cómo representamos una cuadrícula triangular? Considere el siguiente ejemplo (ignore el diagrama correcto por ahora):

ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

Las celdas caen perfectamente en una cuadrícula regular (la diferencia con una cuadrícula regular es solo qué celdas se consideran adyacentes):

1234567
89abcde
fghijkl
mnopqrs

Ahora, como muestra el diagrama de la derecha, una cuadrícula triangular tiene tres ejes principales: uno horizontal y dos diagonales.

Destacando estos en la cuadrícula ASCII:

AVAVAVA
VAabcAV
fVAiAVl
mnVAVrs

El reto

Se le da una cadena rectangular que representa una cuadrícula triangular (donde la esquina superior izquierda es un triángulo que apunta hacia arriba). La mayoría de las celdas con be ., pero exactamente dos celdas serán #, por ejemplo:

....#
.#...
.....

Determine si los dos #están alineados a lo largo de cualquiera de los tres ejes de la cuadrícula (es decir, si se encuentran en una sola fila en cualquiera de las tres direcciones resaltadas anteriormente). Para este ejemplo, la respuesta es "no".

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

La entrada puede ser una sola cadena delimitada por saltos de línea o algún otro carácter conveniente, o una lista de cadenas. Puede usar dos caracteres ASCII imprimibles (consistentes) en lugar de .y #.

La salida debe ser un valor verdadero si las celdas resaltadas están alineadas y un valor falso de lo contrario.

Aplican reglas estándar de .

Casos de prueba

Rejillas de verdad:

.#..#.

#
#

...........
...#.......
...........
...........
...........
.......#...
...........

...........
.......#...
...........
...........
...........
...#.......
...........

.#.........
...........
...........
...........
...........
.......#...
...........

...........
...#.......
...........
...........
...........
...........
.......#...

.........#.
...........
...........
...........
...........
...#.......
...........

...........
.......#...
...........
...........
...........
...........
...#.......

...........
.#.....#...
...........
...........
...........

Rejillas de falsa:

#.....
.....#

.....#
#.....

...#.......
...........
...........
...........
...........
.......#...
...........

...........
...#.......
...........
...........
...........
...........
.........#.

.......#...
...........
...........
...........
...........
...#.......
...........

...........
.......#...
...........
...........
...........
...........
.#.........
Martin Ender
fuente

Respuestas:

3

Caracoles , 40 39 bytes

\#{z|=(ul.ul.`,l~a~)(l.a3|.a|d.ea5}.,\#
\# ,, partido '#'
{
  z | ,, Gire en cualquier dirección octinilar o haga todo lo demás antes del}
  = (,, Si esta afirmación tiene éxito, la celda inicial es un "triángulo que apunta hacia arriba"
    ul.ul.`` ,, sube una celda hacia arriba o hacia la izquierda dos veces, cualquier cantidad de veces.
              ,, ¿Esto debería haber sido un byte más corto con ul.`2 o ul.`2 +? pero
              ,, el análisis de `tiene errores.
    l ~ a ~ ,, Compruebe que estamos en la celda superior izquierda haciendo coincidir los límites exteriores a la izquierda y luego al noreste
  )
  (l.a3 | ,, Muévase hacia la izquierda una vez, luego establezca la dirección hacia el noroeste; o
    .a | ,, Muévase a la derecha (la dirección inicial) una vez, luego ajuste la dirección al noreste; o
    d.ea5 ,, Desplácese hacia abajo una vez, luego establezca la dirección hacia el noroeste o el noreste
}
. ,, ,, Coincide con cualquier número de caracteres arbitrarios (moviéndose en la dirección actual)
\# ,, partido '#'
Feersum
fuente
2

CJam, 47 bytes

Bueno, ahora que hay una solución más corta, ya no me siento mal compartiendo la mía. :) (Principalmente para mostrar que esto no es particularmente difícil, incluso si no tiene un lenguaje de coincidencia de patrones 2D ...)

qN%:eeee::f+:~{S&},2f<:P0f=P::+Xf|P::-Xf|]::=:|

Esto utiliza espacios en lugar de #y realmente cualquier otra cosa para ..

Ejecute todos los casos de prueba en línea.

Realmente odio la duplicación, P::+Xf|P::-Xf|pero hasta ahora no he encontrado nada para deshacerme de ella.

Explicación

No siga leyendo si quiere encontrar una solución para usted.

Primero, la parte aburrida: obtener los dos pares de coordenadas de los dos espacios en la cuadrícula de entrada:

qN%   e# Read input and split into lines.
:ee   e# Enumerate the characters in each line. I.e. turn each character 'x into a pair
      e# [N 'x] where N is its horizontal 0-based index.
ee    e# Enumerate the lines themselves, turning each line [...] into [M [...]] where M
      e# is its vertical 0-based index.
::f+  e# This distributes the vertical index over the individual lines, by prepending it
      e# to each pair in that line. So now we've got a 2-D array, where each character 'x
      e# has been turned into [M N 'x].
:~    e# Flatten the outermost dimension, so that we have a flat list of characters with
      e# their coordinates.
{S&}, e# Filter only those lists that contain a space.
2f<   e# Truncate the two results to only their first two elements.
:P    e# Store the result in P.

Ahora la parte interesante es cómo determinar si esas coordenadas están alineadas o no. Mi código calcula los tres ejes por separado:

  • El eje horizontal es trivial. Compruebe si las coordenadas verticales coinciden.
  • Veamos la diagonal noreste. En la cuadrícula ASCII, siempre hay dos antidiagonales que pertenecen a cada diagonal de triple cuadrícula:

    ....AV..
    ...AV...
    ..AV....
    

    Podemos identificar el antidiagonal actual sumando las coordenadas xy y:

    01234567
    12345678
    23456789
    

    Por lo tanto, queremos 0y 1pertenecer a la misma diagonal, así como 2y 3, y 4y 5y así sucesivamente. Eso significa que, una vez que tenemos nuestro índice anti-diagonal, queremos redondear al siguiente número impar. En otras palabras, tomamos el OR bit a bit 1. (También podríamos redondear al siguiente número par bit a bit Y con -2pero el código es más costoso).

  • Ahora las diagonales del sudeste:

    .VA.....
    ..VA....
    ...VA...
    

    Para dar a las diagonales un índice, restamos el xde la ycoordenada (que representa números negativos como letras):

    0abcdefg
    10abcdef
    210abcde
    

    En este caso, querríamos 0y 1pertenecer a la misma diagonal, así como -1y -2, o 2y 3. Entonces, una vez más, queremos redondear al siguiente número impar.

Aquí está el código para eso:

0f=  e# The coordinates are still on the stack. Replace each with its vertical coordinate
     e# to check for the horizontal axis.
P    e# Push the coordinates again.
::+  e# Sum each pair to get an anti-diagonal index.
Xf|  e# OR each index with 1 to round up to the next odd number.
P    e# Push the coordinates again.
::-  e# In each pair, subtract the horizontal coordinate from the vertical, to
     e# get a diagonal index.
Xf|  e# OR each index with 1.
]    e# Wrap all three index pairs in an array.
::=  e# Check equality for each pair.
:|   e# Fold bitwise OR over the results to check if at least one pair of indices
     e# was equal.
Martin Ender
fuente