Swap out some periodic and non-periodic parts

21

5

In the decimal representation of every rational number p/q, you have a periodic tail, a non-periodic head, and a section before the decimal point in the following format:

(before decimal point).(non-periodic)(periodic)

Some examples include:

1/70 = 0.0142857... = (0).(0)(142857)
10/7 = 1.428571... = (1).()(428571)            ## no non-periodic part
1/13 = 0.076923... = (0).()(076923)
3/40 = 0.075 = (0).(075)()                    ## no periodic part
-2/15 = -0.13... = -(0).(1)(3)                ## negative
75/38 = 1.9736842105263157894... = (1).(9)(736842105263157894)
                                              ## periodic part longer than float can handle
25/168 = 0.148809523... = (0).(148)(809523)
120/99 = 40/33 = 1.212121... = (1).()(21)
2/1 = 2 = (2).()()                            ## no periodic, no non-periodic
0/1 = 0 = (0).()()
0/2 = 0 = (0).()()
299/792 = 0.37752... = (0).(377)(52)
95/-14 = -6.7857142... = -(6).(7)(857142)
-95/-14 = 6.7857142... = (6).(7)(857142)

The challenge is to swap the periodic and non-periodic parts, leaving the before decimal point alone, to create a new number. For example:

25/168 = 0.148809523... = (0).(148)(809523)
       => (0).(809523)(148) = 0.809523148148... = 870397/1080000

If a number has no periodic part like 0.25 turn that number into a new periodic number, and vice versa.

1/4 = 0.25 = (0).(25)() => (0).()(25) = 0.252525... = 25/99
4/9 = 0.444444... = (0).()(4) => (0).(4)() = 0.4 = 2/5
5/1 = 5 = (5).()() => (5).()() = 5 = 5/1

The challenge

  • Take a fraction x as input, as a string, two inputs, a rational number, or whatever method suits your language.
  • Swap the periodic and non-periodic parts of the decimal representation of x to create a new number, leaving the part before the decimal alone. The periodic part always starts as soon as possible so that the non-periodic part is as short as possible. Examples are below.
  • Return the swapped number as a new fraction. The input is not necessarily reduced though the output should be. Input format is allowed to differ from output format.
  • The numerator p of x will be an integer with absolute value of one million or less and the denominator q of x will be a non-zero integer with absolute value of one million or less.
  • The numerator r and denominator s of the result is not guaranteed to be less than one million. Given the length of the periodic parts of these numbers, it is recommended that you avoid directly converting to floats.
  • This is code golf. Shortest answer in bytes wins.

Examples

1/70 = (0).(0)(142857)     => (0).(142857)(0) = (0).(142857)() = 0.142857 = 142857/1000000
10/7 = (1).()(428571)      => (1).(428571)() = 1.428571 = 1428571/1000000
1/13 = (0).()(076923)      => (0).(076923)() = 0.076293 = 76923/1000000
3/40 = (0).(075)()         => (0).()(075) = 0.075075... = 75/999 = 25/333
-2/15 = -(0).(1)(3)        => -(0).(3)(1) = -0.311111... = -28/90 = -14/45
75/38 = (1).(9)(736842105263157894)
      => (1).(736842105263157894)(9) = (1).(736842105263157895)()  ## since 0.999... = 1
      = 1.736842105263157895 = 1736842105263157895/1000000000000000000
      = 347368421052631579/200000000000000000
25/168 = (0).(148)(809523) => (0).(809523)(148) = 0.809523148148... = 870397/1080000
120/99 = (1).()(21)        => (1).(21)() = 1.21 = 121/100
2/1 = (2).()()             => (2).()() = 2 = 2/1
0/1 = (0).()()             => (0).()() = 0 = 0/1
0/2 = (0).()()             => (0).()() = 0 = 0/1
299/792 = (0).(377)(52)    => (0).(52)(377) = 0.52377377... = 2093/3996
95/-14 = -(6).(7)(857142)  => -(6).(857142)(7) = -6.857142777... = -12342857/1800000
-95/-14 = (6).(7)(857142)  => (6).(857142)(7) = 6.857142777... = 12342857/1800000

Sherlock9

Posted 2016-12-11T10:26:06.357

Reputation: 11 664

There is a missing 0 at the end of test case 2 (10/7): 1428571/100000 should be 1428571/1000000. – JungHwan Min – 2016-12-11T21:30:54.397

1As stated there won't be a unique answer for a given input. 1/7 could be represented as (0).()(142857) or (0).(1)(428571), 1 could be represented as (1).()(), (0).()(9), (0).()(99), (0).(9)(9), etc. – ngenisis – 2016-12-11T23:40:13.257

@ngenisis That was implicit in the examples, but I have made it explicit. Thanks for the feedback :) – Sherlock9 – 2016-12-12T02:17:26.117

@R.Kap I have already stated in the challenge that it is best to avoid using floats here. There are ways to find the decimal digits of a number without converting to a float. I hope this answers your question :) – Sherlock9 – 2016-12-12T02:20:37.720

can both p and q be negative? – edc65 – 2016-12-23T13:51:40.383

@edc65 Yes. I'll edit in a test case – Sherlock9 – 2016-12-23T13:54:32.473

Answers

5

Python 2, 292 bytes

def x(n,d):
 L=len;s=cmp(n*d,0);n*=s;b=p=`n/d`;a={};n%=d
 while not n in a:
  a[n]=p;q=n/d;n=n%d
  if q==0:n*=10;p+=' '
  p=p[:-1]+`q`
 p=p[L(a[n]):];a=a[n][L(b):]
 if n==0:p=''
 n=int(b+p+a);d=10**L(p+a)
 if a!='':n-=int(b+p);d-=10**L(p)
 import fractions as f;g=f.gcd(n,d);return(n/g*s,d/g)

Ungolfed version, works in both python 2&3. Also prints decimal representation.

def x(n,d):
# sign handling
 s=n*d>0-n*d<0
 n*=s
# b, a, p: BEFORE decimal, AFTER decimal, PERIODIC part
 b=p=str(n//d)
 a={}
 n%=d
# long division
 while not n in a:
  a[n]=p
  q=n//d
  n=n%d
  if q==0:
   n*=10
   p+=' '
  p=p[:-1]+str(q)
# a/p still contain b/ba as prefixes, remove them
 p=p[len(a[n]):]
 a=a[n][len(b):]
 if n==0: p=''
# print decimal representation
 print("(" + b + ").(" + a + ")(" + p + ")")
# reassemble fraction (with a and p exchanged)
 n=int(b+p+a)
 d=10**len(p+a)
 if a!='':
  n-=int(b+p)
  d-=10**len(p)
# reduce output
 from fractions import gcd
 g=gcd(n,d)
 return(n//g*s,d//g)

Rainer P.

Posted 2016-12-11T10:26:06.357

Reputation: 2 457

Try d=10**len(p+a) – Sherlock9 – 2016-12-11T18:20:26.797

1

Here's a TIO link for easy testing: Try it online!

– user41805 – 2016-12-11T18:21:35.037

Well done on your answer :D. Some further golfing tips: use more semicolons where possible, get rid of the space in the line if n==0: p='', use \`` in every place you use str, such as \n/d`` instead of str(n/d), and rename len to L with L=len; at the beginning of the function. – Sherlock9 – 2016-12-11T18:35:33.780

@Sherlock9 I didn't even know about the backticks. Thanks for all the advice. – Rainer P. – 2016-12-11T18:42:38.407

Not a problem. Here's some more :D Two places for semicolons: n=int(b+p+a);d=10**L(p+a) and import fractions as f;g=f.gcd(n,d);return(n/g*s,d/g). Also, I get 295 bytes for your current edit. Is there an extra newline you're forgetting to leave out? – Sherlock9 – 2016-12-11T18:42:54.287

@RainerP. do you have resources or algorithms that you followed explaining how to find the periodicity and to reconstruct the fraction? – dfernan – 2016-12-12T09:42:51.460

2

Jelly, 102 101 89 87 83 81 79 78 77 74 bytes

This took way to long to write, way too long to debug, and definitely needs a lot of golfing (eight seven six five four links, holy cow), but it is, to the best of my knowledge, correct. Many, many thanks to Dennis for his help here, especially with the first two links. Many thanks to Rainer P. as well, as I ended up borrowing a lot of the algorithm in their Python answer.

Golfing edits: -1 byte thanks to Xanderhall. Bug fix from not using the correct logical NOT builtin. -13 bytes from golfing the numerator links. +1 byte from fixing a bug for negative d with thanks to Dennis. Restructured the links so that the numerator generation is all in one link. -2 bytes from combining the second and third links. -4 bytes from moving some common elements of the third and fourth links to the second link and the main link. -2 bytes from removing some superfluous chain operators. -2 bytes from rearranging the numerator link. -1 byte from moving Ḣ€ to end of the second link. Fixed a bug in the main link. -1 byte from changing Ṫ ... ,Ḣ to Ḣ ... ṭ. -3 bytes from moving the numerator link into the main link.

Golfing suggestions welcome! Try it online!

2ị×⁵d⁴
ÇÐḶ,ÇÐĿḟ@\µḢḅÐfıṭµḢḊṭµḢ€€µF,ḢQ
ÇL€⁵*
×Ṡ©⁸×%µ³,⁴A:/;Ѐ2ĿḌ×®,Ç_/€µ:g/

Explanation

First, I'll explain the main link, which calls the other links.

×Ṡ©⁸×%µ³,⁴A:/;Ѐ2ĿḌ×®,Ç_/€µ:g/  Main link. Left argument: n (int), right argument: d (int)
                                Split into three chains.
×Ṡ©⁸×%  First chain
×       Multiply n by d.
 Ṡ©     Yield sign(n*d) and save it to the register.
   ⁸×   Multiply by n.
     %  Yield n*sgn(n*d) modulo d.

µ³,⁴A:/;Ѐ2ĿḌ×®,Ç_/€  Second chain
                        What follows is the formula for the numerator.
                        (+) means combining the digits of two numbers into one number.
                        ( `integer (+) periodic (+) non-periodic` - `integer (+) periodic` )
µ                     Start a new monadic chain with n*sgn(n*d)%d.
 ³,⁴                  Pair the original two arguments as a nilad.
    A                 Get their absolute values.
     :/               Integer divide to get the integer part of abs(n)/abs(d).
          2Ŀ          Yield the results of the second link.
       ;Ѐ            Append the integer part to each item in the right argument.
                        This appends to both lists from the second link.
            Ḍ         Convert each list from decimal to integer.
             ×®       Multiply by sign(n*d) retrieved from the register.
               ;Ç     Concatenate with the result of the third link (our new denominator).
                 _/€  Reduced subtract over each list.
                        Yields the proper numerator and denominator.

µ:g/  Third chain
µ     Start a new monadic chain with [numerator, denominator].
  g/  Yield gcd(numerator, denominator).
 :    Divide [numerator, denominator] by the gcd.
      Return this as our new fraction.

Then, the first link that gets the digits.

2ị×⁵d⁴  First link: Gets the decimal digits one at a time in the format:
          [digit, remainder to use in the next iteration]
2ị      Gets the second index (the remainder).
  ×⁵    Multiply by 10.
    d⁴  Divmod with d.

Now, the second link that gets the periodic and non-periodic parts of n/d, and a lot of other heavy lifting.

ÇÐḶ,ÇÐĿḟ@\µḢḅÐfıṭµḢḊṭµḢ€€µF,ḢQ  Second link: Loops the first link,
                                  separates the periodic digits and non-periodic digits,
                                  removes the extras to get only the decimal digits,
                                  and prepares for the third and fourth links.
                                Split into five chains.
ÇÐḶ,ÇÐĿḟ@\  First chain
ÇÐḶ         Loop and collect the intermediate results **in the loop**.
    ÇÐĿ     Loop and collect **all** of the intermediate results.
   ,        Pair into one list.
       ḟ@\  Filter the loop results out the list of all results,
              leaving only [[periodic part], [non-periodic part]].

µḢḅÐfıṭµḢḊṭ  Second and third chains
µ            Start a new monadic chain.
 Ḣ           Get the head [periodic part].
   Ðf        Filter out any [0, 0] lists from a non-periodic number,
  ḅ  ı        by converting to a complex number before filtering.
               Only removes 0+0j. This removes extra zeroes at the end.
      ṭ      Tack the result onto the left argument again.
       µ     Start a new monadic chain.
        Ḣ    Get the head [non-periodic and extra baggage].
         Ḋ   Dequeue the extra baggage.
          ṭ  Tack the result onto the left argument again.

µḢ€€µF,ḢQ  Fourth and fifth chains
µ          Start a new monadic chain with the processed periodic and non-periodic parts.
 Ḣ€€       Get the head of each list (the digits)
            in both the periodic and non-periodic parts.
    µ      Start a new monadic chain with these lists of digits.
     F     Left argument flattened.
       Ḣ   Head of the left argument.
      ,    Pair the flattened list and the head into one list.
        Q  Uniquify this list. (Only removes if non-periodic part is empty)
             Removes any duplicates resulting from a purely periodic n/d.

The third link, which yields our new denominator.

ÇL€⁵*  Third link: Generate the denominator.
         What follows is the formula for the denominator.
         ( 10**(num_digits) - ( 10**(num_periodic_digits) if len(non-periodic) else 0 ) )
Ç      Yield the results of the second link.
 L€    Get the length of each item in the list.
         The number of digits in total and the number of digits in the periodic part.
   ⁵*  10 to the power of each number of digits.

Sherlock9

Posted 2016-12-11T10:26:06.357

Reputation: 11 664