Jumping and Running

Question

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:

• bash (Thanks to Ventero)
• PowerShell

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:

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

Our own solutions were

•   92 – Ruby
• 124 – PowerShell

Answer 1

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.

Answer 2

Ruby, 93 90 79 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.

Answer 3

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: -_-_-_-_-_-)

Answer 4

Python - 89 93 97 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.

Answer 5

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