Problem 658. Find the biggest empty box

Created by Ned Gulley

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are given a matrix that contains only ones and zeros. Think of the ones as columns in an otherwise empty floor plan. You want to fit a big square into the empty space (denoted by zeros). What is the largest empty square sub-matrix you can find in the given matrix? You will return the row and column extent of the sub-matrix. The answer may not be unique. We will test that your sub-matrix is square, that it is empty, and that it contains the correct number of elements.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input a = [ 1 0 0 \n             0 0 0 \n             0 0 0 ]\n\n Output si = [ 2 3 2 3 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>That is, the square indices are a(2:3,2:3). We verify that sum(sum(a(2:3,2:3))) is zero, and that it has four elements.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

1567 Solutions
523 Solvers

Last Solution submitted on Aug 10, 2020

Last 200 Solutions

Problem Comments

8 Comments

8 Comments

Show 5 older comments

David Hruska on 9 Jun 2012

There appears to be an error is Test Suite #3.

Richard Zapor on 10 Jun 2012

Agree, len for Test Suite 3 should be 4 not 3.

Ned Gulley on 10 Jun 2012

Yes. Fixed it.

Jean-Marie Sainthillier on 29 Nov 2012

Very exciting, as always with Ned

Brian Hannan on 16 Jan 2015

Good puzzle!

Jerivington on 10 Jun 2016

Challenging like all the other problems set in the ASEE Challenge

jmac on 23 May 2020

Nice!

Maryam HCTRAK Yousef on 14 Aug 2020 at 13:46

I need help!

Solution Comments

Solution 1198702

2 Comments

2 Comments

Informaton on 1 Oct 2017

Wow! Size 10.

yurenchu on 2 Oct 2017

@Informaton: Oh, it's nothing; just a cheating script ("gaming the test suite answers") combined with the well-known 'regexp' trick. A proper small solution was first submitted by Tim (Solution 97452 - size:51) and was later optimized in size by Alfonso Nieto-Castanon (Solution 181060 - size:48). My alternative Solution 1198643 (size:63), which uses for-loops instead of conv2 or filter2 function, is also much better than this 'regexp' cheat.

Solution 110110

1 Comment

1 Comment

Jean-Marie Sainthillier on 30 Nov 2012

Splendid !

Problem Recent Solvers523

Problem Tags

asee

Problem 658. Find the biggest empty box

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers523

Suggested Problems

More from this Author49

Problem Tags

Problem 658. Find the biggest empty box

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers523

Suggested Problems

More from this Author49

Problem Tags

Players