Bijion antara string biner dan pasangannya

8

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 11memberi 00000, maka memasukkan 00000harus 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.

kotak kardus
sumber

Jawaban:

3

Python, 183

Bijection di-cache di disk.

x=raw_input()
try:d=eval(open('d').read())
except:d={'':'','1 ':'1 '}
t='1 '*not' 'in x
if x not in d:
 while t in d:t+=`(id(t)/9)%2`
 d[t]=x;d[x]=t
 open(*'dw').write(`d`)
print d[x]

sunting: Ups, sepertinya ini bukan jawaban yang digasak. Tambang saya konsisten di antara run!

stan
sumber
Anda dapat mengganti if x not in d:dengan if(x in d)-1:dan menyimpan satu byte.
Jonathan Frech
2

Python, 326

s=lambda i,l:bin(i)[2:].zfill(l)
f=lambda n:2**n*(n-3)+4
g=lambda n:2**n-2
i=raw_input()
if' 'in i:
 a,b=i.split();n=len(a+b);r=f(n)+int(a+b,2)*(n-1)+len(a)-1;l=1
 while g(l+1)<=r:l+=1
 print s(r-g(l),l)
else:
 n=len(i);r=g(n)+int(i,2);l=2
 while f(l+1)<=r:l+=1
 r-=f(l);p=r%(l-1)+1;w=s(r/(l-1),l);print w[:p],w[p:]

Contoh input / output:

     input | output
-----------+-----------
         0 | 0 0
       0 0 | 0
     10 10 | 10101
     10101 | 10 10
0000000000 | 101 0100
  101 0100 | 0000000000
kotak kardus
sumber
2

Perl 5, 197 karakter

sub n{'0'x$_[0].sprintf'%b',$_[1]}sub N{/0*(?=.)/;length$&,oct"0b$'"}$_=<>;print/ /?n map{($a,$b)=N;($a+$b)*($a+$b+1)/2+$b}split:"@{[map{$w=int((sqrt(8*$_+1)-1)/2);$y=$_-($w*$w+$w)/2;n$w-$y,$y}N]}"

Dengan beberapa jeda baris:

sub n{'0'x$_[0].sprintf'%b',$_[1]}
sub N{/0*(?=.)/;length$&,oct"0b$'"}
$_=<>;print/ /?n map{
  ($a,$b)=N;($a+$b)*($a+$b+1)/2+$b
}split:"@{[map{
  $w=int((sqrt(8*$_+1)-1)/2);$y=$_-($w*$w+$w)/2;n$w-$y,$y
}N]}"

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. nadalah fungsi ini dan Nkebalikannya (kecuali yang Nmenggunakan $_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.

Kevin Reid
sumber
Input 1111111111111111111111111111111111111111111111111111111111111111(64 1s) tampaknya macet, dan input dari pasangan 0dan 50 1detik memberikan hasil yang sama dengan 0dan 51 1detik, keduanya output 64 1detik. Saya pikir ada semacam overflow dengan jumlah 0s terkemuka , jadi solusinya mungkin untuk mendapatkan nilai output Ndari pasangan Cantor Nnilai input , dan nnilai dari pasangan nnilai (atau sebaliknya untuk invers). Saya seorang perl noob, jadi saya mungkin telah melakukan sesuatu yang salah.
cardboard_box
Ya, program ini tidak akan bekerja untuk string biner yang bagian 1-berisi terlalu besar untuk Perl untuk bekerja dengan bilangan bulat. Saya merasa itu adalah batasan implementasi yang wajar sebagai ganti keanggunan algoritma. Pada prinsipnya, semua operasi numerik dapat diganti dengan operasi bigint.
Kevin Reid
1

Perl, 56 karakter

menambahkan +1 char untuk -psaklar baris perintah

$s.=1;$h{$h{$_}||=(split>1?$s:"$s $s").$/}=$_;$_=$h{$_}
ardnew
sumber
Mungkin saya tidak cukup jelas. Saya ingin program Anda mengambil beberapa input, mencetak beberapa output, dan kemudian mengakhiri. Kemudian jalankan program kembali dengan output karena input harus mengembalikan apa yang pertama kali Anda input.
cardboard_box
@ cardboard_box pemetaan harus tetap ada di antara beberapa proses? Anda harus benar-benar menambahkannya ke deskripsi masalah
ardnew
0

Python, 394

Saya yakin ini bisa di-golf lebih lanjut, tetapi monolith ini menggunakan Fungsi Penyandingan Cantor dan kebalikannya.

import math
s=lambda n:n*(n+1)/2
p=lambda a:'0'*a[0]+bin(a[1])[2:]
q=lambda t:t.index('1')
B=raw_input().split()
def f(x,y):r=x+y+1;return s(r)-[y,x][r%2]-1
def g(z):r=int(math.ceil((2*(z+1)+1/4.)**(1/2.)-1/2.))-1;d=s(r+1)-z-1;return [(d,r-d),(r-d,d)][r%2]
if len(B)<2:a=[g(q(B[0])),g(int(B[0],2))];print p(a[0])+' '+p(a[1])
else:print p([f(q(B[0]),int(B[0],2)),f(q(B[1]),int(B[1],2))])

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.

scleaver
sumber
Hanya memperhatikan bahwa ini gagal pada input apa saja yang semuanya 0, saya akan memperbaikinya besok, saya bosan dengan python sekarang -_-
scleaver