Recognize a vine

Question

Background

I have a bunch of old and grainy black-and-white images. Some of them depict vines climbing on a wall, others don't – your task is to classify them for me.

Input and output

Your input is a rectangular 2D array of bits A, given in any convenient format. It will not be empty, but it's not guaranteed to contain both 0s and 1s. The array depicts a vine if the following conditions hold:

• The bottom row of A contains at least one 1. These are the roots of the vine.
• Every 1 in A is connected to the bottom row by a path of 1s that only goes left, right and down (not up, and not diagonally). These paths are the branches of the vine.

Your output is a consistent truthy value if the input depicts a vine, and a consistent falsy value otherwise.

Examples

This array depicts a vine:

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

This input does not depict a vine, since there's a 1 at the middle of the right border that's not connected to the roots by a branch:

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

The all-0 array never depicts a vine, but the all-1 array always does.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

Truthy inputs:

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

Falsy inputs:

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

Answer 1

Snails, 25 19 17 bytes

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

Try it online!

Explanation

Snails is a 2D pattern-matching language inspired by regex, which was originally developed for our 2D pattern matching language design challenge.

The & makes Snails try the pattern from every possible starting position and prints 0 or 1 depending on whether the pattern fails in any of them or matches in all of them.

Now Snails can work with implicit parentheses, so the pattern is shorthand for the following:

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

The , acts like a * in regex (i.e. match zero or more times), whereas the + is the same as in regex (match one or more times). So we start by matching \0z as often as necessary, which matches a single 0 and then allows the snail to reset its direction arbitrarily with z. This allows zeros in the input, provided a valid vine cell can be found anywhere else.

Then we match at least one \1dlr, which matches a single 1 and then allows the snail to reset its direction either down, left or right. Note that if the cell we've started at contains a 1 then we're only matching this part. It basically allows the snail to traverse a vine from a branch down to the roots.

Finally, we need to ensure that we did reach the ground by looking for an out-of-bounds cell (~) below (d).

Answer 2

JavaScript (ES6), 135 bytes

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

Note: Due to limitations of integer type, only works for vines of up to 31 characters wide. Explanation: Each row is bitwise ANDed with the adjacent row to determine the connection points, and then the g function is used to recursively expand the row horizontally until it can expand no more. For instance, if two adjacent rows are 1110111 and 1011100 then the connection points are 1010100 and this is then expanded to 1110110 and then 1110111 which then finds that the row is connected. If the g function fails then it returns zero which causes all subsequent g functions to fail too, and the result is then falsy. If the g function succeeds it returns the new row which is then propagated through the reduce to test the next row.

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

Answer 3

Python 2, 254 bytes

No libraries

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

Note that the second and third level indents are formed with tabs in the byte count.

Try it online

Answer 4

Wolfram - 254

Spend some time making this work, so I'll just leave it here:

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&]]{}
)

Basically I construct a grid graph with directed edges pointing up, remove vertices that correspond to 0s, check that bottom vertex components contain all vertices. Ridiculous, I know...

Answer 5

Python + NumPy 204 202 195 Bytes

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

Expects A to be a 2D numpy array.

Takes the matrix, pads zero columns left and right and flattens the matrix. s is a stencil that points to the left, right and lower element. The loop checks each element except the last line if it is 1 and at least one of its stencil is 1, returns False otherwise. Afterwards, check if the last line contains any 1.

Two testcases for you:

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

Edit1: 1<0 is shorter than False

Edit2: flat is a fine alternative to flatten() and using tabulators for the second intendation in the loop