8
\$\begingroup\$

It is well-known that there are one-to-one correspondences between pairs of integers and the positive integers. Your task is to write code defining such a correspondence (by defining a pair of functions/programs that are inverses of each other) in your programming language of choice, plus a correctness check (see below) with the smallest number of bytes for the correspondence definition (not taking the correctness check into account).

The solution must include :

  • the definition of a function/program f having two integer arguments and returning an integer (that's one direction of the bijection).

  • either the definition of a function/program g having one integer argument and returning a pair of integers (might be an array, a list, the concatenation of the two integers separated by something ...) or two functions/programs a and b having an integer argument and returning an integer (that's the other direction).

  • an additional code snippet checking that for the f and g (or f and a,b) you defined above, you have g(f(x,y))=(x,y) (or a(f(x,y))=x and b(f(x,y))=y) for any integers x,y in the range -100 < x < 100,-100 < y < 100. Note that f and g have to work for values outside of this range as well.

You may rename a,b,f or g of course. The two solutions do not have to be written in the same language.

Below is a not-optimal-at-all solution in PARI/GP, with 597 characters for the function definitions.

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]);
}

and the correctness-check code :

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ We've already done the second part of this but I guess the fact that both functions need to be each other's inverse might be sufficient interaction to justify a multi-part challenge. \$\endgroup\$ – Martin Ender Apr 26 '16 at 10:03
  • \$\begingroup\$ @MartinBüttner I'm not sure independent multi-part works. Part of the challenge is to pick the encoding that gives you the shortest functions. \$\endgroup\$ – Level River St Apr 26 '16 at 10:06
  • 1
    \$\begingroup\$ Can we provide only one program which can be called both ways? \$\endgroup\$ – Fatalize Apr 26 '16 at 10:07
  • 1
    \$\begingroup\$ @EwanDelanoy I think Fatalize was suggesting to count the program that can do both things only once. \$\endgroup\$ – Martin Ender Apr 26 '16 at 11:33
  • 2
    \$\begingroup\$ @LevelRiverSt To supplement Katenkyo's comment, the reason Z^n stands for n-tuples is that the omitted operator isn't (pairwise) multiplication but the Cartesian product. Z^2 = ZxZ. \$\endgroup\$ – Martin Ender Apr 26 '16 at 11:34
7
\$\begingroup\$

MATL, 43 36 bytes

This uses the spiral (1YL) function, which generates a square 2D array of given size with values arranged in an outward spiral. For example, with input 7 it produces

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

The center of the array, which contains 1, corresponds to the tuple [0 0]. The upper left corner corresponds to [-3 -3] etc. So for example f (-3,-3) will be 43 and g (43) will be [-3 -3].

The code generates a 2D array with this spiral matrix, as large as needed to do the conversion. Note that larger sizes always give the same result for the entries already included in smaller sizes.

From Z2 to N (18 bytes):

|X>tEQ1YLGb+QZ}3$)

Try it 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

From N to Z2 (25 18 bytes)

Eqt1YLG=2#fhw2/k-q

Try it 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]

Snippet for checking

Note that G needs to be modified to accomodate the fact that we have don't have a single input. The code is slow, so the link checks tuples with values from -9 to 9 only. For -99 to 99 just replace the first line.

The code tests each tuple with values in the defined range. It does the conversion to a number, then from that number back to a tuple, and then checks if the original and recovered tuple are equal. The results should all be 1, indicating that all comparisons give true.

It takes a while to run.

Try it 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?
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 171 bytes

(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))])

Bit twiddling: negative numbers have their bits flipped; each integer is then doubled, and 1 added if it was originally negative; the bits from the integers are then interleaved. The reverse operation deletes alternate bits, divides by 2, and flips all the bits if the value was negative. I could save 3 bytes by limiting myself to 15-bit values instead of 16-bit values.

f=(x,y)=>(h=x=>parseInt((x^x>>31).toString(2)+(x>>>31),4),h(x)*2+h(y))
g=x=>(h=x=>parseInt(x.toString(2).replace(/.(?!(..)*$)/g,''),2),i=x=>x<<31>>31^x>>>1,[i(h(x>>>1)),i(h(x))])
for(i=-100;i<=100;i++)for(j=-100;j<100;j++)if(g(f(i,j))[0]!=i||g(f(i,j))[1]!=j)alert([i,j])

\$\endgroup\$
3
\$\begingroup\$

Jelly, 50 48 46 45 43 40 39 bytes

Plane to line (18 17 16 bytes):

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

Try it online!

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

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

Try it online!

Explanation:

I'll only explain plane to line, because line to plane is just its opposite.

Firstly, we convert each integer to a natural number, by the function f(x) = 2*|x| - (x<0).

Then, we convert the two natural numbers to another two natural numbers, by the function g(x,y) = (x+y,y).

Finally, we convert them into one natural number, by the function h(x,y) = (x+1)C2 + y

\$\endgroup\$
  • \$\begingroup\$ @LuisMendo Yes, and now the try-it-online links' input is 7 \$\endgroup\$ – Leaky Nun Apr 26 '16 at 14:31
  • \$\begingroup\$ This looks better :-) I assume you are working on the checking snippet \$\endgroup\$ – Luis Mendo Apr 26 '16 at 14:35
  • \$\begingroup\$ @LuisMendo Does the checking snippet count towards the score? \$\endgroup\$ – Leaky Nun Apr 26 '16 at 16:29
  • \$\begingroup\$ No, the challenge says not taking the correctness check into account \$\endgroup\$ – Luis Mendo Apr 26 '16 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.