The Collatz urut mulai dari bilangan bulat positif n didefinisikan dengan cara ini:
- jika n bahkan maka membaginya dengan 2 (
n' = n / 2
) - jika n ganjil maka kalikan dengan 3 dan tambahkan 1 (
n' = 3n + 1
)
Ulangi iterasi di atas hingga n mencapai 1.
Tidak diketahui (ini adalah masalah utama yang belum terpecahkan dalam teori bilangan) jika urutan akhirnya akan mencapai nomor 1, terlepas dari bilangan bulat positif yang dipilih pada awalnya.
Sebuah Dua Kontra Machine (2cm) adalah mesin dilengkapi dengan dua register yang dapat menyimpan nilai integer non-negatif dan dapat diprogram dengan set instruksi berikut:
INCX increase the value of register X
INCY increase the value of register Y
JMP n jump to instruction n
DJZX n if register X is zero jump to instruction n,
otherwise decrement its value
DJZY n if register Y is zero jump to instruction n,
otherwise decrement its value
HALT halt (and accept)
PRINTX print the content of register X
Program 2CM hanyalah urutan instruksi, misalnya program berikut hanya menyalin isi register X untuk mendaftar Y:
cp: DJZX end
INCY
JMP cp
end: HALT
Perhatikan bahwa 2CM adalah Turing Lengkap (yaitu dapat menghitung setiap fungsi yang dapat dihitung dengan pengkodean input yang sesuai, tetapi tidak relevan di sini). Perhatikan juga bahwa set instruksi sedikit berbeda dari yang ada di artikel Wikipedia.
Tantangan
Tulis program 2CM terpendek, yang menghitung dan mencetak urutan collatz hingga 1 dan berhenti (register X awalnya berisi nilai awal n
dan register Y awalnya berisi 0). Perhatikan bahwa panjang program 2CM adalah jumlah instruksi yang digunakan (bukan panjang teks).
Misalnya, ketika mulai dari X = 3 harus dicetak: 3 10 5 16 8 4 2 1
dan HALT.
Jadi Anda dapat menggunakan bahasa favorit Anda untuk membangun simulator / juru bahasa 2CM, tetapi kode akhir (terpendek) yang Anda masukkan dalam jawaban harus dalam bahasa 2CM .
sumber
Jawaban:
18 instruksi
Saya agak kecewa bahwa saya datang terlambat ke tempat kejadian, karena sifat minimalis dari masalah dan bahasa yang ada (tampaknya) hanya satu pendekatan umum untuk jawaban yang baik. Saya mendapat jawaban 19 instruksi dengan cukup cepat, tetapi saya merasa tidak cukup dibawa ke meja untuk mempostingnya. Tapi setelah banyak yang menggaruk-garuk kepala, pengalaman perakitan z80 yang kadaluwarsa datang dan saya menemukan cara untuk menyimpan instruksi dengan menggunakan kembali satu blok kode untuk tujuan yang tidak dimaksudkan!
sumber
SCORE: 21
Ini usaha saya:
main
: cetakanX
dan melompat kefinish
(jikaX==1
).divisibility
: membuat perbedaan jikaX%2==0
atauX%2==1
. Juga salinanX
keY
dan merekX==0
. Melompat ke salahisDivisible
(jikaX%2==0
) atauisNotDivisible
(jikaX%2==1
).isDivisible
: loop digunakan saatY%2==0
. Untuk setiap penurunanY
sebesar 2, itu meningkatX
sebesar 1. SaatY==0
, melompat kemain
.isNotDivisible
: digunakan saatY%2==1
. Ini meningkatX
sebesar 1.notDivLoop
: loop digunakan saatY%2==1
. Untuk setiap penurunanY
sebesar 1, itu meningkatX
sebesar 3. SaatY==0
, melompat kemain
.finish
: berhentiDisertakan dengan 3 (menggunakan juru bahasa yang disediakan oleh @orlp), hasil yang dihasilkan adalah:
sumber
19 instruksi
Saya menulis juru bahasa saya sendiri karena saya suka itu. Ini solusi saya untuk juru bahasa saya sendiri:
Dan inilah tampilannya dengan sintaks yang kompatibel dengan juru bahasa lain:
sumber
19 instruksi
Anda dapat menjalankannya menggunakan juru bahasa saya .
sumber