Troque algumas partes periódicas e não periódicas

21

Na representação decimal de todo número racional p/q, você tem uma cauda periódica, uma cabeça não periódica e uma seção antes do ponto decimal no seguinte formato:

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

Alguns exemplos incluem:

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)

O desafio é trocar as partes periódicas e não periódicas, deixando before decimal pointsozinho, para criar um novo número. Por exemplo:

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

Se um número não possui parte periódica, como 0.25transformar esse número em um novo número periódico, e 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

O desafio

  • Tome uma fração xcomo entrada, como uma string, duas entradas, um número racional ou qualquer outro método adequado ao seu idioma.
  • Troque as partes periódicas e não periódicas da representação decimal de xpara criar um novo número, deixando a parte antes do decimal sozinha. A parte periódica sempre começa o mais rápido possível, para que a parte não periódica seja o mais curta possível. Exemplos estão abaixo.
  • Retorne o número trocado como uma nova fração. A entrada não é necessariamente reduzida, embora a saída deva ser. É permitido que o formato de entrada seja diferente do formato de saída.
  • O numerador pde xserá um número inteiro com valor absoluto de um milhão ou menos e o denominador qde xserá um número inteiro diferente de zero com valor absoluto de um milhão ou menos.
  • Não é garantido que o numerador re o denominador sdo resultado sejam inferiores a um milhão. Dado o comprimento das partes periódicas desses números, é recomendável evitar a conversão direta em flutuadores.
  • Isso é código de golfe. A resposta mais curta em bytes vence.

Exemplos

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
fonte
Há uma falta 0no final do caso de teste 2 ( 10/7): 1428571/100000deveria ser 1428571/1000000.
JungHwan Min
11
Como afirmado, não haverá uma resposta exclusiva para uma determinada entrada. 1/7Pode ser representado como (0).()(142857) ou (0).(1)(428571), 1pode ser representada como (1).()(), (0).()(9), (0).()(99), (0).(9)(9), etc
ngenisis
@ngenisis Isso estava implícito nos exemplos, mas eu expliquei isso. Obrigado pelo feedback :)
Sherlock9
@ R.Kap Eu já afirmei no desafio que é melhor evitar o uso de carros alegóricos aqui. Existem maneiras de encontrar os dígitos decimais de um número sem converter em um número flutuante. Espero que isso responda à sua pergunta :) #
Sherlock9
tanto pe quanto q podem ser negativos?
edc65

Respostas:

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)

Versão ungolfed, funciona em python 2 e 3. Também imprime representação decimal.

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.
fonte
Tented=10**len(p+a)
Sherlock,
11
Aqui está um link do TIO para testes fáceis: Experimente online!
Kritixi Lithos
Muito bem na sua resposta: D. Algumas dicas adicionais sobre golfe: use mais pontos e vírgulas sempre que possível, livre-se do espaço na linha if n==0: p='', use ``em todos os lugares que você usar str, como em `n/d`vez de str(n/d), e renomeie lenpara Lcom L=len;no início da função.
Sherlock9
@ Sherlock9 Eu nem sabia sobre os backticks. Obrigado por todos os conselhos.
Rainer P.
Não é um problema. Aqui está mais um pouco: D Dois lugares para ponto n=int(b+p+a);d=10**L(p+a)e vírgula: e import fractions as f;g=f.gcd(n,d);return(n/g*s,d/g). Além disso, recebo 295 bytes para sua edição atual. Existe uma nova linha extra que você está esquecendo de deixar de fora?
Sherlock9
2

Geléia , 102 101 89 87 83 81 79 78 77 74 bytes

Isso levou muito tempo para escrever, muito tempo para depurar e definitivamente precisa de muito golfe ( oito sete seis cinco quatro links, vaca sagrada), mas é, dentro do meu conhecimento, correto. Muito, muito obrigado a Dennis por sua ajuda aqui, especialmente com os dois primeiros links. Muito obrigado a Rainer P., pois acabei pegando emprestado muito do algoritmo na resposta em Python.

Edições de golfe: -1 byte graças a Xanderhall. Correção de bug por não usar o NÃO lógico correto incorporado. -13 bytes de golfe nos links do numerador. +1 byte para corrigir um erro negativo, dgraças a Dennis. Reestruturou os links para que a geração do numerador fique em um único link. -2 bytes da combinação do segundo e terceiro links. -4 bytes de mover alguns elementos comuns do terceiro e quarto links para o segundo e o link principal. -2 bytes da remoção de alguns operadores de cadeia supérfluos. -2 bytes de reorganizar o link do numerador. -1 byte da mudança Ḣ€para o final do segundo link. Corrigido um erro no link principal. -1 byte da alteração Ṫ ... ,Ḣpara Ḣ ... ṭ. -3 bytes de mover o link do numerador para o link principal.

Sugestões de golfe são bem-vindas! Experimente online!

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

Explicação

Primeiro, explicarei o link principal , que chama os outros 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.

Em seguida, o primeiro link que obtém os dígitos.

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.

Agora, o segundo link que recebe as partes periódicas e não periódicas n/de muitas outras atividades pesadas.

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

O terceiro link , que produz nosso novo denominador.

Ç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
fonte