Standardise a Phinary Number

Question

Background

Most people on here should be familiar with a few integer base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, a number abc.de₁₆ would represent

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

However, one can also use non-integer bases, like irrational numbers. Once such base uses the golden ratio φ = (1+√5)/2 ≈ 1.618.... These are defined analogously to integer bases. So a number abc.de_φ (where a to e are integer digits) would represent

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

Note that in principle any of the digits could be negative (although we're not used to that) - we'll represent a negative digit with a leading ~. For the purpose of this question we restrict ourselves to digits from ~9 to 9, so we can unambiguously write a number as one string (with tildes in between). So

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

would be written as ~290.~43. We call such a number a phinary number.

A phinary number can always be represented in standard form, which means that the representation uses only digits 1 and 0, without containing 11 anywhere, and with an optional minus sign to indicate that the entire number is negative. (Interestingly, every integer has a unique finite representation in standard form.)

Representations which are not in standard form can always be converted into standard form using the following observations:

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

In addition:

4. If the most significant digit is ~1 (with the rest of the number being standard form), the number is negative, and we can convert it into standard form by swapping all 1 and ~1, prepending a minus sign, and applying the above three rules again until we obtain the standard form.

Here is an example of such a normalisation of 1~3.2~1φ (I'm using additional spaces for positive digits, to keep each digit position aligned):

      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)

Yielding -0.0101φ.

For further reading, Wikipedia has a very informative article on the topic.

The Challenge

Hence, or otherwise, write a program or function which, given a string representing a phinary number (as described above), outputs its standard form, without leading or trailing zeroes. The input does not necessarily contain the phinary point, but will always contain the digit left of it (so no .123). The output must always include the phinary point and at least one digit to the left of it.

You may take input via STDIN, ARGV or function argument and either return the result or print it to STDOUT.

You may use a different algorithm than the above procedure as long as it is in principle correct and exact for arbitrary (valid) inputs - that is, the only limits which could potentially break your implementation should be technical limitations like the size of built-in data types or the available RAM. For instance, evaluating the input as a floating-point number and then picking digits greedily is not allowed, as one could find inputs for which floating-point inaccuracies would lead to incorrect results.

This is code golf, the shortest answer (in bytes) wins.

Test Cases

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

Answer 1

Javascript (ES6) - 446 418 422 420 bytes

Minified:

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

Expanded:

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

The code produces a function F that performs the specified conversion.

It's a tough problem to golf. Numerous edge cases creep up that prevent simplification of the code. In particular, dealing with negatives is a pain, both in terms of parsing and in terms of logical handling.

I should note that the code only handles a "reasonable range" of inputs. To extend the domain of the function without bound, the number of zeros in z can be increased, and the constant bounding the while( c++ < 99 ) loop can be increased. The range currently supported is already overkill for the supplied test cases.

Sample Outputs

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

The -0. isn't pretty, but the answer is still correct. I can fix it if necessary.

Answer 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

This is the greedy algorithm, but with an exact representation [a,b] of numbers a + bφ (a, b ∈ ℤ) to avoid floating-point errors. g[a,b] tests whether a + bφ < 0. Usage example:

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