Matthew aime résoudre des énigmes. Chaque fois qu'il parvient à en résoudre un, il saute joyeusement. Récemment, il a vraiment besoin de le faire car une pluie de météores a ouvert des cratères et des trous dans le sol dans lesquels il ne voudrait pas tomber.

On vous donne une partie du paysage que Matthew veut traverser, en espérant arriver en bonne santé à la fin. Le sol est donné en mètres, chaque mètre étant soit un sol normal, soit un trou. Lorsqu'il court, il parvient à franchir un mètre par pas; l'alternative est le saut qui franchit quatre mètres par pas. Matthew commence à l'extrême gauche sur le premier mètre au sol et veut atteindre le dernier (pas au-delà, cependant - imaginez un trou sans fin au-delà du dernier mètre donné dans le paysage).

Contribution

L'entrée est donnée sous la forme d'une seule ligne sur l'entrée standard, terminée par un saut de ligne. La ligne se compose de tirets ( -) ou de traits de soulignement ( _), représentant respectivement un mètre au sol ou un trou. Un exemple d'entrée pourrait être:

----__--___---

Le paysage donné fait au moins un et au plus 30 mètres de long et commence toujours par le sol.

Production

La sortie est donnée sur la sortie standard et représente une série de commandes de mouvement pour Matthew, soit run ( R) soit jump ( J). Comme indiqué ci-dessus, une commande de course oblige Matthew à courir un mètre tandis que le saut le fait avancer exactement de quatre mètres. Pour l'exemple donné ci-dessus, le mouvement suivant est possible:

RRJRJRR

qui ressemble approximativement à ce qui suit:

S'il n'y a pas de chemin sûr à travers le paysage, un seul point d'exclamation ( !) doit être imprimé.

Exemples d'entrées

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

Exemples de sorties

JRRR
RRJRJRR
!
!

(la dernière sortie est vide car aucun mouvement n'est nécessaire, mais je suppose que Markdown ne peut pas analyser cela)

Remarque

Un seul chemin possible est nécessaire, de sorte que la sortie du programme n'a pas à se conformer exactement aux sorties d'échantillons. Tant qu'une solution est donnée si elle existe et que chaque commande de mouvement se déplace vers le sol et que le dernier mètre est finalement atteint, la sortie est valide.

La sortie supplémentaire sur l'erreur standard est ignorée.

Condition gagnante

Le code le plus court gagne, comme c'est la coutume dans le golf. En cas d'égalité, la solution précédente l'emporte.

Cas de test

Il existe deux scripts de test, contenant des cas de test identiques:

• bash (Merci à Ventero )
• PowerShell

L'invocation est dans les deux cas:, <test script> <my program> [arguments]par exemple ./test ruby jumprun.rbou ./test.ps1 ./jumprun.exe.

Une autre note

Cette tâche faisait partie d'un concours de golf organisé dans mon université en 2011-S24. Les scores et les langues de nos candidats étaient les suivants:

• 104 - Haskell
• 131 - Haskell
• 154 - C
• 170 - C
• 275 - VB.NET
• 286 - Lisp commun

Nos propres solutions étaient

•   92 - Rubis
• 124 - PowerShell

Perl, 53 caractères

s/-...(?=(-|-...)*-$)/J/g;y/-/R/;/_/?$_="!":s/.$//

Exécutez cela avec perl -p jumpnrun.pl. J'ai compté 3 caractères pour l' -poption, qui est la différence de longueur entre perl jumpnrun.plet perl -p jumpnrun.pl.

Je ne parle pas très bien Perl, donc je suis sûr que cela peut être raccourci davantage. Cela utilise une expression rationnelle similaire à la solution de Howard .

Ruby, 93 90 79 70 caractères

Je pensais qu'une solution regex serait assez fine et compacte (laissez le matcher faire le travail). Malheureusement, tous les cas de bord et les traitements spéciaux ont rendu celui-ci si long - au moins je n'ai pas touché le 100 ;-).

puts gets.gsub(/-...(?=(-|-...)*-$)/,?J).tr(?-,?R)=~/^([JR]*)R$/?$1:?!

Il passe tous les cas de test du script fourni.

Plusieurs caractères enregistrés par rapport au script précédent (maintenant un seul appel à gsubest suffisant).

Edit 1: Changé puts z!=?-??!:''pour z!=?-&&$><<?!après le script de test a permis pas de sortie pour le cas de test 1.

Edit 2: La version précédente était

z=gets.chop
z.chars{z.sub!(/^(-|-...)((-|-...)*-)$/){$><<($1==?-??R:?J);$2}}
z!=?-&&$><<?!

Mon idée originale était de remplacer les personnages en utilisant une stratégie de regard en arrière et d'anticipation comme celle-ci: Le motif était ^(?<=[RJ]*)(-|-...)(?=(-|-...)*-$)et je remplacerais ensuite «-» par «R» et sinon par «J». Malheureusement, Ruby n'autorise pas la recherche de longueur variable et un autre groupe de capture pour la première partie a rendu le code encore plus long.

Alors j'ai fait l'approche itérative: si je peux commencer par une étape ou un saut ^(-|-...)suivi par une série d'autres étapes ou sauts jusqu'à la dernière plate-forme, (-|-...)*-$j'imprime la lettre correspondante, supprime les premiers 1/4 caractères et recommence. On peut même régler la priorité RJ vs. JR en changeant les choix à l'intérieur de l'expression (actuellement, il préfère RJ).

Edit 3: Fractionnement de la sous-substitution unique

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

Entre deux

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

a donné quelques autres caractères. Enfin j'ai réussi à me débarrasser de ce problème de fin de ligne mais à un prix: la détection de panne coûte encore plus de caractères.

Perl - 71 60

$_=<>;y/-/R/;s/R...(?=(R(...)?)*R$)/J/g;print/_/?"!":s/.$//r

Passe maintenant tous les tests. :) Il s'avère que je supprimais le dernier personnage trop tôt ... et la moitié de mon expression originale était entièrement redondante.

$ _ = $ ARGV [0]; y / - / R /; s / (R ... (? = R)) (R * (? = R)) / J $ 2 / g; hacher; imprimer / /? "!": $ , $ /

Encore une autre solution regex, passe les 5 cas de test par la poste.

Pourrait être raccourci en fonctionnant en monoplace avec -E et sayau lieu de print, mais perl essaie alors d'interpréter l'entrée comme un commutateur ... ( Unrecognized switch: -_-_-_-_-_-)

Python - 89 93 97 93 caractères

Juste parce que.

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

N'échoue que dix cas de test maintenant (en tenant compte des cas où il existe plusieurs solutions valides). Je vais le réparer complètement plus tard.

Empruntant l'une des expressions rationnelles de travail, il finit par

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

Avec 96 caractères.

Haskell, 90 caractères:

Ma première solution - longue, mais fonctionne en temps linéaire, en utilisant la programmation dynamique. :) 150 caractères :

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

La deuxième solution - beaucoup plus lente (temps exponentiel), mais beaucoup plus courte: 90 caractères

s"-\n"=""
s('-':t)=max('R'#s t)$'J'#s(drop 3 t)
s _="!"
c#"!"="!"
c#s=c:s
main=interact s