Correspondência um a um entre pares de números inteiros e números inteiros positivos

É sabido que existem correspondências um a um entre pares de números inteiros e números inteiros positivos. Sua tarefa é escrever um código definindo essa correspondência (definindo um par de funções / programas que são inversos um ao outro) na linguagem de programação de sua escolha, além de uma verificação de correção (veja abaixo) com o menor número de bytes para a correspondência definição (sem levar em consideração a verificação de correção).

A solução deve incluir:

a definição de uma função / programa f com dois argumentos inteiros e retornando um número inteiro (essa é uma direção da bijeção).
seja a definição de uma função / programa g com um argumento inteiro e retornando um par de números inteiros (pode ser uma matriz, uma lista, a concatenação dos dois números inteiros separados por algo ...) ou duas funções / programas a e b tendo um argumento inteiro e retornando um número inteiro (essa é a outra direção).
um trecho de código adicional que verifica se, para efeg (ou f e a, b) que você definiu acima, você tem g (f (x, y)) = (x, y) (ou a (f (x, y)) ) = x eb (f (x, y)) = y) para quaisquer números inteiros x, y no intervalo -100 <x <100, -100 <y <100. Observe que f e g precisam trabalhar com valores fora dessa faixa também.

Você pode renomear a, b, f ou g, é claro. As duas soluções não precisam ser escritas no mesmo idioma.

Abaixo está uma solução não ótima em PARI / GP, com 597 caracteres para as definições de função.

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

e o código de verificação da correção:

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)

code-golf number arithmetic grid Ewan Delanoy
fonte

Já fizemos a segunda parte disso, mas acho que o fato de que ambas as funções precisam ser inversas uma da outra pode ser interação suficiente para justificar um desafio de várias partes .

Martin Ender

@ MartinBüttner Não tenho certeza de que funciona com várias partes independentes. Parte do desafio é escolher a codificação que oferece as funções mais curtas.

Level River St

Podemos fornecer apenas um programa que pode ser chamado nos dois sentidos?

Fatalize

@EwanDelanoy Acho que Fatalize estava sugerindo contar o programa que pode fazer as duas coisas apenas uma vez.

Martin Ender

@LevelRiverSt Para complementar o comentário de Katenkyo, o motivo Z^né n-tuples é que o operador omitido não é a multiplicação (em pares), mas o produto cartesiano. Z^2 = ZxZ.

Martin Ender

Respostas:

MATL , 43 36 bytes

Isso usa a função spiral( 1YL), que gera uma matriz 2D quadrada de determinado tamanho com valores organizados em uma espiral externa. Por exemplo, com entrada 7, produz

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

O centro da matriz, que contém 1, corresponde à tupla [0 0]. O canto superior esquerdo corresponde a [-3 -3]etc. Portanto, por exemplo, f (-3, -3) será 43 e g (43) será [-3 -3].

O código gera uma matriz 2D com essa matriz espiral, tão grande quanto necessário para fazer a conversão. Observe que tamanhos maiores sempre dão o mesmo resultado para as entradas já incluídas em tamanhos menores.

De Z ² a N (18 bytes):

|X>tEQ1YLGb+QZ}3$)

Experimente 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

De N a Z ² ( 25 18 bytes)

Eqt1YLG=2#fhw2/k-q

Experimente 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 para verificação

Observe que Gprecisa ser modificado para acomodar o fato de que não temos uma única entrada. O código é lento, portanto, o link verifica as tuplas com valores de -9 a 9 apenas. Para -99 a 99, substitua a primeira linha.

O código testa cada tupla com valores no intervalo definido. Ele faz a conversão para um número e, a partir desse número, volta para uma tupla, e depois verifica se a tupla original e recuperada são iguais. Os resultados devem ser todos 1, indicando que todas as comparações fornecem true.

Demora um pouco para correr.

Experimente 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
fonte

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: números negativos têm seus bits invertidos; cada número inteiro é então duplicado e 1 adicionado se era originalmente negativo; os bits dos números inteiros são então intercalados. A operação reversa exclui bits alternativos, divide por 2 e vira todos os bits se o valor for negativo. Eu poderia economizar 3 bytes, limitando-me a valores de 15 bits em vez de valores de 16 bits.

Mostrar snippet de código

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

Expandir snippet

Neil
fonte

Geléia, 50 48 46 45 43 40 39 bytes

Plano para linha ( 18 17 16 bytes ):

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

Experimente online!

Linha ao plano ( 32 30 29 27 24 23 bytes ):

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

Experimente online!

Explicação:

Só vou explicar plane to line, porque line to planeé exatamente o contrário.

Em primeiro lugar, nós convertemos cada inteiro a um número natural, pela função f(x) = 2*|x| - (x<0).

Então, nós convertemos os dois números naturais para mais dois números naturais, pela função g(x,y) = (x+y,y).

Finalmente, nós os convertemos em um número natural, pela função h(x,y) = (x+1)C2 + y

Freira Furada
fonte

@LuisMendo Sim, e agora a entrada dos links de try-it-online é7

Leaky Nun 26/16

Este parece melhor :-) Eu suponho que você está trabalhando no trecho de verificação

Luis Mendo

@LuisMendo O snippet de verificação conta para a pontuação?

Freira vazada

Não, o desafio diz não levar em conta a verificação da correção #

Luis Mendo

Correspondência um a um entre pares de números inteiros e números inteiros positivos

Respostas:

MATL , 43 36 bytes

De Z 2 a N (18 bytes):

De N a Z 2 ( 25 18 bytes)

Snippet para verificação

JavaScript (ES6), 171 bytes

Geléia, 50 48 46 45 43 40 39 bytes

Plano para linha ( 18 17 16 bytes ):

Linha ao plano ( 32 30 29 27 24 23 bytes ):

Explicação:

De Z ² a N (18 bytes):

De N a Z ² ( 25 18 bytes)