Problem 1122. USC Fall 2012 ACM: Rover Maze

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 to solve Question F, Martian Pits, of the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home\"><w:r><w:t>USC ACM Fall 2012 Contest</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 task is to determine the minimum time for the Rover to drive from its current position to a Goal location. The Rover must STOP on the Goal location. Commands are processed at 1 Cmd per sec. Rover must stay on array.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is an intriguing Maze problem that incorporates turn penalties, variable speed forward, and a fixed reverse speed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[Initial conditions are Rover Stopped and Facing +Y.\nCommands are processed at 1 second intervals\n\nCommands and their attributes:\nFORWARD: Starts rolling forward at 1 cm/s\nBACKWARDS: Roll backwards at 1 cm/s\nFASTER: Increase forward speed by 1 cm/s up to 5 cm/s\nSLOWER: Decrease forward speed by 1 cm/s down to 0 cm/s. At 0 cm/s Rover is \"Stopped\"\nSTOP: Halts rover movement\nRIGHT: Turn rover 90 degrees to the right\nLEFT: Turn the rover 90 degrees to the left\nNOOP: No change in anything \n\nCommands FORWARD, BACKWARDS, RIGHT, LEFT only take effect if the rover is stopped. A moving rover ignores these commands.\n\nCommands FASTER and SLOWER only take effect if the rover is moving forward.]]></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: [Char array]</w:t></w:r><w:r><w:t> \".\" is Flat ground, \"P\" Pit, \"R\" Rover start location, \"D\" is Destination. Matrix max dim 50, min 1.</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: [T]</w:t></w:r><w:r><w:t>; Drive Time to destination; -1 if not possible</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>Scoring: Time (msec)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The full</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=pits.in.txt\"><w:r><w:t>USC data file</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</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: [A]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[...................D\n.P......P.P.........\n.P...PPPP.P.........\n.P...P....P.........\n.P...P.PPPP.........\n.P.PPP.P............\n.P.P...P............\n.PPP.PPPPPPPPPPPPPPP\n....R...............\nPPPPPPPPPPPPPPPPPPPP]]></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: [19]</w:t></w:r><w:r><w:t> as the best path is L, Fwd, Faster, Slower, Stop to (9,1). The cmds to reach (1,1) are R, Fwd, Faster, Faster, Slower, Stop. Cmds to optimally reach (1,20) are R, Fwd, Faster, Faster, Faster, Faster, Slower, Stop.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Once again my code is large thus the contest will be scored based on Processing Time.</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>Hints:</w:t></w:r><w:r><w:t> One Speed-Up method is to do an initial Start/Finish connectivity check.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=pits.yucheng.cpp.txt\"><w:r><w:t>Martian Pits C solution</w:t></w:r></w:hyperlink><w:r><w:t>. Time to Solve: 40 minutes. Only three solved this puzzle during the contest. Start.</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 to solve Question F, Martian Pits, of the <a href="http://contest.usc.edu/index.php/Fall12/Home">USC ACM Fall 2012 Contest</a>.The task is to determine the minimum time for the Rover to drive from its current position to a Goal location. The Rover must STOP on the Goal location. Commands are processed at 1 Cmd per sec. Rover must stay on array.This is an intriguing Maze problem that incorporates turn penalties, variable speed forward, and a fixed reverse speed.<pre class="language-matlab">Initial conditions are Rover Stopped and Facing +Y.
Commands are processed at 1 second intervals
</pre><pre class="language-matlab">Commands and their attributes:
FORWARD: Starts rolling forward at 1 cm/s
BACKWARDS: Roll backwards at 1 cm/s
FASTER: Increase forward speed by 1 cm/s up to 5 cm/s
SLOWER: Decrease forward speed by 1 cm/s down to 0 cm/s. At 0 cm/s Rover is "Stopped"
STOP: Halts rover movement
RIGHT: Turn rover 90 degrees to the right
LEFT: Turn the rover 90 degrees to the left
NOOP: No change in anything 
</pre><pre class="language-matlab">Commands FORWARD, BACKWARDS, RIGHT, LEFT only take effect if the rover is stopped. A moving rover ignores these commands.
</pre><pre class="language-matlab">Commands FASTER and SLOWER only take effect if the rover is moving forward.
</pre>Input: [Char array] "." is Flat ground, "P" Pit, "R" Rover start location, "D" is Destination. Matrix max dim 50, min 1.Output: [T]; Drive Time to destination; -1 if not possibleScoring: Time (msec)The full <a href="http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=pits.in.txt">USC data file</a>Example:Input: [A]<pre class="language-matlab">...................D
.P......P.P.........
.P...PPPP.P.........
.P...P....P.........
.P...P.PPPP.........
.P.PPP.P............
.P.P...P............
.PPP.PPPPPPPPPPPPPPP
....R...............
PPPPPPPPPPPPPPPPPPPP
</pre>Output: [19] as the best path is L, Fwd, Faster, Slower, Stop to (9,1). The cmds to reach (1,1) are R, Fwd, Faster, Faster, Slower, Stop. Cmds to optimally reach (1,20) are R, Fwd, Faster, Faster, Faster, Faster, Slower, Stop.Once again my code is large thus the contest will be scored based on Processing Time.Hints: One Speed-Up method is to do an initial Start/Finish connectivity check.<a href="http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=pits.yucheng.cpp.txt">Martian Pits C solution</a>. Time to Solve: 40 minutes. Only three solved this puzzle during the contest. Start.

Solve

Solution Stats

6 Solutions
3 Solvers

Last Solution submitted on Nov 06, 2013

Last 200 Solutions

Problem Recent Solvers3

Problem Tags

Problem 1122. USC Fall 2012 ACM: Rover Maze

Solution Stats

Last 200 Solutions

Problem Recent Solvers3

Suggested Problems

More from this Author236

Problem Tags

Problem 1122. USC Fall 2012 ACM: Rover Maze

Solution Stats

Last 200 Solutions

Problem Recent Solvers3

Suggested Problems

More from this Author236

Problem Tags

Players