Korespondensi satu-ke-satu antara pasangan bilangan bulat dan bilangan bulat positif

8

Sudah diketahui bahwa ada korespondensi satu-ke-satu antara pasangan bilangan bulat dan bilangan bulat positif. Tugas Anda adalah menulis kode yang mendefinisikan korespondensi tersebut (dengan mendefinisikan sepasang fungsi / program yang saling berlawanan) dalam bahasa pemrograman pilihan Anda, ditambah pemeriksaan kebenaran (lihat di bawah) dengan jumlah byte terkecil untuk korespondensi definisi (tidak memperhitungkan kebenaran).

Solusinya harus meliputi:

  • definisi fungsi / program f memiliki dua argumen integer dan mengembalikan integer (itu adalah satu arah dari bijection).

  • baik definisi fungsi / program g memiliki satu argumen integer dan mengembalikan sepasang integer (mungkin array, daftar, gabungan dari dua integer yang dipisahkan oleh sesuatu ...) atau dua fungsi / program a dan b memiliki argumen integer dan mengembalikan integer (itulah arah lain).

  • potongan kode tambahan memeriksa bahwa untuk f dan g (atau f dan a, b) yang Anda tetapkan di atas, Anda memiliki g (f (x, y)) = (x, y) (atau a (f (x, y) ) = x dan b (f (x, y)) = y) untuk setiap bilangan bulat x, y dalam kisaran -100 <x <100, -100 <y <100. Perhatikan bahwa f dan g harus bekerja untuk nilai di luar kisaran ini juga.

Anda dapat mengganti nama a, b, f atau g tentu saja. Kedua solusi tidak harus ditulis dalam bahasa yang sama.

Di bawah ini adalah solusi yang tidak optimal sama sekali dalam PARI / GP, dengan 597 karakter untuk definisi fungsi.

plane_to_line(x,y)={
my(ax,ay,z);
ax=abs(x);
ay=abs(y);
if((ax<=ay)*(y<0),        z=4*y*y-2*y+x+2;);
if((ax<=ay)*(y>=0),       z=4*y*y-2*y-x+2;);
if((ay<=ax)*(x<0),        z=4*x*x    -y+2;);
if((ay<=ax)*(x>=0)*(y<0), z=4*x*x+4*x+y+2;);
if((ay<=ax)*(x>=0)*(y>=0),z=4*x*x-4*x+y+2;);
if((x==0)*(y==0),z=1;);
return(z);
}


line_to_plane(z)={
my(l,d,x,y);
l=floor((1+sqrt(z-1))/2);
d=z-(4*l*l-4*l+2);
if(d<=l,x=l;y=d;);
if((l<d)*(d<=3*l),x=2*l-d;y=l;);
if((3*l<d)*(d<=5*l),x=(-l);y=4*l-d;);
if((5*l<d)*(d<=7*l),x=d-6*l;y=(-l););
if((7*l<d)*(d<8*l) ,x=l;y=d-8*l;);
if(z==1,x=0;y=0;);
return([x,y]);
}

dan kode pemeriksaan kebenaran:

accu=List([])
m=100;
for(x=-m,m,for(y=-m,m,if(line_to_plane(plane_to_line(x,y))!=[x,y],\
listput(accu,[x,y]);)))
Vec(accu)
Ewan Delanoy
sumber
1
Kami sudah melakukan bagian kedua dari ini, tetapi saya kira kenyataan bahwa kedua fungsi harus saling berlawanan mungkin merupakan interaksi yang cukup untuk membenarkan tantangan multi-bagian .
Martin Ender
@ MartinBüttner Saya tidak yakin karya multi-bagian yang independen. Bagian dari tantangannya adalah memilih pengodean yang memberi Anda fungsi terpendek.
Level River St
1
Bisakah kita menyediakan hanya satu program yang bisa disebut dua arah?
Fatalkan
1
@ EwanDelanoy Saya pikir Fatalize menyarankan untuk menghitung program yang dapat melakukan kedua hal hanya sekali.
Martin Ender
2
@LevelRiverSt Untuk melengkapi komentar Katenkyo, alasan Z^nsingkatan n-tuples adalah bahwa operator yang dihilangkan bukan perkalian (berpasangan) tetapi produk Cartesian. Z^2 = ZxZ.
Martin Ender

Jawaban:

7

MATL , 43 36 byte

Ini menggunakan fungsi spiral( 1YL), yang menghasilkan array 2D persegi dari ukuran yang diberikan dengan nilai-nilai yang diatur dalam spiral luar. Misalnya, dengan input 7yang dihasilkannya

43 44 45 46 47 48 49
42 21 22 23 24 25 26
41 20  7  8  9 10 27
40 19  6  1  2 11 28
39 18  5  4  3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31

Pusat array, yang berisi 1, sesuai dengan tupel [0 0]. Sudut kiri atas sesuai dengan [-3 -3]dll. Jadi misalnya f (-3, -3) akan menjadi 43 dan g (43) akan menjadi [-3 -3].

Kode menghasilkan array 2D dengan matriks spiral ini, sebesar yang diperlukan untuk melakukan konversi. Perhatikan bahwa ukuran yang lebih besar selalu memberikan hasil yang sama untuk entri yang sudah termasuk dalam ukuran yang lebih kecil.

Dari Z 2 hingga N (18 byte):

|X>tEQ1YLGb+QZ}3$)

Cobalah online!

|X>   % input is a 2-tuple. Take maximum of absolute values
tEQ   % duplicate. Multiply by 2 and increase by 1. This gives necessary size of spiral
1YL   % generate spiral
G     % push input 2-tuple again
b+Q   % bubble up, add, increase by 1. This makes the center correspont to [0 0]
Z}    % split tuple into its values
3$)   % use those two value as indices into the spiral array to obtain result

Dari N hingga Z 2 ( 25 18 byte)

Eqt1YLG=2#fhw2/k-q

Cobalah online!

Eq      % input is a number. Multiply by 2, add 1. This assures size is enough and odd
t1YL    % duplicate. Generate spiral of that size
G=      % compare each entry with the input value
2#fh    % 2-tuple of row and column indices of matching entry
w2/k-q  % swap. Offset values so that center corresponds to [0 0]

Cuplikan untuk diperiksa

Catatan yang Gperlu dimodifikasi untuk mengakomodasi fakta bahwa kita belum memiliki satu input. Kode lambat, jadi tautan memeriksa tupel dengan nilai dari -9 hingga 9 saja. Untuk -99 hingga 99 cukup ganti baris pertama.

Kode menguji setiap tupel dengan nilai dalam rentang yang ditentukan. Itu konversi ke nomor, kemudian dari nomor itu kembali ke tuple, dan kemudian memeriksa apakah tuple asli dan pulih sama. Hasilnya semua harus 1, menunjukkan bahwa semua perbandingan memberi true.

Butuh beberapa saat untuk berlari.

Cobalah online!

-9:9                     % Or use -99:99. But it takes long
HZ^!"@                   % Cartesian power: gives tuples [-9 -9] ... [9 9].
                         % For each such tuple
|X>tEQ1YL@b+QZ}3$)       % Code from Z^2 to N with `G` replaced by `@` (current tuple)
XJ                       % Copy result into clipboard J
Eqt1YLJ=2#fhw2/k-q       % Code from N to Z^2 with `G` replaced by `J`
@!X=                     % Compare original tuple with recovered tuple: are they equal?
Luis Mendo
sumber
4

JavaScript (ES6), 171 byte

(x,y)=>(h=x=>parseInt((x^x>>31).toString(2)+(x>>>31),4),h(x)*2+h(y))
x=>(h=x=>parseInt(x.toString(2).replace(/.(?!(..)*$)/g,''),2),i=x=>x<<31>>31^x>>>1,[i(h(x>>>1)),i(h(x))])

Sedikit memutar-mutar: angka negatif memiliki bit mereka terbalik; setiap bilangan bulat kemudian digandakan, dan 1 ditambahkan jika awalnya negatif; bit dari integer kemudian disisipkan. Operasi mundur menghapus bit alternatif, membaginya dengan 2, dan membalik semua bit jika nilainya negatif. Saya bisa menyimpan 3 byte dengan membatasi diri saya pada nilai 15-bit, bukan nilai 16-bit.

Neil
sumber
3

Jelly, 50 48 46 45 43 40 39 byte

Plane to line ( 18 17 16 byte ):

AḤ_<0$
+RS+
,Ñç/

Cobalah online!

Line to plane ( 32 30 29 27 24 23 bytes ):

HĊN⁸¡
³R‘R’U⁹¡F³ịÇ
ç1,¢

Cobalah online!

Penjelasan:

Saya hanya akan menjelaskan plane to line, karena line to planejustru kebalikannya.

Pertama, kami mengonversi setiap bilangan bulat ke bilangan asli, berdasarkan fungsinya f(x) = 2*|x| - (x<0).

Kemudian, kami mengonversi dua bilangan asli menjadi dua bilangan alami lainnya, berdasarkan fungsinya g(x,y) = (x+y,y).

Akhirnya, kami mengonversinya menjadi satu bilangan alami, berdasarkan fungsinya h(x,y) = (x+1)C2 + y

Biarawati Bocor
sumber
@LuisMendo Ya, dan sekarang input tautan coba-online adalah7
Leaky Nun
Ini terlihat lebih baik :-) Saya menganggap Anda sedang mengerjakan cuplikan pemeriksaan
Luis Mendo
@LuisMendo Apakah potongan pengecekan dihitung untuk skor?
Leaky Nun
Tidak, tantangannya mengatakan tidak memperhitungkan kebenaran
Luis Mendo