23
\$\begingroup\$

Write a program or function that given two integers a, b outputs a string containing a decimal number representing the fraction a/b exactly.

If a/b is integer, simply output the value, without a decimal dot or leading zeroes:

123562375921304812375087183597 / 2777 -> 44494913907563850333124661
81 / 3 -> 27
-6 / 2 -> -3

If a/b is not integer but has a finite representation in base 10, output the value without leading or trailing zeroes (except a single zero before the dot):

1 / 2 -> 0.5
3289323463 / -250000000 -> -13.157293852

Finally, if and only if (so no 0.999...) a/b is not integer and does not have a finite representation, output the finite part followed by the repeating part in parenthesis. The repeating part must be as small as possible, and start as early as possible.

-1 / 3 -> -0.(3)
235 / 14 -> 16.7(857142)
123 / 321 -> 0.(38317757009345794392523364485981308411214953271028037)
355 / 113 -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)

Your program must work for all above examples in under 10 seconds on a modern desktop PC. Smallest program in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ @DestructibleWatermelon This is possible in pretty much all languages, including Turing tarpits. (Those might struggle with the time limit though.) \$\endgroup\$ – Dennis Aug 9 '16 at 5:46
  • \$\begingroup\$ @DestructibleWatermelon I was under the impression that most languages are turing complete. \$\endgroup\$ – orlp Aug 9 '16 at 5:46
  • \$\begingroup\$ Can we safely assume the fraction won't be something like: 0.33333333333336333...? \$\endgroup\$ – brianush1 Aug 9 '16 at 5:50
  • 2
    \$\begingroup\$ This seems like a long-winded way of asking for solutions to PE26 ;) \$\endgroup\$ – Conor O'Brien Aug 9 '16 at 6:24
  • 1
    \$\begingroup\$ Generalisation of this question; also related. \$\endgroup\$ – Peter Taylor Aug 9 '16 at 7:52
3
\$\begingroup\$

Perl 6,  63 58  50 bytes

{->$a,$b {$a~"($b)"x?$b}(|($^a.FatRat/$^b).base-repeating(10))}
{->\a,$b {a~"($b)"x?$b}(|($^a.FatRat/$^b).base-repeating)}
{$/=($^a.FatRat/$^b).base-repeating;$0~"($1)"x?$1}

Test it

If you don't care that it will only work with denominators that fit into a 64 bit integer it can be shortened to just 43 bytes:

{$/=($^a/$^b).base-repeating;$0~"($1)"x?$1}

Expanded:

{
  # store in match variable so that we can
  # use 「$0」 and 「$1」
  $/ = (

    # turn the first value into a FatRat so that
    # it will continue to work for all Int inputs
    $^a.FatRat / $^b

  ).base-repeating;

  # 「$0」 is short for 「$/[0]」 which is the non-repeating part
  $0

  # string concatenated with
  ~

  # string repeat once if $1 is truthy (the repeating part)
  # otherwise it will be an empty Str
  "($1)" x ?$1
}
\$\endgroup\$
  • \$\begingroup\$ The way you formatted your answer is confusing. You should remove your old programs, because right now it looks like a multi-line program. \$\endgroup\$ – mbomb007 Jul 13 '17 at 21:26
  • \$\begingroup\$ @mbomb007 The main reason I have for posting golfs is for marketing, and education of Perl 6. So I leave old versions in to show more of the language. That's also why I rarely post one until I have some sort of explanation in there. I have altered it so that the different examples are in different code blocks. \$\endgroup\$ – Brad Gilbert b2gills Jul 14 '17 at 0:39
  • \$\begingroup\$ Old versions are always visible in the post's edit history. \$\endgroup\$ – mbomb007 Jul 14 '17 at 13:32
  • \$\begingroup\$ @mbomb007 Not if I wait to post until after trying several different ways to write it. \$\endgroup\$ – Brad Gilbert b2gills Jul 15 '17 at 2:41
  • \$\begingroup\$ Then just edit one in every 5 minutes. \$\endgroup\$ – mbomb007 Jul 15 '17 at 3:46
8
\$\begingroup\$

Python 2, 174 bytes

x,y=input()
a=abs(x)
b=abs(y)
r=a%b*10
L=[]
M=''
while~-(r in L):L+=r,;M+=str(r/b);r=r%b*10
i=L.index(r)
t=M[:i]+"(%s)"%M[i:]*(M[i:]>'0')
print"-%d."[x*y>=0:(t>'')+3]%(a/b)+t

I'm not quite convinced about the validity of this answer, but it's worked for the test cases above and other test cases I've thrown at it. It looks like a right mess though, so I'm sure there's plenty of room for golfing.

The initial setup takes absolute values of both arguments to ensure that we're dealing with nonnegative numbers (saving the sign calculation for later), and delegates the quotient part of the result to Python's arbitrary precision arithmetic. The fractional part is done with the grade-school division algorithm until we get a repeat in the remainder. We then look up when we last saw this repeat in order to get the period, and construct the string accordingly.

Note that the algorithm's actually quite slow due to the O(n) in operation, but it's fast enough for the examples.

\$\endgroup\$
5
\$\begingroup\$

Batch, 349 344 bytes

@echo off
set/ad=%2,i=%1/d,r=%1%%d
if not %r%==0 set i=%i%.&if %r% leq 0 set/ar=-r&if %i%==0 set i=-0.
set d=%d:-=%
set/ae=d
:g
if %r%==0 echo %i%&exit/b
set/ag=-~!(e%%2)*(!(e%%5)*4+1)
if not %g%==1 set/ae/=g&call:d&goto g
set/as=r
set i=%i%(
:r
call:d
if %r%==%s% echo %i%)&exit/b
goto r
:d
set/ar*=10,n=r/d,r%%=d
set i=%i%%n%

Edit: Saved 5 bytes by removing unnecessary characters. "Ungolfed":

@echo off
set /a d = %2
set /a i = %1 / d
set /a r = %1 % d
if not %r%==0 (
    set i=%i%.                  Decimal point is required
    if %r% leq 0 (
        set /a r = -r           Get absolute value of remainder
        if %i%==0 set i=-0.     Fix edge case (-1/3 = 0 remainder -1)
    )
)
set d = %d:-=%                  Get absolute value of divisor
set /a e = d
:g
if %r%==0 echo %i% & exit /b    Finished if there's no remainder
set /a g = gcd(e, 10)           Loop through nonrecurring decimals
if not %g%==1 (
    set /a e /= g
    call :d
    goto g
)
set /a s = r                    Save remainder to know when loop ends
set i=%i%(
:r
call :d
if %r%==%s% echo %i%)&exit/b
goto r
:d                              Add the next decimal place
set /a r *= 10
set /a n = r / d
set /a r %= d
set i=%i%%n%
\$\endgroup\$
  • 2
    \$\begingroup\$ I have no idea how any of this works, but I commend you for doing it in batch lmao \$\endgroup\$ – Alexander Aug 9 '16 at 17:10
  • \$\begingroup\$ I'm impressed with the capabilities of set /a. \$\endgroup\$ – Joe Aug 11 '16 at 3:22
2
\$\begingroup\$

Java, 625 605

Golfed code:

import static java.math.BigInteger.*;
String f(BigInteger a, BigInteger b){BigInteger[]r=a.divideAndRemainder(b);String s=r[0].toString();if(r[1].signum()<0)s="-"+s;if(!ZERO.equals(r[1])){s+='.';List<BigInteger>x=new ArrayList();List<BigInteger>y=new ArrayList();for(BigInteger d=TEN.multiply(r[1].abs());;){BigInteger[]z=d.divideAndRemainder(b.abs());int i=y.indexOf(z[1]);if(i>-1&&i==x.indexOf(z[0])){for(int j=0;j<i;++j)s+=x.get(j);s+='(';for(int j=i;j<x.size();++j)s+=x.get(j);s+=')';break;}x.add(z[0]);y.add(z[1]);if(ZERO.equals(z[1])){for(BigInteger j:x)s+=j;break;}d=TEN.multiply(z[1]);}}return s;}

Note: I count the static import as part of the function for golfing purposes.

This function starts out by getting the division result. It adds the integral portion and sign, if necessary. Then if there is a remainder, it performs base 10 long division. At each step, perform the division. Store the calculated digit and the remainder in two lists. If we encounter the same digit and remainder again, there is a repeated portion and we know what index it starts at. The code either adds the digits (no repeat) or the pre-repeat digits, then the repeated digits enclosed in parentheses.

This is a bit big mostly because of BigInteger. If the inputs did not overflow even a long then it could be a bit shorter. Still, I expect there are ways to improve this entry.

Ungolfed code with main method for testing:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import static java.math.BigInteger.*;

public class FractionToExactDecimal {

  public static void main(String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "123562375921304812375087183597", "2777", "44494913907563850333124661" },
      { "81", "3", "27" },
      { "-6", "2", "-3" },
      { "1", "2", "0.5" },
      { "3289323463", "-250000000", "-13.157293852" },
      { "-1", "3", "-0.(3)" },
      { "235", "14", "16.7(857142)" },
      { "123", "321", "0.(38317757009345794392523364485981308411214953271028037)" },
      { "355", "113", "3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println(data[0] + " / " + data[1]);
      System.out.println("  Expected -> " + data[2]);
      System.out.print("    Actual -> ");
      System.out.println(new FractionToExactDecimal().f(new BigInteger(data[0]), new BigInteger(data[1])));
      System.out.println();
    }
  }

  // Begin golf
  String f(BigInteger a, BigInteger b) {
    BigInteger[] r = a.divideAndRemainder(b);
    String s = r[0].toString();
    if (r[1].signum() < 0) s = "-" + s;
    if (!ZERO.equals(r[1])) {
      s += '.';
      List<BigInteger> x = new ArrayList();
      List<BigInteger> y = new ArrayList();
      for (BigInteger d = TEN.multiply(r[1].abs());;) {
        BigInteger[] z = d.divideAndRemainder(b.abs());
        int i = y.indexOf(z[1]);
        if (i > -1 && i == x.indexOf(z[0])) {
          for (int j = 0; j < i; ++j)
            s += x.get(j);
          s += '(';
          for (int j = i; j < x.size(); ++j)
            s += x.get(j);
          s += ')';
          break;
        }
        x.add(z[0]);
        y.add(z[1]);
        if (ZERO.equals(z[1])) {
          for (BigInteger j : x)
            s += j;
          break;
        }
        d = TEN.multiply(z[1]);
      }
    }
    return s;
  }
  // End golf
}

Program output:

123562375921304812375087183597 / 2777
  Expected -> 44494913907563850333124661
    Actual -> 44494913907563850333124661

81 / 3
  Expected -> 27
    Actual -> 27

-6 / 2
  Expected -> -3
    Actual -> -3

1 / 2
  Expected -> 0.5
    Actual -> 0.5

3289323463 / -250000000
  Expected -> -13.157293852
    Actual -> -13.157293852

-1 / 3
  Expected -> -0.(3)
    Actual -> -0.(3)

235 / 14
  Expected -> 16.7(857142)
    Actual -> 16.7(857142)

123 / 321
  Expected -> 0.(38317757009345794392523364485981308411214953271028037)
    Actual -> 0.(38317757009345794392523364485981308411214953271028037)

355 / 113
  Expected -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)
    Actual -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)
\$\endgroup\$
  • \$\begingroup\$ Nice! I think you can save a few bytes by making this a function that returns a string, and by removing that one space in a, BigInteger. I also think you could alias BigInteger.TEN and BigInteger.ZERO. \$\endgroup\$ – FryAmTheEggman Aug 9 '16 at 21:07
  • \$\begingroup\$ @FryAmTheEggman thanks, I didn't realize the static import saved space over the more verbose references. It does. I also found a few other things I had missed, such as while (true) -> for (;;) which also allowed me to put stuff in the for initializer, saving another byte. \$\endgroup\$ – user18932 Aug 9 '16 at 21:23
  • \$\begingroup\$ First, how about extending BigInteger? Second, a repeated remainder is enough to show it repeats; if you limit the input to int you can use an int[] with the remainder as index and the index as value, if that makes sense. \$\endgroup\$ – JollyJoker Aug 10 '16 at 7:15
  • \$\begingroup\$ @JollyJoker extending BigInteger would require writing a whole class to try to save space, and I seriously doubt the tradeoff would work. Plus, I cannot restrict input. Anyway, there are eight instances of the text BigInteger in my code, and I don't see how adding more code to shrink them to a single character class name will pay off. And certainly adding code to deal with int[] (which BigInteger already does internally) will only bloat my answer. \$\endgroup\$ – user18932 Aug 10 '16 at 21:23
  • \$\begingroup\$ @JollyJoker it is also worth mentioning that unless I override every BigInteger method I call to return an instance of the subclass, I will need to add several casts which further bloat the code. On top of the wasted bytes for a subclass's overhead, that would certainly increase the code size. \$\endgroup\$ – user18932 Aug 10 '16 at 21:26
1
\$\begingroup\$

PHP, 277 Bytes

list(,$n,$d)=$argv;$a[]=$n;$n-=$d*$r[]=$n/$d^0;!$n?:$r[]=".";while($n&&!$t){$n*=10;$n-=$d*$r[]=$n/$d^0;$t=in_array($n%=$d,$a);$a[]=$n;}if($t){$l=count($a)-($p=array_search(end($a),$a));echo join(array_slice($r,0,2+$p))."(".join(array_slice($r,2+$p,$l)).")";}else echo join($r);
\$\endgroup\$
0
\$\begingroup\$

Mathematica 198 bytes

i=Integer;t=ToString;a_~h~b_:=f[a/b];f@q_i:= t@q;
f@q_:=""<>{t@IntegerPart[q],".",RealDigits[FractionalPart[q]][[1]]//.{{x___,{k__i}}:> {x,"("<>(t/@{k})<>")"},{x__i,j___String}:>""<> {""<>t/@{x},j}}}

UnGolfed

(* hand over quotient of a, b to function f *)
h[a_, b_] := f[a/b];

(* if the quotient is an integer, return it as a string *)
f[q_Integer] := ToString@q;

(* otherwise, return the integer part, followed by a decimal point ...*)
f[q_] := "" <> {ToString@IntegerPart[q], ".", 

   (* replacing the repeating part (if it exists) between parentheses *)
   RealDigits[FractionalPart[q]][[1]] //. {{x___, {i__Integer}} :> {x, "(" <>(ToString /@ {i}) <> ")"},

   (* and the non-repeating part (if it exists) without parentheses *)
   {x__Integer, i___String} :> "" <> {"" <> ToString /@ {x}, i}}}

Tests

h @@@ {{81, 3}, {-81, 3}, {1, 4}, {-13, 3}, {19, 7}, {3289323463, 25000}, {235, 14}, {1325, 14}}

{"27", "-27", "0.25", "-4.(3)", "2.(714285)", "131572.93852", "16.7(857142)", "94.6(428571)"}

\$\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.