Input : Baik satu atau dua string '0's dan' 1's. Jika ada 2, mereka dipisahkan oleh spasi. Semua string memiliki panjang minimal 1.
Output : Jika satu string adalah input, 2 adalah output. Jika 2 adalah input, 1 adalah output. String keluaran dapat berupa apa pun yang Anda suka, tetapi jika menjalankan program Anda dengan input A memberi Anda B, maka menjalankannya dengan B harus memberikan A (jika memasukkan 111 11
memberi 00000
, maka memasukkan 00000
harus memberi 111 11
).
Itu berarti jika Anda mem-pipe program Anda sendiri, Anda harus mendapatkan kembali apa pun yang Anda input. Jika program Anda disebut foo, Anda dapat mengujinya seperti ini:
>echo 101 101|foo|foo
101 101
Untuk mencegah penggunaan teknik brute force, kode Anda harus dapat dijalankan dengan string 1000 digit dalam waktu kurang dari 10 detik. Solusi python saya untuk ini membutuhkan waktu kurang dari 1 detik pada 10.000 digit string jadi ini seharusnya tidak menjadi masalah.
Kode terpendek menang.
sumber
if x not in d:
denganif(x in d)-1:
dan menyimpan satu byte.Python, 326
Contoh input / output:
sumber
Perl 5, 197 karakter
Dengan beberapa jeda baris:
Program ini beroperasi dengan menyusun dua bijections:
Sepasang bilangan alami dapat dipetakan ke string biner dengan mengonversikan satu ke basis-2 dan yang lainnya menjadi nol yang mengarah ke luar.
n
adalah fungsi ini danN
kebalikannya (kecuali yangN
menggunakan$_
parameternya).Sepasang bilangan natural dapat dipetakan ke bilangan alami tunggal menggunakan fungsi pemasangan Cantor . Pertama
map
's blok fungsi ini dan yang kedua adalah kebalikannya.Jadi dua string biner dibagi menjadi empat angka, digabungkan menjadi dua angka, dan kemudian digabungkan menjadi satu string biner - atau sebaliknya.
Diuji pada 100 input acak dari setiap jenis dengan panjang hingga 8 simbol. Saya telah menemukan banyak cara untuk membuat ini sedikit lebih pendek, tetapi saya akan berhenti dan mempostingnya. Jika ada ruang untuk dioptimalkan lebih lanjut, itu mungkin dalam ekspresi aritmatika.
sumber
1111111111111111111111111111111111111111111111111111111111111111
(641
s) tampaknya macet, dan input dari pasangan0
dan 501
detik memberikan hasil yang sama dengan0
dan 511
detik, keduanya output 641
detik. Saya pikir ada semacam overflow dengan jumlah0
s terkemuka , jadi solusinya mungkin untuk mendapatkan nilai outputN
dari pasangan CantorN
nilai input , dann
nilai dari pasangann
nilai (atau sebaliknya untuk invers). Saya seorang perl noob, jadi saya mungkin telah melakukan sesuatu yang salah.Perl, 56 karakter
menambahkan +1 char untuk
-p
saklar baris perintahsumber
Python, 394
Saya yakin ini bisa di-golf lebih lanjut, tetapi monolith ini menggunakan Fungsi Penyandingan Cantor dan kebalikannya.
Penjelasan
Ada hubungan alami antara string biner dan sepasang bilangan alami: angka pertama dari gambar adalah jumlah nol di depan, dan yang kedua adalah nilai integer dari angka biner. Mengetahui bahwa kita memiliki:
S ~ N^2
dan dengan bijih Cantor
N ~ N^2
karena itu:
S ~ N^2 ~ N^4 ~ S^2
S ~ S^2
Di mana S diatur dari semua string biner. Solusi ini mengimplementasikan bijection antara S dan S ^ 2.
sumber