Математика Метагольф Мания!

12

Mathemania Specs:

Каждый фрагмент кода Mathemania начинается с цифры 2. Из 2, вы можете сделать следующие операции:

  • e: Экспонирование. По умолчанию этой команды возводится в квадрат числа.
  • fФакториал. По умолчанию эта команда использует один факториал для числа ( using f on 2 = 2! = 2).
  • r: Root. По умолчанию этой команды вводится квадратный корень из числа.
  • cФункция потолка.
  • lФункция пола.

Чтобы сгенерировать число в Mathemania, вы должны связать воедино эти команды, которые выполняются слева направо над номером 2.

Примеры:

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

В e, fи rкоманды могут быть изменены с помощью дополнительных команд Mathemania (которые также начинают с в 2качестве «базового» номера) для создания различного возведения в степени, факториалов и корней, помещая скобки после измененной функции и размещения команд Mathemania внутри него.

Например, чтобы кубизировать число, а не возводить его в квадрат, вы можете поместить команду для 3after eследующим образом:

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

ПРИМЕЧАНИЕ: для нашей цели команда factorial ( f) начинается с 2одного факториала. Так что если вы это сделаете f(efrrc), это будет оцениваться с двойным факториалом, а не с тройным факториалом.

Для n-факториалов (например, двойные факториалы = 2-факториал, тройной факториал = 3-факториал и т. Д.) Базовое число умножается на число, которое nменьше его и nменьше этого, и так далее, пока окончательное число не может быть вычитается, nне становясь 0или отрицательным.

Например:

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)

Для получения дополнительной информации см. Здесь .

Вы можете вставить его куда угодно, и Mathemania будет рассматривать его как одну функцию:

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

Вам также разрешено вкладывать их друг в друга:

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

Чтобы получить интерпретатор кода Mathemania, нажмите здесь (ура, @ BradGilbertb2gills!)

Задача:

Ваша задача - создать программу, которая при получении положительного целого числа в nкачестве входных данных генерирует программу Mathemania, которая при выполнении возвращает n.

Тем не менее, программа Mathemania что вы порождающая должна быть как малые (golfed) , насколько это возможно, и ваш итоговый результат определяется суммой числа байт в сгенерированных программах Mathemania образца, которые являются целыми числами 10,000в 10,100. Самый низкий балл побеждает.

Правила и характеристики:

  • Ваша программа должна вывести действительную программу Mathemania для любого положительного целого числа, но только числа между 10,000и 10,100будут проверены.
  • Вам не разрешено выводить программы Mathemania, которые не приводят к целому числу. Если вы это сделаете, ваша программа будет дисквалифицирована.
  • Для команд e, fи r, код Mathemania внутри этих функций (например e(efrrc), когда efrrcэто код внутри функции) должен оценивать с положительным целым числом выше 2. Если ваша программа не следует этому правилу, она также будет дисквалифицирована.
  • Ваша программа должна вернуть программу Mathemania для любого из 101 целого числа тестов в течение не более 30 минут на современном ноутбуке.
  • Ваша программа должна возвращать одно и то же решение для любого целого числа при каждом запуске. Например, когда программе дают вход, 5и она выводит efrc, она должна выводить это каждый раз , когда вводится 5.
  • Вы не можете жестко кодировать любые решения для любого положительного целого числа.
  • Чтобы максимально увеличить потенциал игры в гольф, ваша программа должна иметь возможность обрабатывать произвольно большие целые числа. Это не требование, хотя удачи, если ваш язык не поддерживает это.

Это , поэтому выигрывает самая низкая оценка!

clismique
источник
2
Я написал оценщик для этого языка в Perl 6 на TIO Nexus.
Брэд Гилберт b2gills
@ BradGilbertb2gills Ого, спасибо! Я поставлю ссылку в вызове.
clismique
Если ввод, efнапример, разрешен ли коду «пропустить» и просто вывести результат перед efоперацией?
devRicher
@devRicher Если вы имеете в виду, что программа «ef» заранее жестко запрограммирована, то по текущим правилам, да, вам разрешено это делать, потому что «ef» не находится в диапазоне от 10 000 до 10 100. Я не уверен, что вы это имели в виду, и я мог бы изменить правила, потому что жесткое кодирование делает задачу слишком простой, IMO.
clismique
1
Я писал программу для этого испытания в течение последних нескольких часов. Я думаю, что у меня есть рабочий код, но я не могу его точно протестировать, потому что некоторые числа, сгенерированные факториалами, абсолютно огромны, и Python (где у меня есть моя программа и интерпретатор) не может получить их квадратный корень. Я не совсем уверен, что делать с программой на данный момент. Кстати, я изначально неправильно прочитал и подумал, что ВСЕ 101 тестовые наборы должны были уложиться в сроки, которые казались почти невозможными. Любой кажется более разумным.
notjagan

Ответы:

1

Python 3.5, Оценка ??

На данный момент у меня нет выходных данных для всех 101 входных данных, но как только я запустите программу для всех тестовых случаев, я обновлю свои результаты.

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)

Кроме того, мне не удалось проверить результаты некоторых тестовых случаев, которые я пробовал, из-за огромного размера номера, и в этот момент тайм-аут @ BradGilbertb2gills истек. Надеюсь, все выходы работают.

notjagan
источник
У меня есть интерпретатор в Python 2 (возможно, 3), который должен быть в состоянии обрабатывать произвольную точность здесь . Скопируйте и вставьте его в IDE для запуска.
clismique
Каковы были некоторые результаты, чтобы я мог оптимизировать это.
Брэд Гилберт b2gills