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, 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
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:
- 011φ = 100φ (because φ2 = φ + 1)
- 0200φ = 1001φ (because φ2 + 1/φ = 2φ)
- 0~10φ = ~101φ (because φ - 1/φ = 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, 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)
For further reading, Wikipedia has a very informative article on the topic.
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.
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