Problem 294. A stroll on the beach: finding a route round a connected region

Created by David Young

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 standing on the beach of an island, which you must explore by walking all the way round its coast. Each step is in one of the four directions north, south, east or west, and you must travel clockwise, keeping the sea on your left.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The island is represented by a \"blob\" of non-zero elements in an array, completely surrounded by zeros representing the sea. All the elements in the blob are 1, except for a single 2 giving your starting and finishing point. Each step takes you to one of the positions in the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Von_Neumann_neighborhood\"><w:r><w:t>von Neumann neighbourhood</w:t></w:r></w:hyperlink><w:r><w:t> of your current position. Your function must return your steps as a string of the characters N, E, S and W. (N is towards the top of the array as printed, E to the right, etc.) The route must visit every non-zero element that has a 0 as one of its nearest 8 neighbours, and it must not visit any other elements. An element may need to be visited more than once.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The start position will have a 0 as one its nearest 4 neighbours, and the direction of the first step from it will not be ambiguous.</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=\"code\"/></w:pPr><w:r><w:t><![CDATA[Input array = [0 0 0 0 0 0\n 0 2 1 1 0 0\n 0 1 1 1 1 0\n 0 0 0 0 0 0]\n\n Route = EESEWWWN\n\nInput array = [0 0 0 0\n 0 1 1 0\n 0 2 0 0\n 0 0 0 0];\n\n Route = NEWS]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is an example of finding a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Chain_code\"><w:r><w:t>chain code</w:t></w:r></w:hyperlink><w:r><w:t> description of a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Pixel_connectivity#4-connected\"><w:r><w:t>4-connected</w:t></w:r></w:hyperlink><w:r><w:t> shape.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The reference solution has a size of 140.</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>"}]}

You are standing on the beach of an island, which you must explore by walking all the way round its coast. Each step is in one of the four directions north, south, east or west, and you must travel clockwise, keeping the sea on your left.The island is represented by a "blob" of non-zero elements in an array, completely surrounded by zeros representing the sea. All the elements in the blob are 1, except for a single 2 giving your starting and finishing point. Each step takes you to one of the positions in the <a href="http://en.wikipedia.org/wiki/Von_Neumann_neighborhood">von Neumann neighbourhood</a> of your current position. Your function must return your steps as a string of the characters N, E, S and W. (N is towards the top of the array as printed, E to the right, etc.) The route must visit every non-zero element that has a 0 as one of its nearest 8 neighbours, and it must not visit any other elements. An element may need to be visited more than once.The start position will have a 0 as one its nearest 4 neighbours, and the direction of the first step from it will not be ambiguous.Examples:<pre class="language-matlab">Input array = [0 0 0 0 0 0
 0 2 1 1 0 0
 0 1 1 1 1 0
 0 0 0 0 0 0]
</pre><pre> Route = EESEWWWN</pre><pre class="language-matlab">Input array = [0 0 0 0
 0 1 1 0
 0 2 0 0
 0 0 0 0];
</pre><pre> Route = NEWS</pre>This is an example of finding a <a href="http://en.wikipedia.org/wiki/Chain_code">chain code</a> description of a <a href="http://en.wikipedia.org/wiki/Pixel_connectivity#4-connected">4-connected</a> shape.The reference solution has a size of 140.

Solve

Solution Stats

80 Solutions
10 Solvers

Last Solution submitted on Jan 14, 2019

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Paul Berglund on 9 Mar 2013

This was cool: a very easy problem to specify, but hard (for me, anyway) to solve. Even now, I'm not confident that my gigantic bloated code will solve all possible problems, it just managed the four in the test suite!

Solution Comments

Solution 38804

1 Comment

1 Comment

David Young on 29 Feb 2012

I like the reference - it's a good resource.

Solution 35476

3 Comments

3 Comments

Alfonso Nieto-Castanon on 15 Feb 2012

very nice commented code!

David Young on 16 Feb 2012

Thank you Alfonso! (They're my comments.)

Alfonso Nieto-Castanon on 17 Feb 2012

Well, very nice commented solution and very nice problem as well!

Problem Recent Solvers10

Problem Tags

blob chain code connected region

Community Treasure Hunt

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

Start Hunting!