Esse desafio é baseado na ideia do inversor da Plouffle .
Escreva um programa em qualquer idioma que faça o seguinte:
Toma como entrada um número racional não negativo,
Xescrito em decimal, por exemplo 34.147425.Retorna uma expressão matemática usando apenas números inteiros não negativos, espaços em branco, parênteses e os seguintes operadores binários:
- Adição
+ - Subtração
- - Multiplicação
* - Divisão
/ - Exponenciação
^
A expressão deve ser avaliada como
X, ou pelo menos concordar com todos os dígitos deX. Para continuar o exemplo, uma saída correta pode ser13 + 20^(5/4) / 2, já que 13 + 20 ^ (5/4) / 2 = 34.1474252688 ...- Adição
A saída pode opcionalmente ser escrita em notação polonesa (prefixo) ou notação polonesa reversa (postfix), ou seja,
+ 13 / ^ 20 / 5 4 2está correta.
O programa está sujeito às seguintes retribuições:
As brechas padrão são proibidas! Em particular, o programa não pode ler nenhuma tabela de pesquisa externa.
O código fonte do programa deve ter menos de 1024 caracteres.
O programa com a menor taxa de compressão média vencerá.
Para determinar sua taxa de compactação média, você pode usar o seguinte script Python ou escrever seu próprio programa equivalente. Aqui está a lista de 1000 números aleatórios.
import random
def f(x):
# edit this function so that it will return
# the output of your program given x as input
return "1 + 1"
random.seed(666)
S = 1000 # number of samples
t = 0.0
for n in xrange(0, S):
# pick a random decimal number
x = random.uniform(0, 1000)
# compute the compression ratio
# length of output / length of input
r = len(f(x).translate(None, " +-*/^()")) / float(len(str(x).translate(None, ".")))
t += r
print "Your average compression ratio is:", t / S
Boa sorte!
NOTAS:
Espaços em branco na saída não são obrigatórios. Cordas gosta
1+1,1 +2ou1 + 2, estão todos bem. De fato, o script para calcular a pontuação não conta espaços em branco e parênteses no comprimento da saída. No entanto, observe que o uso de espaços em branco é necessário se você escolher notação polonesa ou invertida.Em relação à notação de infixo usual, as regras de precedência são as seguintes: primeiro toda exponenciação (
^), depois todas as divisões (/), depois todas as multiplicações (*), depois todas as adições (+) e todas as subtrações (-). Mas não sei o quanto isso poderia importar, pois você pode usar parênteses.Uma maneira de editar a função
fno script acima pode ser a seguinte, no entanto, acho que depende do seu sistema operacional; no GNU / Linux funciona. Nomeie seu programa "inverter" (ou "inverter.exe") e coloque-o no mesmo diretório que o script Python. Seu programa deve serXo primeiro argumento da linha de comando e retornar a expressão em STDOUT. Edite dafseguinte maneira:import os def f(x): return os.popen("./inverter " + str(x)).read()
EDIT: Como conseqüência do comentário de Thomas Kwa, agora os operadores não contribuem para o comprimento da expressão. O desafio deve ser mais "desafiador".
fonte
X = 5.23um valor de5.2301está ok, mas5.2299não?Respostas:
Haskell, 1.08404005439
Isso usa a
approxRationalfunção que converte um número de ponto flutuante em uma fração com a precisão de um dado epsilon. Simplesmente retorna essa fração. Como Haskell imprime os racionais com um%intermediário, temos que substituí-lo pelo sinal de divisão/.O parâmetro de precisão é calculado a partir do número de entrada. Temos que levar em consideração que todos os dígitos precisam corresponder, então
4.39é bom,4.3mas4.29não é. Anexo5a ao número e a precisão está4999na mesma casa decimal que a anexada5, por exemploPor exemplo
34.147425->43777/1282.Editar: as regras de precisão foram alteradas. O caso de teste inclui números com até 11 casas decimais e todos precisam corresponder.
Edit II: parece que o script Python fornece não retira novas linhas, então mudei de
putStrLnparaputStr.Edit III: novamente, novas regras de pontuação
fonte
1e-6também funciona, mas isso não é codegolf ...Mathematica,
1.10121.10976107226107Até agora, esta tem a menor pontuação! Dá o racional com o menor denominador, dados os dígitos. (Desculpe pela ilegibilidade, esqueci que este não era um concurso de golfe por um minuto.) Alguns testes:
fonte
Python, 1.25927791772
Estou surpreso que ninguém mais tenha tentado a abordagem óbvia, que gera cerca de 26% de sobrecarga:
Isso apenas se converte
XX.XXXXemXXXXXX/10^4e assim por diante. Para a maioria dos números de teste, isso significa converter 12 dígitos (e um ponto decimal não contado) nos mesmos 12 dígitos e mais três (mais dois símbolos não contados).fonte
JavaScript 1.7056771894771656
Pontuação muito simples, muito ruim
fonte
Python, 1.9901028749
Infelizmente, as frações continuadas acabam não sendo um candidato sério.
exemplos:
fonte
Python, 1.10900874126
Avaliar de fato as frações continuadas em minha resposta anterior produz o equivalente à resposta matemática de @ LegionMammal978, que eu acho que é o ideal ingênuo. Para fazer melhor do que isso, será necessário ser criativo com a representação dos números inteiros, possivelmente incluindo a busca de frações abaixo do ideal para obter números inteiros mais fáceis de representar.
exemplos:
fonte