Metagolf Mania!

12

Mathemania Especificações:

Cada parte do código da Mathemania começa com o número 2. No 2, você pode executar as seguintes operações:

  • e: Exponenciação. O padrão deste comando é quadrado o número.
  • f: Fatorial. O padrão deste comando é usar o fatorial único no número ( using f on 2 = 2! = 2).
  • r: Raiz. O padrão deste comando é o número da raiz quadrada.
  • c: Função de teto.
  • l: Função de piso.

Para gerar um número no Mathemania, você deve encadear esses comandos, que são executados da esquerda para a direita no número 2.

Exemplos:

ef = (2^2)! = 4! = 24
rl = floor(sqrt(2)) = floor(1.4...) = 1
er = sqrt(2^2) = sqrt(4) = 2
efrrc = ceil(sqrt(sqrt((2^2)!)))
      = ceil(sqrt(sqrt(24)))
      = ceil(sqrt(4.89...))
      = ceil(2.21...)
      = 3

Os comandos e, fe rpodem ser alterados por comandos extras do Mathemania (que também começam com 2seu número "base") para gerar diferentes exponenciações, fatoriais e raízes, colocando colchetes após a função alterada e colocando os comandos do Mathemania dentro dele.

Por exemplo, para cubar um número em vez de quadrá-lo, você pode colocar o comando para 3depois da seguinte emaneira:

e(efrrc) -> cube a number, "efrrc" = 3

NOTA: para nosso propósito, o comando fatorial ( f) começa 2como um fatorial único. Portanto, se o fizer f(efrrc), isso será avaliado em fatorial duplo, e não triplo.

Para nfatoriais (por exemplo, fatorial duplo = fatorial 2, fatorial triplo = fatorial 3, etc.), o número base é multiplicado pelo número que é nmenor que ele, e nmenor que isso, e assim sucessivamente até que o número final não possa ser subtraído por nsem se tornar 0ou negativo.

Por exemplo:

7!! = 7 * 5 * 3 * 1 = 105 (repeatedly subtract 2, 1 is the last term as
                           1 - 2 = -1, which is negative)
9!!! = 9 * 6 * 3 = 162 (repeatedly subtract 3, 3 is the last term as
                        3 - 3 = 0, which is 0)

Para mais informações, clique aqui .

Você pode inseri-lo em qualquer lugar e ele será tratado pelo Mathemania como uma única função:

e(efrrc)rc = ceil(sqrt(2^3))
           = ceil(2.82...)
           = 3

Você também pode aninhar estes dentro um do outro:

e(e(e)) = e(4th power)
        = (2^4)th power
        = 16th power

Para um intérprete do código da Mathemania, clique aqui (felicidades, @ BradGilbertb2gills!)

Tarefa:

Sua tarefa é criar um programa que, quando recebe um número inteiro positivo ncomo entrada, gera um programa Mathemania que, quando executado, retorna n.

No entanto, os programas Mathemania que geram deve ser tão pequena (golfed) quanto possível, e sua pontuação final é determinado pela soma do número de bytes nos programas Mathemania gerados da amostra, que são os números inteiros 10,000para 10,100. A pontuação mais baixa vence.

Regras e especificações:

  • Seu programa deve gerar um programa Mathemania válido para qualquer número inteiro positivo, mas apenas os números entre 10,000e 10,100serão testados.
  • Você não tem permissão para produzir programas Mathemania que não resultam em um número inteiro. Se você fizer isso, seu programa será desqualificado.
  • Para os comandos e, fe r, o código Mathemania dentro dessas funções (por exemplo e(efrrc), onde a efrrcé o código no interior da função) deve ser avaliada como um número inteiro positivo acima 2. Se o seu programa não seguir esta regra, também será desqualificado.
  • Seu programa deve retornar um programa Mathemania para qualquer um dos 101 números inteiros de teste em no máximo 30 minutos em um laptop moderno.
  • Seu programa deve retornar a mesma solução para qualquer número inteiro sempre que for executado. Por exemplo, quando um programa recebe uma entrada 5e gera efrc, ele deve gerar essa saída toda vez que a entrada 5é fornecida.
  • Você não pode codificar soluções para nenhum número inteiro positivo.
  • Para maximizar totalmente o potencial de golfe em sua saída, seu programa deve ser capaz de lidar com números inteiros arbitrariamente grandes. Não é um requisito, apesar de boa sorte se o seu idioma não suportar isso.

Isso é , então a pontuação mais baixa vence!

clismique
fonte
2
Eu escrevi um avaliador para esse idioma no Perl 6 no TIO Nexus.
Brad Gilbert b2gills
@ BradGilbertb2gills Uau, obrigado! Vou colocar um link no desafio.
Clismique
Se a entrada for, efpor exemplo, o código pode "pular" e apenas gerar o resultado antes da efoperação?
devRicher
@devRicher Se você quer dizer que o programa "ef" é codificado anteriormente, de acordo com as regras atuais, sim, você pode fazer isso porque "ef" não está entre 10.000 e 10.100. Não tenho certeza se foi isso que você quis dizer, e posso mudar as regras porque a codificação codificada facilita muito o desafio, IMO.
Clismique
1
Eu tenho escrito um programa para esse desafio nas últimas horas. Eu acho que tenho código de trabalho, mas não posso testá-lo exatamente porque alguns dos números gerados por fatoriais são absolutamente enormes e o Python (onde eu tenho meu programa e intérprete) não pode ter sua raiz quadrada. Não tenho muita certeza do que fazer com o programa neste momento. Em uma nota lateral, originalmente eu interpretei errado e pensei que TODOS os 101 casos de teste deviam caber dentro do prazo, o que parecia quase impossível. Qualquer um parece muito mais razoável.
notjagan

Respostas:

1

Python 3.5, Pontuação de ??

No momento, não tenho a saída para todas as 101 entradas, mas depois de executar o programa para todos os casos de teste, atualizarei com minha pontuação.

from math import *

memoized = {}
same = {}

def _(mathmania, n):
    memoized[n] = mathmania
    return mathmania

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False
    for divisor in range(3, int(sqrt(n)) + 1, 2):
        if n % divisor == 0:
            return False
    return True

def pair_key(pair):
    low, high = pair
    diff = high - low
    if diff == 0:
        return 100
    low_done, high_done, diff_done = low in memoized, high in memoized, diff in memoized
    if high_done and memoized[high] == None or low_done and memoized[low] == None:
        return -1
    return (high_done + diff_done + (diff + 1 == low)) * 33 + low / high

def major_pairs(n):
    for i in range(n, int(sqrt(n)), -1):
        d = n / i
        if i - d < d - 1:
            break
        if d == int(d):
            yield (int(d), i)

def fact_key(pair):
    i, f = pair
    if i in memoized:
        if memoized[i] == None:
            return -1
        return 1
    return i / f

def near_fact(n, level):
    s = 4
    if n in same:
        s = same[n]
    for i in range(s, n ** 2 ** level):
        f = factorial(i)
        if f > (n - 1) ** 2 ** level:
            if f < (n + 1) ** 2 ** level:
                same[n] = i
                yield (i, f)
            else:
                return

def generate_mathmania(n):
    if n in memoized and memoized[n] != None:
        return memoized[n]
    memoized[n] = None
    binx = log(n, 2)
    if binx == int(binx):
        if binx == 2:
            return _("e", n)
        if binx == 1:
            return _("er", n)
        if binx == 0:
            return _("rl", n)
        return _("e(" + generate_mathmania(int(binx)) + ")", n)
    sq = sqrt(n)
    if sq == int(sq):
        return _(generate_mathmania(int(sq)) + "e", n)
    low, high = max(major_pairs(n), key=pair_key)
    if pair_key((low, high)) == -1:
        level = 1
        while True:
            try:
                i, f = max(near_fact(n, level), key=fact_key)
            except:
                level += 1
                continue
            if fact_key((i, f)) == -1:
                return _(generate_mathmania((n - 1) ** 2 + 1) + "rc", n)
            if f == n ** 2 ** level:
                return _(generate_mathmania(i) + "f" + "r" * level, n)
            if f < n ** 2 ** level:
                return _(generate_mathmania(i) + "f" + "r" * level + "c", n)
            return _(generate_mathmania(i) + "f" + "r" * level + "l", n)
    if low != 1:
        if low == high:
            return _(generate_mathmania(low) + "e", n)
        if high - low == 1:
            return _(generate_mathmania(high) + "f", n)
        return _(generate_mathmania(high) + "f(" + generate_mathmania(high - low + 1) + ")", n)
    good = None
    for i in range(n ** 2 - 1, (n - 1) ** 2, -1):
        if i in memoized:
            return _(generate_mathmania(i) + "rc", n)
        if not is_prime(i):
            good = i
    if good:
        return _(generate_mathmania(good) + "rc", n)
    for i in range((n + 1) ** 2 - 1, n ** 2, -1):
        if i in memoized:
            return _(generate_mathmania(i) + "rl", n)
        if not is_prime(i):
            good = i
    if good:
        return _(generate_mathmania(good) + "rl", n)
    return _(generate_mathmania((n - 1) ** 2 + 1), n)

Além disso, não consegui verificar as saídas de alguns dos casos de teste que experimentei devido ao grande número de números e, nesse ponto, o intérprete on-line do @ BradGilbertb2gills expira. Espero que todas as saídas funcionem.

notjagan
fonte
Eu tenho um intérprete em Python 2 (possivelmente 3) que deve ser capaz de lidar com precisão arbitrária aqui . Copie e cole-o no seu IDE para executá-lo.
clismique
Quais foram algumas das saídas para que eu pudesse otimizá-la.
precisa saber é o seguinte