Ini kecelakaan yang lucu bahwa dunia ini kebetulan hanya memiliki 1 dimensi waktu, tetapi tidak harus seperti itu. Sangat mudah untuk membayangkan dunia dengan dimensi waktu 2 atau lebih, dan di dunia itu Anda dapat membangun komputer dan menjalankan perangkat lunak pada mereka, seperti di dunia ini.
Sistem
Berikut adalah sistem untuk menjalankan program Brainf * ck dalam dua dimensi waktu:
Dua dimensi waktu adalah x dan y. Setiap program Brainf * ck terdiri dari x setengah program, dan setengah program, misalnya, sebuah program bisa
x: +>+
y: [-]
Kedua program setengah masing-masing memiliki pointer program mereka sendiri, tetapi mereka berbagi satu tape pointer (yaitu, keduanya beroperasi pada sel yang sama dari rekaman itu).
Waktu adalah 2 dimensi, jadi terdiri dari kisi momen:
Bergerak sepanjang dimensi x, program setengah x mengeksekusi satu langkah waktu. Bergerak sepanjang dimensi y, program setengah y mengeksekusi satu langkah waktu.
Jadi, misalnya, katakanlah rekaman itu dimulai sebagai [0] 0 0( []mewakili penunjuk kaset) dan program x / y adalah +dan ->-. Eksekusi program ini akan terlihat seperti ini:
x y tape x-action y-action
0 0 [ 0] 0 0 + at 0 - at 0
1 0 [ 1] 0 0 (done) - at 0
0 1 [-1] 0 0 + at 0 move >
1 1 [ 0] 0 0 (done) move >
Perhatikan bahwa, seiring berjalannya waktu ke arah y, program setengah x terus melakukan hal yang sama berulang kali, karena waktunya tidak berkembang.
Rekaman pada setiap saat termasuk efek kumulatif dari semua tindakan yang dimasukkan ke dalamnya (setiap tindakan dihitung sekali). Jadi, misalnya, rekaman pada waktu (2, 1) berisi efek kumulatif dari:
- x-action from (0, 0)
- x-action from (1, 0)
- x-action from (0, 1)
- x-action from (1, 1)
- aksi-y dari (0, 0)
- aksi-y dari (1, 0)
- aksi-y dari (2, 0)
Kumulatif berarti:
- Semua kenaikan dan penurunan jumlah sel bersama-sama.
- Semua gerakan kiri (-1) dan kanan (+1) ke jumlah penunjuk kaset bersama-sama.
Petunjuk petunjuk tidak terakumulasi. Setiap setengah program mendapatkan penunjuk instruksinya dari momen sebelumnya dalam dimensinya. Yaitu, progres program x hanya berkembang dalam dimensi x, dan progres program x hanya berjalan dalam dimensi y. Jadi, misalnya, dalam program ( [], +) mulai dari [0] 0 0, eksekusi akan dilakukan
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 0 0 0 + at 0 0 0
1 0 0 0 0 + at 0 2 (from jump) 0
0 1 1 0 0 0 1
1 1 2 0 0 1 (from NO jump) 1
Beberapa momen lagi dari simulasi di atas ( +, ->-) adalah:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
2 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 > 0 1
1 1 [ 0] 0 0 > 1 1
2 1 [-1] 0 0 > 1 1
0 2 -1 [ 0] 0 + at 1 - at 1 0 2
1 2 0 1 [ 0] - at 2 1 2
2 2 [-1] 1 0 - at 0 1 2
Operator Brainf * ck diizinkan adalah sebagai berikut (mereka memiliki arti standar):
+,-: increment, decrement;[,]: loop sampai nol (memproses a[atau]mengambil satu langkah waktu, seperti pada Brainf * ck standar);<,>: bergerak ke kiri / kanan pada kaset.
Contoh Kompleks
Untuk program ( >, +) dimulai dengan [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > + at 0 0 0
1 0 0 [ 0] 0 + at 1 1 0
0 1 [ 1] 0 0 > 0 1
1 1 1 1 [ 0] 1 1
Untuk ( +, -) dimulai dengan [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 0 1
1 1 [ 0] 0 0 1 1
Perhatikan bahwa rekaman itu berakhir [0] 0 0karena masing +- masing dan -terjadi dua kali, jumlah ke 0.
Untuk program ( >+, [-]) dimulai dengan [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > 0 0
1 0 0 [ 0] 0 + at 1 1 0
2 0 0 [ 1] 0 2 0
0 1 [ 0] 0 0 > 0 3
1 1 0 0 [ 0] + at 2 1 3
2 1 0 1 [ 1] - at 2 2 1
0 2 [ 0] 0 0 > 0 3
1 2 [ 0] 0 0 + at 0 1 3
2 2 [ 1] 1 0 2 2
Diagram dengan Panah
Diagram di bawah ini menunjukkan cara menghitung tindakan dan rekaman:
Teka-teki
Tulis program 2D Brainf * ck (dengan program setengah x dan setengah program) untuk dijalankan pada pita 3-sel, yang memenuhi kedua kondisi berikut:
- Jika pita dimulai sebagai
[0] 0 0, pada waktu (5, 5) ia memiliki0dalam sel nol. - Jika pita dimulai sebagai
[1] 0 0, pada waktu (5, 5) ia memiliki0dalam sel nol.
Program terpendek yang memenuhi persyaratan menang.
+dan>? Jika itu1 1 [0](cukup gila tapi sepertinya apa yang disarankan oleh spec), Bagaimana cara menggabungkan instruksi? Jika dua utas adalah+dan[], maka pada1 2rekaman data akan[3], tetapi apakah penunjuk instruksi kedua di dalam loop ([]+path), atau di luar ([+]path) atau bahkan ilegal (+[])?+,>) untuk melihat apakah saya mendapatkan hasil yang sama seperti Anda.(1,1)salah satu(1,0)atau(0,1), tetapi satu program dimulai>dan satu dimulai+, maka tentu urutan relatif mereka penting?Jawaban:
Total 4 byte: (
[-],>)Saya menulis brute-forcer untuk menemukan program terkecil seperti itu.
Berikut adalah diagram dari program ini yang sedang beraksi. Kisi-kisi ini disusun dengan cara yang mirip dengan kisi dalam spesifikasi, dengan (0,0) sudut kiri bawah, x-waktu sepanjang sumbu x, dan waktu-y sepanjang sumbu y. Pojok kanan atas berisi hasilnya.
Pertama, dengan rekaman
0 0 0:Sekarang dengan rekaman
1 0 0:Ada beberapa hal yang tidak dijelaskan secara jelas dalam spesifikasi, seperti fakta bahwa pita 3-sel membungkus.
Sebagai bonus, berikut adalah visualisasi dari (
>+,[-]):Dan salah satu (
>+,+>):Perhatikan bahwa sudut kanan atas berbeda dari yang Anda daftarkan, saya pikir ini adalah kesalahan dalam contoh Anda karena kode saya cocok dengan setiap contoh lain yang saya coba.
sumber