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) *****
** *
*****
źródło
AV VA\nVAVAV
zamiast,** **\n*****
ponieważ ułatwia to ludziom wizualizację. Dokonałem już edycji jednego ze schematów ASCII Martina.Odpowiedzi:
Ślimaki , 95 bajtów
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.
źródło
CJam,
10198 bajtówWypró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:źródło