12
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why the third test case is true? \$\endgroup\$
    – Fmbalbuena
    Jan 29 at 18:40
  • \$\begingroup\$ @Fmbalbuena That's the case we use as an example in the body of the post. Swap the top and bottom rows. \$\endgroup\$
    – Wheat Wizard
    Jan 29 at 18:41

8 Answers 8

3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ 265 \$\endgroup\$
    – AnttiP
    Jan 29 at 21:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – AnttiP
    Jan 29 at 21:54
  • \$\begingroup\$ @AnttiP Thank you, updated. \$\endgroup\$
    – Ajax1234
    Jan 30 at 3:50
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 31 at 14:55
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 129 112 bytes

WS⊞υ⌕Aι1≔⟦⟦⟧⟧θFυ«≔⟦⟧ηFθF⊕Lκ⊞η⁺⁺✂κ⁰λ¹⟦ι⟧✂κλLκ≔ηθ»Fθ«≔⟦⟧ηFLιF§ικ⊞η⟦κλ⟧≔E⊟ι⟦Lικ⟧ιWΦ⁻ηιΦ⁴№ιEλ⁺π∧⁼ρ﹪ν²⊖⁻νρFκ⊞ιλP↔¬⁻ηι

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:

WS⊞υ⌕Aι1

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

≔⟦⟦⟧⟧θ

Start building up the permutations of the rows.

Fυ«

Loop through the rows.

≔⟦⟧η

Start building up the permutations that include this row.

Fθ

Loop through the permutations of the previous rows.

F⊕Lκ

Loop through the possible insertion points.

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

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

≔ηθ

Save the list of permutations.

»Fθ«

Loop through all of the permutations.

≔⟦⟧ηFLιF§ικ⊞η⟦κλ⟧

List the coordinates of all the 1s.

≔E⊟ι⟦Lικ⟧ι

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

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

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

Fκ⊞ιλ

... save all the newly discovered stable coordinates.

P↔¬⁻ηι

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.