Pertimbangkan lima makhluk laut seni ASCII ini:
- Ikan standar:
><>
atau<><
- Ikan cepat:
>><>
atau<><<
- Ikan kokoh:
><>>
atau<<><
- Ikan melar:
><<<>
atau<>>><
- Kepiting:
,<..>,
Tulis program yang menerima string karakter yang berubah-ubah <>,.
. Jika ada cara untuk menafsirkan seluruh string sebagai serangkaian makhluk laut yang tidak tumpang tindih, maka string tersebut harus dicetak ulang dengan spasi tunggal yang disisipkan di antara makhluk. Jika penafsiran ini tidak mungkin, tidak ada yang harus dihasilkan (program diam-diam berakhir).
Sebagai contoh, string <><><>
dapat diartikan sebagai dua ikan standar back-to-back. Output yang sesuai adalah<>< ><>
.
Sebagai contoh lain, string ><>><>>
berisi "instance" dari ...
(tanda kurung hanya ditambahkan sebagai indikator)
- beberapa ikan standar:
[><>][><>]>
- ikan cepat:
><[>><>]>
- ikan yang kokoh dalam beberapa cara:
[><>>]<>>
dan><>[><>>]
namun, hanya pasangan ikan standar dan ikan kokoh yang [><>][><>>]
membentang sepanjang tali tanpa karakter berbagi ikan (tanpa tumpang tindih). Jadi output yang sesuai ><>><>>
adalah ><> ><>>
.
Jika ada beberapa cara string dapat ditafsirkan, Anda dapat mencetak salah satu dari mereka. (Dan hanya mencetak satu . Dari mereka) Sebagai contoh, <><<<><
dapat diartikan sebagai ikan standar dan ikan kokoh: [<><][<<><]
, atau sebagai ikan cepat dan ikan standar: [<><<][<><]
. Jadi salah satu <>< <<><
atau <><< <><
akan menjadi output yang valid.
Kepiting hanya untuk bersenang-senang. Karena mereka tidak memulai atau mengakhiri dengan <
atau >
, mereka lebih mudah untuk diidentifikasi (setidaknya secara visual). Misalnya, string
,<..>,><<<>,<..>,><>,<..>,<>>><,<..>,><>>,<..>,<<><,<..>,<><,<..>,>><>
jelas akan menghasilkan output
,<..>, ><<<> ,<..>, ><> ,<..>, <>>>< ,<..>, ><>> ,<..>, <<>< ,<..>, <>< ,<..>, >><>
Berikut adalah beberapa contoh string (satu per baris) yang tidak menghasilkan output:
<><>
,<..>,<..>,
>>><>
><<<<>
,
><><>
,<><>,
<<<><><<<>>><>><>><><><<>>><>><>>><>>><>><>><<><
String terakhir di sini dapat diuraikan jika Anda menghapus yang memimpin <
:
<<>< ><<<> >><> ><> ><> <>< <>>>< >><> >><> >><> ><>> <<><
(Mungkin ada output lain yang mungkin.)
Detail
- String input hanya akan berisi karakter
<>,.
. - String input akan memiliki setidaknya satu karakter.
- Ambil input dengan cara biasa (baris perintah, stdin) dan output ke stdout.
- Kode terpendek dalam byte menang. ( Penghitung byte berguna. ) Tiebreaker adalah posting sebelumnya.
sumber
Jawaban:
Pyth,
644850 byteKasus cobaan.
Versi yang tidak memakan waktu lama ( ) di sini , dalam 52 byte.
O(9n/3)
Ini adalah pendekatan brute force, hasilkan semua urutan dan periksa apakah ada jumlah pada input. Diagram ikan dikompresi sebagai karakter, yang representasi binernya adalah
>
dan<
. Semuanya dibungkus dalam blok try-catch sehingga tidak ada output yang terjadi ketika tidak ada hasil yang ditemukan.Ini solusinya.
O(9n)
Beberapa karakter dilucuti di atas, karena karakter kontrol digunakan. Mereka direproduksi dengan setia pada tautan di atas.
output xxd:
sumber
><>><>>
membutuhkan 15 detik pada mesin saya.Mesin Turing Non-deterministik, 20 negara, 52 transisi (mungkin 882 byte)
Bagaimana Anda mengonversikan ini menjadi byte? Saya telah menulis file (sama sekali tidak golf) untuk mengeksekusi mesin ini dengan Simulator Alex Turing dari Mesin Turing 1 dari Alex Vinokur .
wc -c
menampilkan yang berikut (tidak termasuk file deskripsi dan file input):Ngomong-ngomong, saya sedang mempersiapkan A-Level Ilmu Komputer saya, jadi saya pikir ini akan menjadi latihan yang baik (saya tidak tahu apa yang saya pikirkan). Jadi, inilah definisi:
(fungsi transisi)
Maafkan gambar yang buruk, tapi saya tidak bisa repot-repot menggambar ulang hal ini di komputer. Jika Anda benar-benar ingin menguraikan aturan transisi, saya sarankan Anda membaca file aturan yang saya tautkan di atas.
Saya telah menggunakan
X
s bukan spasi karena spasi sulit untuk divisualisasikan di sini dan simulator tidak menerima spasi dalam alfabet.Konsepnya cukup sederhana - q1 ke q4 digunakan untuk menangkap ikan yang menghadap ke kanan, q11 ke q14 digunakan untuk menangkap ikan yang menghadap ke kiri, q15 ke q19 untuk kepiting dan gumpalan q5 ke q10 hanya untuk memasukkan ruang dan memindahkan semua mengikuti karakter satu ke kanan.
Jika string dapat diartikan, ia menerima string dan rekaman itu berisi string dengan spasi yang disisipkan. Kalau tidak, ia menolak string (saya kira ini dianggap sebagai tidak ada output - mengosongkan rekaman itu akan sangat mudah tetapi akan membutuhkan banyak aturan transisi dan saya tidak berpikir itu akan membuat fungsi transisi lebih cantik untuk dilihat).
1 Catatan: Sulit untuk dikompilasi. Saya harus mengedit
src/tape.cpp
file dan menggantiLONG_MAX
dengan1<<30
dan kemudian pergi kedemo
direktori, edit Makefile untuk menggantiEXE_BASENAME
denganturing.exe
dan menjalankanmake
. Lalu pergi ke direktori dengan file yang saya tulis dan jalankan/path/to/turing/download/src/turing.exe meta
.sumber
ikan (ya, ikan itu), 437 byte
Ini menurut saya sebagai salah satu tugas pemrograman di mana tepatnya satu bahasa benar.
Versi berikut masih merupakan jawaban terpanjang untuk tantangan,
tetapi karena ini dilakukan terutama untuk permainan kata-kata (saya harap, saya berharap), bermain golf lebih baik dibiarkan sebagai latihan untuk pembaca.
sumber
printf 'H4sIADSjKlUCA4VPQW6DMBC89xUj5AOocSSOlV1/BHGgjgMrBUPN0kRRHl/jmEg99WBLszM7M7s4BqMw2hQotNHxNy+QkDYJZU7rTJqED/p4NIdCLdFmVOfVW6bJY04DeQGhVteBLg4cVqfYLQxBkD3jQ6HzJwTHa/BRRmf4ibEtBpRfriefXCxKZ4cJghtB7eNqIW2lnqMu9D9N3T7sGtOssDInJCk+982/MlmOHQ+I6rqKRv5UpRxCntN7XSk7eSYfK0f+eR3EmI23qilH3iFCrjIqdyNO8nzJvJH7alMu7jsnlHZafWw5VluD9r/0/c2vQ95+AYBxAwS2AQAA'|base64 --decode|gzip -d>a;fish a
> <>, 602 byte
Sebuah solusi di Fish, mungkin sangat golf tetapi ini adalah program pertama saya>. Dibutuhkan input dari tumpukan input dan berjalan pada penerjemah online> <>.
Bagaimana itu bekerja :
Sebuah loop membaca semua input dan menumpuknya, membalikkannya dan meletakkan -1 di bagian bawah yang akan menandai bahwa parsing selesai (semua karakter tetap di stack sampai string dianggap parsable).
Penguraian menggunakan fakta bahwa semua karakter berbeda modulo 5, dan semua pola adalah deterministik kecuali <> << dan> <>>. Karakter yang diuraikan diletakkan di bagian bawah tumpukan.
Ketika sebuah pola selesai, jika -1 di atas, semua karakter dicetak, jika tidak spasi ditambahkan dan program loop.
Jika <> << atau> <>> ditemukan, register bertambah (0 di awal), dan 0 ditempatkan di tumpukan sebelum karakter terakhir (sehingga <> <atau> <> tetap setelah rollback) . Jika kesalahan muncul sesudahnya selama penguraian, register berkurang, semua karakter setelah 0 dimasukkan kembali ke atas (kecuali spasi berkat% 8 = 0 test).
Jika kesalahan terdeteksi saat register adalah 0, atau di dalam kepiting, program langsung berakhir.
sumber
Python 3, 156
Strateginya adalah untuk menghasilkan daftar ikan dan membandingkan rangkaian mereka dengan string input.
Ini sangat lama. Jika Anda benar-benar ingin melihat output, ganti
for _ in s
denganfor _ in [0]*3
, di mana 3 adalah batas atas untuk jumlah ikan. Ini berfungsi untuk digunakans
karenas
mengandung paling banyak satu ikan per arang.Terima kasih kepada Sp3000 untuk perbaikan bug dan char save on input.
Lama 165:
sumber
a and b or c
memberikan nilai yang salah ketikab
mungkin Falsey. Saya kembali keif/else
untuk 2 karakter, tetapi mungkin ada cara untuk membuat pekerjaan ternary.*l,s=[],input()
Perl, 81 +1 byte
Coba kode ini secara online.
Kode ini mengharapkan input dalam
$_
variabel; jalankan ini dengan-n
sakelar Perl ( dihitung sebagai +1 byte ) untuk menerapkannya pada setiap jalur input, misal seperti ini:Kode ini menggunakan mesin regexp dari Perl (dan khususnya fitur eksekusi kode yang disematkan ) untuk melakukan pencarian penelusuran mundur yang efisien. Masing-masing ikan yang ditemukan dikumpulkan dalam
@a
susunan, yang dirangkai dan dicetak jika kecocokan berhasil.Kode ini juga menggunakan fitur Perl 5.10+
say
, sehingga harus dijalankan dengan-E
atau-M5.010
beralih (atauuse 5.010;
) untuk mengaktifkan fitur modern tersebut. Secara tradisional, sakelar semacam itu yang hanya digunakan untuk mengaktifkan versi bahasa tertentu tidak termasuk dalam jumlah byte.Atau, inilah versi 87-byte yang tidak memerlukan sakelar baris perintah khusus sama sekali. Bunyinya satu baris dari stdin, dan mencetak hasilnya (jika ada) ke stdout, tanpa linefeed baris tambahan:
Ps. Jika mencetak ruang ekstra di awal output diizinkan, saya bisa menghemat dua byte dengan:
sumber
><(>|<<)>
Python 3,
196186 byteRekursi sederhana.
g
baik mengembalikan daftar ikan yang diuraikan, atauNone
jika string input tidak dapat diurai.sumber
Python 2, 234 byte
Saya mencoba solusi regex Python pertama, tetapi tampaknya tidak ada cara untuk mengekstrak grup setelah kecocokan pada beberapa pola. Berikut ini adalah pencarian rekursif yang tampaknya bekerja dengan baik pada kasus uji.
Contoh tes:
Dan versi yang tidak diserang:
sumber
if
bisa berada pada satu baris (seperti yang Anda lakukan di tempat lain). Juga, alih-alihif p<len(t)
saya pikir Anda dapat melakukanif t[p:]
untuk menghemat beberapa byte.C # - 319 byte
Solusi ini memalukan sederhana, hampir tidak apa-apa untuk Golf. Ini adalah program yang lengkap, mengambil input sebagai garis dari STDIN, dan output hasilnya ke STDOUT.
Ini hanya mencoba untuk mencocokkan setiap ikan ke posisi pertama setelah spasi (atau di awal string), dan mencocokkan setiap jenis ikan dengan itu. Jika ikan cocok, maka secara rekursif memanggil pemecah setelah memasukkan spasi setelah ikan, atau hanya mengembalikan input itu (dengan \ n untuk alasan output) jika string yang tidak cocok secara harfiah adalah ikan (yaitu kami telah menemukan solusi) .
Saya belum melakukan banyak upaya untuk memberikan ikan string pengobatan kolmogorov yang biasa, karena tidak terlalu lama, dan saya tidak dapat menemukan cara murah untuk membalikkan string dalam C # (saya tidak berpikir LINQ akan membayar), jadi mungkin ada beberapa peluang di sana, tapi saya agak meragukannya.
sumber
Haskell (Parsec) - 262
sumber
im sedikit python noob jadi abaikan keanehannya: P
sumber
m
Alih- alihmsg
,s
bukannyastart
, ...) dan hanya menggunakan 1 spasi per kenaikan. Dan tolong posting menambahkan jumlah karakter program Anda (Anda dapat menghitungnya di sini ).Ruby, 177 byte
Bukan yang terpendek tapi yang pertama di ruby:
Upaya di sini adalah memperluas regexp secara rekursif dan mencocokkannya dengan input.
Jika kecocokan yang lebih panjang ditemukan r () akan muncul kembali, jika tidak maka kecocokan akan memeriksa apakah kecocokan terakhir mengkonsumsi seluruh string input dan hanya kemudian mengeluarkannya dengan spasi tambahan.
sumber
CJam,
111 9691 (atau 62 byte)Pendekatan serakah yang berulang untuk mencari tahu semua kombinasi ikan yang mungkin dilakukan saat Anda mengulanginya. Benar-benar tidak bermain golf sekarang.
Kode berisi beberapa karakter yang tidak patut dicetak, jadi gunakan tautan di bawah ini untuk referensi.
Perbarui Mengodekan string
Akan menambah penjelasan begitu selesai bermain golf
Cobalah online di sini
62 byte
Versi super lambat. Ini pada dasarnya menciptakan semua kombinasi dan pemeriksaan yang sama dengan input.
Ini juga mengandung karakter yang tidak patut dicetak, jadi andalkan tautan di bawah ini.
Cobalah online di sini
sumber
Haskell,
148146 bytesPengujian:
$ echo "> <>> <>>" | runhaskell fishes.hs
Penjelasan
Berdasarkan jawaban saya sebelumnya untuk pertanyaan serupa. Algoritme berjalan dalam waktu eksponensial.
Ini berbunyi dari kanan ke kiri.
Ini tidak akan mencetak string yang berakhir dengan spasi, meskipun string seperti itu dihasilkan juga, karena lawannya tanpa spasi dihasilkan terlebih dahulu.
sumber
JavaScript (ES6), 164
Pemindaian berulang rekursif dan mendalam.
Sebagai program dengan I / O via popup:
Sebagai fungsi yang dapat diuji:
Test suite (dijalankan di Firefox / FireBug console)
Keluaran
Tidak digabungkan hanya fungsi k
sumber
Haskell,
148142ini menggunakan daftar pemahaman untuk beralih pada ikan, memilih orang-orang yang cocok dengan awal dan melanjutkan secara rekursif.
sumber
Javascript (
122135 byte)Bukan yang paling golf di sini, bisa dilucuti sedikit.
Yang ini berdasarkan regex, dan agak sulit untuk mencari tahu apa yang sedang terjadi.
Yang ini satu kalimat.
Pada dasarnya, saya memeriksa sintaks dan kemudian saya membagi string berdasarkan karakter dan bergabung bersama.
Ini melempar pengecualian ketika Anda memberikan input yang tidak valid.
Jika tidak bisa melempar pengecualian (
126139 byte):Keduanya satu garis.
Keduanya bekerja dengan cara yang sama.
Terima kasih @ edc65 untuk mendeteksi kasing tepi yang tidak berfungsi dengan baik.
Anda dapat mengujinya di sini (output akan ditulis ke dokumen).
Ini didasarkan pada versi yang melempar pengecualian ketika Anda memasukkan kode yang tidak valid.
Tampilkan cuplikan kode
(Saat ini, ada bug di tumpukan potongan,
Saya telah memposting di metaItu sudah ditanyakan kemarin. Agar berfungsi, saya telah diganti$
dengan\x24
, yang memiliki output yang sama. Anda dapat membaca tentang bug di sini: http://meta.codegolf.stackexchange.com/questions/5043/stack-snippets-messing-with-js )sumber
><>><>>
. Saya pikir ini tidak dapat diselesaikan dengan begitu mudah dengan Regexp, Anda memerlukan beberapa lookahead atau backtrak atau apa pun ...Scala, 299 Bytes
Uji Kasus
Keluaran
sumber
Java, 288 byte
Diformat:
sumber
Saya tidak mencari ukuran, tapi di sini ada cara mudah untuk melakukan hal ini di Dart.
sumber
Python 3,
166164 byteSolusi rekursif. Terlambat ke pesta, tapi kupikir aku akan mempostingnya karena mengalahkan Sp3000's
2022 byte tanpa harus memaksa jawaban.sumber