18
\$\begingroup\$

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:

Illustration of the movement RRJRJRR

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:

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

Our own solutions were

  •   92 – Ruby
  • 124 – PowerShell
\$\endgroup\$
  • \$\begingroup\$ @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 \$\endgroup\$ – swilliams Jun 18 '11 at 18:25
  • \$\begingroup\$ @Joey I cleared my cache, redownloaded and it works great now. Thanks. \$\endgroup\$ – swilliams Jun 18 '11 at 18:52
  • \$\begingroup\$ Looking at the solutions, it was apparently really too trivial. Apologies. \$\endgroup\$ – Joey Jun 19 '11 at 0:09
  • 1
    \$\begingroup\$ I presume backwards running/jumping isn't allowed? If it were, it would make landscapes like ---- solvable. \$\endgroup\$ – Keith Randall Jun 19 '11 at 3:27
  • \$\begingroup\$ Keith: a bit too late now to change the task, I guess. \$\endgroup\$ – Joey Jun 19 '11 at 7:47
7
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can save 3 characters by changing the last line to z!=?-&&$><<?!. Other than that, great solution, +1! \$\endgroup\$ – Ventero Jun 18 '11 at 16:43
  • \$\begingroup\$ @Ventero I had that one put the first test failed because of no output at all for "-" ;-) \$\endgroup\$ – Howard Jun 18 '11 at 17:01
  • \$\begingroup\$ 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. \$\endgroup\$ – Joey Jun 18 '11 at 17:19
  • \$\begingroup\$ Ok, the test script should be fixed and no longer reject an actually empty result for test 1. Ok, now it should be fixed. \$\endgroup\$ – Joey Jun 18 '11 at 17:32
  • \$\begingroup\$ @Joey Danke. Nun sind es 90 ;-) \$\endgroup\$ – Howard Jun 18 '11 at 17:47
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Ventero Jun 18 '11 at 17:47
  • \$\begingroup\$ @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... >_> \$\endgroup\$ – swilliams Jun 18 '11 at 17:56
  • \$\begingroup\$ Well, the intention of the scripts was to allow people to easily check for validity and adherance to the specification :-) \$\endgroup\$ – Joey Jun 18 '11 at 18:30
  • \$\begingroup\$ @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 \$\endgroup\$ – swilliams Jun 18 '11 at 18:55
1
\$\begingroup\$

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.

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

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.