Matthew suka memecahkan teka-teki. Setiap kali dia berhasil menyelesaikannya, dia melompat-lompat dengan gembira. Baru-baru ini dia benar-benar perlu melakukan ini karena hujan meteor telah membuka kawah dan lubang di tanah di mana dia tidak ingin jatuh.

Anda diberi bagian pemandangan yang ingin diseberangi oleh Matthew, semoga pada akhirnya akan menjadi sehat. Tanah diberikan dalam meter, dengan masing-masing meter baik tanah normal atau lubang. Ketika dia berlari dia berhasil menyeberang satu meter per langkah; alternatifnya adalah melompat yang melintasi empat meter per langkah. Matius dimulai di paling kiri pada meteran pertama dan ingin sampai ke yang terakhir (tidak melampauinya - bayangkan saja lubang tak berujung di luar meter terakhir yang diberikan dalam lanskap).

Memasukkan

Input diberikan sebagai satu baris pada input standar, diakhiri oleh satu baris. Garis terdiri dari tanda hubung ( -) atau garis bawah ( _), masing-masing mewakili meteran tanah atau lubang. Input sampel dapat berupa:

----__--___---

Lanskap yang diberikan setidaknya satu dan paling panjang 30 meter dan selalu dimulai dengan tanah.

Keluaran

Output diberikan pada output standar dan mewakili serangkaian perintah gerakan ke Matthew, baik run ( R) atau jump ( J). Seperti disebutkan di atas, perintah jalankan menyebabkan Matius berlari satu meter sementara melompat membawanya ke depan tepat empat meter. Untuk contoh yang diberikan di atas, gerakan berikut dimungkinkan:

RRJRJRR

yang terlihat kira-kira sebagai berikut:

Jika tidak ada jalur aman melalui lanskap, maka tanda seru tunggal ( !) harus dicetak.

Input sampel

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

Output sampel

JRRR
RRJRJRR
!
!

(output terakhir kosong karena tidak ada gerakan yang diperlukan, tapi saya kira, penurunan harga tidak dapat menguraikan ini)

Catatan

Hanya satu jalur yang mungkin diperlukan, sehingga keluaran program tidak harus benar-benar sesuai dengan keluaran sampel. Selama solusi diberikan jika ada dan setiap perintah gerakan bergerak ke ground dan meter terakhir akhirnya tercapai, hasilnya valid.

Output tambahan pada kesalahan standar diabaikan.

Kondisi menang

Kode terpendek menang, seperti kebiasaan dalam golf. Dalam kasus seri, solusi sebelumnya menang.

Uji kasus

Ada dua skrip pengujian, yang berisi kasus pengujian yang identik:

• bash (Terima kasih kepada Ventero )
• PowerShell

Doa dalam kedua kasus:, <test script> <my program> [arguments]misalnya ./test ruby jumprun.rbatau ./test.ps1 ./jumprun.exe.

Catatan lain

Tugas ini adalah bagian dari kontes golf yang diadakan di universitas saya selama 2011-W24. Nilai dan bahasa kontestan kami adalah sebagai berikut:

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

Solusi kami sendiri adalah

•   92 - Ruby
• 124 - PowerShell

Perl, 53 karakter

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

Jalankan ini dengan perl -p jumpnrun.pl. Saya telah menghitung 3 karakter untuk -popsi, yang merupakan perbedaan panjang antara perl jumpnrun.pldan perl -p jumpnrun.pl.

Saya tidak lancar berbahasa Perl, jadi saya cukup yakin ini bisa dipersingkat lebih lanjut. Ini menggunakan regexp mirip dengan solusi Howard .

Ruby, 93 90 79 70 karakter

Saya pikir solusi regex akan cukup bagus dan kompak (biarkan korek api melakukan pekerjaannya). Sayangnya semua kasus tepi dan perawatan khusus membuat ini begitu lama - setidaknya saya tidak menyentuh 100 ;-).

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

Itu melewati semua testcases dari skrip yang disediakan.

Menyimpan beberapa karakter dibandingkan dengan skrip sebelumnya (sekarang satu panggilan gsubsudah cukup).

Sunting 1: Diubah puts z!=?-??!:''menjadi z!=?-&&$><<?!setelah skrip uji tidak diizinkan output untuk kasus uji 1.

Sunting 2: Versi sebelumnya adalah

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

Ide awal saya adalah mengganti karakter dengan menggunakan strategi melihat-belakang dan melihat ke depan seperti ini: Pola itu ^(?<=[RJ]*)(-|-...)(?=(-|-...)*-$)dan saya kemudian akan mengganti '-' dengan 'R' dan sebaliknya dengan 'J'. Sayangnya Ruby tidak mengizinkan variabel-panjang melihat-belakang dan grup penangkap lain untuk bagian pertama membuat kode lebih lama.

Jadi saya melakukan pendekatan iteratif: jika saya bisa mulai dengan langkah atau lompatan ^(-|-...)diikuti dengan serangkaian langkah lain atau lompatan hingga platform terakhir (-|-...)*-$maka saya mencetak huruf yang sesuai, hapus satu / empat karakter pertama dan mulai lagi. Aktif bahkan dapat menyetel prioritas RJ vs JR dengan mengalihkan pilihan di dalam ekspresi (saat ini lebih disukai RJ).

Sunting 3: Memisahkan subtitusi tunggal

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

menjadi dua

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

memberi beberapa karakter lagi. Akhirnya saya berhasil menyingkirkan masalah end-of-line ini tetapi dengan biaya: deteksi kegagalan membutuhkan beberapa karakter lagi.

Perl - 71 60

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

Sekarang lewati semua testcases. :) Ternyata saya terlalu cepat menghapus karakter terakhir ... dan setengah dari regex asli saya sepenuhnya berlebihan.

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

Namun solusi regex lain, melewati 5 testcases di pos.

Dapat dipersingkat dengan berjalan sebagai satu-liner dengan -Edan saybukannya print, tetapi kemudian perl mencoba menginterpretasikan input sebagai saklar ... ( Unrecognized switch: -_-_-_-_-_-)

Python - 89 93 97 93 karakter

Hanya karena.

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

Hanya gagal sepuluh kasus uji sekarang (dengan mempertimbangkan kasus di mana ada beberapa solusi yang valid). Saya akan memperbaikinya sepenuhnya nanti.

Meminjam salah satu regex yang berfungsi, berakhir sebagai

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

Dengan 96 karakter.

Haskell, 90 karakter:

Solusi pertama saya - panjang, tetapi bekerja dalam waktu linier, menggunakan pemrograman dinamis. :) 150 karakter :

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

Solusi kedua - jauh lebih lambat (waktu eksponensial), tetapi jauh lebih pendek: 90 karakter

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