Прыжки и Бег

18

Мэтью любит решать головоломки. Всякий раз, когда ему удается решить один, он счастливо пропускает. В последнее время ему действительно нужно это сделать, поскольку метеорный поток открыл в земле кратеры и дыры, в которые он не хотел бы упасть.

Вам дана часть ландшафта, который Мэтью хочет пересечь, надеясь, что он прибудет здоровым в конце. Земля дана в метрах, причем каждый метр представляет собой либо нормальную землю, либо дыру. Когда он бежит, ему удается пересечь один метр за шаг; альтернатива - прыжки, которые пересекают четыре метра за шаг. Мэтью начинает в крайнем левом углу первого наземного метра и хочет добраться до последнего (но не дальше его - просто представьте бесконечную дыру за последним метром, указанным в ландшафте).

вход

Входные данные задаются в виде одной строки на стандартном входе и заканчиваются переводом строки. Линия состоит из либо dashes ( -) или underscores ( _), представляющих метр земли или скважины, соответственно. Пример ввода может быть:

----__--___---

Данный ландшафт имеет длину не менее одного и не более 30 метров и всегда начинается с земли.

Выход

Выходные данные выдаются на стандартный вывод и представляют собой последовательность команд перемещения для Мэтью, либо run ( R), либо jump ( J). Как отмечалось выше, команда запуска заставляет Мэтью бежать на один метр, в то время как прыжки переносят его вперед ровно на четыре метра. Для приведенного выше примера возможно следующее движение:

RRJRJRR

который выглядит примерно так:

Иллюстрация движения RRJRJRR

Если нет безопасного пути через ландшафт, то !должен быть напечатан один восклицательный знак ( ).

Образцы входов

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

Пример выходов

JRRR
RRJRJRR
!
!

(последний вывод пустой, так как никакого движения не требуется, но я думаю, Markdown не может разобрать это)

Заметка

Необходим только один возможный путь, поэтому выходные данные программы не обязательно должны точно соответствовать выходным данным примера. Пока дается решение, если оно существует, и каждая команда перемещения перемещается на землю, и в конце концов достигается последний метр, выходные данные действительны.

Дополнительный вывод по стандартной ошибке игнорируется.

Выигрышное условие

Самый короткий код выигрывает, как это принято в гольфе. В случае ничьей победит более раннее решение.

Контрольные примеры

Есть два сценария тестирования, содержащие идентичные тестовые случаи:

Вызов в обоих случаях: <test script> <my program> [arguments]например, ./test ruby jumprun.rbили ./test.ps1 ./jumprun.exe.

Еще одна заметка

Эта задача была частью соревнования по гольфу, проводимого в моем университете в течение 2011-W24. Баллы и языки наших конкурсантов были следующими:

  • 104 - Хаскелл
  • 131 - Хаскелл
  • 154 - С
  • 170 - С
  • 275 - VB.NET
  • 286 - Общий Лисп

Наши собственные решения были

  •   92 - Рубин
  • 124 - PowerShell
детеныш
источник
@Joey Я получаю сообщение об ошибке при попытке запустить test.sh с ./test.sh perl jump.pl- ./test.sh: line 42: syntax error near unexpected token 'done', под bash 3.2.48
swilliams
@Joey Я очистил свой кеш, перезагружен, и теперь он отлично работает. Благодарю.
swilliams
Глядя на решения, это было действительно слишком тривиально. Извиняюсь.
Джои
1
Я предполагаю, что бег назад / прыжки не разрешены? Если бы это было так, это сделало бы пейзажи как - - - - разрешимыми.
Кит Рэндалл
Кит: я думаю, уже слишком поздно менять задачу.
Джои

Ответы:

7

Perl, 53 символа

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

Запустите это с perl -p jumpnrun.pl. Я посчитал 3 символа для -pопции, которая является разницей в длине perl jumpnrun.plи perl -p jumpnrun.pl.

Я не очень хорошо говорю на Perl, поэтому я уверен, что это можно сократить дальше. Это использует регулярное выражение, похожее на решение Говарда .

Ventero
источник
3

Рубин, 93 90 79 70 символов

Я думал, что решение для регулярных выражений будет достаточно тонким и компактным (пусть этот механизм сделает всю работу). К сожалению, все крайние случаи и специальные процедуры сделали это таким длинным - по крайней мере, я не коснулся 100 ;-).

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

Он проходит все тестовые сценарии предоставленного скрипта.

Сохранено несколько символов по сравнению с предыдущим скриптом (теперь достаточно одного вызова gsub).

Редактировать 1: изменено puts z!=?-??!:''на z!=?-&&$><<?!после того, как тестовый скрипт не разрешал вывод для тестового примера 1.

Изменить 2: предыдущая версия была

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

Моя первоначальная идея состояла в том, чтобы заменить персонажей с помощью стратегии «смотреть сзади» и «смотреть вперед», например, так: шаблон был, ^(?<=[RJ]*)(-|-...)(?=(-|-...)*-$)и тогда я бы заменил «-» на «R», а в противном случае на «J». К сожалению, Ruby не позволяет просматривать данные переменной длины, и другая группа захвата для первой части сделала код еще длиннее.

Затем я применил итеративный подход: если я могу начать с шага или прыжка с ^(-|-...)последующими сериями других шагов или прыжков до последней платформы, (-|-...)*-$то я печатаю соответствующую букву, удаляю первые один / четыре символа и начинаю заново. Он может даже настроить приоритет RJ против JR, переключая варианты внутри выражения (в настоящее время он предпочитает RJ).

Редактировать 3: Разделение одного подстановки

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

на две

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

дал еще несколько символов. В конце концов мне удалось избавиться от этой проблемы конца строки, но за определенную плату: обнаружение сбоев стоит еще несколько символов.

Говард
источник
Вы можете сохранить 3 символа, изменив последнюю строку на z!=?-&&$><<?!. Кроме этого, отличное решение, +1!
Вентеро
@Ventero У меня было то, что первый тест не удался, потому что ничего не выводилось для "-" ;-)
Говард
Хм, похоже, что в моем скрипте PowerShell есть маленькая ошибка. Он , видимо , не принимает не вход для теста 2 и не будет принимать его для теста 1. Это ... странно, по меньшей мере сказать. Я постараюсь исправить.
Джои
Хорошо, тестовый скрипт должен быть исправлен и больше не отклонять фактически пустой результат теста 1. Хорошо, теперь он должен быть исправлен.
Джои
@ Джои Данке. Монахиня Синд Эс 90 ;-)
Говард
1

Perl - 71 60

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

Сейчас проходит все тестовые случаи. :) Оказывается, я убрал последнего персонажа слишком рано ... и половина моего исходного выражения была полностью излишней.

$ _ = $ ARGV [0]; y / - / R /; s / (R ... (? = R)) (R * (? = R)) / J $ 2 / г; chop; печать / /? "!": $ , $ /

Еще одно решение регулярных выражений, проходит 5 тестов в посте.

Можно сократить, запустив как одну строку с -Eи sayвместо print, но затем Perl пытается интерпретировать ввод как переключатель ... ( Unrecognized switch: -_-_-_-_-_-)

swilliams
источник
Вопрос гласит, что ввод дается на стандартный ввод. Когда вы изменяете свое решение на чтение из стандартного ввода вместо того, чтобы использовать $ARGVего, оно все равно не может выполнить 108 тестовых случаев из тестовых сценариев.
Вентеро
@Ventero Ой ... я думаю, я знаю, почему это происходит, я скоро исправлю ... вот что я получаю, если не буду проходить все тесты ...> _>
swilliams
Итак, цель сценариев состояла в том, чтобы позволить людям легко проверить правильность и соответствие спецификации :-)
Joey
@Joey Проблема заключалась в том, что мне каким-то образом удавалось путать «тестовый сценарий» с «ссылочной реализацией», пока Вентеро не опубликовал свой комментарий :) ... сценарий теперь почти исправлен, хотя, в настоящее время он дает сбой только 20, все ложные отрицания
свилиям
1

Python - 89 93 97 93 персонажа

Да просто так.

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

В настоящее время проходит только десять тестовых случаев (с учетом случаев, когда существует несколько допустимых решений). Я исправлю это позже.


Занимая один из рабочих регулярных выражений, он в конечном итоге как

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

С 96 персонажами.

JAB
источник
1
Проходит только 728 тестовых случаев. На самом деле я поставил тестовые сценарии по какой-то причине.
Джои
@ Джой: Похоже, я забыл обрезать ведущий символ из ввода. Дурак я. Это сейчас исправлено.
JAB
До сих пор только 766/849 тестовых случаев.
Вентеро
1

Haskell, 90 символов:

Мое первое решение - длинное, но работает за линейное время с использованием динамического программирования. :) 150 символов :

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

Второе решение - намного медленнее (экспоненциальное время), но намного короче: 90 символов

s"-\n"=""
s('-':t)=max('R'#s t)$'J'#s(drop 3 t)
s _="!"
c#"!"="!"
c#s=c:s
main=interact s
Rotsor
источник