A Matthew le gusta resolver acertijos. Cada vez que logra resolver uno, salta felizmente. Recientemente, realmente necesita hacer esto, ya que una lluvia de meteoritos ha abierto cráteres y agujeros en el suelo en los que no le gustaría caer.

Te dan una parte del paisaje que Matthew quiere cruzar, con suerte llegando sano al final. El terreno se da en metros, y cada metro es terreno normal o un hoyo. Cuando está corriendo, logra cruzar un metro por paso; La alternativa es saltar, que cruza cuatro metros por paso. Matthew comienza en el extremo izquierdo en el primer metro de tierra y quiere llegar al último (no más allá, sin embargo, solo imagine un agujero sin fin más allá del último metro dado en el paisaje).

Entrada

La entrada se da como una sola línea en la entrada estándar, terminada por un salto de línea. La línea consta de guiones ( -) o guiones bajos ( _), que representan un medidor de suelo o de agujero, respectivamente. Una entrada de muestra podría ser:

----__--___---

El paisaje dado es al menos uno y como máximo 30 metros de largo y siempre comienza con el suelo.

Salida

La salida se da en la salida estándar y representa una serie de comandos de movimiento para Matthew, ya sea run ( R) o jump ( J). Como se señaló anteriormente, un comando de carrera hace que Matthew corra un metro mientras que el salto lo lleva exactamente cuatro metros hacia adelante. Para el ejemplo dado anteriormente, es posible el siguiente movimiento:

RRJRJRR

que se ve aproximadamente de la siguiente manera:

Si no hay un camino seguro a través del paisaje, se !debe imprimir un solo signo de exclamación ( ).

Entradas de muestra

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

Resultados de muestra

JRRR
RRJRJRR
!
!

(la última salida está en blanco ya que no es necesario ningún movimiento, pero supongo que Markdown no puede analizar esto)

Nota

Solo es necesaria una única ruta posible, por lo que la salida del programa no tiene que ajustarse exactamente a las salidas de muestra. Mientras exista una solución si existe y cada comando de movimiento se mueve al suelo y se alcanza el último medidor, la salida es válida.

Se ignora la salida adicional en el error estándar.

Condición ganadora

El código más corto gana, como es habitual en el golf. En caso de empate, la solución anterior gana.

Casos de prueba

Hay dos scripts de prueba que contienen casos de prueba idénticos:

• bash (Gracias a Ventero )
• Potencia Shell

La invocación es en ambos casos: <test script> <my program> [arguments]por ejemplo, ./test ruby jumprun.rbo ./test.ps1 ./jumprun.exe.

Otra nota

Esta tarea fue parte de un concurso de golf celebrado en mi universidad durante 2011-W24. Los puntajes e idiomas de nuestros concursantes fueron los siguientes:

• 104 - Haskell
• 131 - Haskell
• 154 - C
• 170 - C
• 275 - VB.NET
• 286 - Lisp común

Nuestras propias soluciones fueron

•   92 - Ruby
• 124 - PowerShell

Perl, 53 caracteres

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

Ejecute esto con perl -p jumpnrun.pl. He contado 3 caracteres para la -popción, que es la diferencia de longitud entre perl jumpnrun.ply perl -p jumpnrun.pl.

No soy tan fluido en Perl, así que estoy bastante seguro de que esto se puede acortar aún más. Esto usa una expresión regular similar a la solución de Howard .

Ruby, 93 90 79 70 caracteres

Pensé que una solución regex sería bastante fina y compacta (deja que el matizador haga el trabajo). Desafortunadamente, todos los casos límite y los tratamientos especiales hicieron que este fuera tan largo, al menos no toqué los 100 ;-).

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

Pasa todos los casos de prueba del script proporcionado.

Guardado varios caracteres en comparación con el script anterior (ahora una sola llamada gsubes suficiente).

Editar 1: Cambiado puts z!=?-??!:''a z!=?-&&$><<?!después de la escritura de la prueba permite ninguna salida para el caso de prueba 1.

Edición 2: la versión anterior era

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

Mi idea original era reemplazar a los personajes usando una estrategia de mirar hacia atrás y mirar hacia adelante como esta: el patrón era ^(?<=[RJ]*)(-|-...)(?=(-|-...)*-$)y luego reemplazaría '-' con 'R' y, de lo contrario, con 'J'. Desafortunadamente, Ruby no permite mirar hacia atrás de longitud variable y otro grupo de captura para la primera parte hizo que el código fuera aún más largo.

Entonces hice el enfoque iterativo: si puedo comenzar con un paso o salto ^(-|-...)seguido de una serie de otros pasos o saltos hasta la última plataforma, (-|-...)*-$entonces imprimo la letra correspondiente, elimino los primeros uno / cuatro caracteres y comienzo de nuevo. On puede incluso ajustar la prioridad de RJ vs. JR cambiando las opciones dentro de la expresión (actualmente prefiere RJ).

Edición 3: dividir la subtitulación única

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

En dos

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

dio otros pocos caracteres. Finalmente logré deshacerme de este problema de fin de línea pero a un costo: la detección de fallas cuesta algunos caracteres más.

Perl - 71 60

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

Ahora pasa todos los casos de prueba. :) Resulta que estaba eliminando el último personaje demasiado pronto ... y la mitad de mi expresión regular original era completamente redundante.

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

Sin embargo, otra solución de expresiones regulares, pasa los 5 casos de prueba en la publicación.

Podría acortarse ejecutándose como una línea con -Ey en saylugar de print, pero luego Perl intenta interpretar la entrada como un interruptor ... ( Unrecognized switch: -_-_-_-_-_-)

Python - 89 93 97 93 caracteres

Simplemente porque.

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

Ahora solo fallan diez casos de prueba (teniendo en cuenta los casos en los que hay varias soluciones válidas). Lo arreglaré completamente más tarde.

Tomando prestado una de las expresiones regulares de trabajo, termina como

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

Con 96 caracteres.

Haskell, 90 caracteres:

Mi primera solución: larga, pero funciona en tiempo lineal, usando programación dinámica. :) 150 caracteres :

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 segunda solución: mucho más lenta (tiempo exponencial), pero mucho más corta: 90 caracteres

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