Problem 502. Would Homer Like It?

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>Given a matrix of ones and zeros, you must determine if there are any doughnuts present (would Homer Simpson like it?). A doughnut is a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/4-connected_neighborhood\"><w:r><w:t>4-connected region</w:t></w:r></w:hyperlink><w:r><w:t> of ones completely enclosing a 4-connected region of zeros. You can assume that any regions of ones are either blobs (or</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Genus_%28mathematics%29\"><w:r><w:t>genus 0</w:t></w:r></w:hyperlink><w:r><w:t>) or doughnuts (genus 1). Thus if you find any hole in a region of ones, it is a doughnut. Also, there are no nested doughnuts.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Return true if any doughnuts are present, otherwise false.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Examples:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is a doughnut:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 1 1 1\n 1 0 1 \n 1 1 1]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Here is another doughnut:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 0 0 1 1 1\n 0 1 1 1 0 1\n 0 0 1 0 0 1\n 0 0 1 1 1 1]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is not a doughnut:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 1 0\n 1 0 1\n 0 1 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>because the ones are not 4-connected and so can't surround anything.</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

44 Solutions
12 Solvers

Last Solution submitted on Apr 04, 2019

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

Alfonso Nieto-Castanon on 15 Mar 2012

mmm... the image processing toolbox seems to be available again?

Ned Gulley on 16 Mar 2012

Oh! Thanks for pointing that out. It will disappear again shortly. Sorry about that.

Alfonso Nieto-Castanon on 16 Mar 2012

Sounds good (it was too easy this way)

Ned Gulley on 19 Mar 2012

Okay, we should be back to no-toolbox coding.

Problem Recent Solvers12

Problem Tags

images topology

Problem 502. Would Homer Like It?

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers12

Suggested Problems

More from this Author49

Problem Tags

Problem 502. Would Homer Like It?

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers12

Suggested Problems

More from this Author49

Problem Tags

Players