Is there a left-right connection?

Question

Task

Given a square array of 0s and 1s, determine whether or not there exists a path of 1s connecting the leftmost and rightmost columns. A path can take steps of one unit up, down, left or right, but not diagonally. Every symbol on the path must be a 1, and it must start somewhere in the first column and end somewhere in the last column.

Shortest code in each language wins.

Examples

000
111   ->  True
111

110
110   ->  False
110

101
010   ->  False
101

0     ->  False

1     ->  True

11110
00010
01110 ->  True
01000
01111

11110
00010
01100 ->  False
01000
01111

Notes

The array may be represented in any reasonable form, such as a list of lists [[0,0,0],[1,1,1],[1,1,1]] or a string '000 111 111'. Optionally it can be in transposed form (so that the roles of rows and columns are exchanged); equivalently the code can instead determine whether there is a top-bottom connection. Any two distinct symbols can be used in place of 0 and 1. The output can be in any truthy/falsy form.

Answer 1

MATLAB/Octave, 115 109 98* bytes

-6 bytes thanks to Luis Mendo
-7 bytes thanks to Luis Mendo

function p=f(A)
B=A;B(:,2:end)=0;for k=1:nnz(A)
B=conv2(B,mod(magic(3),2),'same').*A;end
p=any(B);

Try it online!
(end keyword is in footer because it's not required when you define the function in a file)

Takes binary array, outputs:

• truthy value as vector full of logical ones
• falsy value as vector having some logical zeros
  Such unconsistent falsy was suggested by Luis Mendo and confirmed as valid by as aeh5040.

For consistent true/false logical output replace any(B) with all(any(B)).

*for MATLAB it's possible to skim 3 bytes by replacing 'same' with 's'.

Ungolfed:

function path = f(A)

B = A;                  % copy of A
B(:, 2:end) = 0;        % zero everything besides 1st column

mask = mod(magic(3),2); % mask for making "steps"
                        % equal to: [0 1 0           
                        %            1 1 1
                        %            0 1 0];

for k=1:nnz(A)          % max number of necessary steps is amount of 1s in A
  % uses 2D convolution of B with m, takes only central part of size of B
  B = conv2(B,mask,'same');  % makes "step" in every direction
  B = B.*A;                  % filters only valid steps
end

path = any(B); % check if each column has any value != 0
      % if returned vector is full of 1s each column contains nonzero value
      % which mean there is a path between both sides

end

Explaination

How 2D convolution works?

If we have array like so:

1 1 0 0 0
0 0 0 1 0
0 0 0 0 0

and a mask

0 1 0
1 1 1
0 1 0

we can imagine convolution of array with mask as taking a mask and placing it on top (so that position of corner is the same) of every cell of array and multiplying it with value of that cell - such operation for one cell gives us one array. And then we sum all of the arrays. In our example:

1 0 0 0 0         0 1 0 0 0         0 0 0 0 0         1 1 0 0 0
0 0 0 0 0    +    0 0 0 0 0    +    0 0 0 1 0    =    0 0 0 1 0
0 0 0 0 0         0 0 0 0 0         0 0 0 0 0         0 0 0 0 0
    |                 |                 |                 |
    V                 V                 V                 V
0 1 0 0 0 0 0     0 0 1 0 0 0 0     0 0 0 0 0 0 0     0 1 1 0 0 0 0
1 1 1 0 0 0 0     0 1 1 1 0 0 0     0 0 0 0 1 0 0     1 2 2 1 1 0 0
0 1 0 0 0 0 0  +  0 0 1 0 0 0 0  +  0 0 0 1 1 1 0  =  0 1 1 1 1 1 0
0 0 0 0 0 0 0     0 0 0 0 0 0 0     0 0 0 0 1 0 0     0 0 0 0 1 0 0
0 0 0 0 0 0 0     0 0 0 0 0 0 0     0 0 0 0 0 0 0     0 0 0 0 0 0 0

Also, in our case because we were using argument 'same' we were taking only "central" part of result, so because mask was 3x3 we need to cut off sum of 2 columns and 2 rows from the result. To make it even we're cutting first and last rows and are left with:

2 2 1 1 0
1 1 1 1 1
0 0 0 1 0

How we are making "steps"?

Having our input array:

1 1 1 1 0
0 0 0 1 0
0 1 1 1 0
0 1 0 0 0
0 1 1 1 1

We're taking first column:

1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

then by convolution with our "step" pattern:

0 1 0
1 1 1
0 1 0

we're selecting cells where we could make step from all current/past positions:

1 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

but since we only can move where 1s are in input array we filter valid positions by multiplying arrays elementwise:

1 1 0 0 0         1 1 1 1 0        1 1 0 0 0
1 0 0 0 0         0 0 0 1 0        0 0 0 0 0
0 0 0 0 0   .*    0 1 1 1 0    =   0 0 0 0 0
0 0 0 0 0         0 1 0 0 0        0 0 0 0 0
0 0 0 0 0         0 1 1 1 1        0 0 0 0 0

and so we made 1st "step". Then again - convolution to select positions where we can move and filter out result:

1 1 0 0 0             2 2 1 0 0                2 2 1 0 0
0 0 0 0 0 convolution 1 1 0 0 0 multiplication 0 0 0 0 0
0 0 0 0 0     ==>     0 0 0 0 0      ==>       0 0 0 0 0
0 0 0 0 0    steps    0 0 0 0 0    filtering   0 0 0 0 0
0 0 0 0 0             0 0 0 0 0                0 0 0 0 0

Notice we're getting values other than 1, but that doesn't matter - positive numbers will produce only more positive numbers, so we care only if something is 0 or something greater. So, we continue, next step:

2 2 1 0 0     4 5 3 1 0     4 5 3 1 0
0 0 0 0 0     2 2 1 0 0     0 0 0 0 0
0 0 0 0 0 ==> 0 0 0 0 0 ==> 0 0 0 0 0
0 0 0 0 0     0 0 0 0 0     0 0 0 0 0
0 0 0 0 0     0 0 0 0 0     0 0 0 0 0

and so on, we continue making steps, finally reaching such state:

15511   26324   29964   27016       0
    0       0       0   20240       0
    0    3080    6853   12804       0
    0    1143       0       0       0
    0     340      77      12       1

with 1 in final column, meaning we've reached the right side.

Answer 2

J, 48 bytes

_1{0{1([:+./ .*^:_~1>:|@-/~)@($j./@#:I.@,)@,~1,]

Try it online!

Takes a binary matrix, and checks for a top-to-bottom path. Hence, the input pre-processor transposes the test cases.

the idea

• Add a row of ones to the top and bottom.
• Convert all ones to coordinates, encoded as complex numbers.
• Create an adjacency matrix for those points, with adjacency defined as "euclidean distance is <= 1".
• Self "multiply" that matrix to a fixed point, where the addition part of the matrix multiplication is boolean "or".
• The top row will now be connected to the bottom row iff the upper right entry in the matrix is a 1.
• So return that entry.

Answer 3

R, 138... 118 bytes

-9 bytes thanks to Dominic van Essen.

function(m,k=nrow(m),r=m,`/`=cbind){r[,-1]=0
for(i in m)r=r|m&r[,-1]/0+0/r[,-k]+t(t(r[-1,])/0+0/t(r[-k,]))
any(r[,k])}

Try it online!

At first, the matrix r contains only the 1s of the first column of the input m; all other entries are 0.

At iteration i of the loop, entries which are attainable in at most i steps become non-0. This is done by incrementing the cells for which both of these conditions hold: (1) the value is 1 in m and (2) the value of one of its neighbours is non-0 in r. A less golfy but more readable version of the command in the for loop would be

r = r | ( m & (cbind(r[,-1],0) | cbind(0,r[,-k]) | rbind(r[-1,],0) | rbind(0,r[-k,])))

Note that using + instead of some of the | allows to omit the brackets, thanks to R's operator precedence (+ before & before |).

The length of the path to reach the rightmost column is bounded by k^2, where k is the side length of the input. After k^2 iterations (i.e. the number of elements of m), we check whether there any non-0 values in the rightmost column of r.

Answer 4

Haskell, 96 bytes

e=[]:e
(2:l)%1=2:2:l
l%x=x:l
h a=any(>=[2])$foldl(zipWith(%))e`iterate`map(2:)a!!(sum(2<$a)^2+2)

Try it online!

Similarly to other answers, this "flood-fills" the input with 2s and checks if we reach the right edge.

l%x acts like x:l, but if l starts with a 2 and x is 1, then x is replaced by a 2 also.

foldl(zipWith(%))e is then a function that rotates a list of rows 90° while making 2s "spread into" 1s, using our infectious flipped-cons operator. This is based on the shorter transpose trick: Using foldl instead of foldr rotates the array instead of transposing it.

We start from map(2:)a (append a column of 2s on the left), and apply foldl(zipWith(%))e \$4\,\mathrm{length}(a)^2+2\$ times. This is enough iterations to flood-fill even the twistiest of paths, and also turns the input upside-down. Then we check if any upside-down row starts with a two using any(>=[2]).

The \$4\,\mathrm{length}(a)\$ part of the iteration count is computed as \$\left( \sum_{x \in a} 2 \right)^2\$.

Thanks to xnor for contributing lots of good ideas!

Answer 5

Jelly, 28 bytes

+þ2ŒRBU¤ẎQfðƬṪ
ŒṪḷ/Ị$Ƈç$Ḣ€iL

Try it online!

-2 bytes thanks to caird coinheringaahing
-2 bytes using transposed form

Returns 0 for falsy and non-zero for truthy

Uses the exact same breadth-first-fill helper link as my answer to "But, Is It Art?"

+þ2ŒRBU¤ẎQfðƬṪ     Helper Link; given a list of starting coordinates on the left and a list of accessible coordinates on the right, fill
           ðƬ      Repeat until results are no longer unique
+þ                 Product table by addition of the current coordinates and
  2ŒRBU¤           As a nilad:
  2ŒR              - [-2, -1, 0, 1, 2]
     B             - Binary: [[-1, 0], [-1], [0], [1], [1, 0]]
      U            - Reverse Each: [[0, -1], [-1], [0], [1], [0, 1]]
        Ẏ          Tighten; dump the product table into a flat list of coordinates
         Q         Remove duplicates
          f        Filter to only keep valid coordinates (based on the right side)
             Ṫ     Tail; get the last list (the breadth-first-filled list of coordinates)
ŒṪḷ/Ị$Ƈç$Ḣ€iL      Main Link; take a binary matrix
ŒṪ                 Convert to a list of filled coordinates
        $          Call this monad on this list of coordinates:
       ç           - Call the helper link, with the following on the left:
     $Ƈ              - The list of coordinates, filtered to keep elements where:
  ḷ/                   - The first element (the row coordinate)
    Ị                  - Is insignificant (in inclusive range [-1, 1])
         Ḣ€        Get the row of each filled coordinate
           i       Index of (0 if not found)
             L     The length of the matrix (height)

Essentially, this just starts at every position in the top row, fills, and sees if it reaches the bottom row.

Answer 6

05AB1E, 42 36 bytes

A slower but maybe golfable? version. After looking at Jonah's J answer I was able to remove 6 bytes.

gÅ1¸.øεā*0K€¸<Nδš}€`DδαO2‹DvDδ*O}нθĀ

Try it online!

---

05AB1E, 42 bytes

A lot of this is similar to this recent answer of mine. Tests for a top-bottom connection.

εā*0K€¸<Nδš}D€gU€`DδαO2‹DvDδ*O}Xθ.£øOXн£OĀ

Try it online! Header transposes the input to test left-right connections.

This is quite long because of missing builtins for all indices of and matrix operations. High-level explanation:

εā*0K€¸<Nδš} get all indices of 1's.
€gU store the number of 1's in each row in variable X.
DδαO2‹ calculates a adjacency matrix \$A\$ of all 1's.
DvDδ*O} squares the matrix \$k=\operatorname{len}(A)\$ times.
Xθ.£øOXн£OĀ checks if there is a positive integer in the top left submatrix of \$A^{2k}\$ of size \$c_1\times c_n\$, where \$c_i\$ is the number of 1's in row \$i\$.

Answer 7

APL (Dyalog Unicode), 24 bytes

Uses the same method as Jonah's J answer. Full program that detects top-bottom connections.

⊃⌽⌈.×⍣≡⍨2>+/¨|∘.-⍨⍸1⍪⎕⍪1

Try it online! Footer transposes inputs.

                   1⍪⎕⍪1 ⍝ the input matrix with additional rows of 1's at the top and bottom
                  ⍸      ⍝ get all 2d indices of 1's
             |∘.-⍨       ⍝ table of absoulute element-wise differences
          +/¨            ⍝ sum each pair of absoulte differences
        2>               ⍝ values of 1 or 0 mark adjacent (or same) 1's
  ⌈.×⍣≡⍨                 ⍝ "matrix multiplication" until convergence. Instead of summing values we take the maximum to keep everything as 0 or 1
 ⌽                       ⍝ reverse each row of the matrix
⊃                        ⍝ take the very first number of the matrix

Answer 8

Wolfram Language (Mathematica), 81 bytes

Max[Intersection@@MorphologicalComponents[#,CornerNeighbors->False][[{1,-1}]]]>0&

Solves the transpose problem, looking for connections between the top and bottom rows. The long-named overkill builtin MorphologicalComponents[#,CornerNeighbors->False] changes the 1s in the input to different integers shared by connected groupings (where we must override the default that diagonal connections count); then we simply look to see if there's a positive integer in common in the first and last rows. Someone should translate this into Sledgehammer....

Answer 9

Python 3, 135 127 123 bytes

Answering my own question since there is no python solution yet. Expects a transposed matrix. Strongly inspired by Lynn's rotation method. I'm sure there is room for improvement!

def f(x):
 x+=[[3]*len(x)]
 for _ in x*4*len(x):x=[map(lambda a,b:a|a*2&b,y,(0,*y))for y in zip(*x)][::-1]
 return 3in x[0]

Try it online!

Answer 10

MATL, 21 20 19 18 bytes

Translation of @elementiro's MATLAB/Octave answer, with small modifications.

The input is a binary matrix (using ; as row separator).

The output is either a row vector with all entries eqwual to 1 (which is truthy), or a row vector with at least one entry eqwual to 0 (which is falsy). The footer contains the truthiness/falsihood test.

O4LZ(Gz:"2Y6Z+G*]a

Try it online! Or verify all test cases.

Answer 11

JavaScript (ES7),  103 101  94 bytes

Expects a transposed binary matrix. Returns 0 or 1.

f=(m,X,Y=-1)=>!m[Y+1]|m.some((r,y)=>r.some((v,x)=>v&&(X-x)**2+(Y-y)**2<2|!y&&--r[x]|f(m,x,y)))

Try it online!

Commented

f = (                  // f is a recursive function taking:
  m,                   //   m[] = input matrix
  X, Y = -1            //   (X, Y) = current position, starting with
) =>                   //            X undefined and Y = -1
!m[Y + 1] |            // success if we've reached the last row
m.some((r, y) =>       // for each row r[] at position y in m[]:
  r.some((v, x) =>     //   for each value v at position x in r[]:
    v &&               //     abort if v = 0
    (X - x) ** 2 +     //     if the squared distance between
    (Y - y) ** 2 < 2 | //     (x, y) and (X, Y) is less than 2
    !y                 //     or y = 0 (see the note below):
    &&                 //
      --r[x] |         //       clear r[x]
      f(m, x, y)       //       do a recursive call
  )                    //   end of inner some()
)                      // end of outer some()

Note: Any cell at \$(x,0)\$ with a \$1\$ on it is considered to be a valid destination square, no matter what the current position is, which may result in an invalid move. But if we start a path from \$(x_0,0)\$, suddenly jump to \$(x_1,0)\$ and find an apparently invalid solution, it just means that we could have started from \$(x_1,0)\$ and find a valid solution.

Answer 12

Perl 5 (-p), 65 bytes

/
/;$,="(.{@-})?";s/^1/#/gm;1while s/#$,\K1|1(?=$,#)/#/s;$_=/#$/m

Try it online!

-00l012 options are just used to run all tests and to print result.

/\n/ to match first end of line, to get the width

$,="(.{@-})?"; to define the variable $, with expression that matches the line width characters (used to match a character above or below another

s/^1/#/gm to replace all 1 in the first column with #

1while s/#$,\K1|1(?=$,#)/#/s while a 1 is found (below, on the right, on the left or above a #, replace with #

$_=/#$/m result is: is there a # in the last column

Answer 13

Charcoal, 25 bytes

ＷＳ⊞υ⭆⪫11ι℅¬Ｉκ⪫υ¶←¤-Ｊ⁰¦⁰Ｔ¹

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of strings (-3 bytes to take a input as a cumbersome array of strings: Try it online!) and outputs a Charcoal boolean, i.e. - if a path exists, blank if not. Explanation:

ＷＳ⊞υ⭆⪫11ι℅¬Ｉκ

Wrap each line in 1s. This changes the condition to requiring a path from the top left to the bottom right corner. The 1s and 0s are then changed to null and non-null bytes.

⪫υ¶

Print the non-null bytes. (Null bytes erase rather than printing.)

←

Move to the bottom right corner.

¤-

Try to fill with -s.

Ｊ⁰¦⁰Ｔ¹

Delete everything except the top right corner, which will have been filled with - if there is a path and left erased if not.

Answer 14

Jelly, 20 bytes

ḣ1ŒṪạÆịỊẸʋƇ@ƬŒṪ=LḄỊȦ

A monadic Link that accepts a list of the columns (i.e. transposed version of the OP's examples) and yields 1 (no connection) or 0 (connection).

Try it online! Or see the test-suite.

How?

Builds up all coordinates reachable from the first column by repeatedly adding those within a unit circle of any found so far, then checks if any of these coordinates is in the final column by virtue of their column coordinate being equal to the total number of columns.

ḣ1ŒṪạÆịỊẸʋƇ@ƬŒṪ=LḄỊȦ - Link: List of lists, Columns
ḣ1                   - head to index 1 (first column wrapped in a list)
  ŒṪ                 - multi-dimensional truthy indices (of that) -> X
             ŒṪ      - multi-dimensional truthy indices (of Columns) -> Y
            Ƭ        - start with X and collect until no change, applying:
           @         -   with swapped arguments:
          Ƈ          -     filter keep those (coordinates, c, in Y) for which:
         ʋ           -       last four links as a dyad - f(c,X):
    ạ                -         (c) absolute diference (X) (vectorises)
     Æị              -         from [Real, imaginary] to complex (vectorises)
       Ị             -         absolute value <= 1? (vectorises)
        Ẹ            -         any?
               =L    - equals length(M)? (vectorises)
                 Ḅ   - convert from binary (vectorises)
                  Ị  - absolute value <= 1? (vectorises)
                   Ȧ - any and all? (0 if 0 present when flattened else 1)

Answer 15

JavaScript, 85 bytes

A=>f=(i=0,X=0,Y=-1)=>Y<0||A[Y][X]?(A+0)[i]&&[2,1,0,-1].map(t=>f(i+1,X+t--%2,Y+t%2)):0

Slow. Error if possible. Treating all area Y<0 as solid and try walking enough time, error if it goes Y>Ymax(A[Y] is undefined)

Try it online!

Answer 16

Retina 0.8.2, 61 bytes

.+
1$&2
+`(?<=(.)*)(1|2)((?>.*¶(?<-1>.)*))?(?!\2)[12]
2$+2
^2

Try it online! Explanation:

.+
1$&2

Wrap each row between a 1 and a 2.

+`(?<=(.)*)(1|2)((?>.*¶(?<-1>.)*))?(?!\2)[12]
2$+2

Repeatedly find pairs of 1s and 2s either horizontally or vertically adjacent and replace them both with 2s. This will hopefully find a path from the right-hand column of 2s through the input and end up filling the whole left-hand column of 1s.

^2

Check whether a path was found.