Dans ce défi, il vous sera demandé d'implémenter toute fonction (ou programme complet) qui remplit deux propriétés. Ces propriétés sont:

• Votre fonction doit être une fonction injective (réversible) des polynômes à coefficients entiers non négatifs aux entiers non négatifs. Cela signifie que deux entrées inégales ne peuvent pas correspondre à une sortie égale.

• Votre fonction doit conserver le nombre total de "sur bits" de son entrée à sa sortie. Cela signifie que si vous comptez les 1 bits de chaque coefficient du polynôme, leur somme doit être la même que le nombre de 1 bits dans la représentation binaire de la sortie. Par exemple, 9est 1001en binaire, il a donc 2 1bits.

IO

Un polynôme entier non négatif est identique à une liste infinie d'entiers non négatifs de sorte qu'après un certain point, tous les entiers sont nuls. Ainsi, les polynômes peuvent être représentés soit par des listes infinies (bien que ce soit probablement indésirable) soit par des listes finies avec des zéros implicites après la fin de la liste.

La principale distinction entre les polynômes et les listes finies est que l'ajout d'un zéro à la fin d'une liste changera la liste:

En ajoutant un zéro à la fin d'un polynôme ne change pas sa valeur:

Ainsi, si votre fonction prend en entrée une liste finie représentant un polynôme, l'ajout d'un zéro ne doit pas changer son résultat.

Lorsque vous représentez des polynômes sous forme de listes, vous pouvez les représenter avec la première ou la dernière entrée représentant le terme constant. Par exemple, vous pouvez avoir l'une des possibilités suivantes:

Dans le premier cas, l'ajout de zéros à la fin de la liste ne devrait pas modifier le résultat; dans le second cas, l'ajout de zéros au début de la liste ne devrait pas modifier le résultat.

Bien sûr, si votre langue prend en charge les polynômes, vous pouvez les utiliser comme entrées.

La sortie doit être une sortie entière non négative via toutes les méthodes standard.

Il s'agit de code-golf donc les réponses seront notées en octets, avec moins d'octets étant mieux.

Gelée , 8 octets

BFṢḄæ«ÆẸ

Essayez-le en ligne!

Inverse gauche, 5 octets

Bċ0ÆE

Essayez-le en ligne!

Comment ça fonctionne

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 octets

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

Essayez-le en ligne!

Prend un polynôme f (x) en entrée. Évalue y * f (y), où y = 2 ^ (f (2)!). Malheureusement, cela signifie que les sorties deviennent assez grandes.

L'évaluation de y * f (y) préservera le nombre de 1 bits chaque fois que y est une puissance de 2 supérieure à n'importe quel coefficient, ce qui est vrai pour la valeur choisie ci-dessus. On choisit y = 2 ^ (f (2)!) Pour rendre le résultat injectif:

• Deux entrées différentes avec la même valeur de y donneront des sorties différentes car nous lisons essentiellement deux nombres différents dans la base y.
• Si nous fixons k = f (2) et donc y, la plus petite valeur de y * f (y) est obtenue lorsque l'entrée est un polynôme constant égal à k et la plus grande valeur est atteinte lorsque l'entrée est le polynôme donnant la base -2 expansion de k. Dans le premier cas, y * f (y) = 2 ^ (k!) * K, et dans le second cas, y * f (y) <2 ^ (k! * Ceil (lg k)), ce qui est moins que 2 ^ ((k + 1)!) * (k + 1).
• Par conséquent, pour deux polynômes f et g avec f (2) <g (2), l'entier que nous obtenons de f sera inférieur à l'entier que nous obtenons de g.

Wolfram Language (Mathematica) , 61 octets

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

Essayez-le en ligne!

Deux entiers positifs peuvent être mappés sur un seul entier positif. Soit a, bdeux entiers positifs. alorsa, b -> (2a - 1) 2^(b-1) , est une bijection de NxN à N.

Cette fonction trouve la position de tous 1 bits dans l'entrée (à partir de la position 1) et applique une variante uniquement injective de la carte ci-dessus à chaque position. Ensuite, chaque nombre résultant est élevé à la puissance de deux, et tous les nombres sont additionnés (ce qui est correct puisque nous avons appliqué une carte NxN -> N injective).

Par exemple:

{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 *)

Fonction inverse (124 octets)

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

Voici une fonction inverse pour tester l'injectivité.

Essayez-le en ligne!

Python 2 , 118 117 114 103 100 octets

100 octets de 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)

Essayez-le en ligne!

103 octets avec possibilité de jouer au golf ¹

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

Essayez-le en ligne!

-15 octets grâce à Jonathan Frech

Il crée un nombre qui contient d'abord les "sur bits" puis la représentation unaire du tableau interprétée comme un nombre trinaire.

Le nombre trinaire est créé en convertissant les nombres en chaînes binaires ( 0bNNN), puis en les remplaçant bpar 2.

¹ J'aurais pu économiser 14 octets en le convertissant à la place en un nombre de base 12, mais TIO a manqué de mémoire, j'ai donc décidé de l'utiliser.

05AB1E , 14 octets

gÅpImPoIbS{2β*

Essayez-le en ligne!

Donne les mêmes résultats que la solution de gelée de Dennis, mais la technique est légèrement différente.

Comment?

Essayons l'entrée [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 octets

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

Essayez-le en ligne!

JavaScript 6, 96 83 octets

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

génère une expression binaire

([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)