Fondo
La mayoría de las personas aquí deberían estar familiarizadas con algunos sistemas de base entera: decimal, binario, hexadecimal, octal. Por ejemplo, en el sistema hexadecimal, un número abc.de 16 representaría
a*16^2 + b*16^1 + c*16^0 + d*16^-1 + e*16^-2
Sin embargo, también se pueden usar bases no enteras, como números irracionales. Una vez que tal base utiliza la proporción de oro φ = (1 + √5) / 2 ≈ 1,618 ... . Estos se definen de forma análoga a las bases enteras. Entonces, un número abc.de φ (donde a a e son dígitos enteros) representaría
a*φ^2 + b*φ^1 + c*φ^0 + d*φ^-1 + e*φ^-2
Tenga en cuenta que, en principio, cualquiera de los dígitos podría ser negativo (aunque no estamos acostumbrados a eso): representaremos un dígito negativo con un interlineado ~
. A los fines de esta pregunta, nos restringimos a los dígitos de ~9
a 9
, por lo que podemos escribir sin ambigüedad un número como una cadena (con tildes en el medio). Asi que
-2*φ^2 + 9*φ^1 + 0*φ^0 + -4*φ^-1 + 3*φ^-2
se escribiría como ~290.~43
. Llamamos a ese número un número finario .
Un número phinary siempre se puede representar en forma estándar , lo que significa que la representación usa solo dígitos 1
y 0
, sin contener 11
ningún lugar, y con un signo menos opcional para indicar que todo el número es negativo. (Curiosamente, cada entero tiene una representación finita única en forma estándar).
Las representaciones que no están en forma estándar siempre se pueden convertir en forma estándar utilizando las siguientes observaciones:
- 011 φ = 100 φ (porque φ 2 = φ + 1)
- 0200 φ = 1001 φ (porque φ 2 + 1 / φ = 2φ)
- 0 ~ 10 φ = ~ 101 φ (porque φ - 1 / φ = 1)
Adicionalmente:
- Si el dígito más significativo es
~1
(con el resto del número en forma estándar), el número es negativo, y podemos convertirlo en forma estándar intercambiando todo1
y~1
, anteponiendo un signo menos, y aplicando las tres reglas anteriores nuevamente hasta que Obtenga el formulario estándar.
Aquí hay un ejemplo de tal normalización de (estoy usando espacios adicionales para dígitos positivos, para mantener alineada la posición de cada dígito):
1~3.2~1φ
1~3. 2~1φ Rule:
= 0~2. 3~1φ (3)
= ~1~1. 4~1φ (3)
= ~1 0 0. 4~1φ (3)
= ~1 0 0. 3 0 1φ (3)
= ~1 0 1. 1 0 2φ (2)
= ~1 1 0. 0 0 2φ (1)
= ~1 1 0. 0 1 0 0 1φ (2)
= - 1~1 0. 0~1 0 0~1φ (4)
= - 0 0 1. 0~1 0 0~1φ (3)
= - 0 0 1.~1 0 1 0~1φ (3)
= - 0 0 0. 0 1 1 0~1φ (3)
= - 0 0 0. 0 1 1~1 0 1φ (3)
= - 0 0 0. 0 1 0 0 1 1φ (3)
= - 0 0 0. 0 1 0 1 0 0φ (1)
Produciendo .-0.0101φ
Para leer más, Wikipedia tiene un artículo muy informativo sobre el tema.
El reto
Por lo tanto, o de lo contrario, escriba un programa o función que, dada una cadena que representa un número phinary (como se describió anteriormente), genera su forma estándar, sin ceros iniciales o finales. La entrada no contiene necesariamente el punto phinary, pero siempre contendrá el dígito a la izquierda del mismo (por lo que no .123
). La salida siempre debe incluir el punto phinary y al menos un dígito a la izquierda del mismo.
Puede recibir información a través de STDIN, ARGV o argumento de función y devolver el resultado o imprimirlo en STDOUT.
Puede usar un algoritmo diferente al procedimiento anterior siempre que sea, en principio, correcto y exacto para entradas arbitrarias (válidas), es decir, los únicos límites que podrían interrumpir su implementación deberían ser limitaciones técnicas como el tamaño del incorporado tipos de datos o la RAM disponible. Por ejemplo, no está permitido evaluar la entrada como un número de punto flotante y luego seleccionar dígitos con avidez, ya que uno podría encontrar entradas para las cuales las imprecisiones de punto flotante conducirían a resultados incorrectos.
Este es el código de golf, gana la respuesta más corta (en bytes).
Casos de prueba
Input Output
1 1.
9 10010.0101
1.618 10000.0000101
1~3.2~1 -0.0101
0.~1021 0. (or -0.)
105.~2 1010.0101
~31~5.~1 -100000.1001
fuente
Respuestas:
Javascript (ES6) -
446418422420 bytesMinified:
Expandido:
El código produce una función
F
que realiza la conversión especificada.Es un problema difícil para el golf. Se presentan numerosos casos extremos que impiden la simplificación del código. En particular, lidiar con los negativos es un dolor, tanto en términos de análisis como en términos de manejo lógico.
Debo señalar que el código solo maneja un "rango razonable" de entradas. Para extender el dominio de la función sin límite,
z
se puede aumentar el número de ceros en , y se puede aumentar el límite constante delwhile( c++ < 99 )
bucle. El rango actualmente admitido ya es excesivo para los casos de prueba suministrados.Resultados de muestra
El
-0.
no es bonito, pero la respuesta sigue siendo correcta. Puedo arreglarlo si es necesario.fuente
n
entrada de dígitos sería entren
yn log(n)
. En cualquier caso, el número de pases se puede aumentar en un factor de 10 por cada personaje agregado. El número de ceros en laz
constante también es un problema interesante. Sospecho que 9 es excesivo para cualquier entrada posible.$0
, Javascript no lo admite. O al menos Firefox no. : Pfor( i = e = 0; i < n-3; i = j )
byfor(; i < n-3; i = j )
y mover las declaraciones a la parte superior, siendoN = t = n = 0;
reemplazado porN = t = n = i = e = 0;
j
no se mantiene constante en un valor dei+1
. Aviso en los tresif
bloques,j
se restablece a0
. Por lo tanto, en cualquier punto después del primerif
bloque, no se puede usar como proxyi+1
. La variable eni
sí no se puede actualizar hasta el final del ciclo (usando la tercera instrucción enfor
) ya que su valor se usa hasta el final del ciclo. Pero habiendo dicho eso, tal vez me estoy perdiendo algo. Si puede acortar el código, probarlo y verificar que todavía funciona, publique una copia en pastebin.com y un enlace aquí. Te extenderé el debido crédito en la respuesta. :)Haskell, 336 bytes
Este es el algoritmo codicioso, pero con una representación exacta
[a,b]
de los números a + bφ ( a , b ∈ ℤ) para evitar errores de coma flotante.g[a,b]
prueba si a + bφ <0. Ejemplo de uso:fuente