Matthew lubi rozwiązywać zagadki. Ilekroć uda mu się go rozwiązać, skacze z radością. Ostatnio naprawdę musi to zrobić, ponieważ deszcz meteorów otworzył kratery i dziury w ziemi, na które nie chciałby spaść.

Dostajesz część krajobrazu, którą Matthew chce przejść, miejmy nadzieję, że na końcu dotrze zdrowy. Grunt podany jest w metrach, przy czym każdy metr jest albo normalnym gruntem, albo otworem. Kiedy biega, udaje mu się przekroczyć metr na krok; alternatywą jest skakanie, które przekracza cztery metry na krok. Matthew zaczyna od skrajnie lewej na pierwszym metrze naziemnym i chce dotrzeć do ostatniego (jednak nie poza nim - wyobraź sobie niekończącą się dziurę poza ostatnim metrem podanym w krajobrazie).

Wejście

Wejście jest podawane jako pojedynczy wiersz na standardowym wejściu, zakończone przerwaniem linii. Linia składa się z myślników ( -) lub znaków podkreślenia ( _), reprezentujących odpowiednio miernik gruntu lub otworu. Przykładowe dane wejściowe mogą być:

----__--___---

Dany krajobraz ma co najmniej jeden i co najwyżej 30 metrów długości i zawsze zaczyna się od ziemi.

Wynik

Dane wyjściowe są podawane na standardowe wyjście i reprezentują szereg poleceń ruchu dla Matthew, albo run ( R), albo jump ( J). Jak wspomniano powyżej, polecenie uruchomienia powoduje, że Matthew biegnie o jeden metr, a skakanie prowadzi go dokładnie cztery metry do przodu. W powyższym przykładzie możliwy jest następujący ruch:

RRJRJRR

który wygląda mniej więcej w następujący sposób:

Jeśli nie ma bezpiecznej ścieżki przez krajobraz, !należy wydrukować pojedynczy wykrzyknik ( ).

Przykładowe dane wejściowe

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

Przykładowe wyniki

JRRR
RRJRJRR
!
!

(ostatni wynik jest pusty, ponieważ ruch nie jest konieczny, ale myślę, że Markdown nie może tego przeanalizować)

Uwaga

Konieczna jest tylko jedna możliwa ścieżka, więc wyjście programu nie musi dokładnie odpowiadać wyjściowym próbkom. Tak długo, jak podano rozwiązanie, jeśli istnieje, a każde polecenie ruchu przesuwa się na ziemię i ostatecznie osiągnięty jest ostatni metr, wyjście jest prawidłowe.

Dodatkowe dane wyjściowe dotyczące błędu standardowego są ignorowane.

Warunki wygranej

Wygrywa najkrótszy kod, jak to zwykle jest w golfie. W przypadku remisu wygrywa wcześniejsze rozwiązanie.

Przypadki testowe

Istnieją dwa skrypty testowe, zawierające identyczne przypadki testowe:

• bash (Dzięki Ventero )
• PowerShell

Wywołanie jest w obu przypadkach: <test script> <my program> [arguments]np . ./test ruby jumprun.rbLub ./test.ps1 ./jumprun.exe.

Kolejna uwaga

To zadanie było częścią konkursu golfowego, który odbył się na mojej uczelni w latach 2011-W24. Wyniki i języki naszych zawodników były następujące:

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

Nasze własne rozwiązania były

•   92 - Rubinowy
• 124 - PowerShell

Perl, 53 znaki

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

Uruchom to z perl -p jumpnrun.pl. Dla -popcji policzyłem 3 znaki , czyli różnicę długości między perl jumpnrun.pli perl -p jumpnrun.pl.

Nie jestem zbyt biegły w Perlu, więc jestem pewien, że można to jeszcze bardziej skrócić. Używa wyrażenia regularnego podobnego do rozwiązania Howarda .

Ruby, 93 90 79 70 znaków

Myślałem, że rozwiązanie wyrażenia regularnego byłoby całkiem w porządku i kompaktowe (pozwól dopasowanemu wykonać pracę). Niestety wszystkie przypadki i specjalne zabiegi sprawiły, że ten był tak długi - przynajmniej nie dotknąłem 100 ;-).

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

Przechodzi wszystkie przypadki testowe dostarczonego skryptu.

Zapisano kilka znaków w porównaniu do poprzedniego skryptu (teraz wystarczy jedno wywołanie do gsub).

Edycja 1: Zmieniono puts z!=?-??!:''na z!=?-&&$><<?!po tym, jak skrypt testowy nie zezwalał na żadne wyniki dla przypadku testowego 1.

Edycja 2: Poprzednia wersja była

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

Moim pierwotnym pomysłem było zastąpienie postaci za pomocą strategii patrzenia w przeszłość ^(?<=[RJ]*)(-|-...)(?=(-|-...)*-$)i wybiegania w przyszłość w następujący sposób: wzorzec polegał na zastąpieniu „-” literą „R”, a w przeciwnym razie „J”. Niestety, Ruby nie pozwala na obejrzenie się o zmiennej długości, a kolejna grupa przechwytująca dla pierwszej części wydłużyła kod.

Więc zastosowałem podejście iteracyjne: jeśli mogę zacząć od kroku lub skoku, ^(-|-...)po którym następują serie innych kroków lub skoków do ostatniej platformy, (-|-...)*-$to drukuję odpowiednią literę, usuwam pierwszy / cztery znaki i zaczynam od nowa. On może nawet dostroić priorytet RJ vs. JR, zmieniając opcje w wyrażeniu (obecnie preferuje RJ).

Edycja 3: Podział pojedynczej substytucji

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

na dwa

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

dał kolejne kilka znaków. W końcu udało mi się pozbyć tego problemu końca linii, ale kosztem: wykrywanie awarii kosztuje więcej postaci.

Perl - 71 60

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

Teraz przechodzi wszystkie przypadki testowe. :) Okazuje się, że usunąłem ostatnią postać zbyt wcześnie ... a połowa mojego oryginalnego wyrażenia regularnego była całkowicie zbędna.

$ _ = $ ARGV [0]; y / - / R /; s / (R ... (? = R)) (R * (? = R)) / J 2 $ / g; chop; print / /? „!”: $ , $ /

Jeszcze jedno rozwiązanie wyrażenia regularnego, przekazuje 5 przypadków testowych w poście.

Można to skrócić, uruchamiając jako jednowierszowy z -Elub sayzamiast print, ale wtedy perl próbuje interpretować dane wejściowe jako przełącznik ... ( Unrecognized switch: -_-_-_-_-_-)

Python - 89 93 97 93 znaków

Właśnie dlatego.

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

Obecnie kończy się niepowodzeniem tylko dziesięć przypadków testowych (biorąc pod uwagę przypadki, w których istnieje wiele prawidłowych rozwiązań). Naprawię to w pełni później.

Pożyczając jedno z wyrażeń regularnych, kończy się jako

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

Z 96 znakami.

Haskell, 90 znaków:

Moje pierwsze rozwiązanie - długie, ale działa w czasie liniowym, z wykorzystaniem programowania dynamicznego. :) 150 znaków :

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

Drugie rozwiązanie - znacznie wolniejsze (czas wykładniczy), ale znacznie krótsze: 90 znaków

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