Hotel binario de Hilbert

18

En este desafío, se le pedirá que implemente cualquier función (o programa completo) que cumpla dos propiedades. Esas propiedades son:

  • Su función debe ser una función inyectiva (reversible) desde los polinomios con coeficientes enteros no negativos hasta los enteros no negativos. Esto significa que no hay dos entradas desiguales que puedan asignarse a una salida igual.

  • Su función debe preservar el número total de "en bits" desde su entrada hasta su salida. Esto significa que si cuenta los 1 bits de cada coeficiente del polinomio, su suma debe ser la misma que el número de 1 bits en la representación binaria de la salida. Por ejemplo, 9está 1001en binario, por lo que tiene 2 1bits.


IO

Un polinomio entero no negativo es lo mismo que una lista infinita de enteros no negativos, de modo que después de cierto punto todos los enteros son cero. Por lo tanto, los polinomios pueden estar representados por listas infinitas (aunque esto probablemente no sea deseable) o por listas finitas con ceros implícitos después del final de la lista.

La distinción clave entre polinomios y listas finitas es que agregar un cero al final de una lista cambiará la lista:

Liza

Si bien agregar un cero al final de un polinomio no cambia su valor:

Polinomios

Por lo tanto, si su función toma una lista finita que representa un polinomio como entrada, agregar un cero no debe cambiar su resultado.

Al representar polinomios como listas, puede representarlos con la primera o la última entrada que representa el término constante. Por ejemplo, podría tener cualquiera de las siguientes posibilidades:

Hacia adelante o hacia atrás

En el primer caso, agregar ceros al final de la lista no debería cambiar el resultado; en el segundo caso, agregar ceros al principio de la lista no debería cambiar el resultado.

Por supuesto, si su idioma admite polinomios, puede tomarlos como entradas.

La salida debe ser una salida entera no negativa a través de cualquier método estándar.


Este es el por lo que las respuestas se puntuarán en bytes, con menos bytes mejor.

Asistente de trigo
fuente
¿Es []o [0]una entrada válida?
JungHwan Min
1
@JungHwanMin Sí, ambos son, son el polinomio cero.
Wheat Wizard
Yo sé que quiere decir poner 1 para dividir ceros, pero algunas formas de utilización podrán trabajar y no parece tan bueno ...
l4m2
1
@ l4m2 Lo siento, pero no entiendo ninguno de sus comentarios. En lo que respecta a su pregunta, ¿poner ceros en qué? El polinomio, los coeficientes? Tampoco estoy seguro de lo que quieres decir con "ceros no escritos".
Wheat Wizard
1
¿Son realmente necesarias las imágenes (es decir, no se pueden representar con texto enriquecido)? Porque las personas sin la capacidad de ver imágenes no pueden ver su desafío en su totalidad.
Mindwin

Respuestas:

6

Jalea , 8 bytes

BFṢḄæ«ÆẸ

Pruébalo en línea!

Izquierda inversa, 5 bytes

Bċ0ÆE

Pruébalo en línea!

Cómo funciona

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
fuente
6

Wolfram Language (Mathematica) , 36 20 bytes

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

Pruébalo en línea!

Toma un polinomio f (x) como entrada. Evalúa y * f (y), donde y = 2 ^ (f (2)!). Lamentablemente, esto significa que las salidas se vuelven bastante grandes.

La evaluación de y * f (y) preservará el número de 1 bits siempre que y sea una potencia de 2 mayor que cualquier coeficiente, lo cual es cierto para el valor elegido anteriormente. Elegimos y = 2 ^ (f (2)!) Para que el resultado sea inyectivo:

  • Dos entradas diferentes con el mismo valor de y darán salidas diferentes porque esencialmente estamos leyendo dos números diferentes en la base y.
  • Si fijamos k = f (2) y, por lo tanto, y, el valor más pequeño de y * f (y) se logra cuando la entrada es un polinomio constante igual a k y el valor más grande se alcanza cuando la entrada es el polinomio que da la base -2 expansión de k. En el primer caso, y * f (y) = 2 ^ (k!) * K, y en el segundo caso, y * f (y) <2 ^ (k! * Ceil (lg k)), que es menor que 2 ^ ((k + 1)!) * (k + 1).
  • Como resultado, para dos polinomios f y g con f (2) <g (2), el entero que obtenemos de f será menor que el entero que obtenemos de g.
Misha Lavrov
fuente
5

Wolfram Language (Mathematica) , 61 bytes

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

Pruébalo en línea!

Se pueden asignar dos enteros positivos a un solo entero positivo. Dejado a, bser dos enteros positivos. Entonces a, b -> (2a - 1) 2^(b-1)es una biyección de NxN a N.

Esta función encuentra la posición de todos los 1bits en la entrada (desde el lugar 1), y aplica una variante de solo inyección del mapa anterior a cada posición. Luego, cada número resultante se eleva a la potencia de dos, y todos los números se suman (lo cual está bien ya que aplicamos un mapa inyectivo NxN -> N).

Por ejemplo:

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

Función inversa (124 bytes)

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

Aquí hay una función inversa para probar la inyectividad.

Pruébalo en línea!

JungHwan Min
fuente
5

Python 2 , 118 117 114 103 100 bytes

100 bytes por 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)

Pruébalo en línea!

103 bytes con posibilidad de jugar al golf 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)

Pruébalo en línea!

-15 bytes gracias a Jonathan Frech

Crea un número que primero contiene los "bits" y luego la representación unaria de la matriz interpretada como un número trinario.

El número trinario se crea convirtiendo los números en cadenas binarias ( 0bNNN), y luego reemplazándolo bpor 2.

1 Podría haber guardado 14 bytes al convertirlo en un número base 12, pero TIO se quedó sin memoria, así que decidí usar esto.

fergusq
fuente
@JonathanFrech Muchas gracias :)
fergusq
1

05AB1E , 14 bytes

gÅpImPoIbS{2β*

Pruébalo en línea!

Produce los mismos resultados que la solución Jelly de Dennis, pero la técnica es ligeramente diferente.

¿Cómo?

Probemos la entrada [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).
Sr. Xcoder
fuente
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)

genera una expresión binaria

([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
fuente
cero dará lugar a una cadena vacía que representa cero
l4m2
replace(/0|2/g,0)también parece funcionar, pero es más difícil de decodificar
l4m2
No estoy seguro x=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/2/g,'0'.repeat(t)). Siéntete bien pero no puedo probarlo
l4m2