Stackylogic adalah bahasa pemrograman yang saya buat dalam tantangan sebelumnya: Jalankan Stackylogic . Baca posting itu untuk detail dan contoh lengkap, tetapi di sini adalah cara kerjanya diparafrasekan:

Stackylogic mengambil 0dan 1untuk input dan output tunggal 0 atau 1setelah selesai.

Suatu program terdiri dari baris-baris yang hanya berisi karakter-karakter 01?serta tepat satu <di akhir salah satu baris. Garis tidak boleh kosong dan garis dengan <harus memiliki minimal satu 0, 1atau ?sebelum.

Berikut adalah contoh program yang menghitung NAND dari dua bit:

1
?<
11
?
0

Setiap baris dalam program dianggap sebagai tumpukan , dengan bagian bawah di sebelah kiri dan bagian atas di sebelah kanan. Secara implisit, ada tumpukan kosong (yaitu baris kosong) sebelum baris pertama dalam suatu program dan setelah baris terakhir.

The <, disebut kursor, menandai tumpukan untuk memulai ketika suatu program dijalankan. Eksekusi berlangsung sebagai berikut:

1. Lepaskan karakter teratas dari tumpukan yang saat ini ditunjuk kursor.

   • Jika karakternya adalah ?, minta pengguna untuk 0atau a 1dan bertindak seolah-olah itu adalah karakter.
   • Jika karakternya adalah 0, pindahkan kursor satu tumpukan ke atas (ke garis di atas garis saat ini).
   • Jika karakternya adalah 1, pindahkan kursor satu tumpukan ke bawah (ke garis di bawah garis saat ini).

2. Jika tumpukan kursor bergerak kosong, output nilai terakhir yang muncul dari tumpukan (selalu a 0atau 1), dan akhiri program.

3. Lain, jika tumpukan kursor bergerak ke tidak kosong, kembali ke langkah 1 dan ulangi prosesnya.

Hal utama yang harus disadari untuk tantangan ini adalah bahwa semua program Stackylogic sama dengan tabel kebenaran . Beberapa nilai boolean yang telah ditentukan adalah input dan tepat satu boolean adalah output yang ditentukan.

Jadi tugas Anda adalah menghasilkan program Stackylogic yang memuaskan atau disimulasikan, yaitu memiliki output yang sama dengan tabel kebenaran yang diberikan. Tetapi tidak jelas bahwa Stackylogic dapat mensimulasikan tabel kebenaran apa pun, jadi inilah buktinya dengan induksi :

Kasus Dasar

Dua tabel kebenaran 0-input adalah tabel yang selalu menampilkan 0atau 1. Setara dengan Stackylogic dari tabel ini adalah 0<dan 1< masing - masing.

Langkah Induktif

Asumsikan Stackylogic dapat mensimulasikan tabel kebenaran input-N. Misalkan M = N + 1.

Tabel input-M, T, dapat dinyatakan sebagai dua tabel input-N, T ₀ dan T ₁ , ditambah bit input tambahan B. Ketika B adalah 0, hasil dari T ₀ digunakan. Ketika B adalah 1, hasil T ₁ digunakan.

Misalnya, tabel kebenaran 3-input yang sesuai dengan pseudocode

if B:
    result = x OR y
else:
    result = x NAND y

adalah

B x y | result
0 0 0 | 1
0 0 1 | 1
0 1 0 | 1
0 1 1 | 0
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

yang benar-benar dua tabel kebenaran 2-input untuk NAND dan OR ditumpuk di atas satu sama lain dengan bit B. muxing

Misalkan S ₀ dan S ₁ menjadi program Stackylogic yang memenuhi masing-masing T ₀ dan T ₁ (kita tahu ini ada berdasarkan asumsi pertama). Program S yang memenuhi T kemudian dapat dibangun sebagai:

[lines of S0 excluding the cursor, with 0 appended to all lines below the cursor]
?<
[lines of S1 excluding the cursor, with 1 appended to all lines above the cursor]

Pengaturan ini secara efektif mux antara S ₀ dan S ₁ berdasarkan bit input pertama (dari jalur ?<). Jika ya 0, kursor akan naik yang ditambahkan 0ke posisi kursor asli S ₀ , yang kemudian akan dibatasi atas dan bawah oleh tumpukan kosong, dan dengan demikian berjalan persis identik dengan S _{0 asli} . Demikian juga, jika 1input, kursor akan naik 1turun ke posisi kursor S ₁ dan melanjutkan untuk mengeksekusi seolah-olah itu sendirian.

Sebagai contoh, program Stackylogic untuk OR dan NAND adalah

?
?<

dan

1
?<
11
?
0

Mereka dapat digabungkan untuk disimulasikan

if B:
    result = x OR y
else:
    result = x NAND y

seperti itu:

1
?
110
?0
00
0
?<
?1
?

Dengan demikian, tabel kebenaran apa pun dapat disimulasikan oleh program Stackylogic.

Tantangan

Tulis program atau fungsi yang mengambil dalam tabel kebenaran input N (N> 0) dalam bentuk daftar 2 nilai boolean ^N yang mewakili output tabel dalam urutan biner naik.

Format input yang masuk akal tidak masalah. misalnya untuk tabel kebenaran ATAU

x y | OR
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

salah satu dari gaya input ini akan baik-baik saja:

0111

0, 1, 1, 1

0
1
1
1

[False, True, True, True]

Cetak atau kembalikan program Stackylogic yang memenuhi tabel kebenaran, yaitu memiliki output yang sama persis dengan input yang sama. Setiap program hingga yang memenuhi tabel itu adalah output yang valid. Anda tidak perlu mengikuti metode konstruksi bukti induktif. Program Stackylogic tidak perlu pendek secara optimal.

Misalnya, jika inputnya adalah 11100111, satu output yang valid adalah

1
?
110
?0
00
0
?<
?1
?

tetapi ada banyak lainnya.

Kode terpendek dalam byte menang.

Lihat tantangan Stackylogic asli jika Anda membutuhkan juru bahasa.

Pyth, 53 byte

L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<

Coba online

Ini adalah implementasi tepat dari sistem yang dijelaskan dalam tantangan untuk bagaimana menerapkan tabel kebenaran arbitrer dalam Stackylogic. Kami cukup memotong tabel kebenaran menjadi dua, menerapkannya secara rekursif, dan kemudian menambahkan 0 dan 1 yang sesuai.

Ini mendefinisikan fungsi rekursif, yang nilai [1, ['0', '?', '1']]baliknya adalah , di mana angka pertama adalah lokasi pointer, dan sisanya adalah program stackylogic.

L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<
                                                         Q = eval(input())
L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hb
L                                                 def y(b): return
 ?tb                                              if b[1:] (base case on false)
                                      ,0]`hb      else: [0, str([0])]
                                                  then:
           c2b                                    Cut the input in half
         yM                                       Map y over the halves
        J                                         Store that in J
    ,leh                                          The cursor position is the length 
                                                  of the body of the first function
                 .e                 J             enum-map, where k is the index
                                                  and b is the value, over J
                   .e             eb              enum-map, Y is the index and
                                                  Z is the value, over body of b
                     +W         Zk                Add to Z (line) k (the overall 
                                                  index, 0 or 1) conditional on
                          -Yhb                    Y (line index) - cursor
                       _Wk                        Negated if k
                      >       0                   > 0
               X0                    \?           Add '?' to the first element
              s                                   Concatenate, giving the body

jXF+yQ\<
    yQ      Call the above on the input
   +  \<    Append a '<'
 XF         Splat the 3 element list into the 'append-at' function,
            adding the curson in the right place
j           Join on newlines and print.

Python 3, 352 208 205 byte

Ini masih sangat ungolfed, dan saya akan mencoba menambahkan penjelasan nanti. Setelah beberapa modifikasi, saya berhasil menghapus 144 147 byte.

f=lambda x,l=len,r=range:'\n'.join(*x)if l(x)<2 else f([[x[i][j]+['0',''][j<=l(x[i])//2]for j in r(l(x[i]))]+[['?','?<'][l(x)<3]]+[x[i+1][j]+['1',''][j>=l(x[i])//2]for j in r(l(x[i]))]for i in r(0,l(x),2)])

Sebuah fungsi fyang mengambil input dari nilai tabel kebenaran sebagai daftar Boolean dari formulir ['1','1','1','0','0','1'...], di mana '1'benar dan '0'salah, dan mengembalikan program Stackylogic.

Cobalah di Ideone

Jika Anda ingin menguji program yang dihasilkan, Anda dapat menggunakan juru bahasa GamrCorps di sini .

Bagaimana itu bekerja

Ini adalah fungsi rekursif dan menggunakan metode induktif yang dijelaskan dalam pertanyaan.

Pada level rekursi yang diindeks nol a, fungsi menciptakan n/2 a+1-input program Stackylogic dari n aprogram -input dalam daftar. Ini dilakukan dengan menggabungkan semua pasangan yang berdekatan dari dua program dalam daftar dengan ?; karena kursor selalu berada di elemen tengah dari setiap program konstituen, diperlukan penambahan 0atau1 dapat dilakukan dengan mengulangi setiap baris dari program yang bergabung, dan menambahkan jika indeks dari baris saat ini kurang dari atau sama dengan / lebih besar / lebih besar dari atau sama dengan indeks tengah yang sesuai. Jika daftar hanya berisi dua program, panggilan rekursif berikutnya akan memberikan program akhir; karena ini membutuhkan kursor, bergabung bukan terjadi pada ?<.

Ketika daftar memiliki panjang 1 , daftar harus berisi hanya satu elemen yang berisi program lengkap. Oleh karena itu, semua baris dalam program digabungkan pada baris baru, dan kemudian dikembalikan.

Contoh membantu untuk menggambarkan ini:

Take the input ['1', '1', '1', '0', '0', '1', '1', '1'].

Level  Return value

0  [['1', '?', '1'], ['1', '?', '0'], ['0', '?', '1'], ['1', '?', '1']]
1  [['1', '?', '10', '?', '11', '?', '0'], ['0', '?', '10', '?', '11', '?', '1']]
2  [['1', '?', '10', '?', '110', '?0', '00', '?<', '01', '?1', '101', '?', '11', '?', '1']]
3  '1\n?\n10\n?\n110\n?0\n00\n?<\n01\n?1\n101\n?\n11\n?\n1'

which when printed gives:

1
?
10
?
110
?0
00
?<
01
?1
101
?
11
?
1