This Challenge is to solve Question F, Martian Pits, of the USC ACM Fall 2012 Contest.
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.
Initial conditions are Rover Stopped and Facing +Y. Commands are processed at 1 second intervals
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
Commands FORWARD, BACKWARDS, RIGHT, LEFT only take effect if the rover is stopped. A moving rover ignores these commands.
Commands FASTER and SLOWER only take effect if the rover is moving forward.
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 possible
Scoring: Time (msec)
The full USC data file
...................D .P......P.P......... .P...PPPP.P......... .P...P....P......... .P...P.PPPP......... .P.PPP.P............ .P.P...P............ .PPP.PPPPPPPPPPPPPPP ....R............... PPPPPPPPPPPPPPPPPPPP
Output:  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.
Martian Pits C solution. Time to Solve: 40 minutes. Only three solved this puzzle during the contest. Start.
MATLAB and Simulink resources for Arduino, LEGO, and Raspberry PiLearn more
Opportunities for recent engineering grads.Apply Today
New to MATLAB?Learn MATLAB today!
Play games and win prizes!Learn more