Wyrównanie na siatkach trójkątnych

18

Siatki heksagonalne stały się ostatnio dość popularną odmianą wyzwań związanych z danymi dwuwymiarowymi. Wydaje się jednak, że równie interesujące trójkątne siatki były dotychczas w dużej mierze zaniedbywane. Chciałbym to naprawić za pomocą dość prostego wyzwania.

Po pierwsze, jak reprezentujemy trójkątną siatkę? Rozważ następujący przykład (na razie zignoruj ​​odpowiedni schemat):

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Komórki starannie opadają na regularną siatkę (różnica w stosunku do zwykłej siatki polega tylko na tym, które komórki są uważane za sąsiadujące):

1234567
89abcde
fghijkl
mnopqrs

Teraz, jak pokazuje prawy schemat, siatka trójkątna ma trzy główne osie: poziomą i dwie ukośne.

Zaznaczając je w siatce ASCII:

AVAVAVA
VAabcAV
fVAiAVl
mnVAVrs

Wyzwanie

Otrzymujesz prostokątny ciąg reprezentujący trójkątną siatkę (gdzie lewy górny róg jest trójkątem skierowanym do góry). Większość komórek z być ., ale dokładnie dwie komórki będą #, np .:

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

Ustal, czy oba #są wyrównane wzdłuż którejkolwiek z trzech osi siatki (tj. Czy leżą w jednym rzędzie w dowolnym z trzech wyróżnionych powyżej kierunków). W tym przykładzie odpowiedź brzmi „nie”.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Dane wejściowe mogą być pojedynczym ciągiem rozdzielanym znakami linii lub innym dogodnym znakiem lub listą ciągów. Możesz użyć dowolnych dwóch (spójnych) drukowalnych znaków ASCII zamiast .i #.

Dane wyjściowe powinny być zgodne z prawdą, jeśli podświetlone komórki są wyrównane, a w przeciwnym razie wartością fałsz .

Obowiązują standardowe zasady .

Przypadki testowe

Prawdziwe siatki:

.#..#.

#
#

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

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

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

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

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

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

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

Kratki Falsy:

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

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

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

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

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

...........
.......#...
...........
...........
...........
...........
.#.........
Martin Ender
źródło

Odpowiedzi:

3

Ślimaki , 40 39 bajtów

\#{z|=(ul.ul.`,l~a~)(l.a3|.a|d.ea5}.,\#
\# ,, mecz '#'
{
  z | ,, Albo skręć w dowolnym kierunku o oktililear albo zrób wszystkie inne rzeczy przed}
  = (,, Jeśli to stwierdzenie się powiedzie, komórka początkowa jest „trójkątem skierowanym w górę”
    ul. ul., ,, Idź jedną komórkę w górę lub w lewo dwa razy, dowolną liczbę razy.
              ,, To powinno być o jeden bajt krótsze z ul. 2 lub ul. 2 +? ale
              ,, parsowanie `jest błędne.
    l ~ a ~ ,, Sprawdź, czy znajdujemy się w lewej górnej komórce, dopasowując poza granicami po lewej, a następnie na północny wschód
  )
  (l.a3 | ,, Przesuń raz w lewo, a następnie ustaw kierunek na północny zachód; lub
    .a | ,, Przesuń raz w prawo (kierunek początkowy), a następnie ustaw kierunek na północny wschód; lub
    d.ea5 ,, Zejdź raz w dół, a następnie ustaw kierunek na północny zachód lub północny wschód
}
., ,, Dopasuj dowolną liczbę dowolnych znaków (poruszających się w bieżącym kierunku)
\# ,, mecz '#'
feersum
źródło
2

CJam, 47 bajtów

Teraz, gdy istnieje krótsze rozwiązanie, nie czuję się źle, dzieląc się własnym. :) (Głównie, aby pokazać, że nie jest to szczególnie trudne, nawet jeśli nie masz języka dopasowującego wzór 2D ...)

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

To wykorzystuje spacje zamiast #i tak naprawdę cokolwiek innego ..

Uruchom wszystkie przypadki testowe online.

Naprawdę nienawidzę powielania, P::+Xf|P::-Xf|ale jak dotąd nie wymyśliłem niczego, aby się go pozbyć.

Wyjaśnienie

Nie czytaj dalej, jeśli chcesz znaleźć rozwiązanie dla siebie.

Po pierwsze, nudna część: uzyskanie dwóch par współrzędnych dwóch przestrzeni w siatce wejściowej:

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.

Teraz interesującą częścią jest ustalenie, czy te współrzędne są wyrównane, czy nie. Mój kod oblicza wszystkie trzy osie osobno:

  • Oś pozioma jest banalna. Sprawdź, czy współrzędne pionowe są zgodne.
  • Spójrzmy na przekątną północno-wschodnią. W siatce ASCII zawsze są dwie antydiagonale, które należą do każdej przekątnej trójsiatkowej:

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

    Możemy zidentyfikować obecny antydiagonalny, sumując xi ywspółrzędne:

    01234567
    12345678
    23456789
    

    Tak, że chcemy 0i 1należą do tej samej przekątnej, jak 2i 3i 4i 5i tak dalej. Oznacza to, że po uzyskaniu naszego indeksu anty-diagonalnego chcemy zaokrąglić w górę do następnej liczby nieparzystej. Innymi słowy, bierzemy bitową OR z 1. (Możemy również zaokrąglić w dół do następnej liczby parzystej bitowo ORAZ z, -2ale to jest droższe w kodzie).

  • Teraz południowo-wschodnie przekątne:

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

    W celu zapewnienia przekątnych indeksu, że odejmujex od ywspółrzędnych (reprezentujących ujemne numery jak litery):

    0abcdefg
    10abcdef
    210abcde
    

    W tym przypadku chcielibyśmy 0i 1należeć do tej samej przekątnej, a także -1i -2, lub 2i 3. Tak więc po raz kolejny chcemy zaokrąglić w górę do następnej liczby nieparzystej.

Oto kod do tego:

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
źródło