Standardiser un numéro phinaire

32

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

En plus:

  1. 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
Martin Ender
la source
Maintenant, je veux utiliser des chiffres négatifs dans mes chiffres! 1 ~ 3 * 6 == 5 ~ 8
Aaron

Réponses:

6

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.

COTO
la source
@ MartinBüttner: Oui, mais ce serait difficile. Il limite le nombre de "passes" sur l'entrée complète, et chaque passe comprend plusieurs opérations. Mon intuition est que le nombre de passes nécessaires pour normaliser toute nentrée à -digit serait quelque part entre net n log(n). Dans tous les cas, le nombre de passes peut être augmenté d'un facteur 10 pour chaque personnage ajouté. Le nombre de zéros dans la zconstante est également un problème intéressant. Je soupçonne que 9 est exagéré pour toute entrée possible.
COTO
@ MartinBüttner: Merci. J'ai supprimé l'évasion dans la classe de personnage. Quant au $0, Javascript ne le supporte pas. Ou du moins Firefox ne le fait pas. : P
COTO
D'accord, je pense que vous n'avez jamais besoin de plus de 7 zéros de tête comme tampon, mais je pense que les zéros de fin seront un peu plus difficiles à estimer. En ce qui concerne la boucle externe, je ne pense pas que vous en ayez même besoin, si vous faites juste une boucle while (ou que vous l'intégrez dans la boucle for interne) et que vous éclatiez quand plus aucun changement n'est trouvé. Je suppose que mes spécifications auraient pu être un peu plus claires à cet égard, mais par "en principe correct et exact pour les entrées arbitraires (valides)", je voulais dire que la seule limite théorique devrait être la taille de vos types de données intégrés / votre RAM.
Martin Ender
1
@COTO Pour économiser 1 octet, vous pouvez essayer de déplacer la première partie du for( i = e = 0; i < n-3; i = j )by for(; i < n-3; i = j )et déplacer les déclarations vers le haut, en les N = t = n = 0;remplaçant parN = t = n = i = e = 0;
Ismael Miguel
1
@IsmaelMiguel: jn'est pas maintenu constant à une valeur de i+1. Remarquez dans les trois ifblocs, jest réinitialisé à 0. Par conséquent, à tout moment après le premier ifbloc, il ne peut pas être utilisé comme proxy pour i+1. La variable ielle-même ne peut pas être mise à jour jusqu'à la fin de la boucle (en utilisant la troisième instruction dans for) car sa valeur est utilisée jusqu'à la fin de la boucle. Mais cela dit, peut-être que je manque quelque chose. Si vous pouvez raccourcir le code, le tester et vérifier qu'il fonctionne toujours, veuillez en poster une copie sur pastebin.com et un lien ici. Je vous accorderai tout le mérite dans la réponse. :)
COTO
2

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 + ( a , b ∈ ℤ) pour éviter les erreurs en virgule flottante. g[a,b]teste si a + <0. Exemple d'utilisation:

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