Eins-zu-eins-Entsprechung zwischen Paaren von ganzen Zahlen und den positiven ganzen Zahlen

8

Es ist bekannt, dass es Eins-zu-Eins-Entsprechungen zwischen Ganzzahlpaaren und den positiven Ganzzahlen gibt. Ihre Aufgabe ist es, Code zu definieren, der eine solche Korrespondenz definiert (indem Sie ein Paar von Funktionen / Programmen definieren, die invers zueinander sind), in einer Programmiersprache Ihrer Wahl sowie eine Korrektheitsprüfung (siehe unten) mit der kleinsten Anzahl von Bytes für die Korrespondenz Definition (ohne Berücksichtigung der Korrektheitsprüfung).

Die Lösung muss Folgendes umfassen:

  • die Definition einer Funktion / eines Programms f mit zwei ganzzahligen Argumenten und der Rückgabe einer ganzen Zahl (das ist eine Richtung der Bijektion).

  • entweder die Definition einer Funktion / eines Programms g mit einem Ganzzahlargument und die Rückgabe eines Paares von Ganzzahlen (kann ein Array, eine Liste, die Verkettung der beiden durch etwas getrennten Ganzzahlen sein ...) oder zwei Funktionen / Programme a und b mit ein ganzzahliges Argument und die Rückgabe einer Ganzzahl (das ist die andere Richtung).

  • Ein zusätzliches Code-Snippet überprüft, ob für das oben definierte f und g (oder f und a, b) g (f (x, y)) = (x, y) (oder a (f (x, y)) gilt. ) = x und b (f (x, y)) = y) für alle ganzen Zahlen x, y im Bereich -100 <x <100, -100 <y <100. Beachten Sie, dass f und g für Werte außerhalb arbeiten müssen auch in diesem Bereich.

Sie können natürlich a, b, f oder g umbenennen. Die beiden Lösungen müssen nicht in derselben Sprache geschrieben sein.

Im Folgenden finden Sie eine überhaupt nicht optimale Lösung in PARI / GP mit 597 Zeichen für die Funktionsdefinitionen.

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

und den Korrektheitsprüfcode:

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
quelle
1
Wir haben den zweiten Teil davon bereits erledigt, aber ich denke, dass die Tatsache, dass beide Funktionen invers sein müssen, eine ausreichende Interaktion sein könnte, um eine mehrteilige Herausforderung zu rechtfertigen .
Martin Ender
@ MartinBüttner Ich bin mir nicht sicher, ob unabhängige mehrteilige Werke. Ein Teil der Herausforderung besteht darin, die Codierung auszuwählen, die Ihnen die kürzesten Funktionen bietet.
Level River St
1
Können wir nur ein Programm bereitstellen, das in beide Richtungen aufgerufen werden kann?
Fatalize
1
@EwanDelanoy Ich denke, Fatalize hat vorgeschlagen, das Programm zu zählen, das beide Dinge nur einmal ausführen kann.
Martin Ender
2
@LevelRiverSt Um Katenkyos Kommentar zu ergänzen, Z^nsteht für n-tuples, dass der ausgelassene Operator keine (paarweise) Multiplikation ist, sondern das kartesische Produkt. Z^2 = ZxZ.
Martin Ender

Antworten:

7

MATL , 43 36 Bytes

Dies verwendet die Funktion spiral( 1YL), die ein quadratisches 2D-Array mit einer bestimmten Größe mit Werten erzeugt, die in einer nach außen gerichteten Spirale angeordnet sind. Zum Beispiel mit Eingang 7es produziert

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

Die Mitte des Arrays, das enthält 1, entspricht dem Tupel [0 0]. Die obere linke Ecke entspricht [-3 -3]usw. So ist beispielsweise f (-3, -3) 43 und g (43) [-3 -3].

Der Code generiert mit dieser Spiralmatrix ein 2D-Array, das so groß ist, wie es für die Konvertierung erforderlich ist. Beachten Sie, dass größere Größen immer das gleiche Ergebnis für die Einträge liefern, die bereits in kleineren Größen enthalten sind.

Von Z 2 bis N (18 Bytes):

|X>tEQ1YLGb+QZ}3$)

Probieren Sie es online aus!

|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

Von N bis Z 2 ( 25 18 Bytes)

Eqt1YLG=2#fhw2/k-q

Probieren Sie es online aus!

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 zur Überprüfung

Beachten Sie, dass GÄnderungen vorgenommen werden müssen, um der Tatsache Rechnung zu tragen, dass wir keinen einzigen Eingang haben. Der Code ist langsam, daher prüft der Link nur Tupel mit Werten von -9 bis 9. Für -99 bis 99 ersetzen Sie einfach die erste Zeile.

Der Code testet jedes Tupel mit Werten im definierten Bereich. Es konvertiert in eine Zahl, dann von dieser Zahl zurück in ein Tupel und prüft dann, ob das ursprüngliche und das wiederhergestellte Tupel gleich sind. Die Ergebnisse sollten alle sein 1, was darauf hinweist, dass alle Vergleiche ergeben true.

Das Laufen dauert eine Weile.

Probieren Sie es online aus!

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

Bit Twiddling: Bei negativen Zahlen werden die Bits umgedreht. Jede ganze Zahl wird dann verdoppelt und 1 hinzugefügt, wenn sie ursprünglich negativ war. Die Bits aus den ganzen Zahlen werden dann verschachtelt. Die umgekehrte Operation löscht alternative Bits, dividiert durch 2 und dreht alle Bits um, wenn der Wert negativ war. Ich könnte 3 Bytes sparen, indem ich mich auf 15-Bit-Werte anstelle von 16-Bit-Werten beschränke.

Neil
quelle
3

Gelee, 50 48 46 45 43 40 39 Bytes

Ebene zu Zeile ( 18 17 16 Bytes ):

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

Probieren Sie es online aus!

Linie zu Ebene ( 32 30 29 27 24 23 Bytes ):

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

Probieren Sie es online aus!

Erläuterung:

Ich werde es nur erklären plane to line, weil line to planees genau umgekehrt ist.

Zunächst konvertieren wir jede Ganzzahl durch die Funktion in eine natürliche Zahl f(x) = 2*|x| - (x<0).

Dann konvertieren wir die beiden natürlichen Zahlen durch die Funktion in zwei weitere natürliche Zahlen g(x,y) = (x+y,y).

Schließlich konvertieren wir sie durch die Funktion in eine natürliche Zahl h(x,y) = (x+1)C2 + y

Undichte Nonne
quelle
@ LuisMendo Ja, und jetzt ist die Eingabe der Try-It-Online-Links7
Leaky Nun
Das sieht besser aus :-) Ich nehme an, Sie arbeiten an dem Checking-Snippet
Luis Mendo
@LuisMendo Zählt das Überprüfungsschnipsel für die Punktzahl?
Undichte Nonne
Nein, die Herausforderung besagt , dass die Korrektheitsprüfung nicht berücksichtigt wird
Luis Mendo