The biggest square

Question

This question is similar to Biggest Square in a grid.

Challenge

Given a matrix of 1 and 0 in a string format "xxxx,xxxxx,xxxx,xx.." or array format ["xxxx","xxxx","xxxx",...], You will create a function that determines the area of the largest square submatrix that contains all 1.

A square submatrix is one of equal width and height, and your function should return the area of the largest submatrix that contains only 1.

For Example:

Given "10100,10111,11111,10010", this looks like the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

You can see the bolded 1 create the largest square submatrix of size 2x2, so your program should return the area which is 4.

Rules

• Submatrix must be one of equal width and height
• Submatrix must contains only values 1
• Your function must return the area of the largest submatrix
• In case no submatrix is found, return 1
• You can calculate the area of the submatrix by counting the number of 1 in the submatrix

Test cases

Input: "10100,10111,11111,10010" Output: 4

Input: "0111,1111,1111,1111" Output: 9

Input "0111,1101,0111" Output: 1

---

This is code-golf, so the shortest answer in bytes win.

Answer 1

Haskell, 113 121 118 117 bytes

x!s=[0..length x-s]
t#d=take t.drop d
f x=last$1:[s*s|s<-min(x!0)$x!!0!0,i<-x!!0!s,j<-x!s,all(>'0')$s#i=<<(s#j)x,s>0]

Try it online!

_{-3 bytes thanks to Laikoni!}

_{-1 byte thanks to Lynn!}

_{+8 bytes for the ridiculous requirement of returning 1 for no all-1s sub-matrix..}

Explanation/Ungolfed

The following helper function just creates offsets for x allowing to decrement them by s:

x!s=[0..length x-s]

x#y will drop y elements from a list and then take x:

t#d=take t.drop d

The function f loops over all possible sizes for sub-matrices in order, generates each sub-matrix of the corresponding size, tests whether it contains only '1's and stores the size. Thus the solution will be the last entry in the list:

--          v prepend a 1 for no all-1s submatrices
f x= last $ 1 : [ s*s
                -- all possible sizes are given by the minimum side-length
                | s <- min(x!0)$x!!0!0
                -- the horizontal offsets are [0..length(x!!0) - s]
                , i <- x!!0!s
                -- the vertical offsets are [0..length x - s]
                , j <- x!s
                -- test whether all are '1's
                , all(>'0') $
                -- from each row: drop first i elements and take s (concatenates them to a single string)
                              s#i =<<
                -- drop the first j rows and take s from the remaining
                                      (s#j) x
                -- exclude size 0...........................................
                , s>0
                ]

Answer 2

APL (Dyalog Unicode), 35 34 32 bytes

{⌈/{×⍨⍵×1∊{∧/∊⍵}⌺⍵ ⍵⊢X}¨⍳⌊/⍴X←⍵}

Try it online!

Adám's SBCS has all of the characters in the code

Explanation coming eventually!

Answer 3

Haskell, 99 97 bytes

b s@((_:_):_)=maximum$sum[length s^2|s==('1'<$s<$s)]:map b[init s,tail s,init<$>s,tail<$>s]
b _=1

Checks if input is a square matrix of just ones with s==('1'<$s<$s), if it is, answer is length^2, else 0. Then recursively chops first/last column/row and takes the maximum value it finds anywhere.

Try it online!

Answer 4

K (ngn/k), 33 28 bytes

{*/2#+/|/',/'{0&':'0&':x}\x}

Try it online!

Answer 5

J, 33 27 bytes

-6 bytes thanks to FrownyFrog!

[:>./@,,~@#\(#**/)@,;._3"$]

Try it online!

Explanation:

I'll use the first test case in my explanation:

    ] a =. 3 5$1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

I generate all the possible square submatrices with size from 1 to the number of rows of the input.

,~@#\ creates a list of pairs for the sizes of the submatrices by stitching ,. togehter the length of the successive prefixes #\ of the input:

   ,~@#\ a
1 1
2 2
3 3

Then I use them to cut x u ;. _3 y the input into submatrices. I already have x (the list of sizes); y is the right argument ] (the input).

 ((,~@#\)<;._3"$]) a
┌─────┬─────┬─────┬───┬─┐
│1    │0    │1    │0  │0│
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │0    │1    │1  │1│
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │1    │1    │1  │1│
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0  │0 1  │1 0  │0 0│ │
│1 0  │0 1  │1 1  │1 1│ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1 0  │0 1  │1 1  │1 1│ │
│1 1  │1 1  │1 1  │1 1│ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0 1│0 1 0│1 0 0│   │ │
│1 0 1│0 1 1│1 1 1│   │ │
│1 1 1│1 1 1│1 1 1│   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

For each submatrix I check if it consist entirely of 1s: (#**/)@, - flatten the matrix, and mutiply the number of items by their product. If all items are 1s, the result will be their sum, otherwise - 0:

   (#**/)@, 3 3$1 0 0 1 1 1 1 1 1
0
   (#**/)@, 2 2$1 1 1 1
4 

   ((,~@#\)(+/**/)@,;._3"$]) a
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

0 0 0 0 0
0 0 4 4 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Finally I flatten the list of results for each submatrix and find the maximum:

>./@,

   ([:>./@,,~@#\(+/**/)@,;._3"$]) a
4

Answer 6

Ruby -n, 63 bytes

p (1..l=$_=~/,|$/).map{|i|/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max

Try it online!

Ruby version of my Python answer. Golfier as a full program. Alternatively, an anonymous lambda:

Ruby, 70 68 bytes

->s{(1..l=s=~/,|$/).map{|i|s=~/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max}

Try it online!

Answer 7

Jelly, 18 bytes

_{+2 to handle no-all-1 sublist present output}

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1

Try it online! Or see the test-suite

How?

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1 - Link: list of lists of 1s and 0s
Ẇ                  - all slices (lists of "rows") call these S = [s1,s2,...]
       $           - last two links as a monad:
     L€            -   length of each (number of rows in each slice) call these X = [x1, x2, ...]
    "              -   zip with (i.e. [f(s1,x1),f(s2,x2),...]):
   ¥               -     last two links as a dyad:
 Z                 -       transpose (get the columns of the current slice)
  ṡ                -       all slices of length xi (i.e. squares of he slice)
        Ẏ          - tighten (to get a list of the square sub-matrices)
          Ðf       - filter keep if:
         Ȧ         -   any & all (all non-zero when flattened?)
            L€     - length of €ach (the side length)
              Ṁ    - maximum
               ²   - square (the maximal area)
                »1 - maximum of that and 1 (to coerce a 0 found area to 1)

Answer 8

Retina, 143 bytes

%`$
,;#
+%(`(\d\d.+;#)#*
$1¶$&¶$&#
\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2
)r`((11)|\d\d)(\d*,;?#*)\G
$#2$3
1,
#
Lv$`(#+).*;\1
$.($.1*$1
N`
-1G`
^$
1

Try it online! Link includes test cases. Takes input as comma-separated strings. Explanation:

%`$
,;#

Add a , to terminate the last string, a ; to separate the strings from the #s and a # as a counter.

+%(`
)

Repeat the block until no more subsitutions happen (because each string is now only one digit long).

(\d\d.+;#)#*
$1¶$&¶$&#

Triplicate the line, setting the counter to 1 on the first line and incrementing it on the last line.

\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2

On the first line, delete the first digit of each string, while on the second line, delete all the digits but the first.

r`((11)|\d\d)(\d*,;?#*)\G
$#2$3

On the third line, bitwise and the first two digits together.

1,
#

At this point, each line consists of two values, a) a horizontal width counter and b) the bitwise and of that many bits taken from each string. Convert any remaining 1s to #s so that they can be compared against the counter.

Lv$`(#+).*;\1
$.($.1*$1

Find any runs of bits (vertically) that match the counter (horizontally), corresponding to squares of 1s in the original input, and square the length.

N`

Sort numerically.

-1G`

Take the largest.

^$
1

Special-case the zero matrix.

Answer 9

JavaScript, 92 bytes

a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1

f=
a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1
console.log(f('0111,1111,1111,1111'));
console.log(f('10100,10111,11111,10010'));
console.log(f('0111,1101,0111'));

Answer 10

APL (Dyalog Classic), 21 20 bytes

×⍨{1∊⍵:1+∇2×/2×⌿⍵⋄0}

Try it online!

Answer 11

Python 2, 117 109 bytes

Credit to @etene for pointing out an inefficiency that cost me an additional byte.

lambda s:max(i*i for i in range(len(s))if re.search(("."*(s.find(',')-i+1)).join(["1"*i]*i),s))or 1
import re

Try it online!

Takes input as a comma-separated string. This is a regex-based approach that tries matching the input string against patterns of the form 111.....111.....111 for all possible sizes of the square.

In my calculations, doing this with an anonymous lambda is just a tad shorter than defined function or a full program. The or 1 part in the end is only necessary to handle the strange edge case, where we must output 1 if there are no ones in the input.

Answer 12

Python 2, 116 115 117 109 bytes

Credits to @Kirill for helping me golf it even more and for his clever & early solution

Edit: Golfed 1 byte by using a lambda, I didn't know assigning it to a variable didn't count towards the byte count.

Edit 2: Kirill pointed out my solution didn't work for cases where the input only contains 1s, I had to fix it and lost two precious bytes...

Edit 3: more golfing thanks to Kirill

Takes a comma separated string, returns an integer.

lambda g:max(i*i for i in range(len(g))if re.search(("."*(g.find(",")+1-i)).join(["1"*i]*i),g))or 1
import re

Try it online!

I independently found an answer that is close to Kiril's one, i.e regex based, except that I use re.search and a def.

It uses a regex built during each loop to match an incrementally larger square and returns the largest one, or 1.

Answer 13

Perl 6, 61 60 58 bytes

{(^$_ X.. ^$_).max({[~&](.[|$^r||*])~~/$(1 x$r)/&&+$r})²}

Try it online!

Answer 14

Python 2, 138 128 bytes

def f(m):j=''.join;L=j(m);k=map(j,zip(*m));return len(L)and max(len(L)*(len(m)**2*'1'==L),f(k[1:]),f(k[:-1]),f(m[1:]),f(m[:-1]))

Try it online!

---

Saved

• -10 bytes thanks to ovs

Answer 15

Clojure, 193 bytes

#(apply max(for [f[(fn[a b](take-while seq(iterate a b)))]R(f next %)R(f butlast R)n[(count R)]c(for[i(range(-(count(first R))n -1)):when(apply = 1(for[r R c(subvec r i(+ i n))]c))](* n n))]c))

Wow, things escalated :o

Less golfed:

(def f #(for [rows (->> %    (iterate next)    (take-while seq)) ; row-postfixes
              rows (->> rows (iterate butlast) (take-while seq)) ; row-suffixes
              n    [(count rows)]
              c    (for[i(range(-(count(first rows))n -1)):when(every? pos?(for [row rows col(subvec row i(+ i n))]col))](* n n))] ; rectangular subsections
          c))