Contexte

La plupart des gens ici devraient être familiers avec quelques systèmes de base entiers: décimal, binaire, hexadécimal, octal. Par exemple, dans le système hexadécimal, un nombre abc.de ₁₆ représenterait

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

Cependant, on peut également utiliser des bases non entières, comme des nombres irrationnels. Une fois que cette base utilise le nombre d' or φ = (1 + √5) / 2 ≈ 1,618 ... . Celles-ci sont définies de manière analogue aux bases entières. Ainsi, un nombre abc.de _φ (où a à e sont des chiffres entiers) représenterait

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

Notez qu'en principe, n'importe lequel des chiffres peut être négatif (bien que nous n'y soyons pas habitués) - nous représenterons un chiffre négatif avec un interligne ~. Aux fins de cette question, nous nous limitons aux chiffres de ~9à 9, afin que nous puissions écrire sans ambiguïté un nombre sous la forme d'une chaîne (avec des tildes entre les deux). Alors

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

serait écrit comme ~290.~43. Nous appelons un tel numéro un numéro phinaire .

Un nombre phinaire peut toujours être représenté sous une forme standard , ce qui signifie que la représentation n'utilise que des chiffres 1et 0, sans contenir 11nulle part, et avec un signe moins facultatif pour indiquer que le nombre entier est négatif. (Fait intéressant, chaque entier a une représentation finie unique sous forme standard.)

Les représentations qui ne sont pas sous forme standard peuvent toujours être converties en forme standard en utilisant les observations suivantes:

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

En plus:

4. Si le chiffre le plus significatif est ~1(avec le reste du nombre sous forme standard), le nombre est négatif, et nous pouvons le convertir en forme standard en échangeant tous 1et ~1en ajoutant un signe moins et en appliquant à nouveau les trois règles ci-dessus jusqu'à ce que nous obtenir le formulaire standard.

Voici un exemple d'une telle normalisation de (j'utilise des espaces supplémentaires pour les chiffres positifs, pour garder chaque position de chiffre alignée): 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)

Céder .-0.0101φ

Pour une lecture plus approfondie, Wikipedia a un article très informatif sur le sujet.

Le défi

Par conséquent, ou autrement, écrivez un programme ou une fonction qui, étant donné une chaîne représentant un nombre phinaire (comme décrit ci-dessus), sort sa forme standard, sans zéros de début ou de fin. L'entrée ne contient pas nécessairement le point phinaire, mais contiendra toujours le chiffre restant (donc non .123). La sortie doit toujours inclure le point phinaire et au moins un chiffre à sa gauche.

Vous pouvez saisir des données via STDIN, ARGV ou un argument de fonction et renvoyer le résultat ou l'imprimer dans STDOUT.

Vous pouvez utiliser un algorithme différent de la procédure ci-dessus tant qu'il est en principe correct et exact pour des entrées arbitraires (valides) - c'est-à-dire que les seules limites qui pourraient potentiellement casser votre implémentation devraient être des limitations techniques comme la taille de la fonction intégrée types de données ou la mémoire RAM disponible. Par exemple, l'évaluation de l'entrée en tant que nombre à virgule flottante, puis la sélection goulue de chiffres n'est pas autorisée, car on pourrait trouver des entrées pour lesquelles des inexactitudes en virgule flottante conduiraient à des résultats incorrects.

C'est le golf de code, la réponse la plus courte (en octets) l'emporte.

Cas de test

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 octets

Minifié:

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

Étendu:

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

Le code produit une fonction Fqui effectue la conversion spécifiée.

C'est un problème difficile pour le golf. De nombreux cas marginaux surgissent qui empêchent la simplification du code. En particulier, le traitement des négatifs est une douleur, à la fois en termes d'analyse et en termes de gestion logique.

Je dois noter que le code ne gère qu'une "plage raisonnable" d'entrées. Pour étendre le domaine de la fonction sans limite, le nombre de zéros zpeut être augmenté et la constante délimitant la while( c++ < 99 )boucle peut être augmentée. La gamme actuellement prise en charge est déjà excessive pour les cas de test fournis.

Exemples de sorties

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

Ce -0.n'est pas joli, mais la réponse est toujours correcte. Je peux le réparer si nécessaire.

Haskell, 336 octets

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

Il s'agit de l'algorithme gourmand, mais avec une représentation exacte [a,b]des nombres a + bφ ( a , b ∈ ℤ) pour éviter les erreurs en virgule flottante. g[a,b]teste si a + bφ <0. Exemple d'utilisation:

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