Trójkątne siatki: po prostu połączone poliamidy

9

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 :

trójkątna siatka

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:

9-iamond z otworem

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 ) 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

13-iamond bez dziury

który jest po prostu podłączony.


*   *
** **
 ***

odpowiada poliamidowi

9-iamond bez dziury

który jest po prostu podłączony.


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

odpowiada nie- poliamidowi

13 trójkątów, które nie są niczym interesującym

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 , 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) *****
   **   *
    *****
kwintopia
źródło
1
dobre pytanie. Jeśli trójkątne siatki staną się rzeczami, czy mogę zasugerować, aby były przedstawiane jako na przykład AV VA\nVAVAVzamiast, ** **\n*****ponieważ ułatwia to ludziom wizualizację. Dokonałem już edycji jednego ze schematów ASCII Martina.
Level River St
Nie byłem szczególnie zainteresowany czytelnością człowieka, nie. Chciałem zrobić wszystko, co byłoby łatwiejsze do odczytania przez program, pozostając małym.
kwintopia
Więc w zasadzie, fałszywy iff istnieje sekcja tylko „połączona” narożnikami?
Michael Klein,
1
Lub jeśli są części, które w ogóle nie są połączone. Martin ujął to w ten sposób: prawda, że ​​figura i ziemia są połączone wzdłuż krawędzi, dzięki czemu 2 wypełnienia wystarczą do ponownego pokolorowania samolotu.
kwintopia

Odpowiedzi:

4

Ś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
feersum
źródło
Nie rozumiem, jak to działa, ale całkowicie działa.
kwintopia
3

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