Toggle some bits and get an actual square

Question

Inspired by the title of the Toggle some bits and get a square challenge.
In that challenge you output how many bits should be toggled, in order for the base-10 representation of the binary to become a square number.

Challenge:

In this challenge, you'll be given a bit-matrix \$M\$ and an integer \$n\$ as inputs.
Output the edge-size of the largest square you can make by toggling at most \$n\$ bits in the grid. A square is defined as having a border of 1s, with an irrelevant inner body.
E.g., these all contain valid squares of size 4x4, highlighted below with X:
^{(for the third example, more than one 4x4 square is possible)}

1111  1111  11111111  010110
1001  1011  11111111  001111
1001  1101  11111111  101011
1111  1111  11111111  111001
                      011111

XXXX  XXXX  XXXX1111  010110
X00X  X01X  X11X1111  00XXXX
X00X  X10X  X11X1111  10X01X
XXXX  XXXX  XXXX1111  11X00X
                      01XXXX

Example:

So let's say the inputs are \$n=4\$ and \$M=\$

010110
001011
101010
111001
011110

You could toggle these three bits (highlighted as T):

010110
001T11
10101T
111001
01111T

to get the 4x4 square of the fourth example above. So the output is 4.

Challenge rules:

• You can take the input-grid in any reasonable format. Can be a matrix of integers; matrix of booleans; list of strings; list of integers for which their binary representation (with leading 0s) is the binary grid; etc.
• You toggle at most \$n\$ bits, not exactly \$n\$ bits.
• The input-matrix \$M\$ is not guaranteed to be a square, but it is guaranteed to be a (non-empty) rectangle.
• The input-integer \$n\$ is guaranteed to be non-negative (\$n\geq0\$).

General Rules:

• This is code-golf, so the shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (e.g. TIO).
• Also, adding an explanation for your answer is highly recommended.

Test Cases:

Inputs:	Output:
\$n\$=4 and \$M\$= 010110 001011 101010 111001 011110	4
\$n\$=8 and \$M\$= 00101 01010 11011 10010 01001	4
\$n\$=0 and \$M\$= 000 000 000 000	0
\$n\$=0 and \$M\$= 111 111	2
\$n\$=1 and \$M\$= 101 010 101	1
\$n\$=1000 and \$M\$= 100010 010010 100101 100011 110110 110101 010010 101001 101011	6

Answer 1

JavaScript (ES6), 139 bytes

Expects (n)(matrix).

n=>m=>m.map(W=h=(X,w,k,Y)=>m.map((r,y)=>r.map((v,x)=>k?h(x,w,q=t=0,y):(x-X)%w&&(y-Y)%w||x<X|x>X+w|y<Y|y>Y+w||++q<w*4|(t+=!v)>n?0:W=w+1)))|W

Try it online!

Commented

n =>                    // n = max. number of times we can toggle bits
m =>                    // m[] = binary matrix
m.map(W =               // initialize W to a zero'ish value
h = (X, w, k, Y) =>     // for each entry in m[], using a recursive callback h:
  m.map((r, y) =>       //   for each row r[] at index y in m[]:
    r.map((v, x) =>     //     for each value v at index x in r[]:
      k ?               //       if this is the first pass:
        h(              //         do a recursive call:
          x,            //           set X = x
          w,            //           pass w unchanged
          q = t = 0,    //           set k = q = t = 0
          y             //           set Y = y
        )               //         end of recursive call
      :                 //       else (2nd pass):
        (x - X) % w &&  //         do nothing if we're not located on the grid
        (y - Y) % w ||  //         of width w
        x < X |         //         or x is too low
        x > X + w |     //         or x is too high
        y < Y |         //         or y is too low
        y > Y + w       //         or y is too high
        ||              //         otherwise:
          ++q < w * 4 | //           increment q
          (t += !v) > n //           increment t if v = 0
          ?             //           if q < w * 4 (not a complete square)
                        //           or t > n (too many bits must be toggled):
            0           //             do nothing
          :             //           else:
            W = w + 1   //             success: update W
    )                   //     end of map()
  )                     //   end of map()
) | W                   // end of map(); return W

Answer 2

MATL, 30 bytes

xZyP:"0&G@qWQB&+gZ++7Mz<m@*vX>

It uses convolution \o/

Inputs are n, then M.

Try it online! Or verify all test cases.

Explanation

x        % Implicit input: n. Delete
Zy       % Implicit input: M. Size as a length-two vector, [R, C]
P        % Sort. Gives [S, L], where S = min(R, C) is the smallest dimension of A
:        % Range from 1 to the first entry of the vector, that is, A
"        % For each k in [1, 2, ... , A]
  0      %   Push 0
  &G     %   Push the two inputs again: n, then M
  @      %   Push k
  qWQB   %   Subtract 1, 2 raised to that, add 1, binary: gives [1 0 0 ··· 0 1] of
         %   length k
  &+g    %   2D array of pairwise additions. Convert to logical. This gives a binary
         %   k×k array with a frame of ones: [1 1 ··· 1 1;
         %                                    1 0 ··· 0 1;
         %                                    ··· ··· ···  
         %                                    1 0 ··· 0 1;
         %                                    1 1 ··· 1 1]
  Z+     %   2D convolution with M, maintaining size. This counts the number of ones
         %   in M along all sliding frames of the above form. The result is a 2D array
  +      %   Add the above with n, element-wise.
  7M     %   Push the 2D array defining the frame again. Number of nonzeros. This
         %   gives the frame "length", that is, the number of ones (which is 4*(k-1))
  <      %   Less than?, element-wise. An entry equal to 0 indicates that a frame
         %   exists such that the number of ones in M along that frame plus n is at
         %   least the frame length
  m      %   Ismember. This checks if 0 is indeed present in the above result
  @*     %   Multiply the above by k. This will give either 0 or k
  vX>    %   Concatenate stack contents, then maximum. This computes a cumulative
         %   maximum of the results for all k (each result being either 0 or k)
         % End (implicit). Display (implicit)

Answer 3

JavaScript (Node.js), 133 bytes

n=>m=>m.map(W=h=(X,w,Y,t)=>m.every((r,y)=>[...r,0].every((v,x)=>t?x%w&&y%w||x>w|y>w||(t+=1-(m[y+Y]||0)[x+X]):h(x,w,y,~n)?W=w+1:1)))|W

Try it online!

JavaScript (Node.js), 134 bytes

n=>m=>m.map(W=h=(X,w,k,Y)=>m.map((r,y)=>r.map((v,x)=>k?h(x,w,q=t=0,y):x%w&&(y-Y)%w||x>w|y<Y|y>Y+w||++q<w*4|(t+=!r[x+X])>n?0:W=w+1)))|W

Try it online!

Modified from Arnauld's

JavaScript (Node.js), 156 bytes

M=>n=>M.map((_,i)=>M.map((N,y)=>N.map((c,x)=>R=M.map((_,j)=>W-=j<i&&N[x+j]+M[y+i][x-~j]+M[y-~j][x]+M[y+j][x+i],W=4*i+!i*!c)&&W<=n?i+1:R),M.push([])),R=0)&&R

Try it online!

I don't know what I'm doing...

M=>n=> // Unupdated
M.map((_,i)=>      
  M.map((N,y)=>N&&
    N.map((c,x)=>
      R=M.map((_,j)=>
        W-=j<i&&
          N[x+j]+         
          M[y+i][x-~j]+
          M[y-~j][x]+
          M[y+j][x+i],
        W=4*i)|i|c|n&&    // When i=0
                          // Special consider: 
                          // Here is 1, or
                          // n>0
        W<=n?i+1:R),M.push(0)),R=0)&&R
                 // So Z[y+i] isn't undefined

Answer 4

Pyth, 63 bytes

KEVUQVUhQVhS,-lQN-lhQHIgKsm!|*F*V-Rbdd@@Q+Nhd+Hed^Uhb2=eS,Zhb;Z

Try it online!

Expects array of arrays of booleans and \$n\$ in that order.

Explanation

                                                                   # implicitly assign Q = eval(input())
KE                                                                 # assign K = eval(input())
  VUQ                                                              # for N in range(len(Q)):
     VUhQ                                                          #   for H in range(len(Q[0])):
         VhS,-lQN-lhQH                                             #     for b in range(1+max(len(Q)-N, len(Q[0])-H)):
                          m                      ^Uhb2             #       map range(b+1) x range(b+1) to lambda d  (look at coordinates in a square of size b+1)
                           !|                                      #         neither of the following are true
                             *F*V-Rbdd                             #         d[0]*d[1]*(d[0]-b)*(d[1]-b)  (coordinates are in the middle of the square)
                                      @@Q+Nhd+Hed                  #         Q[N+d[0]][H+d[1]]  (coordinates are already a 1 in Q)
                      IgKs                                         #       if K >= (the sum of this map):
                                                      =eS,Zhb      #         Z = max(Z, b+1)
                                                             ;Z    # after all loops complete, output Z

Answer 5

Jelly,  27  25 bytes

¬ẆZṡLƊ€Ẏ.ị$€JṖḊƊ¦FS>ʋÐḟẈṀ

A dyadic Link that accepts the matrix, \$M\$, on the left and the maximal toggle count, \$n\$, on the right and yields the side length of the largest attainable square.

Try it online! Or see the test-suite.

How?

Toggles all bits of \$M\$ and extracts all possible square sub-matrices. Filters out any which have more than \$n\$ ones in their border, and then gets the length of the longest remaining one (or zero).

¬ẆZṡLƊ€Ẏ.ị$€JṖḊƊ¦FS>ʋÐḟẈṀ - Link: list of lists of 1s and 0s; M, integer, n
¬                         - logical NOT (M) -> toggle all bits of M
 Ẇ                        - get all contiguous sublists of rows of that
      €                   - for each (sublist, s, of rows):
     Ɗ                    -   last three links as a monad - f(s):
  Z                       -     transpose (s)
    L                     -     length (s)
   ṡ                      -     all sublists of (transposed s) of length (length (s))
                              -> all full height square sub-matrices from s
       Ẏ                  - tighten to a list of all square-submatrices
                     Ðḟ   - filter discard those for which:
                    ʋ     -   last four links as a dyad - f(sub-matrix, n)
           €    ¦         -     sparse application...
               Ɗ          -     ...to indices: last three links as a monad - f(sub-matrix):
            J             -                      range of length
             Ṗ            -                      pop
              Ḋ           -                      dequeue -> [2,3,...,length-1]
          $               -     ...action: last two links as a monad - f(sub-matrix):
        .                 -                  0.5
         ị                -                  index into (sub-matrix) -> last and first entries
                 F        -     flatten
                  S       -     sum
                   >      -     is greater than (n)?
                       Ẉ  - length of each (remaining sub-matrix)
                        Ṁ - maximum (or 0 if empty)

---

Note: the second € is necessary, even though all of the test cases pass without it (e.g. this should return 2 not 3).

Answer 6

Charcoal, 61 bytes

ＮθＷＳ⊞υι≔ＬυζＷ⬤υ⬤κ›⁻∨×⁴⊖ζ¹θΣ⭆υ⎇№…λ⁺λζπ✂ξν⁺νζ∨∨⁼πλ⁼π⁺λ⊖ζ⊖ζω≦⊖ζＩζ

Try it online! Link is to verbose version of code. Takes n as the first input and then the binary matrix M as a list of newline-terminated strings. Explanation:

Ｎθ

Input n.

ＷＳ⊞υι

Input M.

≔Ｌυζ

Start with the height of M as the current square size.

Ｗ⬤υ⬤κ›⁻∨×⁴⊖ζ¹θΣ⭆υ⎇№…λ⁺λζπ✂ξν⁺νζ∨∨⁼πλ⁼π⁺λ⊖ζ⊖ζω

For each possible cell of M, try to slice a square of the current size out of M, count the number of 1s on its border, and while none of the candidate squares have enough 1s...

≦⊖ζ

... decrement the square size.

Ｉζ

Output the final square size.

Answer 7

PARI/GP, 116 bytes

f(a,n)=for(k=l=0,min(#a,#a~),matrix(#a~-k,#a-k,i,j,sum(s=0,k,sum(t=0,k,!(s*t*(k-s)*(k-t)+a[i+s,j+t])))<=n)&&l=k+1);l

Attempt This Online!

Answer 8

05AB1E, 40 bytes

U˜āR.Δ…€üÿD'øý.V€`ε4Fćˆíø}¯˜_OXs@´}à}Dd*

Since there isn't a 05AB1E answer yet, I'll just create my own.

Inputs in the order \$n,M\$.

Try it online or verify all test cases.

Explanation:

U                  # Pop and store the first (implicit) input-integer in variable `X`
˜                  # Flatten the second (implicit) input-matrix
 ā                 # Push a list in the range [1,length]
  R                # Reverse it to [length,1]
   .Δ              # Pop and find the first value that's truthy for
                   # (or -1 if none are truthy):
     …€üÿD'øý.V€` '#  Get a list of all overlapping block of size y×y
                   #  (where `y` is the current integer):
     …€üÿ          #   Push string "€üÿ",
                   #   where `ÿ` is automatically replaced with the current integer
         D         #   Duplicate it
          'øý     '#   Join the two strings on the stack with "ø" delimiter
             .V    #   Evaluate and execute it as 05AB1E code:
      €            #    Map over each row of the (implicit) input-matrix
       üy          #     Get all overlapping lists of this row of size `y`†
         ø         #    Zip/transpose; swapping rows/columns
          €        #    Map over each list of lists
           üy      #     Get all overlapping lists of these row of size `y`†
             €`    #    Flatten this list of lists of blocks one level down
     ε4Fćˆíø}¯´˜   #  Leave just the borders of each y×y block:
     ε             #   Map over each block:
      4F           #    Inner loop 4 times:
        ć          #     Extract head; pop and push remainder-matrix and first row
                   #     separately to the stack
         ˆ         #     Pop and add this first row to the global array
          íø       #     Rotate the matrix once clockwise:
          í        #      Reverse each inner row
           ø       #      Zip/transpose; swapping rows/columns
       }¯          #    After the loop: push the global array
         ˜         #    Flatten it
          _        #    ==0 check (0 becomes 1; everything else becomes 0)
           O       #    Sum to get the amount of 0s in this block's borders
            X      #    Push the first input from variable `X`
             s@    #    Check amountOfZeros <= `X`
        ´          #    Empty the global array for the next iteration
     }à            #   After the map, do an `any` check by popping and pushing the max
   }Dd*            #  After the find first: fix a potential -1 to 0†:
    D              #   Duplicate the integer
     d             #   Pop the copy and do a non-negative check (1 if >=0; 0 if <0)
      *            #   Multiply the two together
                   # (after which the result is output implicitly)

We have to do the }Dd* instead of just lowering the [length,1] ranged list to [length,0], because ü0 would give an error.