Maths Metagolf Mania!

12

Especificaciones de Mathemania:

Cada pieza del código de Mathemania comienza con el número 2. Desde el 2, puede hacer las siguientes operaciones:

  • e: Exponenciación. El valor predeterminado de este comando es cuadrar el número.
  • f: Factorial. El valor predeterminado de este comando es usar el factorial único en el número ( using f on 2 = 2! = 2).
  • r: Raíz. El valor predeterminado de este comando es el enraizamiento cuadrado del número.
  • c: Función de techo.
  • l: Función de piso.

Para generar un número en Mathemania, debe encadenar estos comandos, que se ejecutan de izquierda a derecha en el número 2.

Ejemplos:

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

Los comandos e, fy rpueden ser alterados por comandos adicionales de Mathemania (que también comienzan con 2su número "base") para generar diferentes exponenciaciones, factoriales y raíces colocando corchetes después de la función alterada y colocando los comandos de Mathemania dentro de ella.

Por ejemplo, para poner un número al cubo en lugar de cuadrarlo, puede poner el comando para 3después de la siguiente emanera:

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

NOTA: para nuestro propósito, el comando factorial ( f) comienza 2como un factorial único. Entonces, si lo hace f(efrrc), se evaluará a un factorial doble, no a un factorial triple.

Para los nfactores (por ejemplo, factores dobles = factorial 2, factorial triple = factorial 3, etc.), el número base se multiplica por el número que es nmenor que él, y nmenor que eso, y así sucesivamente hasta que el número final no pueda ser sustraído por nsin llegar a ser 0o negativo.

Por ejemplo:

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 más información, ver aquí .

Puede insertarlo en cualquier lugar, y Mathemania lo tratará como una función única:

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

También se te permite anidar estos unos dentro de otros:

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

Para obtener un intérprete del código de Mathemania, haga clic aquí (¡salud, @ BradGilbertb2gills!)

Tarea:

Su tarea es crear un programa que, cuando se le da un entero positivo ncomo entrada, genera un programa Mathemania que cuando se ejecuta, regresa n.

Sin embargo, los programas Mathemania que se generan deben ser lo más pequeña (golfed) como sea posible, y su puntuación final se determina por la suma del número de bytes en los programas generados Mathemania de la muestra, que son los números enteros 10,000a 10,100. El puntaje más bajo gana.

Reglas y especificaciones:

  • Su programa debe generar un programa Mathemania válido para cualquier número entero positivo, pero solo se evaluarán los números entre 10,000y 10,100.
  • No está permitido generar programas de Mathemania que no den como resultado un número entero. Si lo hace, su programa queda descalificado.
  • Para los comandos e, fy r, el código de Mathemania dentro de esas funciones (por ejemplo e(efrrc), donde efrrces el código dentro de la función) debe evaluar a un entero positivo arriba 2. Si su programa no sigue esta regla, también queda descalificado.
  • Su programa debe devolver un programa Mathemania para cualquiera de los 101 enteros de prueba en un máximo de 30 minutos en una computadora portátil moderna.
  • Su programa debe devolver la misma solución para cualquier número entero cada vez que se ejecuta. Por ejemplo, cuando un programa recibe una entrada 5y se emite efrc, debe generarla cada vez que 5se da la entrada .
  • No puede codificar ninguna solución para ningún entero positivo.
  • Para maximizar al máximo el potencial de golf en su salida, su programa debería ser capaz de manejar enteros arbitrariamente grandes. No es un requisito, aunque buena suerte si su idioma no lo admite.

Esto es , ¡así que gana la puntuación más baja!

clismique
fuente
2
Escribí un evaluador para este idioma en Perl 6 en TIO Nexus.
Brad Gilbert b2gills
@ BradGilbertb2gills ¡Guau, gracias! Pondré un enlace en el desafío.
clismique
Si la entrada es, efpor ejemplo, ¿se permite que el código se "salte" y solo muestre el resultado antes de la efoperación?
devRicher
@devRicher Si quiere decir que el programa "ef" está codificado de antemano, entonces, según las reglas actuales, sí, puede hacerlo, porque "ef" no está en el rango de 10,000 a 10,100. Sin embargo, no estoy seguro de que eso sea lo que quisiste decir, y podría cambiar las reglas porque la codificación rígida hace que el desafío sea demasiado fácil, en mi opinión.
clismique
1
He estado escribiendo un programa para este desafío durante las últimas horas. Creo que tengo un código de trabajo, pero no puedo probarlo exactamente porque algunos de los números generados por los factoriales son absolutamente enormes y Python (donde tengo mi programa e intérprete) no puede tomar su raíz cuadrada. No estoy muy seguro de qué hacer con el programa en este momento. En una nota al margen, originalmente leí mal y pensé que TODOS los 101 casos de prueba tenían que ajustarse dentro del límite de tiempo, lo que parecía casi imposible. Cualquiera parece mucho más razonable.
notjagan

Respuestas:

1

Python 3.5, puntuación de ??

A partir de ahora no tengo la salida para las 101 entradas, pero una vez que ejecute el programa para todos los casos de prueba, actualizaré con mi puntaje.

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)

Además, no pude verificar los resultados de algunos de los casos de prueba que probé debido al tamaño del número, y en ese momento el intérprete en línea de @ BradGilbertb2gills agotó el tiempo de espera. Esperemos que todos los resultados funcionen.

notjagan
fuente
Tengo un intérprete en Python 2 (posiblemente 3) que debería ser capaz de manejar precisión arbitraria aquí . Cópielo y péguelo en su IDE para ejecutarlo.
clismique
¿Cuáles fueron algunos de los resultados para que posiblemente pueda optimizarlo?
Brad Gilbert b2gills