Hilberts binäres Hotel

18

In dieser Herausforderung werden Sie aufgefordert, eine beliebige Funktion (oder ein vollständiges Programm) zu implementieren, die zwei Eigenschaften erfüllt. Diese Eigenschaften sind:

  • Ihre Funktion muss eine injektive (umkehrbare) Funktion sein, die von den Polynomen mit nicht negativen Ganzzahlkoeffizienten bis zu den nicht negativen Ganzzahlen reicht. Dies bedeutet, dass keine zwei ungleichen Eingaben einer gleichen Ausgabe zugeordnet werden können.

  • Ihre Funktion muss die Gesamtzahl der "Ein-Bits" von der Eingabe bis zur Ausgabe beibehalten. Das heißt, wenn Sie die 1 Bits jedes Koeffizienten des Polynoms zählen, sollte deren Summe der Anzahl der 1 Bits in der Binärdarstellung des Ausgangs entsprechen. Zum Beispiel 9ist es 1001binär, also hat es 2 1Bits.


IO

Ein nicht negatives ganzzahliges Polynom ist dasselbe wie eine unendliche Liste nicht negativer Ganzzahlen, sodass nach einem bestimmten Punkt alle Ganzzahlen Null sind. Somit können Polynome entweder durch unendliche Listen (obwohl dies wahrscheinlich unerwünscht ist) oder durch endliche Listen mit impliziten Nullen nach dem Ende der Liste dargestellt werden.

Der Hauptunterschied zwischen Polynomen und endlichen Listen besteht darin, dass das Hinzufügen einer Null am Ende einer Liste die Liste ändert:

Listen

Das Hinzufügen einer Null am Ende eines Polynoms ändert seinen Wert nicht:

Polynome

Wenn Ihre Funktion also eine endliche Liste als Eingabe verwendet, die ein Polynom darstellt, darf das Hinzufügen einer Null das Ergebnis nicht ändern.

Bei der Darstellung von Polynomen als Listen können Sie diese entweder mit dem ersten oder dem letzten Eintrag darstellen, der den konstanten Term darstellt. Beispielsweise könnten Sie eine der folgenden Möglichkeiten haben:

Vorwärts oder rückwärts

Im ersten Fall sollte das Hinzufügen von Nullen am Ende der Liste das Ergebnis nicht ändern. Im zweiten Fall sollte das Hinzufügen von Nullen am Anfang der Liste das Ergebnis nicht ändern.

Wenn Ihre Sprache Polynome unterstützt, können Sie diese natürlich als Eingabe verwenden.

Die Ausgabe sollte über alle Standardmethoden eine nicht negative Ganzzahl sein.


Dies ist daher werden die Antworten in Bytes gewertet, wobei weniger Bytes besser sind.

Weizen-Assistent
quelle
Ist []oder [0]eine gültige Eingabe?
JungHwan Min 25.12.17
1
@JungHwanMin Ja, beide sind das Nullpolynom.
Wheat Wizard
Ich weiß, dass Sie 1 setzen wollen, um Nullen zu teilen, aber einige Möglichkeiten funktionieren möglicherweise und scheinen nicht so gut zu sein ...
l4m2
1
@ l4m2 Es tut mir leid, aber ich verstehe keinen Ihrer Kommentare. Nach Ihrer Frage führende Nullen auf was? Das Polynom, die Koeffizienten? Ich bin mir nicht sicher, was Sie unter "Nullen, die nicht geschrieben sind" verstehen.
Wheat Wizard
1
Sind die Bilder wirklich notwendig (dh sie können nicht mit Rich Text dargestellt werden) ??? Weil Menschen ohne die Fähigkeit, Bilder zu sehen, Ihre Herausforderung nicht vollständig sehen können.
Mindwin

Antworten:

6

Gelee , 8 Bytes

BFṢḄæ«ÆẸ

Probieren Sie es online!

Links umgekehrt, 5 Bytes

Bċ0ÆE

Probieren Sie es online!

Wie es funktioniert

BFṢḄæ«ÆẸ  Main link. Argument: A (array)

B         Binary; convert each integer in A to base 2.
 F        Flatten; concatenate the resulting binary arrays.
  Ṣ       Sort the resulting bit array.
   Ḅ      Convert from base 2 to integer, yielding an integer x with as much set
          bits as there are set bits in A.
      ÆẸ  Unexponents; convert A = [a1, a2, ...] to y = (p1**a1 + p2**a2 + ...),
          where pn is the n-th prime number.
          By the fundamental theorem of arithmetic, the resulting integer is unique
          for each array A without trailing zeroes.
    æ«    Bitshift left; compute x * 2**y.
Dennis
quelle
6

Wolfram Language (Mathematica) , 36 20 Bytes

x#/.x->2^(#/.x->2)!&

Probieren Sie es online!

Nimmt ein Polynom f (x) als Eingabe. Wertet y * f (y) aus, wobei y = 2 ^ (f (2)!). Leider bedeutet dies, dass die Ausgänge ziemlich groß werden.

Bei der Auswertung von y * f (y) bleibt die Anzahl der 1-Bits erhalten, wenn y eine Potenz von 2 ist, die größer als ein Koeffizient ist, was für den oben ausgewählten Wert zutrifft. Wir wählen y = 2 ^ (f (2)!), Um das Ergebnis injektiv zu machen:

  • Zwei unterschiedliche Eingaben mit demselben Wert von y ergeben unterschiedliche Ausgaben, da im Wesentlichen zwei unterschiedliche Zahlen in der Basis y gelesen werden.
  • Wenn wir k = f (2) und damit y festlegen, wird der kleinste Wert von y * f (y) erreicht, wenn die Eingabe ein konstantes Polynom gleich k ist, und der größte Wert wird erreicht, wenn die Eingabe das Polynom ist, das die Basis ergibt -2 Erweiterung von k. Im ersten Fall ist y * f (y) = 2 ^ (k!) * K, und im zweiten Fall ist y * f (y) <2 ^ (k! * Ceil (lg k)), was weniger ist als 2 ^ ((k + 1)!) * (k + 1).
  • Infolgedessen ist für zwei Polynome f und g mit f (2) <g (2) die ganze Zahl, die wir von f erhalten, kleiner als die ganze Zahl, die wir von g erhalten.
Mischa Lawrow
quelle
5

Wolfram Language (Mathematica) , 61 Bytes

Tr[2^((2#2-1)2^#)&@@@Position[Reverse/@#~IntegerDigits~2,1]]&

Probieren Sie es online!

Zwei positive Ganzzahlen können einer einzigen positiven Ganzzahl zugeordnet werden. Sei a, bzwei positive ganze Zahlen. Dann a, b -> (2a - 1) 2^(b-1)ist eine Bijektion von NxN nach N.

Diese Funktion ermittelt die Position aller 1Bits in der Eingabe (ab der Einerstelle) und wendet auf jede Position eine Nur-Injektions-Variante der obigen Zuordnung an. Dann wird jede resultierende Zahl zur Potenz von zwei erhöht, und alle Zahlen werden addiert (was in Ordnung ist, da wir eine injektive NxN -> N-Abbildung angewendet haben).

Beispielsweise:

{1, 2, 3}
{{1}, {1, 0}, {1, 1}}             (* Convert to binary *)
{{1}, {0, 1}, {1, 1}}             (* Reverse each *)
{{1, 1}, {2, 2}, {3, 1}, {3, 2}}  (* Position of 1s *)
{2, 12, 8, 24}                    (* Inject to N *)
{4, 4096, 256, 16777216}          (* Raise to the power of 2 *)
16781572                          (* Add *)

Inverse Funktion (124 Bytes)

##+#&~Fold~#&@*Reverse/@Normal@SparseArray[{Log2[j=#~BitAnd~-#],(#/j+1)/2}->1&@@@(Reverse[#~IntegerDigits~2]~Position~1-1)]&

Hier ist eine inverse Funktion zum Testen der Injektivität.

Probieren Sie es online!

JungHwan min
quelle
5

Python 2 , 118 117 114 103 100 Bytes

100 Bytes von Jonathan Frech:

a=input()
while a[0]<1:a.pop(0)
y="".join("2"+bin(v)[2:]for v in a)
print~-2**y.count("1")<<int(y,3)

Probieren Sie es online!

103 Bytes mit einer Golfmöglichkeit 1

a=input()
while a[0]<1:a.pop(0)
x="".join(map(bin,a))
print~-(1<<x.count("1"))<<int(x.replace(*"b2"),3)

Probieren Sie es online!

-15 Bytes dank Jonathan Frech

Es wird eine Zahl erstellt, die zuerst die "Ein-Bits" und dann die unäre Darstellung des Arrays enthält, die als trinäre Zahl interpretiert wird.

Die Binärzahl wird erstellt, indem die Zahlen in binäre Zeichenfolgen ( 0bNNN) konvertiert und dann durch ersetzt bwerden 2.

1 Ich hätte 14 Bytes einsparen können, indem ich sie stattdessen in eine Zahl zur Basis 12 konvertierte, aber TIO verfügte nicht über genügend Speicher, sodass ich mich entschied, diese zu verwenden.

fergusq
quelle
@ JonathanFrech Vielen Dank :)
Fergusq
1

05AB1E , 14 Bytes

gÅpImPoIbS{2β*

Probieren Sie es online!

Ergibt die gleichen Ergebnisse wie Dennis 'Jelly-Lösung, jedoch ist die Technik etwas anders.

Wie?

Versuchen wir die Eingabe [1, 2, 3]:

gÅpImPoIbS{2β* | Full program.
               | STACK: [[1, 2, 3]]
               |
g              | Push the length.
               | STACK: [3]
 Åp            | Generate the first N primes.
               | STACK: [[2, 3, 5]]
   Im          | Push the input, and apply pairwise exponentiation.
               | STACK: [2, 9, 125]
     P         | Push the product.
               | STACK: 2250
      o        | Push 2 ** N.
               | STACK: 2 ** 2250 (way too large)
       Ib      | Push the input and convert to binary.
               | STACK: [2 ** 2250, ['1', '10', '11']].
         S{    | Sort all the characters.
               | STACK: [2 ** 2250, ['0', '1', '1', '1', '1']]
           2β  | Convert from binary.
               | STACK: [2 ** 2250, 15]
             * | Multiplication.
               | STACK: [2 ** 2250 * 15]
               | Implicitly print the top of the stack (2 ** 2250 * 15).
Mr. Xcoder
quelle
0

JavaScript 6, 96 83 Bytes

x=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/0|2/g,'')+'0'.repeat(t)

gibt einen binären Ausdruck aus

([1,2]) => 3*2^21210(Decimal)
([0,1,2]) => 3*2^21210
([1,2,0]) => 3*2^2121020
([1,2,3,4]) => 31*2^212102112100(Threotically)
l4m2
quelle
null führt zu einer leeren Zeichenfolge, die null darstellt
l4m2
replace(/0|2/g,0)scheint auch zu funktionieren, aber schwieriger zu dekodieren
l4m2
Ich bin mir nicht sicher x=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/2/g,'0'.repeat(t)). Fühle mich okay, kann aber nicht beweisen
l4m2