For xor Young (15+)

Question

A Young diagram is a rectangular binary mask whose every row and every column are sorted in descending order.

It is easy to check that every rectangular binary mask can be formed by xor-ing together a finite number of Young diagrams.

This decomposition is by no means unique, but there will be a minimum number of Young diagrams required. Your task in this code golf challenge is given a number \$k\$ and an \$m\$-by-\$n\$ binary mask \$b\$ determine whether \$b\$ can be represented as xor of \$k\$ \$m\$-by-\$n\$ Young diagrams.

Example xor decompositions: These are minimal and can be used as test cases: Just take the leftmost pattern. The minimum number of Young diagrams is written just below it. If you take the pattern together with a smaller number you get a falsy test case and a truthy one otherwise. Your code needn't output the decomposition. It is typically not unique anyway.

1001        1000   1110   1111   1111   1111
0010   <-   0000   1100   1110   1111   1111
1001        0000   0000   1000   1110   1111
5

0010        1100   1110
0110   <-   1000   1110
1100        0000   1100
2

1001        1000   1100   1100   1110   1111
0100   <-   0000   1000   1100   1110   1110
1010        0000   0000   1000   1100   1110
5

1010        1000   1100   1110   1111   1111
1011   <-   0000   0000   1000   1100   1111
0010        0000   0000   0000   1100   1110
5

00111110        11000000   11110000   11110000   11111110   11111111   11111111
11101001   <-   00000000   11100000   11110000   11111000   11111110   11111111
00110111        00000000   00000000   11000000   11110000   11111000   11111111
6

10111010        10000000   11000000   11100000   11100000   11111000   11111100   11111110   11111111   11111111
10010111   <-   00000000   00000000   10000000   11100000   11110000   11111000   11111110   11111110   11111111
11100101        00000000   00000000   00000000   00000000   11100000   11111000   11111100   11111110   11111111
9

11100110        11100000   11110000   11110000   11111000   11111110   11111111   11111111
00110110   <-   00000000   11000000   11110000   11111000   11111110   11111111   11111111
00100001        00000000   00000000   00000000   11000000   11100000   11111110   11111111
7

10110011        10000000   11000000   11110000   11111000   11111000   11111100   11111111   11111111   11111111
00111100   <-   00000000   00000000   00000000   11000000   11111000   11111000   11111100   11111111   11111111
01110101        00000000   00000000   00000000   10000000   11110000   11111000   11111100   11111110   11111111
9

10110        10000   11000   11110   11111   11111
01111        00000   10000   11110   11110   11111
11101   <-   00000   00000   11100   11110   11111
10000        00000   00000   10000   11110   11110
00110        00000   00000   00000   11000   11110
5

00101        11000   11100   11110   11111   11111   11111
10010        00000   10000   11100   11110   11111   11111
10010   <-   00000   10000   11100   11110   11111   11111
10101        00000   10000   11000   11100   11110   11111
11011        00000   00000   00000   11000   11100   11111
6

0111101        1000000   1110000   1110000   1111100   1111110   1111111   1111111   1111111
1101000        0000000   1100000   1110000   1111000   1111100   1111100   1111111   1111111
1001100   <-   0000000   0000000   0000000   1000000   1110000   1111100   1111111   1111111
0000001        0000000   0000000   0000000   0000000   1110000   1110000   1111110   1111111
0110010        0000000   0000000   0000000   0000000   1000000   1110000   1111100   1111110
8

0001010        1000000   1000000   1110000   1111000   1111100   1111110   1111111   1111111
1000011        0000000   1000000   1100000   1100000   1111000   1111000   1111100   1111111
0100011   <-   0000000   0000000   1000000   1100000   1111000   1111000   1111100   1111111
1011010        0000000   0000000   0000000   1000000   1100000   1111000   1111100   1111110
1111110        0000000   0000000   0000000   0000000   0000000   0000000   0000000   1111110
8

011000101        100000000   111000000   111111000   111111100   111111110   111111110   111111110   111111111
000100001        000000000   000000000   111000000   111100000   111111110   111111110   111111110   111111111
111100111   <-   000000000   000000000   000000000   111100000   111111000   111111110   111111110   111111111
111100001        000000000   000000000   000000000   000000000   000000000   111100000   111111110   111111111
110000000        000000000   000000000   000000000   000000000   000000000   000000000   000000000   110000000
8

001100011        110000000   111100000   111110000   111110000   111111100   111111110   111111110   111111111   111111111   111111111
000110101        110000000   110000000   111000000   111110000   111111000   111111100   111111110   111111111   111111111   111111111
011011100   <-   100000000   110000000   110000000   111000000   111100000   111111000   111111000   111111100   111111111   111111111
100000001        000000000   100000000   110000000   110000000   111100000   111100000   111111000   111111000   111111110   111111111
110101001        000000000   000000000   000000000   110000000   111000000   111100000   111110000   111111000   111111110   111111111
10

Standard rules apply.

Answer 1

Python with numpy, 94 93 bytes

from numpy import*
S=cumsum
f=lambda k,m:f(k-1,flip(S(S(flip(m),0),1)>0)^m)if k else any(m)<1

Attempt This Online!

Takes a sequence of sequences of ints.

---

This uses a greedy algorithm.

Let A be the smallest Young diagram that contains the input (that is, has 1s where the input has 1s). I claim that A is part of an optimal solution.

Observe that the AND of two Young diagrams is a Young diagram, and the OR of two Young diagrams is a Young diagram.

Firstly, any solution can be converted to a solution that lies within A by ANDing each diagram with A.

Next, if the solution is X,Y,Z, we can replace X and Y with X|Y and X&Y without changing the overall XOR. Apply the same process to X|Y and Z next, to obtain a solution that includes X|Y|Z; this necessarily contains A, and thus is equal to A. (A similar repeating process works on solutions of any size.)

---

After flip reverses the input, cumsum in each direction spreads positiveness forwards, then >0 reduces the entries back to Booleans. flip again to return to the original orientation, then apply the XOR.

Answer 2

Charcoal, 36 bytes

ＮθＷＳ⊞υＩ⪪⮌ι¹ＦθＵＭυＥκ⁻⌈Ｅ✂υλＬυ¹⌈…ξ⊕νμ⌈⌈υ

Try it online! Link is to verbose version of code. Takes input as k and then the binary mask represented as a list of newline-terminated strings, and outputs - if k was too small, nothing if k was sufficient. Explanation: Uses a greedy algorithm.

Ｎθ

Input k.

ＷＳ⊞υＩ⪪⮌ι¹

Convert the newline-terminated list of strings into a binary matrix, although flip it horizontally because that saves a byte.

Ｆθ

Loop k times.

ＵＭυＥκ⁻⌈Ｅ✂υλＬυ¹⌈…ξ⊕νμ

Flip only those bits in the array that have a 1 bit in the rectangle whose original corners are the bit and the bottom right corner of the array. The array of the bits that were flipped is itself a Young diagram and the result of the flip is the same as the XOR of that diagram with the array.

⌈⌈υ

If k was sufficient, then the array will be all 0s, so its double maximum will also be 0, but if it was insufficient, then the maximum row will contain a 1, so the double maximum will also be 1. This is then output in unary as a count of -s.

Example:

0010
0110
1100

All the 1s get flipped because obviously any rectangle containing them contains a 1, but the 0s above and left also get flipped because there is a 1 in the rectangle from them to the bottom right corner. The Young matrix of bits that get flipped is therefore as follows:

1110
1110
1100

Answer 3

Wolfram Language (Mathematica), 55 bytes

-27 bytes thanks to @att.

r/@r@#-#&~Nest~##==0#&
r=#@*FoldList[BitOr]@*#&@Reverse

Try it online!

---

Wolfram Language (Mathematica), 82 bytes

If[#==0#,0,1+#0[#~BitXor~Map[Reverse@FoldList[BitOr,Reverse@#]&,#,{0,1}]]]&@#<=#2&

Try it online!

Or shorter if I can just take the matrix and output the minimum number \$k\$.

If[#==0#,0,1+#0[#~BitXor~Map[Reverse@FoldList[BitOr,Reverse@#]&,#,{0,1}]]]&

Try it online!

Answer 4

Pyth, 39 bytes

Lm|MCd._CbWss=QmxMCdC,Q__Myy__MQ=hZ;>EZ

Try it online!

A port of @m90's answer, be sure to upvote them.

Answer 5

Jelly, 25 bytes

ZLr0œċL⁸ḣ"ⱮFE$ƇḢ!^µÐ¡§§0e

A full program that accepts a rectangular list of lists of ones and zeros and a non-negative integer and prints 1 if possible or 0 if not.

Try it online!

This test-suite alters the code so it is callable as a dyadic Link (by replacing the µ with a newline and Ç⁹) and calls the link starting with 0 until a truthy result is found for each of the grids and returns the values reached. Note that going any higher is guaranteed to give a truthy result due to the implementation (repeatedly applying an operation and collecting up).

How?

Greedily inverts the Young "cut-out" that contains all of the same elements with the maximal row-length array. Performs this \$N\$ times and then checks for the existence of an array with no ones.

ZLr0œċL⁸ḣ"ⱮFE$ƇḢ!^µÐ¡§§0e - Main Link: grid of 1s and 0s, G (n rows, m columns)
                   С     - repeat and collect (starting with G)...
                          - ...times: (implicit) second program argument, N
                  µ       - ...action: the monadic chain to the left - f(Current):
Z                         -   transpose (Current)
 L                        -   length
  r0                      -   inclusive range to 0 -> [m,...,2,1,0]
      L                   -   length (Current) -> n
    œċ                    -   combinations with replacement
                              -> [[m,m,m],...,[m,m,1],[m,m,0],[m,m-1,m-1],...,[0,0,0]]
       ⁸                  -   chain's left argument -> Current
          Ɱ               -   map with:
         "                -     zip with:
        ḣ                 -       head to
                              -> Young-style "cut-outs" reverse sorted by row-lengths
              Ƈ           -   keep those for which:
             $            -     last two links as a monad:
           F              -       flatten
            E             -       all equal?
               Ḣ          -   head
                !         -   factorial (vectorises) -> converts all 0s to 1s
                 ^        -   XOR (Current)
                     §    - sums
                      §   - sums
                       0  - zero
                        e - exists in?

Answer 6

Python + NumPy, 82 bytes

from numpy import*
f=lambda k,m:~k<0<all(~m)|f(k-1,triu([email protected]<2)@m@tril(m[0]<2)^m)

Attempt This Online!

As @m90 doesn't seem to want my golfs and I don't want to let them go to waste I post them here.

This takes the input mask as a boolean array.

How?

It uses that a cumsum can be written as multiplication with a triangular matrix. By choosing upper or lower triangles we can choose whether to sum from left to right or from right to left.

Also, note that matrix multiplication preserves the type, bool in this case, so we needn't restore any larger values to 1.

Also worthwhile noting that NumPy bools behave differently to Python bools w.r.t. to ~.