9
\$\begingroup\$

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 , so the shortest answer in bytes win.

\$\endgroup\$
  • 3
    \$\begingroup\$ Why string format? \$\endgroup\$ – Stewie Griffin Apr 25 '18 at 18:23
  • 3
    \$\begingroup\$ Can we take the input as a binary (numeric) matrix? \$\endgroup\$ – Stewie Griffin Apr 25 '18 at 18:28
  • 5
    \$\begingroup\$ For [0] still required to output 1? \$\endgroup\$ – l4m2 Apr 25 '18 at 20:37
  • 6
    \$\begingroup\$ Hang about, why return 1 when no all-1 sub-matrix is found, wouldn't 0 make much more sense? (Otherwise it is simply a special case to handle) \$\endgroup\$ – Jonathan Allan Apr 25 '18 at 21:01
  • 2
    \$\begingroup\$ As it stands I think both answerers would not mind if you changed the specs and I strongly recommend doing so because there's no point for returning 1 and it doesn't make the submissions more interesting. \$\endgroup\$ – ბიმო Apr 25 '18 at 23:15

15 Answers 15

2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Awesome. Can you add some explanation? \$\endgroup\$ – Luis felipe De jesus Munoz Apr 25 '18 at 20:32
  • \$\begingroup\$ I will, I'm trying to think of shorter first... \$\endgroup\$ – Jonathan Allan Apr 25 '18 at 20:33
  • \$\begingroup\$ @Mr.Xcoder I have updated to handle the requirement for now \$\endgroup\$ – Jonathan Allan Apr 25 '18 at 21:10
5
\$\begingroup\$

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
                ]
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

K (ngn/k), 33 28 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I never knew you had a K version! \$\endgroup\$ – Zacharý Apr 26 '18 at 14:31
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ ,~@#\ and "1 2 -> "$ \$\endgroup\$ – FrownyFrog Apr 26 '18 at 11:56
  • \$\begingroup\$ @FrownyFrog Thank you! I didn't know about "$ \$\endgroup\$ – Galen Ivanov Apr 26 '18 at 12:02
  • 1
    \$\begingroup\$ # is shorter than adding up the 1s. \$\endgroup\$ – FrownyFrog Apr 26 '18 at 13:15
  • \$\begingroup\$ @ FrownyFrog Hmm, it really is. Cool, thanks! \$\endgroup\$ – Galen Ivanov Apr 26 '18 at 13:19
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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'));

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Classic), 21 20 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Recursion! Nice! \$\endgroup\$ – Zacharý Apr 26 '18 at 10:51
  • \$\begingroup\$ @Zacharý Thanks. Actually, instead of recursion I'd prefer something like k's f\x for a monadic f, which is (x; f x; f f x; ...) until convergence, but there's no equivalent in APL (yet). Doing it with ⍣≡ takes too many bytes. \$\endgroup\$ – ngn Apr 26 '18 at 12:40
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice, I somehow automatically discarded the if approach as "too long for sure", but then had to make up some other way to make a bool value out of the match. Unfortunately, your solution misses one point - you cannot have just range(l) - it will miss the case when there are no zeroes at all. E.g., take 2nd test case and make it all 1s - it should become 16, not 9. \$\endgroup\$ – Kirill L. Apr 26 '18 at 13:44
  • \$\begingroup\$ Damn, I thought about testing with all zeroes but not with all ones (never mentioned in the challenge...). I'll try to make something up. \$\endgroup\$ – etene Apr 26 '18 at 13:48
  • \$\begingroup\$ @KirillL. by the way, you're fast ! I was still working on my answer when you posted yours and was a bit bummed (and proud!) when I saw our approaches were similar... the level around here is impressive. \$\endgroup\$ – etene Apr 26 '18 at 13:52
  • 1
    \$\begingroup\$ Golfed a few more bytes by getting rid of duplicated find. Now that our codes are not identical anymore, I suggest we at least fix the obvious mistakes from each other - in your case the extra byte comes from using tuple ("1"*i,) instead of list. \$\endgroup\$ – Kirill L. Apr 26 '18 at 14:53
  • \$\begingroup\$ Thank you, yeah the useless tuple is pretty stupid on my part. And the extra find too, that was clever of you. \$\endgroup\$ – etene Apr 26 '18 at 14:59
2
\$\begingroup\$

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!

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

Perl 6, 61 60 58 bytes

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

Try it online!

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

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

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))
\$\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.