Correspondencia uno a uno entre pares de enteros y los enteros positivos

8

Es bien sabido que hay correspondencias uno a uno entre pares de enteros y los enteros positivos. Su tarea es escribir el código que define dicha correspondencia (definiendo un par de funciones / programas que son inversos entre sí) en el lenguaje de programación de su elección, más una verificación de corrección (ver más abajo) con el menor número de bytes para la correspondencia definición (sin tener en cuenta la verificación de corrección).

La solución debe incluir:

  • La definición de una función / programa f que tiene dos argumentos enteros y devuelve un entero (esa es una dirección de la biyección).

  • ya sea la definición de una función / programa g que tiene un argumento entero y devuelve un par de enteros (podría ser una matriz, una lista, la concatenación de los dos enteros separados por algo ...) o dos funciones / programas ayb que tienen un argumento entero y devolver un entero (esa es la otra dirección).

  • un fragmento de código adicional que comprueba que para f y g (o f y a, b) que definió anteriormente, tiene g (f (x, y)) = (x, y) (o a (f (x, y) ) = x y b (f (x, y)) = y) para cualquier número entero x, y en el rango -100 <x <100, -100 <y <100. Tenga en cuenta que f y g tienen que trabajar para valores fuera de de este rango también.

Puede cambiar el nombre de a, b, f o g, por supuesto. Las dos soluciones no tienen que estar escritas en el mismo idioma.

A continuación se muestra una solución no óptima en absoluto en PARI / GP, con 597 caracteres para las definiciones de funciones.

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

y el código de verificación de corrección:

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
fuente
1
Ya hemos hecho la segunda parte de esto, pero supongo que el hecho de que ambas funciones deben ser inversas entre sí podría ser una interacción suficiente para justificar un desafío de varias partes .
Martin Ender
@ MartinBüttner No estoy seguro de trabajos independientes de varias partes. Parte del desafío es elegir la codificación que le brinda las funciones más cortas.
Level River St
1
¿Podemos proporcionar un solo programa que se puede llamar en ambos sentidos?
Fatalize
1
@EwanDelanoy Creo que Fatalize estaba sugiriendo contar el programa que puede hacer ambas cosas solo una vez.
Martin Ender
2
@LevelRiverSt Para complementar el comentario de Katenkyo, la razón Z^nde las ntuplas es que el operador omitido no es la multiplicación (en pares) sino el producto cartesiano. Z^2 = ZxZ.
Martin Ender

Respuestas:

7

MATL , 43 36 bytes

Utiliza la función spiral( 1YL), que genera una matriz 2D cuadrada de tamaño dado con valores dispuestos en una espiral hacia afuera. Por ejemplo, con entrada 7produce

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

El centro de la matriz, que contiene 1, corresponde a la tupla [0 0]. La esquina superior izquierda corresponde a [-3 -3]etc. Entonces, por ejemplo, f (-3, -3) será 43 yg (43) será [-3 -3].

El código genera una matriz 2D con esta matriz espiral, tan grande como sea necesario para realizar la conversión. Tenga en cuenta que los tamaños más grandes siempre dan el mismo resultado para las entradas ya incluidas en tamaños más pequeños.

De Z 2 a N (18 bytes):

|X>tEQ1YLGb+QZ}3$)

Pruébalo en línea!

|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

De N a Z 2 ( 25 18 bytes)

Eqt1YLG=2#fhw2/k-q

Pruébalo en línea!

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]

Fragmento para verificar

Tenga en cuenta que Gdebe modificarse para acomodar el hecho de que no tenemos una sola entrada. El código es lento, por lo que el enlace verifica las tuplas con valores de -9 a 9 solamente. Para -99 a 99, simplemente reemplace la primera línea.

El código prueba cada tupla con valores en el rango definido. Realiza la conversión a un número, luego de ese número a una tupla, y luego comprueba si la tupla original y la recuperada son iguales. Todos los resultados deberían ser 1, lo que indica que todas las comparaciones dan true.

Lleva un tiempo correr.

Pruébalo en línea!

-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
fuente
4

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

Cambio de bits: los números negativos tienen sus bits invertidos; cada número entero se duplica y se agrega 1 si originalmente era negativo; Los bits de los enteros se intercalan. La operación inversa elimina bits alternativos, divide por 2 y voltea todos los bits si el valor era negativo. Podría ahorrar 3 bytes limitándome a valores de 15 bits en lugar de valores de 16 bits.

Neil
fuente
3

Gelatina, 50 48 46 45 43 40 39 bytes

Plano a línea ( 18 17 16 bytes ):

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

Pruébalo en línea!

Línea a plano ( 32 30 29 27 24 23 bytes ):

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

Pruébalo en línea!

Explicación:

Solo lo explicaré plane to line, porque line to planees todo lo contrario.

En primer lugar, convertimos cada número entero a un número natural, por la función f(x) = 2*|x| - (x<0).

Luego, convertimos los dos números naturales en otros dos números naturales, por la función g(x,y) = (x+y,y).

Finalmente, los convertimos en un número natural, por la función h(x,y) = (x+1)C2 + y

Monja permeable
fuente
@LuisMendo Sí, y ahora la entrada de los enlaces de prueba en línea es7
Leaky Nun
Esto se ve mejor :-) Supongo que está trabajando en el fragmento de verificación
Luis Mendo
@LuisMendo ¿El fragmento de verificación cuenta para la puntuación?
Leaky Nun
No, el desafío dice no tener en cuenta la verificación de corrección
Luis Mendo