Estandarizar un número finario

32

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 ~9a 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 1y 0, sin contener 11ningú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:

  1. 011 φ = 100 φ (porque φ 2 = φ + 1)
  2. 0200 φ = 1001 φ (porque φ 2 + 1 / φ = 2φ)
  3. 0 ~ 10 φ = ~ 101 φ (porque φ - 1 / φ = 1)

Adicionalmente:

  1. 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 todo 1y ~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
Martin Ender
fuente
¡Ahora quiero usar dígitos negativos en mis números! 1 ~ 3 * 6 == 5 ~ 8
Aaron

Respuestas:

6

Javascript (ES6) - 446 418 422 420 bytes

Minified:

F=s=>{D=[];z='000000000';N=t=n=i=e=0;s=(z+s.replace(/^([^.]*)$/,'$1.')+z).replace(/~/g,'-').replace(/-?\d/g,s=>((D[n++]=s/1),0));for(;i<n-3;i=j){if(p=D[j=i+1]){if(!e&&p<0){D=D.map(k=>-k);N=~N;p=-p}e=1}d=D[i];x=D[i+2];m=D[i+3];if(p<0){d--;p++;x++;e=j=0}if(p>1){d++;m++;p-=2;e=j=0}if(!d&&p*x==1){d=p;e=j=p=x=0}D[i]=d;D[i+1]=p;D[i+2]=x;D[i+3]=m}return(N?'-':'')+s.replace(/0/g,()=>D[t++]).replace(/^(0(?!\.))+|0+$/g,'')}

Expandido:

F = s => {
    D = [];
    z = '000000000';
    N = t = n = i = e = 0;
    s = (z + s.replace( /^([^.]*)$/, '$1.' ) + z).replace( /~/g, '-' ).
        replace( /-?\d/g, s => ((D[n++]=s/1),0) );

    for( ; i < n-3; i = j ) {
        if( p = D[j = i+1] ) {
            if( !e && p < 0 ) {
                D = D.map( k=>-k );
                N = ~N;
                p = -p;
            }
            e = 1;
        }
        d = D[i];
        x = D[i+2];
        m = D[i+3];

        if( p < 0 ) {
            d--;
            p++;
            x++;
            e = j = 0;
        }
        if( p > 1 ) {
            d++;
            m++;
            p-=2;
            e = j = 0;
        }
        if( !d && p*x == 1 ) {
            d = p;
            e = j = p = x = 0;
        }

        D[i] = d;
        D[i+1] = p;
        D[i+2] = x;
        D[i+3] = m;
    }

    return (N ? '-' : '') + s.replace( /0/g, ()=>D[t++] ).replace( /^(0(?!\.))+|0+$/g, '' );
}

El código produce una función Fque 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, zse puede aumentar el número de ceros en , y se puede aumentar el límite constante del while( c++ < 99 )bucle. El rango actualmente admitido ya es excesivo para los casos de prueba suministrados.

Resultados de muestra

F('1')          1.
F('9')          10010.0101
F('1~3.2~1')    -0.0101
F('0.~1021')    -0.
F('105.~2')     1010.0101
F('~31~5.~1')   -100000.1001

El -0.no es bonito, pero la respuesta sigue siendo correcta. Puedo arreglarlo si es necesario.

COTO
fuente
@ MartinBüttner: Podría, pero sería difícil. Limita el número de "pasadas" sobre la entrada completa, y cada pasada comprende varias operaciones. Mi intuición es que el número de pasadas requeridas para normalizar cualquier nentrada de dígitos sería entre ny n 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 la zconstante también es un problema interesante. Sospecho que 9 es excesivo para cualquier entrada posible.
COTO
@ MartinBüttner: Gracias. Eliminé el escape en la clase de personaje. En cuanto a $0, Javascript no lo admite. O al menos Firefox no. : P
COTO
De acuerdo, creo que nunca necesitarás más de 7 ceros iniciales como buffer, pero creo que los ceros finales serán un poco más difíciles de estimar. En cuanto al bucle externo, no creo que necesite eso, si solo lo hace un bucle while (o lo integra en el bucle for interno) y se rompe cuando no se encuentran más cambios. Supongo que mi especificación podría haber sido un poco más clara a ese respecto, pero "en principio correcto y exacto para entradas arbitrarias (válidas)" quise decir que el único límite teórico debería ser el tamaño de sus tipos de datos incorporados / su RAM.
Martin Ender
1
@COTO Para guardar 1 byte, puede intentar mover la primera parte del for( i = e = 0; i < n-3; i = j )by for(; i < n-3; i = j )y mover las declaraciones a la parte superior, siendo N = t = n = 0;reemplazado porN = t = n = i = e = 0;
Ismael Miguel el
1
@IsmaelMiguel: jno se mantiene constante en un valor de i+1. Aviso en los tres ifbloques, jse restablece a 0. Por lo tanto, en cualquier punto después del primer ifbloque, no se puede usar como proxy i+1. La variable en isí no se puede actualizar hasta el final del ciclo (usando la tercera instrucción en for) 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. :)
COTO
2

Haskell, 336 bytes

z=[0,0]
g[a,b]|a*b<0=g[b,a+b]
g x=x<z
k![a,b,c,d]=[b,a+b,d-c+read k,c]
p('.':s)=1:0:2`drop`p s
p('~':k:s)=['-',k]!p s
p(k:s)=[k]!p s
p[]=1:0:z
[1,0]&y='.':z?y
[a,b]&y=[b,a+b]?y
x@[a,b]?y@[c,d]|x==z,y==z=""|g y='-':x?[-c,-d]|g[c-1,d]='0':x&[d,c+d]|g[c,d-1]='1':x&[d,c+d-1]|0<1=[b-a,a]?[d-c,c]
m[a,b,c,d]=[1,0]?[a*d+b*c-a*c,a*c+b*d]
f=m.p

Este es el algoritmo codicioso, pero con una representación exacta [a,b]de los números a + ( a , b ∈ ℤ) para evitar errores de coma flotante. g[a,b]prueba si a + <0. Ejemplo de uso:

*Main> f "9"
"10010.0101"
*Main> f "1~3.2~1"
"-0.0101"
*Main> f "0.~1021"
"0."
Anders Kaseorg
fuente