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:

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

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:

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 Codegolf, daher werden die Antworten in Bytes gewertet, wobei weniger Bytes besser sind.

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.

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.

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!

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 ¹

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.

¹ 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.

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

Python 2 , 74 Bytes

r='print 0';s='<<'
for n in input():r+=oct(n)[:0:-1];s+='0'+'1'*n
exec r+s

Probieren Sie es online!

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)