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,
9
está1001
en binario, por lo que tiene 21
bits.
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:
Si bien agregar un cero al final de un polinomio no cambia su valor:
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:
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 código de golf, por lo que las respuestas se puntuarán en bytes, con menos bytes mejor.
[]
o[0]
una entrada válida?Respuestas:
Jalea , 8 bytes
Pruébalo en línea!
Izquierda inversa, 5 bytes
Pruébalo en línea!
Cómo funciona
fuente
Wolfram Language (Mathematica) ,
3620 bytesPrué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:
fuente
Wolfram Language (Mathematica) , 61 bytes
Pruébalo en línea!
Se pueden asignar dos enteros positivos a un solo entero positivo. Dejado
a, b
ser dos enteros positivos. Entoncesa, b -> (2a - 1) 2^(b-1)
es una biyección de NxN a N.Esta función encuentra la posición de todos los
1
bits 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:
Función inversa (124 bytes)
Aquí hay una función inversa para probar la inyectividad.
Pruébalo en línea!
fuente
Python 2 ,
118117114103100 bytes100 bytes por Jonathan Frech:
Pruébalo en línea!
103 bytes con posibilidad de jugar al golf 1
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ándolob
por2
.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.
fuente
05AB1E , 14 bytes
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]
:fuente
Python 2 , 74 bytes
Pruébalo en línea!
fuente
JavaScript 6,
9683 Bytesgenera una expresión binaria
fuente
replace(/0|2/g,0)
también parece funcionar, pero es más difícil de decodificarx=>(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