Is there a stable way to stack these?

Question

If we have a binary matrix then we will say that a \$1\$ is stable if it is in the bottom row or it is directly adjacent to a \$1\$ which is stable.

In other words there must be a path to the bottom row consisting only of \$1\$s.

So in the following matrix the \$1\$s highlighted in red are not stable.

$$ 0110\color{red}{1}0\\ 0100\color{red}{11}\\ 110000\\ $$

A matrix is stable if every \$1\$ in it is stable.

Your task is to take a matrix or list of rows and determine if there is someway to rearrange the rows into a stable matrix.

The example above can be if we swap the top and bottom row:

$$ 110000\\ 011010\\ 010011\\ $$

But the following matrix cannot:

$$ 01010\\ 10101\\ 00000 $$

You may take input in any reasonable format. You may also assume that there is at least one row and that all rows are at least 1 element long. You should output one of two distinct values if it is possible to rearrange the rows into a stable matrix and the other if it is not.

This is code-golf so the goal is to minimize your source code with answers being scored in bytes.

Test cases

000
000
000
-> True
1
-> True
011010
010011
110000
-> True
01010
10101
00000
-> False
01010
10101
01110
-> True
01010
01100
00011
10101
-> False
10
01
-> False

Answer 1

J, 60 bytes

1 e.i.@!@#(1*/@,@([:+./ .*^:_~1>:[:|@-/~$j./@#:I.@,)@,])@A.]

Try it online!

Feels like there's a trick I'm missing, but this takes a brute force approach as follows:

• For each permutation of rows...
• Prepend of row of all ones...
• Check if the "distance of 1" graph of the 1 positions is fully connected.
• If it is, we've found a solution.

Answer 2

MATL, 27 26 24 bytes

Zy:Y@!"2G@Y)tQ&v4&1ZImvA

Input is a binary matrix. Output is 0 if stable, 1 otherwise.

Try it at MATL online! Or verify all test cases.

Explanation

Zy         % Input (implicit): binary matrixz. Size. Gives [r, c], where r and c
           % are the numbers of rows and of columns
:          % Range. Gives [1, 2, ... r] (c is ignored)
Y@         % All permutations of numbers 1, 2, ..., r. Gives an r-column matrix
           % where each row is a permutation
!"         % For each row
  2        %   Push 2
  G        %   Push input
  @Y)      %   Apply current permutation to the rows of the input
  tQ       %   Duplicate, add 1. Gives a matrix the same size as the input with
           %   all entries different from 0
  &v       %   Concatenate the two matrices vertically. This has the effect of
           %   adding a "bottom" of nonzeros to the permutation of the input
  4&1ZI    %   Connected components, using 4-neighbourhood (i.e. not diagonals)
           %   Each connected component of nonzeros is labelled 1, 2, ...
  m        %   Ismember: gives true if there is a connected component labelled
           %   with 2. This can only happen if some 1 in the input is not
           %   connected to the bottom, meaning that the current permutation
           %   is not stable
  vA       %   Concatenate vertically. All. This acts as a cumulative "and".
           %   The result is 1 if and only if all permutations so far were
           %   not stable
           % End (implicit). Display (implicit)

Answer 3

Python 3.8 (pre-release), 159 bytes

lambda l:any(f(0,len(l[0]),*sum(p,[]))for p in permutations(l))
f=lambda p,a,x,*t:a>len(t)or-(p:=p+t[a-1])-len(t)%a*t[0]+x<f(x*p,a,*t)>0
from itertools import*

Try it online!

Takes input as a 2d list. f is a function that checks if a matrix is stable. Then we just try every permutation, until we find a matrix that works.

Answer 4

JavaScript (Node.js), 167 bytes

f=(a,...b)=>a[0]?a.some(h=>f(a.filter(_=>_!=h),h,...b)):b[b=b.map(x=>[...x]),0].map(g=(y,x)=>(e=b[~y]||0)[x]&&++e[a=2,x]+[-1,1].map(i=>g(y+i,x)+g(y,x+i)))|!/1/.test(b)

Try it online!

Input -1 for true and 0 for false

Answer 5

Python3, 265 bytes:

lambda b:any(v(i)for i in permutations(b))
from itertools import*
E=enumerate
def p(b,c,d):
 if c==len(b)-1:return 1
 try:
  for x,y in[(0,1),(0,-1),(1,0)]:
   if(y:=d+y)*b[c+x][y]:return 1
 except:return 0
v=lambda b:all(p(b,x,y)for x,l in E(b)for y,s in E(l)if s)

Try it online!

Answer 6

JavaScript (Node.js), 116 bytes

f=(a,p=1)=>a.some((r,j)=>r.every((c,i)=>c?(s|=p[i],l=1):!(l=s=l>s),l=s=0)&l<=s|p&&f(b=[...a],b.splice(j,1)[0]))||++a

Try it online!

Input 0/1 matrix. Output true vs NaN.

Answer 7

05AB1E, 53 bytes

œʒ¬!ªÐU˜!ƶsgäΔ0δ.ø¬0*šĆ2Fø€ü3}εεÅsyøÅs«à}}X*}˜0KÙg}gĀ

Try it online or verify all test cases.

Explanation:

In pseudo-code, I do the following steps (with the code-parts behind it - as you can see, the flood-fill takes up most of the bytes):

1. Get all permutations of rows of the input-matrix (œ)
2. Check if any permutation is truthy for the following steps (ʒ...}gĀ):

   1. Append a row of 1s to the matrix as new bottom (¬!ª)

      1. E.g. the permutation we want to check is:

          0,1,1,0,1,0
          0,1,0,0,1,1
          1,1,0,0,0,0
         

      2. Then it will become this with bottom row of 1s:

          0,1,1,0,1,0
          0,1,0,0,1,1
          1,1,0,0,0,0
          1,1,1,1,1,1
         

   2. Flood-fill the matrix, using only horizontal/vertical moves - done in a similar matter as @Jonah's J answer for the To find islands of 1 and 0 in matrix challenge (ÐU˜!ƶsgäΔ0δ.ø¬0*šĆ2Fø€ü3}εεÅsyøÅs«à}}X*}):

      1. We first create a matrix of the same size with unique positive integers:

           1, 2, 3, 4, 5, 6
           7, 8, 9,10,11,12
          13,14,15,16,17,18
          19,20,21,22,23,24
         

      2. Then for each cell we get the maximum among itself and its horizontal/vertical neighbors:

           7, 8, 9,10,11,12
          13,14,15,16,17,18
          19,20,21,22,23,24
          20,21,22,23,24,24
         

      3. Which we multiply by the matrix of 0s/1s we started with (the one from step 2.1.2):

           0, 8, 9, 0,11, 0
           0,14, 0, 0,17,18
          14,15, 0, 0, 0, 0
          20,21,22,23,24,24
         

      4. And we continue steps 2.2.2 and 2.2.3 until the result no longer changes:

           0,24,24, 0,18, 0
           0,24, 0, 0,18,18
          24,24, 0, 0, 0, 0
          24,24,24,24,24,24
         

   3. Check if there is just a single island after the flood-fill (˜0KÙg)

As for the actual code:

œ             # Get all permutations of rows of the (implicit) input-matrix
 ʒ            # Filter this list of matrices by:
  ¬!ª         #  Append a row of 1s:
  ¬           #   Push the first row (without popping the matrix)
   !          #   Convert all 0s/1s to 1s with the faculty
    ª         #   Append this row of 1s to the matrix
  Ð           #  Triplicate the matrix
   U          #  Pop and store a copy in variable `X`
   ˜!ƶsgä     #  Pop and push a matrix of the same size with values [1,length]
   ˜          #   Flatten the matrix
    !         #   Convert everything to 1s with the faculty
     ƶ        #   Multiply every 1 by its 1-based index
      s       #   Swap so the last copy is at the top
       g      #   Pop and push its amount of rows
        ä     #   Pop and split the list into that many equal-sized parts
   Δ          #  Loop until the result no longer changes
              #  (which will be used to flood-fill the matrix):
    0δ.ø¬0*šĆ #   Surround the matrix with a border of 0s:
     δ        #    Map over each row:
    0 .ø      #     Surround it with a leading/trailing 0
        ¬     #    Push the first row (without popping)
         0*   #    Convert all 0s/1s to 0s by multiplying by 0
           š  #    Prepend this row of 0s to the matrix
            Ć #    Enclose; append its own head
    2Fø€ü3}   #   Get all 3x3 blocks of this matrix:
    2F        #    Loop 2 times:
      ø       #     Zip/transpose; swapping rows/columns
       €      #     Map over each row:
        ü3    #      Get all overlapping triplets of this row
          }   #    Close the loop
              #   Looking at horizontal/vertical neighbors only, get the maximum
              #   of each 3x3 block:
    εε        #    Nested map over each 3x3 block:
      Ås      #     Push its middle row
      yøÅs    #     Push its middle column
          «   #     Merge the two triplets together
           à  #     Pop and push the maximum
    }}        #    Close the nested maps
    X*        #   Then multiply each maximum by matrix `X`,
              #   so all cells that contained 0s become 0 again
   }          #  Close the flood-fill loop
    ˜         #  Flatten the matrix to a list
     0K       #  Remove all 0s
       Ù      #  Uniquify the remaining values
        g     #  Pop and push the length (only 1 is truthy in 05AB1E)
}gĀ           # After the filter: check if any permutations remain (length>=1)
              # (which is output implicitly as result)

There are a bunch of 5-bytes alternatives for ˜0KÙg, but I haven't been able to find a 4-byter.

Answer 8

Charcoal, 129 112 bytes

ＷＳ⊞υ⌕Ａι1≔⟦⟦⟧⟧θＦυ«≔⟦⟧ηＦθＦ⊕Ｌκ⊞η⁺⁺✂κ⁰λ¹⟦ι⟧✂κλＬκ≔ηθ»Ｆθ«≔⟦⟧ηＦＬιＦ§ικ⊞η⟦κλ⟧≔Ｅ⊟ι⟦Ｌικ⟧ιＷΦ⁻ηιΦ⁴№ιＥλ⁺π∧⁼ρ﹪ν²⊖⁻νρＦκ⊞ιλＰ↔¬⁻ηι

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings of 0s and 1s and outputs a Charcoal boolean i.e. - if a stable stack exists, nothing if not. Explanation:

ＷＳ⊞υ⌕Ａι1

Input the matrix and save the positions of the 1s in each row.

≔⟦⟦⟧⟧θ

Start building up the permutations of the rows.

Ｆυ«

Loop through the rows.

≔⟦⟧η

Start building up the permutations that include this row.

Ｆθ

Loop through the permutations of the previous rows.

Ｆ⊕Ｌκ

Loop through the possible insertion points.

⊞η⁺⁺✂κ⁰λ¹⟦ι⟧✂κλＬκ

Insert this row at that point and save it to the list of permutations.

≔ηθ

Save the list of permutations.

»Ｆθ«

Loop through all of the permutations.

≔⟦⟧ηＦＬιＦ§ικ⊞η⟦κλ⟧

List the coordinates of all the 1s.

≔Ｅ⊟ι⟦Ｌικ⟧ι

List the coordinates of the 1s on the bottom row, which are stable by definition.

ＷΦ⁻ηιΦ⁴№ιＥλ⁺π∧⁼ρ﹪ν²⊖⁻νρ

While there are unknown coordinates adjacent to at least one stable coordinate, ...

Ｆκ⊞ιλ

... save all the newly discovered stable coordinates.

Ｐ↔¬⁻ηι

Overwrite the output with - if all the coordinates were stable.