Convert a repeated decimal to a fraction

Question

This question doesn't need to apply to just terminating decimals - repeating decimals can also be converted to fractions via an algorithm.

Your task is to make a program that takes a repeated decimal as input, and output the corresponding numerator and denominator (in lowest terms) that produces that decimal expansion. Fractions greater than 1 should be represented as improper fractions like 9/5. You can assume that input will be positive.

The repeated decimal will be given in this format:

5.3.87

with everything after the second dot repeated, like this:

5.3878787878787...

Your program will output two integers representing the numerator and denominator, separated by a slash (or the equivalent form in your language if you do not output plain text):

889/165

Note that terminating decimals will have nothing after the second dot, and decimals with no non-repeating decimal portion will have nothing between the two dots.

Test cases

These test cases cover all of the required corner cases:

0..3 = 1/3
0.0.3 = 1/30
0.00.3 = 1/300
0.6875. = 11/16
1.8. = 9/5
2.. = 2/1
5..09 = 56/11
0.1.6 = 1/6
2..142857 = 15/7
0.01041.6 = 1/96
0.2.283950617 = 37/162
0.000000.1 = 1/9000000
0..9 = 1/1
0.0.9 = 1/10
0.24.9 = 1/4

If you wish, you can also assume that fractions without integer parts have nothing to the left of the first dot. You can test that with these optional test cases:

.25. = 1/4
.1.6 = 1/6
..09 = 1/11
.. = 0/1

Answer 1

Dyalog APL (75 73 69 68 characters)

Here is another and fifth attempt (most probably my last one); I spent the day trying to write some piece of code shorter than 80 characters and being fully consistent with the rules. This challenge made my day!

I finally got a line of APL made of 75 characters, working with Dyalog APL (but not on the online interpreter page because using the ⍎ execute function), which is the following one:

(N,D)÷D∨N←(⍎'0',1↓I/⍨2=+\P)+(⍎'0',I/⍨2>+\P)×D←D+0=D←⍎'0',⌽2↓⍕¯1+10⊥P←'.'=I← '1.2.3'

Of course I could make it a little shorter, but the special cases where one, two or three fields are missing. My code can even handle the .. input case.

I know that APL is difficult to read, and since people enjoy understanding how a piece of code actually works, here are some explanation. Basically, I compute the final denominator in the variable D and the final numerator in the variable N.

APL is parsed from right to left.

• First, the string is stored in variable I (I←).
• Then it is mapped to a vector of booleans indicating where a dot is, and this vector is called P (P←'.'=). For instance '1.2.3' will be mapped to 0 1 0 1 0.
• This vector is digits in base 10 (10⊥); now '1.2.3' is 1010.
• Then 1 is substracted from this number (either with 1-⍨ or with ¯1+, here I chose the second). Now '1.2.3' is 1009.
• Then this number is converted to a string (⍕), two initial digits are removed (2↓), which makes 09 from our initial '1.2.3' example; the string is reversed (⌽).
• Here, as a special case, I add an initial 0 character in front of the string; it makes me sad to use the four characters '0', but I did it for avoiding an error when the second and thirds fields are both empty. The string is converted back to a number (⍎) and it is stored in D, which is the denominator except when both last fields are empty, because in such case D is equal to 0.
• The D←D+0= piece of code set D to 1 if it is currently null, and now D contains the denominator (before GCD division however).
• This denominator is multiplied (×) with the content of the initial string I up to the second dot with (⍎'0',I/⍨2>+\P) which starts from P again (0 1 0 1 0 in my example), adds the successive numbers by cumulating them (which makes 0 1 1 2 2 in my example), check which values are smaller than 2 (making the boolean vector 1 1 1 0 0), and taking corresponding characters in I; another 0 is added in front of the string for preventing another trap (if the two initial fields are empty) and the whole is converted to a number.
• The last part of the input string is added to the previous product with (⍎'0',1↓I/⍨2=+\P), which takes P again, adds by cumulating again, check which values are equal to 2 (see previous explanation), takes the characers, removes the first one which is a dot, adds a preventing initial 0 character and converts to a number.
• This product followed with a sum is stored in N which is the numerator.
• Finally the GCD is computed with D∨N and both numbers are divided by this GCD.

edit: Here is a fix for 73 characters:

(N,D)÷D∨N←(⍎'0',1↓P/I)+(⍎'0',I/⍨~P←2=+\P)×D←D+0=D←⍎'0',⌽2↓⍕¯1+10⊥P←'.'=I←

The idea of this hack is computing first the case where cumulative addition has values equal to 2, storing them for later and inverting this bitwise mask for getting the first case; thus computing the next case needs less characters.

edit: Here is another fix for 69 characters:

(N,D)÷D∨N←(⍎'0',1↓P/I)+(⍎'0',I/⍨~P←2=+\P)×D←⍎'1⌈0',⌽2↓⍕¯1+10⊥P←'.'=I←

The idea of this hack is to embed the most complicated special case as APL code in the string to be evaluated (at string to number conversion stage).

edit: Here is another fix for 68 characters:

(N,D)÷D∨N←(⍎'0',1↓P/I)+(⍎'0',I/⍨~P←2=+\P)×D←⍎'1⌈0',⌽3↓⍕1-10⊥P←'.'=I←

The idea of this hack is to replace adding -1 to the value for substracting 1 to that value by the operation substracting that value to 1 then remove later one character more at the beginning (which will be the minus sign).

edit: Cosmetic change:

(N,D)÷D∨N←(⍎'0',1↓P/I)+(⍎'0',I/⍨~P←2=+\P)×D←1⌈⍎'0',⌽3↓⍕1-10⊥P←'.'=I←

No improvement in size, but more satisfied to get the maximum function out of the code to be evaluated.

Answer 2

Perl 6 (93 101 100 80 68 66 bytes)

$/=split ".",get;say ($0+($1+$2/(9 x$2.comb||1))/10**$1.comb).nude

The size was increased to handle nothing, instead of just failing. Mouq proposed to use $/, so it's now being used, and the code is 20 bytes shorter. Ayiko proposed replacing / with , so the code is even shorter (by 12 bytes). Then Mouq proposed replacing chars with comb (in numeric context, they are identical, because list of characters after conversion to number is number of characters).

Sample output:

$ perl6 script.p6
5.3.87
889 165
$ perl6 script.p6
2.0.0
2 1
$ perl6 script.p6
0..3
1 3
$ perl6 script.p6
0.0.3
1 30
$ perl6 script.p6
0.0.0
0 1
$ perl6 script.p6
0.1.6
1 6
$ perl6 script.p6
0.01041.6
1 96
$ perl6 script.p6
0.2.283950617
37 162
$ perl6 script.p6
123.456.789
41111111 333000

Answer 3

J (85 90 89 chars)

My original function, which was 5 characters shorter than the second, had a couple of bugs: it didn't output integers as "n/1" and it gave the wrong answer on numbers with more than a dozen or so digits. Here's a corrected function in J that also incorporates Eelvex's suggestion to save a character:

f=:3 :0
'a t'=.|:(".@('0','x',~]),10x^#);._1'.',y
(,'/'&,)&":/(,%+.)&1+/a%*/\1,0 1-~}.t
)

It receives a string and returns a string. Here's a sample session:

   f '..'
0/1
   f '0.0.0'
0/1
   f '3..'
3/1
   f '..052631578947368421'
1/19
   f '0.2.283950617'
37/162
   f '.0.103092783505154639175257731958762886597938144329896907216494845360824742268041237113402061855670'
1/97

Answer 4

C, 171

Quite long. Could be further reduced. No scanf, which really can't handle it if there aren't any numbers between the dots. No strtol. Just number crunching:

a,b,c,d,q;main(){while((q=getchar()-48)>-3)q<0?(d=b>0,b+=!b):d?(c=c*10+q,d*=10):(a=a*10+q,b*=10);for(a=a*--d+c,q=b*=d;q>1;a%q+b%q?--q:(a/=q,b/=q));printf("%d/%d\n",a,b);}

Test:

rfc <<< "2..142857"
15/7

Answer 5

Javascript, 203

Way too long, but still fun. Newlines because semicolons are unreadable.

s=prompt(b=1).split(".")
P=Math.pow
a=s[0]
c=s[1]
d=P(10,l=c.length)
f=(P(10,s[2].length)-1)*P(10,l)||1
e=s[2]=+s[2]
a=d*a+b*c;b*=d
a=f*a+b*e;b*=f
function g(a,b){return b?g(b,a%b):a}g=g(a,b);a/g+"/"+b/g

Answer 6

DC (not fully general, shortened to 76 characters)

Not fully general, but please, consider I did it with one of the oldest things in the world:

5.3.87 dsaX10r^d1-rla*sasbdscX10r^dlc*rlb*rlb*la+snsdlnld[dSarLa%d0<a]dsax+dldr/rlnr/f

Edit: I edit my solution; it isn't more general, but a little shorter:

sadsbX10r^sclaX10r^dd1-dsdlblc**rla*+dsnrld*dsd[dSarLa%d0<a]dsax+dldr/rlnr/f

Use it as:

5.3.87 sadsbX10r^sclaX10r^dd1-dsdlblc**rla*+dsnrld*dsd[dSarLa%d0<a]dsax+dldr/rlnr/f

• First field isn't required:

  .1.3 sadsbX10r^sclaX10r^dd1-dsdlblc**rla*+dsnrld*dsd[dSarLa%d0<a]dsax+dldr/rlnr/f
  

  is OK.

• Second and thirst field require at least one digit

Answer 7

J (different method)

Another solution based on a very different method; this time it is fully general; only missing is the 1-denominator when an integer is submitted:

   ".((({.~(i.&1)),'+'"_,((":@(10&^)@#,'%~',])@}.@#~~:/\),'+%',((,~(##'9'"_),'%x:0'"_)@}.@#~2:=+/\@]))(=&'.')) '.1.3'
2r15
   ".((({.~(i.&1)),'+'"_,((":@(10&^)@#,'%~',])@}.@#~~:/\),'+%',((,~(##'9'"_),'%x:0'"_)@}.@#~2:=+/\@]))(=&'.')) '.1.'
1r10
   ".((({.~(i.&1)),'+'"_,((":@(10&^)@#,'%~',])@}.@#~~:/\),'+%',((,~(##'9'"_),'%x:0'"_)@}.@#~2:=+/\@]))(=&'.')) '1..'
1
   ".((({.~(i.&1)),'+'"_,((":@(10&^)@#,'%~',])@}.@#~~:/\),'+%',((,~(##'9'"_),'%x:0'"_)@}.@#~2:=+/\@]))(=&'.')) '1..3'
4r3

Answer 8

GolfScript (67 chars)

`{'.'/1$=.10\,?@-).!+0@+~}+3,/1$4$*]-1%~;*+*+].~{.@\%.}do;{/}+/'/'@

NB This supports empty integer parts.

If the string is of the form 'n.p.q' then the value is n + p/E + q/(DE) = ((nD + p)E + q)/DE where D = 10^(len p) and E = 10^(len q) - 1, except when len q = 0, in which case E = 1 (to avoid division by 0).

Dissection:

           # Stack: 'n.p.q'
`{         # Combined with the }+ below this pulls the value into the block
           # Stack: idx 'n.p.q'
    '.'/   # Stack: idx ['n' 'p' 'q']
    1$=    # Stack: idx str   (where str is the indexed element of ['n' 'p' 'q'])
    .10\,? # Stack: idx str 10^(len str)
    @-)    # Stack: str 10^(len str)-idx+1
           #   If idx = 0 we don't care about the top value on the stack
           #   If idx = 1 we compute D = 10^(len 'p')
           #   If idx = 2 we compute E' = 10^(len 'q') - 1
    .!+    # Handle the special case E'=0; note that D is never 0
    0@+~   # Stack: 10^(len str)-idx+1 eval('0'+str) (GolfScript doesn't treat 011 as octal)
}+         # See above
3,/        # Run the block for idx = 0, 1, 2
           # Stack: _ n D p E q
1$4$*      # Stack: _ n D p E q D*E
]-1%~;     # Stack: D*E q E p D n
*+*+       # Stack: D*E q+E*(p+D*n)
].~        # Stack: [denom' num'] denom' num'
{.@\%.}do; # Stack: [denom' num'] gcd
{/}+/      # Stack: denom num
'/'@       # Stack: num '/' denom

Online demo which simulates running the program with each of the test inputs, one at a time.

Answer 9

Ruby - 112

x,y,z=gets.chop.split".";y||='0';z||='0';puts((y.to_i+Rational(z.to_i,10**z.length-1))/10**y.length+x.to_i).to_s

This is my first experiment with ruby, so feel free to suggest improvements.

$ ruby20 % <<< '5.3.87'
889/165
$ ruby20 % <<< '0..3'
1/3
$ ruby20 % <<< '0.0.3'
1/30
$ ruby20 % <<< '0.00.3'
1/300
$ ruby20 % <<< '0.6875.0'
11/16
$ ruby20 % <<< '1.8.0'
9/5
$ ruby20 % <<< '2..'
2/1
$ ruby20 % <<< '..'
0/1

Answer 10

Python

No libraries - 156 characters

_=lambda a,b:b and _(b,a%b)or a;a,b,c=raw_input().split('.');d,e=int(a+b+c)-bool(c)*int(a+b),
(10**len(c)-bool(c))*10**len(b);f=_(d,e);print'%i/%i'%(d/f,e/f)

Using fractions - 127 characters

from fractions import*;a,b,c=raw_input().split('.');print Fraction(int(a+b+c)-bool(c)*int(a+b
),(10**len(c)-bool(c))*10**len(b))

Answer 11

Mathematica, 143

As usual, Mathematica offers many high-level functions to do the job, but gives them verbose names.

x=StringTake;c=ToExpression;p=s~StringPosition~".";{o,t}=First/@p;u=StringLength@s-t;d=t-o-1;Rationalize@(c@x[s,t-1]+c@x[s,-u]/((10^u)-1)/10^d)

Sample output to be added later when I have time.

Answer 12

Haskell

import Data.Ratio
f n=case s '.' n of
    [x,y,z]->(r x)%1+(r y)%(10^(length y))+(r z)%((10^t-1)*(10^(length y)))
        where
            r ""=0
            r n=read n
            t = if length z==0 then 9 else length z
s _ []=[[]]
s n (x:xs) | x==n = []:(s n xs)
           | otherwise = let (l:ls)=s n xs in (x:l):ls

Answer 13

C, 164

This is similar to orion's C solution, even though I did it from scratch. I confess however stealing a number of his optimizations. It is not much shorter, but it handles .25. = 1/4 and 0.000000.1 = 1/9000000.

long a,b,c,d,e;main(){while((c=getchar()-48)>-3)c+2?a=a*10+c,b*=10:b?e=a,d=b:(b=1);
b>d?a-=e,b-=d:0;for(d=2;d<=a;)a%d+b%d?d++:(a/=d,b/=d);printf("%ld/%ld\n",a,b);}

Answer 14

Two python answers using no libraries. First handles the optional input without a digit before the first . and is 162 chars

_=lambda a,b:b and _(b,a%b)or a;i,t,r=raw_input().split(".");b=r!="";d=(10**len(r)-b)*10**len(t);n=int((i+t+r)or 0)-b*int((i+t)or 0);f=_(d,n);print "%i/%i"%(n,d)

Second doesn't handle nothing before the first digit but does handle all required inputs correctly and is 150 chars

_=lambda a,b:b and _(b,a%b)or a;i,t,r=raw_input().split(".");b=r!="";d=(10**len(r)-b)*10**len(t);n=int(i+t+r)-b*int(i+t);f=_(d,n);print "%i/%i"%(n,d)

Answer 15

JavaScript (ECMASCript 6) 180 175

G=(a,d)=>d?G(d,a%d):a;P=a=>+("1e"+a);L=a=>a.length;f=prompt().split(".");B=P(L(b=f[1]));D=P(L(b)+L(c=f[2]))-P(L(b))||1;alert((m=(f[0]+b||0)*D+B*(c||0))/(g=G(m,n=B*D))+"/"+n/g)

While it isn't a clear winner for the 300 bounty... this is the shortest I can come up with:

• Changes from previous version: some slight alteration to logic, and changes to the Power P function by altering it to +("1e"+a) instead of Math.pow(10,a) thereby saving a few more characters...

Answer 16

Mathematica 175

f@i_:=
If[IntegerQ[g=FromDigits[Map[IntegerDigits@ToExpression@#&,StringSplit[i,"."]/.""-> {}]
/.{a_,b_,c_}:> {{Sequence@@Join[a,b],c},Length@a}]],HoldForm[Evaluate@g]/HoldForm@1,g]

Most of the routine goes to massaging the input. Approximately 50 chars went to handling integers.

---

Examples

f["7801.098.765"]

More examples:

TableForm[
 Partition[{#, f[#]} & /@ {"19..87", "19.3.87", "5.3.87", "0.0.3", "0..3", "0.2.283950617", 
"123.456.789", "6666.7777.8888", "2.0.0","0.0.0"}, 5], TableSpacing -> {5, 5}]

---

How it would normally be accomplished in Mathematica

FromDigits can obtain a fraction directly from a recurring repeating decimal, provided that the input is of a particular form. Integers are displayed as integers.

z={{{1, 9, {8, 7}}, 2}, {{1, 9, 3, {8, 7}}, 2}, {{5, 3, {8, 7}}, 1}, {{{3}}, -1}, {{{3}}, 0}, 
{{2, {2, 8, 3, 9, 5, 0, 6, 1, 7}}, 0}, {{1, 2, 3, 4, 5, 6, {7, 8, 9}}, 3}, 
{{6, 6, 6, 6, 7, 7, 7, 7, {8}}, 4}, {{2}, 1}, {{0}, 1}}

FromDigits/@z

Answer 17

J (96 characters)

I don't use the slash symbol as a separator (but solution in Mathematica doesn't either since it uses a graphical representation which is better anyway); in J language the fraction is displayed with r instead as /:

   (((-.@]#[)((".@[%#@[(10x&^)@-{.@])+({.@](10x&^)@-#@[)*<:@{:@](".%<:@(10x&^)@#)@}.[)I.@])(=&'.')) '1..3'
4r3
   (((-.@]#[)((".@[%#@[(10x&^)@-{.@])+({.@](10x&^)@-#@[)*<:@{:@](".%<:@(10x&^)@#)@}.[)I.@])(=&'.')) '123.456.789'
41111111r333000

Answer 18

APL (not fully general)

Not fully general (like my solution for dc); works with Dyalog APL (but not on the online version of Dyalog APL, not sure why):

(R,F)÷(F←D×N)∨R←(⍎C)+D×(⍎I/⍨2>+\P)×N←10*¯1++/≠\P⊣D←¯1+10*⍴C←1↓I/⍨2=+\P←'.'=I← '123.456.789'

The first field is optional, but at least one digit is required for both other fields.

Answer 19

JavaScript (189)

i=prompt().split(".");a=i[0];b=i[1];c=i[2];B=b.length;p=Math.pow;n=a+b+c-(a+b);d=p(10,B+c.length)-p(10,B);f=1;while(f){f=0;for(i=2;i<=n;i++)if(n%i==0&&d%i==0){n/=i;d/=i;f=1}};alert(n+"/"+d)

Example:

Input:

5.3.87

Output:

889/165

Answer 20

C (420 characters as written; less after removing unnecessary whitespace)

Note that this assumes 64-bit long (e.g. 64 bit Linux); it will fail for the test case 0.2.283950617 on systems using 32-bit long. This can be fixed at the cost of some characters by changing the type to long long and changing the printf format string accordingly.

#include <stdio.h>

long d[3], n[3], i;

int main(int c, char** v)
{
  while (c = *v[1]++)
    switch(c)
    {
    case '.':
      n[++i] = 1;
      break;
    default:
      d[i] = 10 * d[i] + c - '0';
      n[i] *= 10;
    }

  n[2] -= n[2] != 1;

  while (i--)
    d[2] += d[i] * n[i+1], n[i]*=n[i+1];

  i = d[2];
  *n = n[1];

  while (i)
    *d = i, i = *n%i, *n = *d;
  printf("%ld/%ld\n", d[2]/ *n, n[1]/ *n);
}

Answer 21

GTB, 81

`_:s;_,1,l?_)-S;_,"."
s;A;,1,S;_,".")-1
s;_,1+S;_,"."),l?_)-S;_,"."))→_
x?A;+_)►Frac

Example

?3.25.
            13/4