Fraction Frenzy!

9

EDIT: Estou recebendo muitos comentários sobre isso não terminando - darei a tag "resposta correta" para a primeira pessoa que me FF(3)fornecer (como fornece na resposta) ou comprova que FF(3), de fato, explode indefinidamente.

Tarefa:

Sua tarefa é tornar o menor programa possível que gere a lista de recíprocos da função Fraction Frenzy ( FF(n)), dado um número inteiro positivo n.

Introdução:

Antes de poder introduzir a função FF, preciso primeiro explicar as frações egípcias.

Frações egípcias:

As frações egípcias são uma maneira de expressar frações como a soma de frações unitárias distintas - então, uma maneira de expressar a fração 5/8é 1/2 + 1/8. Não são outras somas de fração como

1/4 + 1/4 + 1/8
1/2 + 1/16 + 1/16

porque nem todas as frações são distintas ( 1/4é repetida no primeiro exemplo e 1/16no segundo).

Em nossa definição de frações egípcias, estamos incluindo o uso de denominadores negativos nas frações unitárias.

Função FF:

A função FF (Fraction Frenzy) é descrita assim:

FF(1)é a fração egípcia 1/2 + 1/3 + 1/5 + 1/-30.

FF(2)é igual a FF(1)"multiplicado" por si só ( FF(1)"ao quadrado"):

  (1/2 + 1/3 + 1/5 + 1/-30)(1/2 + 1/3 + 1/5 + 1/-30)
= 1/4 + 1/6 + 1/10 + 1/-60 + 1/6 + 1/9 + 1/15 + 1/-90 +
  1/10 + 1/15 + 1/25 + 1/-150 + 1/-60 + 1/-90 + 1/-150 + 1/900

Esta ainda não é uma fração egípcia totalmente reduzida, porque há "repetições" em frações. Para reduzi-los, o seguinte procedimento é feito:

  1. Soma todas as frações de unidade "like" juntas.
  2. Reduza as somas para as formas mais simples - por exemplo, se uma soma da etapa 1for 2/6, isso pode ser reduzido para 1/3.
  3. Repita 1 e 2 até que todos os denominadores sejam distintos: por exemplo 1/2 + 2/3 + 1/5, ao contrário de 1/2 + 1/3 + 1/3, que possui um denominador repetitivo 3.
  4. Se houver um par de uma fração positiva e uma fração negativa que tenham um valor absoluto igual, remova os dois (por exemplo, 1/-5e 1/5devem ser removidos).
  5. Se as frações não forem unitárias e não puderem ser reduzidas ainda mais, divida-as em frações unitárias com um denominador igual e mantenha uma fração como está. Com os outros, multiplicá-los por FF(1): (1/2 + 1/3 + 1/5 + 1/-30).
  6. Repita as etapas 1 a 5 até que a soma da fração final seja uma fração egípcia válida - ou seja, todas as frações são distintas uma da outra e todas são frações unitárias.

Esta é a redução de FF(2):

  1/4 + 1/6 + 1/10 + 1/-60 + 1/6 + 1/9 + 1/15 + 1/-90 +
  1/10 + 1/15 + 1/25 + 1/-150 + 1/-60 + 1/-90 + 1/-150 + 1/900
= 1/4 + 2/6 + 1/9 + 2/10 + 2/15 + 1/25 + 2/-60 + 2/-90 + 2/-150 + 1/900 (step 1)
= 1/4 + 1/3 + 1/9 + 1/5 + 2/15 + 1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900   (step 2)
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/15(1/2 + 1/3 + 1/5 + 1/-30) +        (step 5)
  1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/30 + 1/45 + 1/75 + 1/-450 +
  1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/25 + 1/-450 + 1/900                  (step 4)

Para todos n(exceto 1), FF(n)é definido por "quadrado" FF(n-1).

Entrada e saída:

Dado um número inteiro n, você deve exibir uma lista de todos os recíprocos de FF(n), classificados em ordem crescente de seus valores absolutos:

1 -> [2, 3, 5, -30]
# 1/2 + 1/3 + 1/5 + 1/-30 = FF(1), reciprocals = [2, 3, 5, -30]

2 -> [3, 4, 5, 9, 15, 25, -450, 900]

Você tem permissão para usar uma string com qualquer delimitador ou a interpretação de uma lista no seu idioma, portanto, essas saídas são aceitáveis ​​com a entrada 1:

2 3 5 -30   (Space-delimited)
2,3,5,-30   (Comma-delimited)
[2 3 5 -30] (Lisp-like lists)
etc. etc.

Especificações:

  • Você deve gerar os resultados da FF(n)função exatamente como especificado acima.
  • Você tem a garantia de que a entrada será um número inteiro positivo - nunca será abaixo de zero e nunca será um decimal (ou fração).

Isso é , então o código mais curto em bytes vence!

clismique
fonte
4
Por curiosidade, isso é garantido para terminar?
Martin Ender
Confirmo que FF (3) parece explodir. Você não testou isso até FF (10) antes de postar na sandbox?
Peter Taylor
2
As frações egípcias não tinham valores negativos, portanto não é realmente uma fração egípcia.
mbomb007

Respostas:

1

Haskell , 365 bytes

import Data.Function;import Data.List;import Data.Ratio;n=numerator;d=denominator
r=until=<<((==)=<<)$filter(/=0).map(sum).groupBy((==)`on`d).sortBy(compare`on`d)
p s=let(o,q)=span((<2).abs.n)s in case q of []->o;(a:b)->let j=a-1%d a*signum a in p.r$o++[a-j]++map(*j)e++b
s s=(*)<$>s<*>s;e=(1%)<$>[2,3,5,-30];f=iterate(p.r.s)e;o i=[abs(d q)*signum(n q)|q<-f!!(i-1)]

Experimente online!

Roman Czyborra
fonte
Hmm… eu corro em um loop aparentemente infinito ao dividir a maior não unidade e verificá-la novamente como apresentado e já o havia feito ao dividir a menor não unidade em sentido inverso à esquerda ou globalmente todas as não-unidades antes de verificar novamente, mas talvez eu devesse não deixar de escolher não-deterministicamente não-unidades entre se alguém cancela outras suficientes para atingir um FF finito (3)?
Roman Czyborra
Usando (1%)<$>[2,4,6,12] como um meramente procrastinates o nontermination de FF (3) a FF (4) 😠
romano Czyborra
(1%)<$>[2,3,10,15]ou (1%)<$>[3,4,6,8,12,24]produzir nenhuma melhoria em tudo 🤔
Roman Czyborra