# Is there a stable way to stack these?

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

• Why the third test case is true? Jan 29 at 18:40
• @Fmbalbuena That's the case we use as an example in the body of the post. Swap the top and bottom rows. Jan 29 at 18:41

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

# MATL, 2726 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)


# Python 3.8 (pre-release), 159 bytes

lambda l:any(f(0,len(l),*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+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.

# JavaScript (Node.js), 167 bytes

f=(a,...b)=>a?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

# 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!

• 265 Jan 29 at 21:50
• If you have a function that just returns an expression it's shorter as a lambda. When you are testing if two integers are positive and non-negative you can multiply them together instead of using and. The values in q don't matter, in fact we don't even need q for anything, and can just return directly 0 or 1. from foo import* is always shorter than import foo as F. Finally, I've split c to the x and y components, since they were always accessed separately. Jan 29 at 21:54
• @AnttiP Thank you, updated. Jan 30 at 3:50
• 249 bytes. Moved if statement into for loop. Replaced except:return 0 to except:pass. Changed c==len(b)-1 to c>len(b)-2. Jan 31 at 14:55

# 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)))||++a


Try it online!

Input 0/1 matrix. Output true vs NaN.

# 05AB1E, 53 bytes

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


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.

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