Pertanyaan ini adalah yang pertama dari beberapa tantangan Ulang Tahun Brain-flak yang dirancang untuk merayakan Ulang Tahun pertama Brain-Flak! Anda dapat menemukan informasi lebih lanjut tentang Ulang Tahun Brain-Flak di sini

Musim panas lalu kami memiliki Metagolf Integer Brain-flak , dan jawaban yang dihasilkannya sangat berguna bagi komunitas Brain-Flak sejak itu. Hal utama yang membuat Integer Metagolf sangat efisien adalah teknik yang disebut Multiplication hardcoding.

Dalam penggandaan runtime Brain-Flak sangat mahal. Cuplikan multiplikasi terpendek yang diketahui adalah:

({}<>)({<({}[()])><>({})<>}{}<><{}>)

Ditemukan oleh Megatom

Namun ada cara yang sangat sederhana untuk membuat kompilasi waktu kompilasi. Misalnya kode berikut akan dikalikan 5:

 (({})({})({})({}){})

Cobalah online!

Ini berfungsi karena ekspresi berurutan ditambahkan bersama. Masing ({})- masing tidak melakukan apa pun pada stack ( {}muncul dan (..)mendorongnya kembali) dan mengevaluasi apa pun yang ada di atas stack. Semua ungkapan ini bersama-sama menjumlahkan hingga lima kali lipat apa pun yang ada di atas tumpukan.

Untuk setiap nekspresi string berikut akan membuat potongan yang akan melipatgandakan bagian atas tumpukan dengan n:

"("+"({})"*(n-1)+"{})"

Ini berfungsi dengan membuat nekspresi yang semuanya dievaluasi ke atas tumpukan. Yang pertama n-1tidak benar-benar mengubah apa pun dan yang terakhir menghilangkan bagian atas tumpukan sebelum dorongan.

Untuk bilangan komposit, Anda dapat mengaitkan beberapa ekspresi yang lebih kecil secara bersamaan untuk menghemat byte. Misalnya Anda dapat mengalikan dengan 25 dengan mengalikan dengan 5 dua kali:

(({})({})({})({}){})(({})({})({})({}){})

Ini cukup sederhana, dan untuk beberapa angka berfungsi dengan baik namun ada cara yang lebih baik untuk melakukan ini. Sebagai contoh satu metode saya datang dengan menggunakan representasi biner dari angka tersebut. ( Berikut ini adalah implementasi python ) Metode baru ini jauh lebih efektif daripada ekspresi string sederhana yang ditunjukkan sebelumnya, tetapi ini bukan akhirnya, ada segala macam cara menarik untuk penggandaan hardcode dan mungkin satu ton yang belum ditemukan oleh siapa pun.

Jadi saya pikir ini saatnya untuk melihat seberapa baik yang bisa kita dapatkan.

Tinjauan Singkat Brain-Flak

Berikut adalah uraian tentang semua yang perlu Anda ketahui tentang Brain-Flak untuk tantangan ini.

Brain-Flak memiliki "nilads" dan "monads". Nilads adalah tanda kurung yang tidak memiliki apapun di dalamnya. Setiap nilad melakukan sesuatu dan mengembalikan nilai. Untuk tantangan ini, dua nilad yang kami perhatikan adalah {}dan <>. {}muncul bagian atas tumpukan aktif dan mengembalikan nilainya. <>mengalihkan tumpukan aktif dan tumpukan aktif, sehingga tumpukan aktif menjadi tidak aktif dan tumpukan tidak aktif menjadi aktif, mengembalikan nol.

Monad adalah tanda kurung dengan hal-hal di dalamnya. Mereka mengambil satu argumen, jumlah dari semua yang ada di dalamnya, terkadang melakukan suatu tindakan, dan kemudian mengembalikan nilai. Tiga hal yang kami perhatikan adalah (...), <...>dan [...]. Monad paling penting untuk tantangan ini (...)mengambil nilai bagian dalam dan mendorongnya ke tumpukan aktif. Kemudian mengembalikan argumen. <...>dan [...]keduanya monad "inert", yaitu mereka tidak melakukan tindakan apa pun melainkan memodifikasi nilai yang dilewati. <...>selalu mengembalikan nol terlepas dari argumen yang diteruskan. Sementara itu [...]selalu mengembalikan waktu argumen -1.

Contoh program dengan penjelasan

Jika Anda belum pernah memprogram dalam Brain-Flak, mungkin ide yang baik untuk melihat beberapa contoh program menggunakan operasi yang dijelaskan

({}{})

Ini menambahkan dua angka teratas di tumpukan. Setiap {}muncul nilai dari tumpukan dan (...)mendorong jumlah mereka kembali.

({}[{}])

Demikian pula ini mengurangi item kedua pada tumpukan dari yang pertama. Seperti sebelum masing-masing {}muncul nilai tetapi [..]sekitar yang kedua menyebabkannya ditambahkan. Sekali lagi (...)push the sum.

({}<{}>)

Ini menghilangkan nilai kedua pada tumpukan menjaga nilai teratas tetap utuh. Ini berfungsi seperti dua yang terakhir kecuali nilai kedua dibungkam oleh <...>sehingga dorongan hanya mendorong nilai pertama kembali.

(({}))

Ini membuat salinan kedua nilai di atas tumpukan. Ia melakukan ini dengan membuka bagian atas tumpukan dengan {}mendapatkan nilainya, yang pertama (..)mendorongnya kembali mengevaluasi nilainya. Yang kedua (...)mengambil nilai yang dikembalikan oleh yang pertama dan mendorongnya ke tumpukan juga. membuat salinan kedua.

Tugas

Diberikan bilangan bulat, nbuat potongan Brain-Flak stack-clean yang mengalikan bagian atas tumpukan saat ini n.

Anda diizinkan menggunakan operasi Brain-Flak berikut

(...) -> Push Monad, Pushes the result of its contents
<...> -> Zero Monad, Returns zero
[...] -> Negative Monad, Returns the opposite of its contents result
{}    -> Pop nilad, Pops the TOS and returns its value
<>    -> Switch nilad, Switches the active and inactive stack

Operasi lain dilarang untuk tujuan tantangan.

Mencetak gol

Skor Anda akan menjadi panjang kumulatif semua program dari n=2hingga n=10000. Pastikan untuk menyertakan tautan ke output program Anda untuk verifikasi.

Ruby, 669856

$answers = Hash.new{|hash,n|
  valid = []
  2.upto(n**0.5){|i|
    valid.push("("+hash[n/i]+")"+"({})"*(i-2)+"{}") if n%i == 0
  }
  valid.push("({})"+hash[n-1])
  (hash[n] = valid.min_by{|s| s.length})
}
$answers[1] = "{}"

def full_answer n
  "("+$answers[n]+")"
end

Ini adalah jawaban dasar yang cepat. 1000 program pertama ditemukan di sini . (Saya mencoba memposting semuanya, tapi itu kelebihan ukuran pastebin maks.) Saya dapat menambahkan penjelasan kode nanti.

Contoh:

360:    ((((((({})(({}){}){})({}){})({}){}){}){}){})
4608:   (((((((((((({})({}){})({}){}){}){}){}){}){}){}){}){}){})
9991:   (({})((({})(((((((({})((({})({}){}){}){}){}){}){}){}){}){}){})({}){}){})