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

1987 Solutions
452 Solvers

Last Solution submitted on May 10, 2022

Last 200 Solutions

Problem Comments

7 Comments

7 Comments

Show 4 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!

Solution Comments

Solution 7843425

1 Comment

1 Comment

László Benedek Nagy on 6 Apr 2022

pain

Solution 3148621

1 Comment

1 Comment

Mayank Bajpai on 10 Oct 2020

Would have been a great question, if time constraints were there.

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 Solvers452

Problem Tags

asee

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 658. Find the biggest empty box

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers452

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 658. Find the biggest empty box

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers452

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players