Rationalise recurring binary [FINALIZED]
Now posted: Rationalise recurring binary
Given a potentially recurring binary string, output the number it represents, as a fraction in lowest terms.
The notation used in this challenge for recurring digits is non-standard. An r
is used to indicate that the remaining digits recur. For example, 0.000r10
means the last 2 digits recur, like this: 0.000101010...
. This is the binary representation of $\frac{1}{12}$, which cannot be expressed in binary without recurring digits.
Input
- A binary string made up of
- Zero or more of
0
- Zero or more of
1
- Zero or one of
.
- Zero or one of
r
- Zero or more of
- If
r
is present then there will always be a.
somewhere to the left of ther
- There may be zero or more leading zeroes
- There may be zero or more trailing zeroes (in both recurring and non-recurring inputs)
- The last character will never be an
r
- There will always be at least 1 character (the string will not be empty)
- The maximum length of input required to be handled is 15 characters
Interpretation
- All digits to the right of an
r
are recurring (repeating forever) - Anything to the left of a
.
represents the integer part of the number (in binary) - Anything to the right of a
.
represents the fractional part of the number (in binary) - If the first character is a
.
then the integer part is zero - If the last character is a
.
then the fractional part is zero - If there is no
.
then the fractional part is zero
Output
- A numerator and denominator, in that order, or a rational type if your language supports one
- These can be in a multi-value data type such as a list/array/vector, or as a single string containing a non-numeric separating character (such as a space or a
/
) - The numerator and denominator must be in lowest terms (that is, their greatest common factor is 1)
- An integer output N is represented as the fraction N/1, a numerator of N and a denominator of 1
- Zero is represented as the fraction 0/1, a numerator of zero and a denominator of 1
- The numerator and denominator are output as base 10 (decimal) - only the input is in binary
Examples
Throughout these examples binary strings are represented as fixed width
and all other numbers are base 10 (decimal).
Non-recurring examples
-
10.00
is the integer 2, represented as 2/1 -
01.00
is the integer 1, represented as 1/1 -
00.10
is the fraction 1/2 -
00.01
is the fraction 1/4
Recurring examples
-
10.r0
is the same as10.000...
, the same as10
, the integer 2, represented as 2/1 -
0.r1
is the same as0.111...
, the same as1
, the integer 1, represented as 1/1 -
0.r01
is the same as0.010101...
, the fraction 1/3 -
0.r10
is the same as0.101010...
, the fraction 2/3 -
1.r01
is the same as1.010101...
, the fraction 4/3 -
0.r001
is the same as0.001001001...
, the fraction 1/7 -
0.r010
is the same as0.010010010...
, the fraction 2/7 -
0.r100
is the same as0.100100100...
, the fraction 4/7 -
1.r001
is the same as1.001001001...
, the fraction 8/7
Test cases
Test cases are in the format input : output
Outputs are in the format numerator/denominator
. : 0/1
.0 : 0/1
0. : 0/1
.1 : 1/2
1. : 1/1
0.0 : 0/1
00.00 : 0/1
.r0 : 0/1
.r1 : 1/1
00.r00 : 0/1
11.r11 : 4/1
00.0r0 : 0/1
11.1r1 : 4/1
.0101r01 : 1/3
.1010r10 : 2/3
.r01 : 1/3
.r0101 : 1/3
.r010101 : 1/3
.r0101010 : 42/127
.r0011 : 1/5
.r0110 : 2/5
.r1001 : 3/5
.r1100 : 4/5
.0r01 : 1/6
.00r10 : 1/6
.1r10 : 5/6
.r001 : 1/7
.r010 : 2/7
.r011 : 3/7
.r100 : 4/7
.r101 : 5/7
.r110 : 6/7
.r111 : 1/1
0001000.r01001 : 257/31
.r000111 : 1/9
.0r001110 : 1/9
.00r011100 : 1/9
.000r111000 : 1/9
.0001r110001 : 1/9
.00011r100011 : 1/9
.000111r000111 : 1/9
.r001110 : 2/9
.r011100 : 4/9
.r100011 : 5/9
.r110001 : 7/9
.r111000 : 8/9
1 : 1/1
10 : 2/1
11 : 3/1
100 : 4/1
101 : 5/1
110 : 6/1
111 : 7/1
111. : 7/1
111.0 : 7/1
111.r0 : 7/1
111.0r0 : 7/1
Explanations in answers are optional, but I'm more likely to upvote answers that have one.
Sandbox questions
- Is the max input length of 15 characters reasonable? Are there any reasons to make it longer or shorter?
- Are there any edge cases that should be added to the test cases?
- Is there a preferred format for the test cases?
- Are there any extra examples that would give insight?
- Is anything ambiguous?
- Is anything underspecified?
- Does anything take multiple readings to make sense, which could be explained more clearly?
To anyone already familiar with converting recurring decimal numbers to fractions, converting recurring binary numbers can be done with exactly the same method.
To anyone not already familiar with converting recurring decimal numbers to fractions, things such as 0.111...
= 1
may be counterintuitive. I have deliberately focused only on explaining the meaning of the numbers, not the method of converting them, as that is the challenge.
Would it help to put a disclaimer at the top of the post, suggesting people look up how to convert recurring decimal numbers to fractions if not already familiar? I'm leaning towards not doing this, but I have carefully aligned the recurring examples to give a hint for those who haven't seen this kind of conversion before.
1 comment thread