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

Ślimaki , 25 19 17 bajtów

&
\0z),(\1dlr)+d~

Wypró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 drukuje 0lub1 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:

(\0z),(\1dlr)+d~

,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 \0ztak często, jak to konieczne, które pasuje do jednego, 0a 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, 1a 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, 1to 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).

JavaScript (ES6), 135 bajtów

s=>s.replace(/^[^1]*\n/,``).split`
`.map(s=>+`0b${s}`).reverse(g=(n,m,o=(m<<1|m|m>>1)&n)=>n-m?o-m&&g(n,o):n).reduce((m,n,i)=>g(n,n&m))

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 gfunkcja 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ą, 1110111a 1011100następnie są punkty połączenia, 1010100a to jest następnie rozwijane do, 1110110a następnie to, 1110111co następnie stwierdza, że ​​rząd jest połączony. Jeśli gfunkcja zawodzi, wówczas zwraca zero, co powoduje grównież awarię wszystkich kolejnych funkcji, a wynikiem jest fałsz. Jeśli gfunkcja się powiedzie, zwraca nowy wiersz, który jest następnie propagowany przez, reduceaby przetestować następny wiersz.

s=>s.replace(/^[^1]*\n/,``)         Remove irrelevant leading "blank" rows
    .split`\n`                      Split into lines
    .map(s=>+`0b${s}`)              Convert into binary
    .reverse(                       Process from bottom to top
     g=(n,m,o=(m<<1|m|m>>1)&n)=>     Expand row horizontally
      n-m?o-m&&g(n,o):n)             Check whether rows are connected
    .reduce((m,n,i)=>g(n,n&m))      Check all rows

Python 2, 254 bajty

Brak bibliotek

def f(A,r=0,c=-1):
 B=A[r];R=len(A)-1;C=len(B);i=1 in A[R]
 if c<0:
    for j in range(R*C+C):
        if A[j/C][j%C]:i&=f(A,j/C,j%C)
    return i&1
 _=B[c];B[c]=0;i=_&(r==R)
 if _:
    if c>0:i|=f(A,r,c-1)
    if r<R:i|=f(A,r+1,c)
    if c<C-1:i|=f(A,r,c+1)
 B[c]=_;return i

Zauważ, że wcięcia drugiego i trzeciego poziomu są tworzone z zakładkami w liczbie bajtów.

Wypróbuj online

Wolfram - 254

Poświęć trochę czasu na zrobienie tego, więc zostawię to tutaj:

f[s_]:=(
v=Characters@StringSplit@s;
{h,w}=Dimensions@v;
g=GridGraph@{w,h};
r=First/@Position[Flatten@v,"0"];
g=VertexDelete[Graph[VertexList@g,
EdgeList@g/.x_y_/;Abs[x-y]>1yx],r];
v=VertexList@g;
v≠{}∧v~Complement~VertexOutComponent[g,Select[v,#>w h-w&]]{}
)

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

Python + NumPy 204 202 195 bajtów

from numpy import*
def f(A):
 r,c=A.shape
 z,s=zeros((r,1)),array([0,2,c+3])
 B=hstack((z,A,z)).flat
 for i in range(1,(r-1)*(c+2)):
    if B[i]and not any(B[s]):return 1<0
    s+=1
 return any(B[i:])

Oczekuje A że będzie tablicą numeryczną 2D.

Bierze matrycę, wstawia zero kolumn w lewo i prawo i spłaszcza macierz. sto szablon, który wskazuje na lewy, prawy i dolny element. Pętla sprawdza każdy element, z wyjątkiem ostatniego wiersza, jeśli jest, 1a przynajmniej jeden z jego szablonów 1, zwraca Falseinaczej. Następnie sprawdź, czy ostatni wiersz zawiera jakieś1 .

Dwie walizki testowe dla Ciebie:

I1 = '001001\n011001\n010111\n110101\n011101\n001011'
A1 = array([int(c) for c in I1.replace('\n','')]).reshape(6,6)
print f(A1) #True

I2 = '001100\n111111\n110101\n010011\n111011'
A2 = array([int(c) for c in I2.replace('\n','')]).reshape(5,6)
print f(A2) #False

Edycja1: 1<0jest krótsza niżFalse

Edycja2: flatjest świetną alternatywą dla flatten()tabulatorów w drugiej pętli i używaniem ich