Alinhamento em grades triangulares

18

As grades hexagonais tornaram-se uma reviravolta bastante popular nos desafios sobre dados bidimensionais recentemente. No entanto, parece que as grades triangulares igualmente interessantes foram amplamente negligenciadas até agora. Eu gostaria de corrigir isso com um desafio bastante simples.

Primeiro, como representamos uma grade triangular? Considere o seguinte exemplo (ignore o diagrama correto por enquanto):

insira a descrição da imagem aqui insira a descrição da imagem aqui

As células caem ordenadamente em uma grade regular (a diferença de uma grade regular é apenas quais células são consideradas adjacentes):

1234567
89abcde
fghijkl
mnopqrs

Agora, como o diagrama à direita mostra, uma grade triangular tem três eixos principais: um horizontal e dois diagonais.

Destacando-os na grade ASCII:

AVAVAVA
VAabcAV
fVAiAVl
mnVAVrs

O desafio

Você recebe uma string retangular representando uma grade triangular (onde o canto superior esquerdo é um triângulo apontando para cima). A maioria das células com be ., mas exatamente duas células estarão #, por exemplo:

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

Determine se os dois #estão alinhados ao longo de qualquer um dos três eixos da grade (ou seja, se estão em uma única linha em qualquer uma das três direções destacadas acima). Neste exemplo, a resposta é "não".

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

A entrada pode ser uma única sequência delimitada por linhas de alimentação ou algum outro caractere conveniente ou uma lista de sequências. Você pode usar dois caracteres ASCII imprimíveis (consistentes) no lugar de .e #.

A saída deve ser um valor verdadeiro se as células destacadas estiverem alinhadas e, caso contrário, um valor falso .

Aplicam-se as regras de padrão .

Casos de teste

Grades de verdade:

.#..#.

#
#

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

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

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

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

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

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

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

Grelhas de falsidade:

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

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

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

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

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

...........
.......#...
...........
...........
...........
...........
.#.........
Martin Ender
fonte

Respostas:

3

Caracóis , 40 39 bytes

\#{z|=(ul.ul.`,l~a~)(l.a3|.a|d.ea5}.,\#
\# ,, Combine '#'
{
  z ,, Gire em qualquer direção octinilear ou faça todas as outras coisas antes da}
  = (,, Se essa afirmação for bem-sucedida, a célula inicial é um "triângulo apontando para cima"
    ul.ul`, ,, Vá uma célula para cima ou para a esquerda duas vezes, qualquer número de vezes.
              ,, Este deveria ter sido um byte mais curto com ul`2 ou ul`2 +? mas
              ,, a análise de `é incorreta.
    l ~ a ~ ,, Verifique se estamos na célula superior esquerda, correspondendo fora dos limites à esquerda e depois a nordeste
  )
  (l.a3 | ,, Mova para a esquerda uma vez e defina a direção para noroeste; ou
    .a ,, Mova para a direita (a direção inicial) uma vez e depois defina a direção para nordeste; ou
    d.ea5 ,, Mova para baixo uma vez e defina a direção para noroeste ou nordeste
}
., ,, Corresponde a qualquer número de caracteres arbitrários (movendo-se na direção atual)
\# ,, Combine '#'
feersum
fonte
2

CJam, 47 bytes

Bem, agora que existe uma solução mais curta, não me sinto mais mal em compartilhar a minha. :) (Principalmente para mostrar que isso não é particularmente difícil, mesmo que você não tenha uma linguagem de correspondência de padrões 2D ...)

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

Isso usa espaços no lugar de #e realmente qualquer outra coisa ..

Execute todos os casos de teste online.

Eu realmente odeio a duplicação, P::+Xf|P::-Xf|mas até agora não encontrei nada para me livrar dela.

Explicação

Não continue a ler se você quiser descobrir uma solução para si mesmo.

Primeiro, a parte chata: obter os dois pares de coordenadas dos dois espaços na grade 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.

Agora, a parte interessante é como determinar se essas coordenadas estão alinhadas ou não. Meu código calcula todos os três eixos separadamente:

  • O eixo horizontal é trivial. Verifique se as coordenadas verticais correspondem.
  • Vamos olhar para a diagonal nordeste. Na grade ASCII, sempre existem duas antidiagonais que pertencem a cada diagonal de três grades:

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

    Podemos identificar o antidiagonal atual adicionando as coordenadas xe y:

    01234567
    12345678
    23456789
    

    Então, queremos 0e 1pertencemos à mesma diagonal, assim como 2e 3, e 4e 5e assim por diante. Isso significa que, assim que tivermos o nosso índice anti-diagonal, queremos arredondar para o próximo número ímpar. Em outras palavras, adotamos o OR bit a bit com 1. (Também podemos arredondar para o próximo número par por AND bit a bit, -2mas isso é mais caro no código.)

  • Agora as diagonais do sudeste:

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

    Para atribuir às diagonais um índice, subtraímos a xpartir da ycoordenada (representando números negativos como letras):

    0abcdefg
    10abcdef
    210abcde
    

    Nesse caso, gostaríamos 0e 1pertenceríamos à mesma diagonal, assim como -1e -2, ou 2e 3. Então, mais uma vez, queremos arredondar para o próximo número ímpar.

Aqui está o código para isso:

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
fonte