Поменяйте местами некоторые периодические и непериодические части

21

В десятичном представлении каждого рационального числа у p/qвас есть периодический хвост, непериодическая головка и раздел перед десятичной точкой в ​​следующем формате:

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

Вот некоторые примеры:

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)

Задача состоит в том, чтобы поменять местами периодические и непериодические части, оставив before decimal pointодни, чтобы создать новое число. Например:

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

Если число не имеет периодической части, как, например, 0.25превратить это число в новое периодическое число, и наоборот.

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

Соревнование

  • Возьмите дробь в xкачестве ввода, в виде строки, двух входных данных, рационального числа или любого другого метода, который подходит вашему языку.
  • Поменяйте местами периодические и непериодические части десятичного представления, xчтобы создать новое число, оставив часть перед одним десятичным знаком. Периодическая часть всегда начинается как можно скорее, поэтому непериодическая часть должна быть как можно короче. Примеры ниже.
  • Вернуть поменяемый номер как новую дробь. Ввод не обязательно уменьшается, хотя выход должен быть. Входной формат может отличаться от выходного формата.
  • Числитель pиз xбудет целым с абсолютным значением одного миллиона или меньше , и знаменателем qв xбудет отличен от нуля целого числа с абсолютным значением одного миллиона или меньше.
  • Числитель rи знаменатель sрезультата не гарантированно будут меньше одного миллиона. Учитывая длину периодических частей этих чисел, рекомендуется избегать прямого преобразования в числа с плавающей точкой.
  • Это код гольф. Кратчайший ответ в байтах побеждает.

Примеры

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
источник
Существует недостающее 0в конце теста 2 ( 10/7): 1428571/100000должно быть 1428571/1000000.
JungHwan Мин
1
Как указано, не будет уникального ответа для данного входа. 1/7может быть представлена в виде , (0).()(142857) или (0).(1)(428571), 1может быть представлена в виде (1).()(), (0).()(9), (0).()(99), (0).(9)(9)и т.д.
ngenisis
@ngenisis Это было неявно в примерах, но я сделал это явным. Спасибо за отзыв :)
Sherlock9
@ R.Kap Я уже говорил в конкурсе, что лучше избегать использования поплавков здесь. Есть способы найти десятичные цифры числа без преобразования в число с плавающей точкой. Я надеюсь, что это отвечает на ваш вопрос :)
Sherlock9
могут ли p и q быть отрицательными?
edc65

Ответы:

5

Python 2, 292 байта

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 версия, работает как в Python 2 и 3. Также печатает десятичное представление.

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)
Райнер П.
источник
Попробуйтеd=10**len(p+a)
Sherlock9
1
Вот ссылка TIO для простого тестирования: попробуйте онлайн!
Kritixi Lithos
Молодцы на ваш ответ: D. Некоторые дополнительные гольфы советы: использование более запятая , где это возможно, избавиться от пространства в линии if n==0: p='', использование ``в любом месте вы используете str, например, `n/d`вместо того str(n/d), переименовывать lenк Lс L=len;в начале функции.
Sherlock9
@ Sherlock9 Я даже не знал об обратном. Спасибо за все советы.
Райнер П.
Не проблема. Вот еще немного: D Два места для точек с запятой: n=int(b+p+a);d=10**L(p+a)и import fractions as f;g=f.gcd(n,d);return(n/g*s,d/g). Кроме того, я получаю 295 байт для вашего текущего редактирования. Есть ли дополнительный символ новой строки, который вы забыли пропустить?
Sherlock9
2

Желе , 102 101 89 87 83 81 79 78 77 74 байта

Это заняло много времени, чтобы написать, слишком долго для отладки, и определенно нужно много играть в гольф ( восемь семь шесть пять четыре ссылки, святая корова), но, насколько я знаю, это правильно. Огромное спасибо Деннису за помощь, особенно с первыми двумя ссылками. Большое спасибо и Райнеру П., так как в итоге я позаимствовал много алгоритма в их ответе на Python.

Редактирование гольфа: -1 байт благодаря Ксандерхоллу. Исправлена ​​ошибка, из-за которой не использовалась правильная логическая НЕ встроенная функция. -13 байтов от связи с нумератором. +1 байт от исправления ошибки за минус dс Деннисом. Перестроил ссылки так, чтобы генерация числителя была в одной ссылке. -2 байта от объединения второй и третьей ссылок. -4 байта от перемещения некоторых общих элементов третьей и четвертой ссылок на вторую ссылку и основную ссылку. -2 байта от удаления некоторых лишних операторов цепочки. -2 байта от перестановки ссылки нумератора. -1 байт от перехода Ḣ€к концу второй ссылки. Исправлена ​​ошибка в основной ссылке. -1 байт от изменения Ṫ ... ,Ḣдо Ḣ ... ṭ. -3 байта от перемещения ссылки нумератора в основную ссылку.

Предложения по игре в гольф приветствуются! Попробуйте онлайн!

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

объяснение

Сначала я объясню основную ссылку , которая называет другие ссылки.

×Ṡ©⁸×%µ³,⁴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.

Затем первая ссылка, которая получает цифры.

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.

Теперь вторая ссылка, которая получает периодические и непериодические части n/d, и много других тяжелых работ.

ÇÐḶ,ÇÐĿḟ@\µḢḅÐ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.

Третье звено , которое дает наш новый знаменатель.

Ç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
источник