Padronizar um número finário

32

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 16 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 φ 2 = φ + 1)
  2. 0200 φ = 1001 φ (porque φ 2 + 1 / φ = 2φ)
  3. 0 ~ 10 φ = ~ 101 φ (porque φ - 1 / φ = 1)

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

  1. 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
Martin Ender
fonte
Agora eu quero usar dígitos negativos nos meus números! 1 ~ 3 * 6 == 5 ~ 8
Aaron

Respostas:

6

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.

COTO
fonte
@ MartinBüttner: Você poderia, mas seria difícil. Limita o número de "passes" sobre a entrada completa e cada passe compreende várias operações. Minha intuição é que o número de passes necessários para normalizar qualquer nentrada de -dígitos estaria entre ne n log(n). De qualquer forma, o número de passes pode ser aumentado em um fator de 10 para cada caractere adicionado. O número de zeros na zconstante também é um problema interessante. Eu suspeito que 9 é um exagero para qualquer entrada possível.
COTO 16/09
@ MartinBüttner: Obrigado. Eu removi a fuga na classe de personagem. Quanto ao $0Javascript não o suporta. Ou pelo menos o Firefox não. : P
COTO
Ok, acho que você nunca precisa de mais de 7 zeros à esquerda como buffer, mas acho que os zeros à direita serão um pouco mais difíceis de estimar. Quanto ao loop externo, acho que você nem precisa disso, se você fizer um loop while (ou integrá-lo ao loop for interno) e apenas sair quando não houver mais alterações. Acho que minhas especificações poderiam ter sido um pouco mais claras a esse respeito, mas por "em princípio corretas e exatas para entradas arbitrárias (válidas)", quis dizer que o único limite teórico deveria ser o tamanho dos seus tipos de dados internos / sua RAM.
Martin Ender
11
@COTO Para salvar 1 byte, você pode tentar mover a primeira parte do for( i = e = 0; i < n-3; i = j )pelo for(; i < n-3; i = j )e mover as declarações para o topo, sendo N = t = n = 0;substituído porN = t = n = i = e = 0;
Ismael Miguel
11
@IsmaelMiguel: jnão é mantido constante no valor de i+1. Observe nos três ifblocos, jé redefinido para 0. Portanto, a qualquer momento após o primeiro ifbloco, ele não pode ser usado como proxy i+1. A variável em isi não pode ser atualizada até o final do loop (usando a terceira instrução in for), pois seu valor é usado até o final do loop. Mas, tendo dito isso, talvez esteja perdendo alguma coisa. Se você puder encurtar o código, testá-lo e verificar se ele ainda funciona, poste uma cópia em pastebin.com e um link aqui. Estenderei o devido crédito a você na resposta. :)
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 é o algoritmo guloso, mas com uma representação exata [a,b]dos números a + ( a , b ∈ ℤ) para evitar erros de ponto flutuante. g[a,b]testa se a + <0. Exemplo de uso:

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