Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Sandbox

Rationalise recurring binary [FINALIZED]

+1
−0

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
  • If r is present then there will always be a . somewhere to the left of the r
  • 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 as 10.000..., the same as 10, the integer 2, represented as 2/1
  • 0.r1 is the same as 0.111..., the same as 1, the integer 1, represented as 1/1
  • 0.r01 is the same as 0.010101..., the fraction 1/3
  • 0.r10 is the same as 0.101010..., the fraction 2/3
  • 1.r01 is the same as 1.010101..., the fraction 4/3
  • 0.r001 is the same as 0.001001001..., the fraction 1/7
  • 0.r010 is the same as 0.010010010..., the fraction 2/7
  • 0.r100 is the same as 0.100100100..., the fraction 4/7
  • 1.r001 is the same as 1.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.

Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment thread

I think it would make sense to set a limit on the inputs the program needs to handle. For example, a ... (2 comments)

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!

Like what we're doing? Support us! Donate