Tulis program brainfuck yang tidak lebih dari 256 karakter yang mengambil langkah sebanyak mungkin, tetapi tidak berulang tanpa henti. Program tidak boleh mengambil input apa pun.
Lebih spesifik:
- Asumsikan jumlah sel tak terbatas di sebelah kanan.
- Suatu
<
ketika di sel paling kiri tidak melakukan apa-apa. - A
-
saat nilai sel nol setel menjadi255
. - Instruksi
+-<>.
semua dihitung sebagai satu langkah saat dijalankan. - Ketika a
[
atau]
ditemui, itu dihitung sebagai satu langkah. Namun, jika kondisi benar dan kontrol aliran melompat, yang sesuai]
atau[
tidak tidak lagi dihitung sebagai langkah. - Solusi yang mengambil langkah terbanyak akan menang.
- Jika ada semacam pola dalam solusi Anda, memberikan fungsi untuk berapa langkah langkah yang sama dengan program panjang
n
akan dihargai tetapi tidak wajib. - Untuk menghitung instruksi, Anda dapat menggunakan penerjemah yang dimodifikasi ini :
Contoh:
++[-]
Instruksi yang ditemui adalah ++[-]-]
, dan program berjalan selama 7 langkah.
code-challenge
brainfuck
busy-beaver
Anton Golov
sumber
sumber
float
ataudouble
primitif yang digunakan untuk komputasi sehari-hari umum. (Pada saat itu komputer sebagian besar hanya memanipulasi string yang mewakili persamaan)Jawaban:
Berikut adalah program 41 karakter yang pada akhirnya berhenti, menyisakan lebih dari 10 ↑ (10) 28) sel-sel yang berdekatan ditetapkan sama dengan 1 (sehingga jumlah instruksi yang dieksekusi jauh lebih besar dari itu):
Jika saya tidak salah, itu adalah terjemahan yang benar dari program berikut dalam bahasa BF-varian yang menggunakan bit tunggal untuk setiap sel memori (yaitu, konten sel 0..1 bukannya 0..255, jadi '+' bertindak untuk membalik nilai bit):
Nilai persisnya (jumlah 1-bit yang berdekatan) yang dihasilkan oleh program yang terakhir adalah
Program di atas menginisialisasi & menghitung fungsi yang tumbuh seperti 2 ↑↑ x (dalam notasi panah atas Knuth ). Konversi serupa dari program varian-BF yang menginisialisasi & menghitung fungsi yang tumbuh seperti 2 ↑ 23 x menyediakan program 256-karakter berikut:
yang akhirnya berhenti, meninggalkan lebih dari 2 ↑ 23 6 sel yang berdekatan ditetapkan sama dengan 1 (sehingga jumlah langkah jauh lebih dari itu).
NB-1 : 2 ↑ 23 6 adalah angka "sangat besar"; misalnya, bahkan 2 ↑ 4 6 = 2 ↑↑↑↑ 6 sudah melampaui suku pertama (3 ↑↑↑↑ 3) dalam urutan yang digunakan untuk menghitung nomor Graham .
NB-2 : Saya pikir kemungkinan 256 karakter sudah cukup untuk program BF untuk menginisialisasi & menghitung fungsi dengan output yang jauh lebih besar dari angka Graham - jika saya punya waktu, mungkin saya akan mencoba menulis satu.
NB-3 : Jika ada yang tertarik dengan asal-usul program di atas, berikut adalah beberapa sumber daya pemrograman untuk "Brainf * ck F" , dengan berbagai program yang ditulis dengan Python. ("Brainf * ck F", atau hanya "F", adalah apa yang saya sebut varian Turing-complete dari Smallf * ck esolanguage.) Saya baru saja mengunggah file-file ini, yang telah offline selama beberapa tahun, dan untuk saat ini halaman web yang ditautkan hanyalah "lemari arsip" - lihat file Busy_Beavers.txt untuk diskusi terperinci yang relevan dengan program-program di atas.
sumber
Ini adalah karakter 39 yang bagus:
Ini pada dasarnya membuat 'kereta luncur' selebar 3 ruang yang bergerak ke kanan dan menurun satu per satu. Diselesaikan dalam 31.919.535.558 instruksi, dengan loop terdalam mengeksekusi 256 ^ 3 kali. Saya masih punya banyak ruang untuk memperpanjang ini cukup jauh dengan laju 14 karakter ke urutan besarnya hingga run time.
Bekerja pada penerjemah apa pun dengan memori tidak terbatas, atau dengan memori pembungkus.
Saya membiarkannya sebagai latihan bagi pembaca untuk menentukan kapan versi 2 loop yang ditingkatkan akan selesai:
Sekarang telah berjalan semalam, dan ini lebih dari 3.000.000.000 langkah. Masih belum melewati satu iterasi dari loop luar. Baru berhasil melewati 15% dari putaran kedua.
sumber
Program ini bekerja dalam jumlah sel yang sangat sedikit. Dua nilai diinisialisasi pada awal dengan nilai ascii 255. Nilai pertama pada rotasi pertama loop utama dibagi menjadi 255 sel dan mereka diinisialisasi dengan 255 masing-masing, pada rotasi kedua loop utama, setiap nilai dalam 255 sel lagi terbagi hingga 255 * 255 sel, dengan cara yang sama untuk 255 putaran loop utama total sel yang diinisialisasi akan 255 ^ 255. Nilai kedua menentukan berapa kali loop utama harus diulang.
sumber
Program ini hampir sama dengan program saya sebelumnya, perbedaannya adalah bahwa nilai menentukan loop luar tetap dalam sel tertentu sehingga jumlah sel yang diinisialisasi dan langkah-langkah total pada akhir program dapat ditingkatkan
sel diinisialisasi pada akhir program 255 ^ 255
sel diinisialisasi pada akhir program 255 ^ 255 ^ 3
Saya lebih lanjut memodifikasinya untuk menjalankan lebih banyak langkah.
itu menginisialisasi 255 ^ 255 sel selama rotasi pertama sel 255 ^ (255 ^ 255 * 255) utama selama rotasi kedua loop utama 255 ^ {255 ^ (255 ^ 255 * 255) * 255} sel selama rotasi ketiga loop utama di loop cara ini berulang 255 kali
sumber