Problem 1903. GJam 2014 China Rd A: Maze with a Left Hand Rule

Created by Richard Zapor

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>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/2924486/dashboard#s=p3\"><w:r><w:t>GJam 2014 China Cross the Maze</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Goal is to minimally traverse a Maze from a Starting Point to Finish Point in less than 10,000 moves where the Bot can only go forward and must maintain its Left Arm in contact with a wall. At the Start Point the Bot can only touch NSEW. After the first move the Bot maintains contact on diagonals. Rotations in a cul-de-sac or turning are not counted as moves.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [M, Start_Finish] where M is an NxN (0,1=Wall) array and Start_Finish is [Sr,Sc,Fr,Fc]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> Path, a string of Movements {N,S,E,W}. If Path is &gt;10,000 moves or No solution return a null string.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><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[.##.#\n.....\n...#.\n.###.\n...#.\n1 1 5 3]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note: (1,1) is Top Left and start point for this case.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The # are replaced by 1s and '.' will be 0s.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output: SEEENSESSSNNNWWSWWSSEE</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Contest Performance:</w:t></w:r><w:r><w:t> Best Delta Time of 17 minutes with only 134 correct solutions in 3 hours.</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>"}]}

This Challenge is derived from <a href = "http://code.google.com/codejam/contest/2924486/dashboard#s=p3">GJam 2014 China Cross the Maze</a>.The Goal is to minimally traverse a Maze from a Starting Point to Finish Point in less than 10,000 moves where the Bot can only go forward and must maintain its Left Arm in contact with a wall. At the Start Point the Bot can only touch NSEW. After the first move the Bot maintains contact on diagonals. Rotations in a cul-de-sac or turning are not counted as moves.Input: [M, Start_Finish] where M is an NxN (0,1=Wall) array and Start_Finish is [Sr,Sc,Fr,Fc]Output: Path, a string of Movements {N,S,E,W}. If Path is >10,000 moves or No solution return a null string.Examples:<pre class="language-matlab">.##.#
.....
...#.
.###.
...#.
1 1 5 3
</pre>Note: (1,1) is Top Left and start point for this case.The # are replaced by 1s and '.' will be 0s.Output: SEEENSESSSNNNWWSWWSSEEContest Performance: Best Delta Time of 17 minutes with only 134 correct solutions in 3 hours.

Solve

Solution Stats

9 Solutions
3 Solvers

Last Solution submitted on Dec 08, 2018

Last 200 Solutions

Problem Comments

Problem Recent Solvers3

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 1903. GJam 2014 China Rd A: Maze with a Left Hand Rule

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers3

Suggested Problems

More from this Author254

Problem Tags

Community Treasure Hunt

Problem 1903. GJam 2014 China Rd A: Maze with a Left Hand Rule

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers3

Suggested Problems

More from this Author254

Problem Tags

Community Treasure Hunt

Players