# Jumping and Running

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

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

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:

RRJRJRR


which looks approximately as follows:

If there is no safe path through the landscape, then a single exclamation mark (!) should be printed.

Sample inputs

--------
----__--___---
-_______
-_-_-_-_-_-
-


Sample outputs

JRRR
RRJRJRR
!
!


(the last output is blank as no movement is necessary, but I guess, Markdown cannot parse this)

Note

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.

Winning condition

Shortest code wins, as is customary in golf. In case of a tie, the earlier solution wins.

Test cases

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 ./test.ps1 ./jumprun.exe.

Another note

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:

• 154 – C
• 170 – C
• 275 – VB.NET
• 286 – Common Lisp

Our own solutions were

•   92 – Ruby
• 124 – PowerShell
• @Joey I get an error trying to run test.sh with ./test.sh perl jump.pl -- ./test.sh: line 42: syntax error near unexpected token 'done', under bash 3.2.48 Jun 18, 2011 at 18:25
• @Joey I cleared my cache, redownloaded and it works great now. Thanks. Jun 18, 2011 at 18:52
• Looking at the solutions, it was apparently really too trivial. Apologies.
– Joey
Jun 19, 2011 at 0:09
• I presume backwards running/jumping isn't allowed? If it were, it would make landscapes like ---- solvable. Jun 19, 2011 at 3:27
• Keith: a bit too late now to change the task, I guess.
– Joey
Jun 19, 2011 at 7:47

## Perl, 53 characters

s/-...(?=(-|-...)*-$)/J/g;y/-/R/;/_/?$_="!":s/.$//  Run this with perl -p jumpnrun.pl. I've counted 3 characters for the -p option, which is the length difference between perl jumpnrun.pl and perl -p jumpnrun.pl. I'm not that fluent in Perl, so I'm pretty sure this can be shortened further. This uses a regexp similar to Howard's solution. ### Ruby, 939079 70 characters I thought a regex solution would be quite fine and compact (let the matcher do the work). Unfortunately all the edge-cases and special treatments made this one such long - at least I didn't touch the 100 ;-). puts gets.gsub(/-...(?=(-|-...)*-$)/,?J).tr(?-,?R)=~/^([JR]*)R$/?$1:?!


It passes all testcases of the provided script.

Saved several characters in comparison to the previous script (now a single call to gsub is sufficient).

Edit 1: Changed puts z!=?-??!:'' to z!=?-&&$><<?! after the test script allowed no output for test case 1. Edit 2: The previous version was z=gets.chop z.chars{z.sub!(/^(-|-...)((-|-...)*-)$/){$><<($1==?-??R:?J);$2}} z!=?-&&$><<?!


My original idea was to replace the characters by using a look-behind and look-ahead strategy like this: The pattern was ^(?<=[RJ]*)(-|-...)(?=(-|-...)*-$) and I then would replace '-' with 'R' and otherwise with 'J'. Unfortunately Ruby does not allow variable-length look-behind and another capturing group for the first part made the code even longer. So then I did the iterative approach: if I can start with a step or jump ^(-|-...) followed by series of other steps or jumps until the last platform (-|-...)*-$ then I print the corresponding letter, remove the first one/four characters and start over again. On can even tune the RJ vs. JR priority by switching the choices inside the expression (currently it prefers RJ).

Edit 3: Splitting the single subtitution

puts (z=gets.chop.gsub(/(-...|-)(?=(-|-...)*-$)/){$1==?-??R:?J})=~/_/??!:z.chop


into two

puts (z=gets.chop.gsub(/-...(?=(-|-...)*-$)/,?J).tr(?-,?R))=~/_/??!:z.chop  gave another few chars. Finally I managed to get rid of this end-of-line issue but at a cost: the fail-detection costs some more characters. • You can save 3 characters by changing the last line to z!=?-&&$><<?!. Other than that, great solution, +1! Jun 18, 2011 at 16:43
• @Ventero I had that one put the first test failed because of no output at all for "-" ;-) Jun 18, 2011 at 17:01
• Hm, it appears that my PowerShell script has a tiny bug. It apparently accepts no input for Test 2 and won't accept it for Test 1. That's ... weird, to say the least. I'll try to fix.
– Joey
Jun 18, 2011 at 17:19
• Ok, the test script should be fixed and no longer reject an actually empty result for test 1. Ok, now it should be fixed.
– Joey
Jun 18, 2011 at 17:32
• @Joey Danke. Nun sind es 90 ;-) Jun 18, 2011 at 17:47

# Perl - 71 60

$_=<>;y/-/R/;s/R...(?=(R(...)?)*R$)/J/g;print/_/?"!":s/.$//r  Now passes all of the testcases. :) Turns out I was removing the last character too soon... and half of my original regex was entirely redundant.$_=$ARGV[0];y/-/R/;s/(R...(?=R))(R*(?=R))/J$2/g;chop;print//?"!":$,$/

Yet another regex solution, passes the 5 testcases in the post.

Could be shortened by running as a one-liner with -E and say instead of print, but then perl tries to interpret the input as a switch... (Unrecognized switch: -_-_-_-_-_-)

• The question states that input is given on stdin. When changing your solution to read from stdin instead of using $ARGV, it still fails 108 testcases from the test scripts. Jun 18, 2011 at 17:47 • @Ventero Oh oops... I think I know why it does that, I'll put up a fix soon... that's what I get for not going through all of the testcases... >_> Jun 18, 2011 at 17:56 • Well, the intention of the scripts was to allow people to easily check for validity and adherance to the specification :-) – Joey Jun 18, 2011 at 18:30 • @Joey The problem was that I somehow managed to confuse 'test script' with 'reference implementation' until Ventero posted his comment :) ... script is now almost fixed now though, currently only fails 20, all false negatives Jun 18, 2011 at 18:55 ## Haskell, 90 characters: My first solution -- long, but works in linear time, using dynamic programming. :) 150 characters: x!y="!" q '-'=max q c=(!) s i=r where r=zipWith3 q i(0&'R')$3&'J';n&c="":replicate n"!"++map(c#)r
c#"!"="!"
c#s=c:s
main=interact$reverse.last.s.init  The second solution -- much slower (exponential time), but much shorter: 90 characters s"-\n"="" s('-':t)=max('R'#s t)$'J'#s(drop 3 t)
s _="!"
c#"!"="!"
c#s=c:s
main=interact s