Matthew likes solving puzzles. Whenever he manages to solve one he skips around happily. Recently he really needs to do this as a meteor shower has opened craters and holes in the ground in which he wouldn't like to fall.
You are given a part of landscape that Matthew wants to cross, hopefully arriving healthy at the end. The ground is given in meters, with each meter being either normal ground or a hole. When he is running he manages to cross one meter per step; the alternative is jumping which crosses four meters per step. Matthew starts at the far left on the first ground meter and wants to get to the last one (not beyond it, though – just imagine an endless hole beyond the last meter given in the landscape).
Input is given as a single line on standard input, terminated by a line break. The line consists of
either dashes (
-) or underscores (
_), representing a ground or hole
meter, respectively. A sample input could be:
The given landscape is at least one and at most 30 meters long and always starts with ground.
Output is given on standard output and represents a series of movement
commands to Matthew, either run (
R) or jump (
J). As noted above, a
run command causes Matthew to run one meter while jumping carries him
forward exactly four meters. For the example given above the following
movement is possible:
which looks approximately as follows:
If there is no safe path through the landscape, then a single exclamation
!) should be printed.
-------- ----__--___--- -_______ -_-_-_-_-_- -
JRRR RRJRJRR ! !
(the last output is blank as no movement is necessary, but I guess, Markdown cannot parse this)
Only a single possible path is necessary, so the program output does not have to conform exactly to the sample outputs. As long as a solution is given if it exists and every movement command moves to ground and the last meter is reached eventually, the output is valid.
Additional output on standard error is ignored.
Shortest code wins, as is customary in golf. In case of a tie, the earlier solution wins.
There are two tests scripts, containing identical test cases:
Invocation is in both cases:
<test script> <my program> [arguments], e.g.
./test ruby jumprun.rb or
This task was part of a golf contest held at my university during 2011-W24. The scores and languages of our contestants were as follows:
- 104 – Haskell
- 131 – Haskell
- 154 – C
- 170 – C
- 275 – VB.NET
- 286 – Common Lisp
Our own solutions were
- 92 – Ruby
- 124 – PowerShell