Basado en la notación "binaria, pero con dos" mencionada en este video de número numérico , escriba una función que tome un solo número como entrada y genere todas las variaciones de ese número en un sistema "binario" donde se permiten dos.
Reglas
- El código solo debe ser una función / método, no un programa completo
- La entrada es un número entero pasado como el único parámetro para la función
- La salida es todas las variaciones válidas del número de entrada convertido a notación "binaria, pero con dos"
- La salida es el valor de retorno de la función, pero puede estar en cualquier formato que sea conveniente siempre que sea obvio (por ejemplo, 3 ints, 3 cadenas, cadena delimitada por comas / espacios, matriz de entradas, etc.), el orden no es importante
- En el caso improbable de que un idioma contenga una función incorporada para lograr el resultado, no se permite
- El código más corto en bytes es el ganador
Explicación de la salida.
Por ejemplo, si se le pasa el número 9
, puede convertirlo en binario como 1001
, pero si permitió 2
s en cada posición, también podría escribirlo como 201
(es decir 2*4 + 0*2 + 1*1
) o 121
(es decir 1*4 + 2*2 + 1*1
), como se muestra en esta tabla:
+----+----+----+----+
| 8s | 4s | 2s | 1s |
+----+----+----+----+
| 1 | 0 | 0 | 1 |
| 0 | 2 | 0 | 1 |
| 0 | 1 | 2 | 1 |
+----+----+----+----+
Entonces, si se aprueba 9
, su función necesitaría devolver los tres números 1001
, 201
y 121
.
Formato y el orden son irrelevantes, tanto tiempo como es obvio (es decir [121,201,1001]
, "0201 0121 1001"
, ("1001","121","201")
son resultados válidos cuando dada una entrada de 9
).
Ejemplos
2
=>10, 2
9
=>1001, 201, 121
10
=>1010, 210, 202, 1002, 122
23
=>2111, 10111
37
=>100101, 20101, 100021, 20021, 12101, 12021, 11221
fuente
Respuestas:
GolfScript (25 bytes) / CJam (
1917 bytes)GolfScript:
Esto crea una función anónima (ver meta discusión sobre la permisibilidad de las funciones anónimas ).
Demostración en línea
Una traducción directa a CJam es (gracias a Martin Büttner por afeitar un par de caracteres)
Disección
La razón de la operación de cuadratura es que necesitamos iterar hasta el mayor valor posible cuya representación ternaria, interpretada en binario, sea igual a
^
. Desde entonces2 = 10
, la representación binaria "normal" de^
es la que importa. Si convertimos eso a ternario, encontramos que los "peores" casos son poderes de 2. Un enfoque óptimo sería llevar el argumento al poder deln 3/ln 2 ~= 1.585
, pero la cuadratura es mucho más corta.fuente
Python 2 (59 bytes)
(Muchas gracias a @grc, @xnor y @PeterTaylor por ayudar en el chat)
Recurrencia simple, llamada con
S(23)
o similar.Explicación
La idea general es que si
n
la expansión binaria termina en a1
, entonces cualquier expansión pseudobinaria ("binaria, pero con dos") también debe terminar con a1
. De lo contrario, podría terminar con0
o2
.Por lo tanto, miramos el último bit de
n
, dividir y ramificar en consecuencia.Disección
Variables:
n
: El número que queremos encontrar expansiones pseudobinarias deB
: Una cadena pseudobinaria que se construye de derecha a izquierdafuente
Bash + coreutils, 77
(Ese es un TABpersonaje en la expresión grep).
Esto está doblando un poco esta regla:
"En el improbable caso de que un idioma contenga una función incorporada para lograr el resultado, no se permite"
Resulta que
dc
tiene el reverso de lo que necesitamos incorporado. Por ejemplo, si establecemos la base de entrada en 2 e ingresamos un número binario con dos, lo analizará correctamente. (Del mismo modo, si el modo de entrada es base 10, AF se analiza como "dígitos" decimales 10-15).seq
crea una lista de todos los números decimales hasta la representación binaria estándar de n, analizada como decimal. Luego, todos los números que contienen algo distinto de {0,1,2} se filtran. Luegodc
analiza los números restantes como binarios para ver cuáles evalúan de nuevo a n.Las funciones Bash solo pueden "devolver" enteros escalares 0-255. Así que me tomo la libertad de imprimir la lista en STDOUT como mi forma de "regresar". Esto es idiomático para los scripts de shell.
Salida:
fuente
Haskell, 82
Esta es solo una solución de fuerza bruta. es muy ineficiente porque se espera que supere las 3 ^ n posibilidades.
fuente
Jelly , 10 bytes, desafío de fechas posteriores al idioma
Pruébalo en línea!
Una solución de fuerza bruta de hasta un número de hiperbits igual a la entrada (este formato se conoce como "hiperbinario"). Como tal, es increíblemente ineficiente, ejecutándose en O (3 n ).
Explicación
fuente
PHP, 138 bytes
Descompostura
fuente
C ++, 159 bytes
Pruébalo aquí
fuente
k, 21 bytes
Utiliza el mismo método que la respuesta Golfscript de Peter Taylor
Ejemplos:
fuente