tło
Mam kilka starych i ziarnistych czarno-białych zdjęć. Niektóre z nich przedstawiają pnącza wspinające się na ścianie, inne nie - Twoim zadaniem jest sklasyfikowanie ich dla mnie.
Wejście i wyjście
Twój wkład to prostokątna tablica 2D bitów A , podana w dowolnym dogodnym formacie. Nie będzie pusty, ale nie ma gwarancji, że zawiera zarówno 0, jak i 1. Tablica przedstawia winorośl, jeśli spełnione są następujące warunki:
- Dolny rząd A zawiera co najmniej jeden 1. Są to korzenie winorośli.
- Każda 1 w A jest połączona z dolnym rzędem ścieżką 1s, która prowadzi tylko w lewo, w prawo i w dół (nie w górę i nie po przekątnej). Te ścieżki są gałęziami winorośli.
Twój wynik jest spójną wartością prawdy, jeśli dane wejściowe przedstawiają winorośl, a spójną wartością fałszu w przeciwnym razie.
Przykłady
Ta tablica przedstawia winorośl:
0 0 1 0 0 1
0 1 1 0 0 1
0 1 0 1 1 1
1 1 0 1 0 1
0 1 1 1 0 1
0 0 1 0 1 1
Ten wkład nie przedstawia winorośli, ponieważ na środku prawej granicy jest 1, który nie jest połączony z korzeniami przez gałąź:
0 0 0 1 1 0
0 1 0 1 1 1
0 1 0 1 0 1
0 1 1 1 1 0
0 0 1 1 0 1
Tablica all-0 nigdy nie przedstawia winorośli, ale tablica all-1 zawsze tak jest.
Zasady i punktacja
Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.
Przypadki testowe
Prawdziwe dane wejściowe:
1
0
1
1
01
11
0000
0111
1100
1001
1111
1111
1111
1111
001001
011001
010111
110101
011101
001011
1011011
1001001
1111111
0100000
0111111
1111001
1001111
1111101
0000000
0011100
0010100
0011100
0001000
1111111
0001000
0011100
0010100
0010100
Fałszywe dane wejściowe:
0
1
0
10
01
000
000
000
011
110
000
111111
000000
101011
111001
010010
001000
000010
110001
001100
111111
110101
010011
111011
000110
010111
010101
011110
001101
11000000
10110001
10011111
11110001
01100011
00110110
01101100
01100001
01111111
źródło
Odpowiedzi:
Ślimaki ,
251917 bajtówWypróbuj online!
Wyjaśnienie
Snails to język dopasowywania wzorców 2D inspirowany regex, który został pierwotnie opracowany dla naszego wyzwania projektowania języka dopasowywania wzorców 2D .
W
&
sprawia, że Ślimaki spróbować wzór z każdej możliwej pozycji wyjściowej i drukuje0
lub1
w zależności od tego, czy wzór nie w żadnym z nich lub meczów we wszystkich z nich.Teraz Ślimaki mogą pracować z niejawnymi nawiasami, więc wzorzec jest krótszy dla następujących:
,
Działa jak*
w regex (czyli zero lub więcej razy), natomiast+
jest taka sama jak w regex (mecz jeden lub więcej razy). Dlatego zaczynamy od dopasowania\0z
tak często, jak to konieczne, które pasuje do jednego,0
a następnie pozwala ślimakowi dowolnie zresetować swój kierunekz
. Pozwala to na wprowadzenie zer, pod warunkiem, że prawidłową komórkę winorośli można znaleźć gdziekolwiek indziej.Następnie dopasowujemy co najmniej jeden
\1dlr
, który pasuje do jednego,1
a następnie pozwala ślimakowi zresetować swój kierunek w dół, w lewo lub w prawo. Zauważ, że jeśli komórka, w której zaczęliśmy, zawiera a,1
to dopasowujemy tylko tę część. Zasadniczo pozwala ślimakowi przejść przez winorośl od gałęzi do korzeni.Na koniec musimy upewnić się, że doszliśmy do celu, szukając komórki poza zakresem (
~
) poniżej (d
).źródło
JavaScript (ES6), 135 bajtów
Uwaga: Z powodu ograniczeń typu liczba całkowita działa tylko dla winorośli o szerokości do 31 znaków. Objaśnienie: Każdy rząd jest bitowo ANDedowany z sąsiednim rzędem w celu ustalenia punktów połączenia, a następnie
g
funkcja służy do rekurencyjnego rozszerzania rzędu w poziomie, aż nie będzie mógł już się rozwinąć. Na przykład, jeśli dwa sąsiednie rzędy są,1110111
a1011100
następnie są punkty połączenia,1010100
a to jest następnie rozwijane do,1110110
a następnie to,1110111
co następnie stwierdza, że rząd jest połączony. Jeślig
funkcja zawodzi, wówczas zwraca zero, co powodujeg
również awarię wszystkich kolejnych funkcji, a wynikiem jest fałsz. Jeślig
funkcja się powiedzie, zwraca nowy wiersz, który jest następnie propagowany przez,reduce
aby przetestować następny wiersz.źródło
Python 2, 254 bajty
Brak bibliotek
Zauważ, że wcięcia drugiego i trzeciego poziomu są tworzone z zakładkami w liczbie bajtów.
Wypróbuj online
źródło
Wolfram - 254
Poświęć trochę czasu na zrobienie tego, więc zostawię to tutaj:
Zasadniczo tworzę wykres siatki skierowanymi w górę krawędziami, usuwam wierzchołki odpowiadające zerom, sprawdzam, czy dolne komponenty wierzchołków zawierają wszystkie wierzchołki. Śmieszne, wiem ...
źródło
Python + NumPy
204202195 bajtówOczekuje
A
że będzie tablicą numeryczną 2D.Bierze matrycę, wstawia zero kolumn w lewo i prawo i spłaszcza macierz.
s
to szablon, który wskazuje na lewy, prawy i dolny element. Pętla sprawdza każdy element, z wyjątkiem ostatniego wiersza, jeśli jest,1
a przynajmniej jeden z jego szablonów1
, zwracaFalse
inaczej. Następnie sprawdź, czy ostatni wiersz zawiera jakieś1
.Dwie walizki testowe dla Ciebie:
Edycja1:
1<0
jest krótsza niżFalse
Edycja2:
flat
jest świetną alternatywą dlaflatten()
tabulatorów w drugiej pętli i używaniem ichźródło