Rotasi string dibuat dengan memisahkan string menjadi dua bagian dan membalik urutannya, misalnya "world! Hello,"
rotasi "Hello, world!"
. Dimungkinkan untuk membuat program yang dapat diputar untuk membentuk program yang berbeda, tetapi masih valid. Perhatikan contoh ini dalam python:
print ")import sys; sys.stdout.write("
Dapat diputar untuk membentuk
import sys; sys.stdout.write("print ")
Itu sendiri merupakan program python yang valid.
Tantangan Anda adalah menulis sebuah program yang menghasilkan rotasi itu sendiri, yang ketika dijalankan akan menampilkan program yang asli. Poin bonus untuk setiap entri dengan panjang siklus lebih dari dua!
Ini adalah kode golf, skor pastinya adalah: (panjang kode) / (panjang siklus - 1).
EDIT: Kami memiliki pemenang (kecuali orang lain mampu mengalahkan skor 4)! Saya masih sangat tertarik untuk melihat solusi lain, baik itu pesaing atau bukan.
sumber
Jawaban:
APL (158 karakter, skor = 4)
Saya menggunakan Dyalog APL di sini. Jumlah siklus dapat ditingkatkan satu dengan menambahkan
0
(0 diikuti oleh spasi) ke akhir ekspresi dan ke akhir string (sebelum'''
). Panjang siklusnya(# 0's) + 1
, dan panjang ekspresi itu150 + 4*(cycle length))
. Dengan asumsi kami terus menambahkan nol selamanya, nilainya adalahLimit[(150 + 4*n)/(n - 1), n -> Infinity] = 4
, di manan
panjang siklusnya.Berikut ini contoh dengan panjang siklus = 6:
192 karakter, skor = 2
Bergantung pada implementasinya, satu titik kegagalan bisa terjadi ketika bilangan bulat diawali ke string terlalu besar. Secara teoritis, kita dapat menambahkan siklus dengan menambahkan dua karakter - a
1
di akhir string (sebelum'''
) dan a1
di akhir seluruh baris.200 karakter, skor = 1
Implementasi APL saya tidak memiliki integer presisi tak terbatas secara default, jadi integer dikonversi menjadi float ketika menjadi terlalu besar, menyebabkan output salah. Jadi yang ini adalah yang paling rewel, tetapi secara teoritis (baik dengan tangan atau dengan penerjemah APL yang berbeda), harus memiliki skor 1. Cukup tambahkan a
1
ke akhir ekspresi, dan Anda mendapatkan siklus lain.Ikhtisar (dengan quine yang lebih pendek)
Saya akan memberikan gambaran tentang versi pertama, karena saya pikir itu mungkin yang paling mudah untuk dipahami. Namun, sebelum menangani versi itu, kami akan mempertimbangkan quine sederhana di APL :
Saya telah menemukan bahwa salah satu cara terbaik untuk memahami beberapa ekspresi APL adalah dengan melihat output di seluruh kaskade operator / fungsi. Semua operator dan fungsi dalam APL bersifat asosiatif-kanan dan memiliki prioritas yang sama, jadi inilah, dari kanan ke kiri:
'''1⌽22⍴11⍴'''
: Ini hanya string literal (daftar karakter).''
adalah cara APL untuk keluar dari tanda kutip tunggal. Output:'1⌽22⍴11⍴'
.11⍴'''1⌽22⍴11⍴'''
: Di sini, kami membentuk kembali (⍴
) string menjadi panjang11
. Karena panjang string di bawah 11, maka string diulangi (yaitu,5⍴'abc'
akan menghasilkan'abcab'
). Output:'1⌽22⍴11⍴''
. Jadi kita sekarang memiliki dua tanda kutip di akhir - kita mendapatkan suatu tempat!22⍴11⍴'''1⌽22⍴11⍴'''
: Demikian pula, kami sekarang membentuk ulang output kami sebelumnya menjadi panjang22
. Output:'1⌽22⍴11⍴'''1⌽22⍴11⍴''
. Kita hampir sampai - kita hanya perlu memindahkan kutipan tunggal ke akhir.1⌽22⍴11⍴'''1⌽22⍴11⍴'''
: Di sini, kami memutar (⌽
) daftar karakter berdasarkan1
. Ini memindahkan karakter pertama dari string ke akhir. Sebagai contoh lain,2⌽'abcdef'
kembali'cdefab'
. Output:1⌽22⍴11⍴'''1⌽22⍴11⍴'''
.Rotating quine
Quine pendek itu adalah dasar utama quine berputar kami. Sekarang, dengan itu dalam pikiran, mari kita lihat quine kami:
{ ... }
mendefinisikan fungsi yang tidak disebutkan namanya, di mana kita akan melakukan pekerjaan. Perhatikan bahwa fungsi dalam APL mengambil argumen kanan, dilambangkan dengan⍵
, dan argumen kiri opsional, dilambangkan dengan⍺
(think infix). Kami ingin memberi makan fungsi ini baik string quine kami dan sesuatu untuk membantu kami dalam menciptakan jumlah siklus yang sewenang-wenang. Untuk membuat segalanya lebih mudah pada diri kita sendiri (dan siapa pun yang ingin menambahkan siklus), kita menjadikan string quine argumen kiri. Maka argumen yang benar adalah di mana kita menempatkan daftar siklus kita. 2 atau lebih item yang dipisahkan oleh spasi membuat daftar, jadi dalam contoh ini, kami memiliki daftar 2 elemen yang terdiri dari a1
dan a0
.Kita dapat melihat bahwa fungsinya mirip dengan quine dari sebelumnya. Kami memiliki
...⌽...⍴...⍴...
bentuk yang sama dari sebelumnya. Jadi itu bagus - kita setidaknya mengerti itu! Mari kita mempelajari lebih dalam elips, dimulai dengan semuanya setelah yang terakhir⍴
:⊃,/(~^/¨⍺=0)/⍺
.⍺=0
mengembalikan daftar, dalam hal ini, dengan bentuk yang sama dengan⍺
, di mana setiap elemen⍺
digantikan oleh1
jika sama dengan0
, dan0
sebaliknya. Ini dilakukan secara rekursif; jadi jika kita memiliki daftar daftar daftar karakter, masing-masing karakter akan diuji terhadap 0, dan Anda akan mendapatkan kembali daftar daftar daftar nilai-nilai biner.⍺
hanya terdiri dari string kami, kami mendapatkan kembali daftar 0. Kalau tidak, argumen kiri kami memiliki beberapa 0 yang diawali untuk itu (misalnya,0 0 0 'quinestring'
), jadi itu adalah daftar yang terdiri dari 0 dan daftar lain, string kami. Maka output kami terlihat seperti1 1 1 <sub-list of zeros>
.^/¨⍺=0
: Kami menerapkan fungsi turunan^/
, yang mengurangi (/
) menggunakan fungsi logis AND (^
), untuk setiap¨
elemen ( ) dari⍺=0
. Ini untuk meratakan sub-daftar nol sehingga kita dapat menganggap string quine sebagai satu nilai biner. Mempertimbangkan contoh sebelumnya, hasilnya adalah1 1 1 0
.~
: Kami biner TIDAK masing-masing nilai dari sebelumnya (misalnya, kembali0 0 0 1
).(~^/¨⍺=0)/⍺
: Untuk setiap elemen dalam⍺
, kami mereplikasi (/
) jumlah kali yang diberikan oleh elemen yang sesuai dalam argumen kiri. Ini menghilangkan semua 0, meninggalkan kita hanya dengan string quine kita.⊃,/
adalah beberapa dokumen yang diperlukan untuk memastikan bahwa kami mendapatkan kembali daftar karakter yang rata, dengan mengurangi hasilnya dengan fungsi gabungan (,
). Jika input sudah daftar rata (yaitu, argumen kiri ke fungsi utama kami hanya string), kami mendapatkan daftar 1-elemen yang berisi daftar itu. Dalam kasus lain, ketika kita memiliki daftar yang terdiri dari sub-daftar untuk string, kita mendapatkan hal yang sama kembali (daftar dengan sub-daftar). Kami kemudian membongkar ini (⊃
), memberi kami hanya elemen pertama dari daftar (yaitu, sub-daftar karakter). Ini mungkin tampak tidak perlu, tetapi jika tidak kita akan mencoba untuk membentuk kembali daftar 1-elemen!Selanjutnya, kita melihat panjang yang diberikan untuk membentuk kembali pertama, dalam tanda kurung:
⍺,⍵
: Kami menggabungkan argumen yang benar dengan argumen pertama⊃,/⍺,⍵
: Sama seperti sebelumnya - ratakan daftar.+/0=⊃,/⍺,⍵
: Tambahkan jumlah nol dalam daftar dengan mengurangi (/
) menggunakan fungsi penambahan (+
).2×+/0=⊃,/⍺,⍵
: Kalikan angka itu dengan dua.z←2×+/0=⊃,/⍺,⍵
: Tetapkan (←
) hasilnya ke variabelz
,. Untuk rekap,z
sekarang dua kali jumlah nol yang ditemukan di argumen kiri dan kanan.77+z←2×+/0=⊃,/⍺,⍵
: Kami kemudian menambahkan77
, untuk karakter dalam string quine, mengabaikan semuanya setelah spasi berikut1
. Seperti pada contoh quine awal, kami menambahkan 1 pada panjang string untuk mendapatkan satu kutipan lagi.'{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 ''
Argumen untuk membentuk kembali yang berikut adalah sederhana dan mencerminkan quine pendek (2 kali panjang untuk membentuk kembali pertama). Output kami sekarang adalah:
Sekarang untuk langkah terakhir, di mana kami menghitung berapa banyak untuk memutar string output:
0
(dan ruang lain) untuk pindah ke awal juga, kami ingin memutar kembali 3 karakter tambahan.+/+/¨⍺=0
: Jumlahkan angka nol di argumen kiri . Yang pertama (dari kanan)+/¨
menjumlahkan jumlah setiap elemen (yaitu, sublist atau hanya integer), dan yang kedua+/
memberi kita jumlah dari daftar yang dihasilkan.5+2×+/+/¨⍺=0
: Kalikan dua (untuk memutar spasi juga), dan tambahkan 5 (hasil yang kami buat sebelumnya).-
untuk menangani kasus ketika kita mencapai akhir siklus kita:(3+z)×^/⍵
: DAN semua elemen dalam argumen yang tepat bersama untuk melihat apakah kita telah mencapai tujuan kita (1
), dan kalikan dengan3+z
.Dan kita selesai!
sumber
⍴
operator (?). Saya pikir saya harus membaca semuanya beberapa kali sebelum mencernanya sepenuhnya!GolfScript, 10046/9999 ≈ 1.0047 (skor asimptotik 1)
OK, saya akan mencoba dan mengalahkan entri APL DC dengan ini:
Kode di atas bukanlah quine yang sebenarnya - Saya merasa memposting 10kB satu-liner bukan ide yang bagus. Alih-alih, menjalankan kode di atas sekali menghasilkan program GolfScript 10046-char yang sebenarnya, yang, ketika diulang sebagaimana ditentukan dalam pertanyaan, menghasilkan 9999 rotasi itu sendiri dan, akhirnya, itu sendiri lagi.
Panjang siklus (dan program) dapat disesuaikan dengan mengubah konstanta
9999
. Untuk singkatnya dan kenyamanan, saya akan menunjukkan seperti apa hasil iterasi jika konstanta dikurangi menjadi9
:Ketika konstanta
9999
meningkat, rasio panjang program dan panjang siklus (minus satu) cenderung satu. Aku cukup yakin bahwa ini solusi tidak dipukuli, setidaknya tidak asimtotik. ;-)Bagaimana cara kerjanya?
GolfScript adalah bahasa yang cukup mudah untuk menulis quines, karena pada dasarnya angka apa pun bertindak sebagai quine: misalnya, program GolfScript
12345
menampilkan - Anda dapat menebaknya -12345
. Juga, menggabungkan beberapa quines biasanya menghasilkan quine. Jadi, saya bisa menggunakan angka sederhana seperti11111...111
sebagai bagian berulang dari quine siklik saya.Namun, agar quine benar-benar berputar, kita perlu membawa dan mengeksekusi "payload" yang tidak sepele. Quine GolfScript paling sederhana yang dapat saya pikirkan yang dapat melakukannya adalah sebagai berikut:
Jadi rencana saya adalah untuk awalan quine seperti itu dengan konstanta numerik berulang, dan menggunakan payload yang memotong satu digit dari angka dan memindahkannya ke akhir program. Jika mendeteksi program yang ada adalah tidak ada konstan numerik di depannya (dalam hal nilai di bawah itu di tumpukan akan menjadi string kosong, dengan asumsi tidak ada input), itu malah akan tambahkan tetap-panjang numerik konstan di depan diri.
Ada satu kerut tambahan, meskipun - ketika "membungkus di sekitar", payload juga harus menekan output dari nomor setelah itu sendiri. Biasanya, ketika program GolfScript berakhir, semua nilai pada stack secara otomatis dicetak, yang akan menjadi masalah di sini.
Namun, ternyata ada cara (AFAIK) tidak berdokumen untuk menghindari hal itu: penerjemah benar-benar memanggil fungsi yang telah ditentukan
puts
untuk melakukan pencetakan, jadi mendefinisikan ulang fungsi itu sebagai no-op menekan output otomatis. Tentu saja, ini juga berarti bahwa kita pertama-tama harus memanggilputs
diri kita untuk mencetak bagian dari tumpukan yang ingin kita cetak.Kode terakhir terlihat cukup berantakan (bahkan untuk GolfScript), tetapi setidaknya berfungsi. Saya menduga mungkin ada beberapa cara cerdas yang saya belum memikirkan untuk mencukur beberapa karakter dari payload, tetapi untuk versi ini saya terutama hanya berfokus pada skor asimptotik.
sumber
puts{}:puts
, meskipun saya bisa melihat argumen untuk{print}:puts
alasan bahwa baris baru dalam output akan berarti bahwa itu tidak benar-benar berputar.]puts{}:puts
diperlukan untuk wrap-around dari{STUFF}.~111111111
ke111111111{STUFF}.~
, jika jumlah1
s pada akhir program hanya terus tumbuh dan berkembang. ({}
Tampaknya tidak perlu, meskipun; tampaknya, juru bahasa GolfScript memungkinkan penugasan dari tumpukan kosong.)HTML, minus tanpa batas (hampir)
-2
AA
-10
AAAAAAAAAA
Dan seterusnya ... Jika seseorang mengatakan itu curang, kita dapat berdebat tentang hal itu, tetapi saya telah menemukan lubang yang dipertanyakan :)
Jadi saya kira semua orang mengerti kode itu, tidak memiliki loop, loop terpanjang
0
dan mempertimbangkan panjang programn
, skorn / (0 - 1)
atau-n
, saya bisa menulis program yang memilikin
bilangan bulat positif besar, tetapi tidak berguna, karena semua orang memahaminya.sumber