Brain-flak adalah bahasa turing-tarpit berbasis stack, ditulis secara kolaboratif antara saya, DJMcMayhem , dan 1000000000 .

Beberapa pengguna sangat berpengalaman dalam cara misterius Brain-Flak. Jadi saya pikir itu ide yang baik untuk mengatur pertanyaan ini sebagai cara untuk kita, dan semoga orang lain juga, untuk berbagi pengetahuan kita dengan masyarakat dan menurunkan standar masuk ke bahasa ini "dirancang untuk menjadi menyakitkan untuk digunakan". Dan mungkin bahkan mengajar kita dengan lebih banyak pengalaman beberapa trik baru.

Jadi tips apa yang Anda miliki untuk bermain golf di brain-flak? Saya mencari ide yang dapat diterapkan pada masalah kode golf secara umum yang setidaknya agak spesifik untuk brain-flak (mis. "Hapus komentar" bukan jawaban).

Silakan kirim satu tip per jawaban.

Gunakan tumpukan ketiga

Jika Anda telah membaca judulnya, Anda mungkin sedikit bingung. Tentunya hanya ada dua tumpukan di Brain-Flak? Namun saya meyakinkan Anda bahwa itu ada dan itu adalah salah satu yang paling kuat jika bukan alat yang paling kuat dalam menulis dan golf Brain-Flak.

Apa itu "Tumpukan Ketiga"?

Setiap program Brain-Flak menggunakan tumpukan ketiga dengan satu atau lain cara, tetapi sebagian besar penggunaannya berlangsung di belakang layar dan seringkali berguna untuk mengabaikan fakta bahwa itu ada. Setiap tanda kurung dalam program menambah atau menghapus satu item dari tumpukan. Tiga dari kawat gigi terbuka ([<semua menambahkan item ke stack sementara tiga konjugat mereka )]>semua menghapus item dari stack. Nilai item pada stack adalah nilai dari cakupan program saat ini dan menggunakan nilads akan mengubah nilai ini dengan cara tertentu. Kurung tutup )memiliki fungsi unik untuk memindahkan elemen dari Tumpukan Ketiga ke tumpukan saat ini; dorongan.

Semoga ini menjadi jelas bagi Anda. Tumpukan Ketiga adalah semacam tumpukan yang mengingat nilai kembali kode yang telah dieksekusi. Mari kita telusuri contoh program sederhana untuk melacak dua tumpukan normal dan tumpukan ketiga.

Contoh

Kami akan berjalan melalui program berikut. Program ini mendorong -3, 1, -2ke stack.

(([()()()])(()))

Kami mulai dengan tiga kawat gigi terbuka, yang semuanya mendorong nol ke tumpukan ketiga.

Tumpukan kami sekarang terlihat seperti ini, Tumpukan Ketiga adalah yang di sebelah kanan dan tumpukan aktif memiliki ^di bawahnya:

        0
        0
  0  0  0
  ^

(([()()()])(()))
   ^

Sekarang kami memiliki tiga ()nilad. Ini tidak melakukan apa pun pada dua tumpukan normal, namun mereka masing-masing menambahkan satu ke atas tumpukan ketiga membuat tumpukan kita terlihat seperti:

        3
        0
  0  0  0
  ^

(([()()()])(()))
         ^

Sekarang kita menjumpai ]seperti yang dinyatakan sebelum kurung tutup menghapus item dari Third Stack, tetapi ]memiliki fungsi mengurangkan elemen yang dihapusnya dari atas tumpukan. Dengan demikian tumpukan baru kita akan terlihat seperti:

       -3
  0  0  0
  ^

(([()()()])(()))
          ^

Ini masuk akal; [...]tidak negasi jadi ]harus mengurangi ke bawah.

Sekarang kita harus menjalankan ). Seperti yang Anda ingat )adalah tempat di program di mana barang-barang didorong ke tumpukan sehingga kami akan memindahkan bagian atas tumpukan ketiga ke tumpukan saat ini, di samping itu kami akan menambahkan elemen -3ke berikutnya di tumpukan ketiga.

 -3  0 -3
  ^

(([()()()])(()))
           ^

Sekali lagi kami menemukan salah satu dari tiga kawat gigi terbuka kami sehingga kami akan menambahkan elemen lain ke tumpukan ketiga kami.

        0
 -3  0 -3
  ^

(([()()()])(()))
            ^

Seperti yang kami katakan sebelumnya ()akan menambah bagian atas tumpukan ketiga kami dengan satu.

        1
 -3  0 -3
  ^

(([()()()])(()))
              ^

Dan )akan memindahkan bagian atas Stack Ketiga ke tumpukan aktif dan tambahkan ke bawah

  1
 -3  0 -2
  ^

(([()()()])(()))
               ^

Yang terakhir )memindahkan Tumpukan Ketiga ke tumpukan aktif dan karena tidak ada elemen yang tersisa di Tumpukan Ketiga untuk ditambahkan, tidak melakukan hal lain.

 -2
  1
 -3  0
  ^

(([()()()])(()))
                ^

Program selesai sehingga kami mengakhiri dan mengeluarkan.

Contoh ini dimaksudkan untuk memberi Anda perasaan tentang apa Stack Ketiga itu dan apa yang dilakukannya. Itu tidak termasuk semua operasi, tetapi mudah-mudahan Anda dapat mengetahui apa yang masing-masing lakukan sendiri. Jika Anda masih berjuang, saya telah memasukkan "cheatsheet" di bagian bawah jawaban ini untuk membantu Anda.

Oke, lalu bagaimana?

Ok, sekarang Anda mengerti tumpukan ketiga, tapi "Jadi apa"? Anda sudah menggunakannya bahkan jika Anda tidak menyebutnya "Third Stack", bagaimana cara berpikir dalam Third Stack membantu Anda bermain golf?

Mari kita lihat suatu masalah. Anda ingin mengambil Segitiga angka . Ini adalah jumlah semua angka yang kurang dari n.

Salah satu pendekatan mungkin untuk membuat akumulator di offstack dan menambahkannya saat Anda menghitung mundur. Ini menciptakan kode yang terlihat seperti ini:

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

Cobalah secara Online!

Kode ini cukup kompak dan orang mungkin berpikir itu tidak bisa jauh lebih kecil. Namun jika kita mendekatinya dari sudut pandang tumpukan ketiga, menjadi jelas bahwa ini sangat tidak efisien. Alih-alih menempatkan akumulator kami di offstack, kita dapat meletakkannya di tumpukan ketiga dengan (dan mengambilnya di akhir yang kita gunakan ). Kami akan sekali lagi mengulang-ulang semua angka, tetapi kali ini kami tidak perlu melakukan banyak hal untuk meningkatkan Stack Ketiga kami, program melakukannya untuk kami. Ini terlihat seperti:

({()({}[()])}{})

Cobalah secara Online

Kode ini kurang dari setengah ukuran dari versi golf yang kami buat sebelumnya. Bahkan pencarian komputer telah membuktikan bahwa program ini adalah program sesingkat mungkin yang dapat melakukan tugas ini. Program ini dapat dijelaskan dengan menggunakan pendekatan "jumlah semua berjalan", tetapi saya pikir itu jauh lebih intuitif dan jelas ketika dijelaskan menggunakan pendekatan Third Stack.

Kapan saya menggunakan tumpukan ketiga?

Idealnya setiap kali Anda mulai mengerjakan masalah baru di Brain-Flak, Anda harus berpikir sendiri bagaimana saya melakukan ini dengan tumpukan ketiga. Namun sebagai aturan umum setiap kali Anda harus melacak beberapa jenis akumulator atau memiliki total berjalan itu adalah ide yang baik untuk mencoba meletakkan itu di tumpukan ketiga Anda, bukan dua tumpukan nyata.

Waktu lain yang mungkin merupakan ide bagus untuk mempertimbangkan menggunakan tumpukan ketiga adalah ketika Anda tidak memiliki ruang untuk menyimpan nilai pada dua tumpukan lainnya. Ini bisa sangat berguna ketika Anda melakukan manipulasi pada dua tumpukan yang ada dan Anda ingin menyimpan nilai untuk digunakan nanti tanpa harus melacak di mana tumpukan itu.

Keterbatasan tumpukan ketiga

Third Stack sangat kuat dalam banyak hal tetapi ia datang dengan keterbatasan dan kekurangannya sendiri.

Pertama, tinggi tumpukan maksimum untuk Tumpukan Ketiga pada titik tertentu ditentukan pada waktu kompilasi. Ini berarti bahwa jika Anda ingin menggunakan sejumlah ruang pada tumpukan Anda harus mengalokasikan ruang itu ketika Anda menulis program.

Kedua Stack Ketiga bukan Akses Acak. Ini berarti Anda tidak dapat melakukan operasi apa pun pada nilai apa pun selain nilai tertinggi. Selain itu, Anda tidak dapat memindahkan nilai di tumpukan (katakan, tukar dua elemen pertama).

Kesimpulan

Tumpukan Ketiga adalah alat yang ampuh dan saya akan menganggapnya penting bagi setiap pengguna Brain-Flak. Dibutuhkan beberapa waktu untuk membiasakan diri dan membutuhkan perubahan dalam cara Anda berpikir tentang pemrograman di Brain-Flak, tetapi ketika digunakan dengan benar itu membuat semua perbedaan antara yang layak dan luar biasa ketika datang ke golf.

Contekan

Berikut adalah daftar operasi dan bagaimana mereka mempengaruhi Tumpukan Ketiga

 Operation  |                 Action
====================================================
   (,[,<    | Put a zero on top of the Third Stack
----------------------------------------------------
     )      | Add the top of the Third Stack to the
            | second element and move it to the 
            | active stack
----------------------------------------------------
     ]      | Subtract the top of the Third Stack
            | from the second element and pop it
----------------------------------------------------
     >      | Pop the top of the Third Stack
----------------------------------------------------
     ()     | Add one to the top of the Third Stack
----------------------------------------------------
     {}     | Pop the top of the active stack and
            | add it to the top of the Third Stack
----------------------------------------------------
     []     | Add the stack height to the Third
            | Stack
----------------------------------------------------
   <>,{,}   | Nothing

Menemukan modulus / sisanya

Menemukan n modulo m adalah salah satu operasi aritmatika dasar, penting bagi banyak tantangan. Untuk kasus m> 0 dan n> = 0 , potongan 46 byte berikut dapat digunakan. Diasumsikan bahwa n ada di atas tumpukan aktif dengan m yang berikutnya turun, dan menggantinya dengan n mod m . Itu meninggalkan sisa tumpukan.

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

Versi beranotasi ini menunjukkan konten tumpukan di beberapa titik dalam program. ;memisahkan kedua tumpukan dan .menandai tumpukan yang aktif.

. n m;
({}(<>))<>
{   . m; r 0   (r = n - km)
    (({}))
    . m m; r 0
    {({}[()])<>}
    {}
}
m-n%m-1 m; . 0
{}<>([{}()]{})
. n%m;

Redundansi Push-Pop

Ini yang besar. Ini juga sedikit yang bernuansa.

Idenya adalah bahwa jika Anda mendorong sesuatu dan membuangnya tanpa melakukan apa pun, Anda seharusnya tidak mendorongnya sama sekali.

Misalnya, jika Anda ingin memindahkan sesuatu ke offstack dan kemudian menambahkannya, Anda dapat menulis kode berikut:

({}<>)({}())

Ini bisa lebih sederhana seperti ini:

({}<>())

Program pertama mengambil item memindahkannya, mengambilnya lagi dan menambahkan satu, sedangkan yang kedua melakukan keduanya sekaligus.

Contoh itu sederhana namun bisa menjadi jauh lebih kompleks. Ambil contoh:

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

Pengurangannya kurang jelas di sini tetapi pop ke-4 dalam program dapat dikurangi dengan push ke-2, seperti:

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

Ini adalah alat yang paling ampuh dalam repertoar golf saya, tetapi perlu latihan untuk menjadi ahli. Setelah Anda melakukan ini selama beberapa saat, Anda akan dapat melihatnya secara instan.

Optimalkan bilangan bulat Anda

Bilangan bulat membosankan untuk diwakili dalam Brain-Flak. Untungnya kami memiliki pertanyaan yang akan membantu Golf Integer Otak-Flak untuk Anda. (Perhatikan bahwa pertanyaan ini dirancang untuk mendorong bilangan bulat ke tumpukan, jadi redundansi push-pop mungkin berlaku untuk program yang lebih realistis.)

Dorong counter loop ekstra

Seringkali, Anda ingin melakukan sesuatu seperti

Lakukan operasi X pada setiap elemen dalam stack

atau

Lakukan operasi X pada setiap pasangan elemen yang berdekatan dalam tumpukan

Ketika input mungkin mengandung '0's, atau hasil operasi X dapat memberikan 0, ini benar-benar merepotkan. Karena Anda harus melakukan:

([])
{

  {}

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

}

Melakukan X untuk setiap elemen, lalu nanti

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

Untuk membalikkan array lagi.

Lebih buruk lagi, jika kita operatiing pada pasangan elemen yang berdekatan, kita harus melakukan ([][()])di tempat ([]). Ini sangat merepotkan. Begini caranya: Saat Anda melakukan X untuk setiap elemen, dorong 1 ke tumpukan alternatif tepat di atas X(element). Kemudian, saat Anda membalikkannya, Anda bisa melakukannya

<>
{
  {}
  ({}<>)
  <>
}
<>

Ini lebih pendek 8 byte, jadi ketika Anda memasukkan kode tambahan ke push 1, Anda akhirnya akan menghemat 4-6 byte. Untuk contoh yang lebih konkret, bandingkan tugas mendapatkan delta dari array. Tanpa trik ini, Anda perlu:

([][()]){

    {}

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

    ([][()])

}{}{}<>

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

Untuk 62. Dengan trik ini, Anda harus

([][()]){

    {}

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

    ([][()])

}{}{}<>

{{}({}<>)<>}<>

Untuk 58. Jika menggunakan cara yang benar (misalnya, membalikkan terlebih dahulu, dan menghapus dua ([][()])dari nanti), ini bisa menyimpan lebih banyak lagi dalam skenario spefik.

Manfaatkan nilad 'Stack-Height'

Terutama dalam tantangan kolmogorov-kompleksitas , atau tantangan di mana Anda selalu tahu ukuran input, Anda dapat mengambil keuntungan dari nilad 'Stack-Height'[] untuk membuat bilangan bulat.

Mari kita selesaikan ini dengan tantangan hipotetis: keluaran CAT. Cara non-golf adalah menggunakan pegolf integer online untuk mendorong 67, 65, dan 84. Ini memberi:

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

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

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

(Baris baru untuk kejelasan). Ini adalah 88 byte, dan tidak terlalu bagus. Jika kita sebagai gantinya mendorong perbedaan berurutan antara nilai, kita dapat menyimpan banyak. Jadi kami membungkus nomor pertama dalam panggilan push , dan kurangi 2:

(   (((((()()()()){}){}){}()){}())  [()()] )

Kemudian, kami mengambil kode ini, membungkusnya dalam panggilan push , dan menambahkan 19 sampai akhir:

(  ((((((()()()()){}){}){}()){}())[()()])   ((((()()()){})){}{}()) )

Ini adalah 62 byte, untuk golf 26 byte kekalahan!

Sekarang di sinilah kita mengambil keuntungan dari nilad tumpukan-tinggi. Pada saat kita mulai mendorong 19, kita tahu bahwa sudah ada 2 item di stack, jadi []akan dievaluasi 2. Kita dapat menggunakan ini untuk membuat 19 byte lebih sedikit. Cara yang jelas adalah untuk mengubah batin ()()()untuk ()[]. Ini hanya menghemat dua byte. Dengan beberapa mengutak-atik, ternyata kita bisa mendorong dengan

((([][]){})[]{})

Ini menghemat 6 byte. Sekarang kita turun ke 56.

Anda dapat melihat tip ini digunakan dengan sangat efektif pada jawaban ini:

• Halo Dunia V1

• Hello World V2

• Magic The Gathering, Friend atau Foe

• Keluarkan Integer yang Hilang

• Alfabet Diagonal (favorit pribadi saya)

Gunakan wiki

Kami punya wiki ! Ini memiliki beberapa kedatangan pendek, tetapi ini adalah sumber yang bermanfaat. Ini memiliki daftar berguna, golf dengan baik, tumpukan program bersih yang dapat Anda tempelkan ke kode Anda. Jika Anda ingin melakukan sesuatu yang Anda pikir telah dilakukan seseorang sebelum ada kemungkinan itu ada di wiki.

Perulangan yang lebih baik

Ini yang mudah:

Konstruk yang cukup umum adalah:

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

Di mana Anda ingin mengulang n kali tetapi tetap menyimpan n. Namun ini dapat ditulis sebagai:

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

untuk menyimpan 2 byte.

Paradigma lain yang cukup umum adalah

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

Yang akan mengulang dan menumpuk seluruh tumpukan. Karena beberapa matematika mewah ini sama dengan:

(([]){[{}]...([])}{})

Periksa negatif Anda

Terkadang Anda dapat bermain golf beberapa byte dengan memilih secara strategis apa yang dinegasikan dengan [...]monad.

Contoh sederhana ada di [...]s bersarang . Misalnya [()()()[()()]]saja bisa[()()()]()()

Katakanlah Anda ingin memeriksa apakah suatu nilai adalah salah satu tanda kurung awal (<{[. Upaya awal adalah untuk mendorong perbedaan antara masing-masing karakter dan mengulangi pengurangan itu

({}<(((((       #Push the differences between start bracket characters
(((()()()()){}){}){})   #Push 32
[()])                   #Push 31
[((()()())()){}{}])     #Push 20
){})><>)                #Push 40
<>({<(([{}]<>{}))>(){[()](<{}>)}<>})

Namun, Anda dapat menyimpan 4bytes dengan mendorong versi negatif dari perbedaan!

({}<(((((       #Push the differences between start bracket characters
((([()()()()]){}){}){}) #Push -32
())                     #Push -31
((()()())()){}{})       #Push -20
){})><>)                #Push -40
<>({<(({}<>{}))>(){[()](<{}>)}<>})

Secara umum, ini tidak menghemat banyak, tetapi juga membutuhkan sedikit usaha untuk mengubah sekitar apa yang [...]ada di sekitarnya. Waspadai situasi di mana Anda dapat mendorong negatif dari penghitung, bukan positif untuk menghemat peningkatan beberapa kali, bukannya mengurangi nanti. Atau bertukar (a[b])dengan ([a]b)untuk membuat perbedaan antara dua angka negatif daripada positif.