Eine Phinary Number standardisieren

32

Hintergrund

Die meisten Leute hier sollten mit einigen ganzzahligen Basissystemen vertraut sein: dezimal, binär, hexadezimal, oktal. ZB im Hexadezimalsystem würde eine Zahl abc.de 16 darstellen

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

Man kann jedoch auch nicht ganzzahlige Basen wie irrationale Zahlen verwenden. Sobald eine solche Basis verwendet das goldene Verhältnis φ = (1 + √5) / 2 ≈ 1,618 ... . Diese werden analog zu ganzzahligen Basen definiert. So würde eine Zahl abc.de φ (wobei a bis e ganzzahlige Ziffern sind) darstellen

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

Beachten Sie, dass im Prinzip jede der Ziffern negativ sein kann (obwohl wir das nicht gewohnt sind) - wir werden eine negative Ziffer mit einem führenden darstellen ~. Für diese Frage beschränken wir uns auf die Ziffern von ~9bis 9, damit wir eine Zahl eindeutig als eine Zeichenfolge schreiben können (mit Tilden dazwischen). So

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

würde geschrieben werden als ~290.~43. Wir nennen eine solche Nummer eine Phinarennummer .

A phinary Nummer kann immer in dargestellt wird Standardform , was bedeutet , dass die Darstellung verwendet nur Ziffern 1und 0ohne enthalten 11überall und optional mit einem Minuszeichen , um anzuzeigen , dass die gesamte Zahl negativ ist. (Interessanterweise hat jede Ganzzahl eine eindeutige endliche Darstellung in Standardform.)

Darstellungen, die nicht in Standardform vorliegen, können immer mit den folgenden Überlegungen in Standardform umgewandelt werden:

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

Und dazu:

  1. Wenn die höchstwertige Ziffer ~1(wobei der Rest der Zahl die Standardform ist) ist, ist die Zahl negativ, und wir können sie in die Standardform konvertieren, indem Sie alle 1und ~1vertauschen, ein Minuszeichen voranstellen und die obigen drei Regeln erneut anwenden, bis wir fertig sind Besorgen Sie sich das Standardformular.

Hier ist ein Beispiel für eine solche Normalisierung von (ich verwende zusätzliche Leerzeichen für positive Ziffern, um jede Ziffernposition ausgerichtet zu halten): 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)

Nachgeben .-0.0101φ

Für die weitere Lektüre hat Wikipedia einen sehr informativen Artikel zum Thema.

Die Herausforderung

Schreiben Sie daher oder auf andere Weise ein Programm oder eine Funktion, die bei gegebener Zeichenfolge, die eine Phinärzahl darstellt (wie oben beschrieben), ihre Standardform ohne führende oder nachfolgende Nullen ausgibt. Die Eingabe enthält nicht notwendigerweise den Phinärpunkt, sondern immer die Ziffer links davon (also nein .123). Die Ausgabe muss immer den Phinary Point und mindestens eine Ziffer links davon enthalten.

Sie können Eingaben über STDIN, ARGV oder Funktionsargumente vornehmen und das Ergebnis entweder zurückgeben oder an STDOUT ausgeben.

Sie können einen anderen Algorithmus als den oben beschriebenen verwenden, sofern dieser im Prinzip für beliebige (gültige) Eingaben korrekt und genau ist. Das heißt, die einzigen Grenzen, die möglicherweise Ihre Implementierung sprengen könnten, sollten technische Einschränkungen wie die Größe der integrierten Funktionen sein Datentypen oder den verfügbaren RAM. Beispielsweise ist es nicht zulässig, die Eingabe als Gleitkommazahl auszuwerten und dann gierig nach Ziffern zu suchen, da Eingaben gefunden werden könnten, bei denen Gleitkommazahlungenauigkeiten zu falschen Ergebnissen führen würden.

Dies ist Code Golf, die kürzeste Antwort (in Bytes) gewinnt.

Testfälle

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
quelle
Jetzt möchte ich negative Ziffern in meinen Zahlen verwenden! 1 ~ 3 * 6 == 5 ~ 8
Aaron

Antworten:

6

Javascript (ES6) - 446 418 422 420 Bytes

Minimiert:

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

Erweitert:

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

Der Code erzeugt eine Funktion F, die die angegebene Konvertierung ausführt.

Es ist ein schweres Problem, Golf zu spielen. Es entstehen zahlreiche Randfälle, die eine Vereinfachung des Codes verhindern. Insbesondere der Umgang mit Negativen ist sowohl im Hinblick auf das Parsen als auch im Hinblick auf den logischen Umgang ein Schmerz.

Ich sollte beachten, dass der Code nur einen "angemessenen Bereich" von Eingaben behandelt. Um die Domäne der Funktion ohne zBegrenzung zu erweitern, kann die Anzahl der Nullen erhöht werden, und die konstante Begrenzung der while( c++ < 99 )Schleife kann erhöht werden. Der derzeit unterstützte Bereich ist für die gelieferten Testfälle bereits überschritten.

Beispielausgaben

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

Das -0.ist nicht schön, aber die Antwort ist immer noch richtig. Ich kann es bei Bedarf beheben.

COTO
quelle
@ MartinBüttner: Du könntest, aber es wäre schwierig. Sie begrenzt die Anzahl der "Durchläufe" über die gesamte Eingabe und jeder Durchlauf umfasst mehrere Operationen. Mein nBauchgefühl ist, dass die Anzahl der Durchläufe, die zur Normalisierung einer zweistelligen Eingabe erforderlich sind, irgendwo zwischen nund liegen würde n log(n). In jedem Fall kann die Anzahl der Durchgänge für jedes hinzugefügte Zeichen um den Faktor 10 erhöht werden. Die Anzahl der Nullen in der zKonstanten ist ebenfalls ein interessantes Problem. Ich vermute, dass 9 für jede mögliche Eingabe übertrieben ist .
COTO
@ MartinBüttner: Danke. Ich habe die Flucht in der Charakterklasse entfernt. Was das $0betrifft, unterstützt Javascript es nicht. Zumindest Firefox nicht. : P
COTO
Okay, ich denke, Sie brauchen nie mehr als 7 führende Nullen als Puffer, aber ich denke, nachstehende Nullen sind etwas schwieriger zu schätzen. Was die äußere Schleife angeht, brauchst du das nicht einmal, wenn du nur eine while-Schleife machst (oder sie in die innere for-Schleife integrierst) und einfach ausbrichst, wenn keine Änderungen mehr gefunden werden. Ich denke, meine Spezifikation hätte in dieser Hinsicht etwas klarer sein können, aber mit "im Prinzip richtig und genau für beliebige (gültige) Eingaben" meinte ich, dass die einzige theoretische Grenze die Größe Ihrer eingebauten Datentypen / Ihres RAM sein sollte.
Martin Ender
1
@COTO um 1 Byte zu speichern, können Sie versuchen , den ersten Teil der bewegenden for( i = e = 0; i < n-3; i = j )durch for(; i < n-3; i = j )und die Erklärungen nach oben zu bewegen, wird N = t = n = 0;mit ersetztN = t = n = i = e = 0;
Ismael Miguel
1
@IsmaelMiguel: Wird jnicht konstant auf einem Wert von gehalten i+1. Hinweis in den drei ifBlöcken jwird auf zurückgesetzt 0. Daher kann es zu keinem Zeitpunkt nach dem ersten ifBlock als Proxy für verwendet werden i+1. Die Variable iselbst kann erst am Ende der Schleife aktualisiert werden (mit der dritten Anweisung in for), da ihr Wert bis zum Ende der Schleife verwendet wird. Aber nachdem ich das gesagt habe, fehlt mir vielleicht etwas. Wenn Sie den Code kürzen, testen und überprüfen können, ob er noch funktioniert, senden Sie eine Kopie an pastebin.com und einen Link hierher. Ich werde Ihnen in der Antwort die gebührende Ehre erweisen. :)
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

Dies ist der Greedy-Algorithmus, jedoch mit einer exakten Darstellung [a,b]der Zahlen a + ( a , b ∈ ∈), um Gleitkommafehler zu vermeiden. g[a,b]testet ob a + <0. Anwendungsbeispiel :

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