32
\$\begingroup\$

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

In addition:

  1. 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
\$\endgroup\$
  • \$\begingroup\$ Now I want to use negative digits in my numbers ! 1~3 * 6 == 5~8 \$\endgroup\$ – Aaron Oct 9 '15 at 12:09
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner: You could, but it would be difficult. It bounds the number of "passes" over the full input, and each pass comprises several operations. My gut feel is that the number of passes required to normalize any n-digit input would be somewhere between n and n log(n). In any case, the number of passes can be raised by a factor of 10 for every character added. The number of zeroes in the z constant is also an interesting problem. I suspect that 9 is overkill for any possible input. \$\endgroup\$ – COTO Sep 16 '14 at 20:44
  • \$\begingroup\$ @MartinBüttner: Thanks. I removed the escape in the character class. As for the $0, Javascript doesn't support it. Or at least Firefox doesn't. :P \$\endgroup\$ – COTO Sep 16 '14 at 20:49
  • \$\begingroup\$ Okay, I think you never need more than 7 leading zeroes as buffer, but I think trailing zeroes will be a bit harder to estimate. As for the outer loop, I don't think you even need that, if you just make that a while loop (or integrate it into the inner for loop) and just break out when no more changes are found. I guess my spec could have been a bit clearer in that respect but by "in principle correct and exact for arbitrary (valid) inputs" I meant that the only theoretical limit should be the size of your built-in data types/your RAM. \$\endgroup\$ – Martin Ender Sep 16 '14 at 22:32
  • 1
    \$\begingroup\$ @COTO To save 1 byte, you can try moving the first part of the for( i = e = 0; i < n-3; i = j ) by for(; i < n-3; i = j ) and move the declarations to the top, being N = t = n = 0; replaced with N = t = n = i = e = 0; \$\endgroup\$ – Ismael Miguel Sep 17 '14 at 18:36
  • 1
    \$\begingroup\$ @IsmaelMiguel: j isn't held constant at a value of i+1. Notice in the three if blocks, j is reset to 0. Hence at any point after the first if block it can't be used as a proxy for i+1. The variable i itself can't be updated until the end of the loop (using the third statement in for) since its value is used right up until the end of the loop. But having said that, maybe I'm missing something. If you're able to shorten the code, test it, and verify that it still works, please post a copy to pastebin.com and a link here. I'll extend due credit to you in the answer. :) \$\endgroup\$ – COTO Sep 18 '14 at 19:57
2
\$\begingroup\$

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 + (a, b ∈ ℤ) to avoid floating-point errors. g[a,b] tests whether a + < 0. Usage example:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.