Podczas gdy jesteśmy na kopniaku z trójkątnymi siatkami , chciałbym zauważyć, że na trójkątnej siatce jest odpowiednik poliomino . Nazywa się je poliamidami i są kształtami utworzonymi przez sklejenie trójkątów równobocznych wzdłuż ich krawędzi. W tym wyzwaniu będziesz decydować, które podzbiory siatki trójkątnej są poliamidami i czy mają w nich dziury. Ponieważ do utworzenia poliamidu z dziurą potrzeba tylko 9 trójkątów, kod musi być możliwie jak najkrótszy.

Siatka

Do wprowadzenia danych wykorzystamy trójkątny układ siatki Martina :

Zwróć uwagę na fakt, że środki trójkątów tworzą z grubsza prostokątną siatkę i że lewy górny trójkąt „wskazuje” w górę. Możemy opisać podzbiór tej siatki, podając prostokątną „mapę gwiazd” wskazującą, które trójkąty są uwzględnione, a które nie. Na przykład ta mapa:

** **
*****

odpowiada najmniejszemu poliamidowi, który zawiera otwór:

Otwory

Poliamid zawierający dziurę jak w powyższym przykładzie (obszar nie będący częścią poliamidu, który jest otoczony ze wszystkich stron przez regiony, które są ) nie jest, topologicznie mówiąc, po prostu połączony .

Wyzwanie

Napisz funkcję lub program, który przyjmuje jako dane wejściowe „mapę gwiezdną”, jak opisano powyżej, i wypisuje prawdę, jeśli i tylko wtedy, gdy wskazany podzbiór trójkątnej siatki jest po prostu połączonym poliamondem .

Więcej przykładów

*** ***
*******

odpowiada poliamidowi

który jest po prostu podłączony.

*   *
** **
 ***

odpowiada poliamidowi

który jest po prostu podłączony.

**  **
*** **
 ****

odpowiada nie- poliamidowi

który nie byłby po prostu podłączony, nawet gdyby był to poliamid.

Dane wejściowe

• Dane wejściowe będą składały się wyłącznie z gwiazdek, spacji i znaków nowej linii.
• Pierwszym znakiem wprowadzania zawsze będzie spacja lub gwiazdka (odpowiadająca skierowanemu w górę trójkątowi w lewym górnym rogu siatki).
• Zawsze będzie co najmniej jedna gwiazdka w pierwszej i ostatniej linii.
• Nie ma ŻADNEJ gwarancji, że wiersze po pierwszym wierszu nie będą puste. Dwa wejścia liniowe z rzędu mogą pojawić się w uzasadnionych danych wejściowych.
• Długość linii nie musi być taka sama.

Warunki wygranej

To jest golf-golf, więc najkrótsza odpowiedź w bajtach wygrywa.

Przypadki testowe

Prawdziwe mapy:

1) *

2) *
   *

3) **

4) *** ***
   *******

5) *   *
   ** **
    ***

6) *
   **
    *

7)    **
     ***
   ****

8) ****
   **   *
    *****

9) ***********
   **    **  **
    ****  **  **
              **
   ************

Mapy Falsy:

1) *
   *
   *

2) * *

3) *
    *

4)  **
   **

5) ***

   ***

6) ** **
   *****

7) **  **
   *** **
    ****

8)  *
    *

9) *****
   **   *
    *****

Ślimaki , 95 bajtów

F&
lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}\*}+l\ ,~a~|{\ (lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}+~

To naprawdę ucierpiało z powodu duplikacji, ponieważ nie wdrożyłem makr ani żadnego rodzaju referencji. Sprawdza, czy dla każdej gwiazdy istnieje ścieżka do gwiazdy znajdującej się najbardziej na lewo w górnej linii; a dla każdej przestrzeni jest ścieżka do krawędzi siatki.

F&                         ,, option F: pad lines with spaces to the length of the longest
                           ,, option &: print 1 iff match succeeds from every cell
lr                         ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, direction down, if we are an even number of orthogonal moves from the top left
      | !((ul.)2 ,l~a~) u  ,, or, direction up if we are odd number of moves from the top left
    }  \*                  ,, literal '*'
}+                         ,, 1 or more times
l\ ,~a~                    ,, check that we are on the leftmost * in the top line

|                          ,, the part before this is for starting on '*'; part after for starting on ' '

{ \                        ,, literal ' '
    (   lr                 ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, same drill as before...
      | !((ul.)2 ,l~a~) u 
}+                         ,, 1 or more times
~                          ,, end on an out of bounds cell

CJam, 101 98 bajtów

qN/_z,f{' e]}{S2*f+W%z}4*:eeee::f+:~{_(aL{+_{_2,.+1$2,.-@_:+1&!2*(a.+}%2${a1$&},\;@1$-@@}h;\;-}2*!

Wypróbuj online.

W końcu przezwyciężyłem strach przed wdrożeniem wypełniania powodzi w CJam. Jest tak brzydki, jak się spodziewałem i zdecydowanie można go grać w golfa.

Ogólną ideą jest wykonanie dwóch wypełnień zalewowych (które są faktycznie realizowane jako usuwanie z listy niewidzianych komórek). Pierwsze przejście usunie wszystkie spacje, które są osiągalne z krawędzi. Drugie przejście wybierze następnie pierwszy *w kolejności czytania i usunie z niego wszystkie dostępne trójkąty. Jeśli i tylko jeśli wynikowa lista jest pusta, poliamid został po prostu podłączony:

• Jeśli poliamid miał dziurę, pierwsze wypełnienie nie może dotrzeć do tej dziury i ją usunąć.
• Jeśli sygnał wejściowy składa się z kilku rozłączonych poliamidów, drugie wypełnienie nie może dotrzeć do wszystkich i usunąć ich.