fundo

A maioria das pessoas aqui deve estar familiarizada com alguns sistemas básicos inteiros: decimal, binário, hexadecimal, octal. Por exemplo, no sistema hexadecimal, um número abc.de ₁₆ representaria

a*16^2 + b*16^1 + c*16^0 + d*16^-1 + e*16^-2

No entanto, também é possível usar bases não inteiras, como números irracionais. Uma vez que tal base utiliza a razão de ouro φ = (1 + √5) / 2 ... ≈ 1.618 . Estes são definidos analogamente às bases inteiras. Portanto, um número abc.de _φ (onde a a e são dígitos inteiros) representaria

a*φ^2 + b*φ^1 + c*φ^0 + d*φ^-1 + e*φ^-2

Observe que, em princípio, qualquer um dos dígitos pode ser negativo (embora não estamos acostumados a isso) - representaremos um dígito negativo com um avanço ~. Para os fins desta pergunta, restringimos-nos a dígitos de ~9para 9, para que possamos escrever inequivocamente um número como uma sequência (com os tons no meio). tão

-2*φ^2 + 9*φ^1 + 0*φ^0 + -4*φ^-1 + 3*φ^-2

seria escrito como ~290.~43. Chamamos esse número de número finário .

Um número finário sempre pode ser representado no formato padrão , o que significa que a representação usa apenas dígitos 1e 0, sem conter 11nenhum lugar, e com um sinal de menos opcional para indicar que o número inteiro é negativo. (Curiosamente, todo número inteiro tem uma representação finita exclusiva na forma padrão.)

As representações que não estão no formato padrão sempre podem ser convertidas no formato padrão usando as seguintes observações:

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

Além do que, além do mais:

4. Se o dígito mais significativo for ~1(com o restante do número no formato padrão), o número é negativo e podemos convertê-lo no formato padrão trocando all 1e~1 , acrescentando um sinal de menos, e aplicando as três regras acima novamente até que obtenha o formulário padrão.

Aqui está um exemplo dessa normalização de (estou usando espaços adicionais para dígitos positivos, para manter cada posição de dígito alinhada): 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)

Produzindo -0.0101φ .

Para ler mais, a Wikipedia tem um artigo muito informativo sobre o assunto.

O desafio

Portanto, ou de outra forma, escreva um programa ou função que, dada uma sequência que representa um número finário (como descrito acima), produz sua forma padrão, sem zeros à esquerda ou à direita. A entrada não contém necessariamente o ponto finário, mas sempre conterá o dígito restante (portanto, não.123 ). A saída deve sempre incluir o ponto finário e pelo menos um dígito à esquerda dele.

Você pode receber entradas via STDIN, ARGV ou argumento de função e retornar o resultado ou imprimi-lo em STDOUT.

Você pode usar um algoritmo diferente do procedimento acima, desde que, em princípio, seja correto e exato para entradas arbitrárias (válidas) - ou seja, os únicos limites que podem potencialmente interromper sua implementação devem ser limitações técnicas, como o tamanho dos componentes internos. tipos de dados ou a RAM disponível. Por exemplo, avaliar a entrada como um número de ponto flutuante e, em seguida, selecionar dígitos com avidez não é permitido, pois é possível encontrar entradas para as quais as imprecisões do ponto flutuante levariam a resultados incorretos.

Este é o código golf, a resposta mais curta (em bytes) vence.

Casos de teste

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

Javascript (ES6) - 446 418 422 420 bytes

Minificado:

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, '' );
}

O código produz uma função Fque executa a conversão especificada.

É um problema difícil para o golfe. Inúmeros casos extremos surgem que impedem a simplificação do código. Em particular, lidar com negativos é uma dor, tanto em termos de análise quanto em termos de manipulação lógica.

Devo observar que o código lida apenas com um "intervalo razoável" de entradas. Para estender o domínio da função sem limite, o número de zeros em zpode ser aumentado e a constante delimitadora do while( c++ < 99 )loop pode ser aumentada. O intervalo atualmente suportado já é um exagero para os casos de teste fornecidos.

Saídas de amostra

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

O -0.não é bonito, mas a resposta ainda está correta. Eu posso consertar se necessário.

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 é o algoritmo guloso, mas com uma representação exata [a,b]dos números a + bφ ( a , b ∈ ℤ) para evitar erros de ponto flutuante. g[a,b]testa se a + bφ <0. Exemplo de uso:

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