# 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
-
+1 for such great test scripts – Howard Jun 18 '11 at 16:17
@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 – swilliams Jun 18 '11 at 18:25
@Joey I cleared my cache, redownloaded and it works great now. Thanks. – swilliams Jun 18 '11 at 18:52
Looking at the solutions, it was apparently really too trivial. Apologies. – Joey Jun 19 '11 at 0:09
I presume backwards running/jumping isn't allowed? If it were, it would make landscapes like ---- solvable. – Keith Randall Jun 19 '11 at 3:27
show 1 more comment

## 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!=?-&&\$><

# 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. – Ventero Jun 18 '11 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... >_> – swilliams Jun 18 '11 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 '11 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 – swilliams Jun 18 '11 at 18:55

### Python - 899397 93 characters

Just because.

``````import re;i=re.sub('...(?<!---)-','J',input()[1:]);print('!'if'_'in i else re.sub('-','R',i))
``````

Only fails ten test cases now (taking into account the cases where there are multiple valid solutions). I'll fix it fully later.

Borrowing one of the working regexes, it ends up as

``````import re;i=re.sub('-...(?=(-|-...)*-\$)','J',input());print('!'if'_'in i else re.sub('-','R',i))
``````

With 96 characters.

-
Passes only 728 of the test cases. I put the test scripts there for a reason, actually. – Joey Jun 20 '11 at 16:29
@Joey: Looks like I forgot to trim off the leading character from the input. Silly me. It's now corrected. – JAB Jun 20 '11 at 16:50
Still only passes 766/849 testcases. – Ventero Jun 20 '11 at 17:11

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
``````
-