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 1
s, 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\$=
|
4 |
\$n\$=8 and \$M\$=
|
4 |
\$n\$=0 and \$M\$=
|
0 |
\$n\$=0 and \$M\$=
|
2 |
\$n\$=1 and \$M\$=
|
1 |
\$n\$=1000 and \$M\$=
|
6 |