Maths Metagolf Mania!

12

Specyfikacja Mathemania:

Każdy fragment kodu Mathemania zaczyna się od cyfry 2. Z poziomu 2możesz wykonać następujące operacje:

  • e: Potęgowanie. Domyślnym poleceniem jest podniesienie liczby do kwadratu.
  • f: Factorial. Domyślnie to polecenie używa pojedynczego silnia na liczbie ( using f on 2 = 2! = 2).
  • r: Root. Domyślnym poleceniem jest zrootowanie liczby na kwadrat.
  • c: Funkcja sufitowa.
  • l: Funkcja podłogi.

Aby wygenerować liczbę w Mathemanii, musisz połączyć te polecenia, które są wykonywane od lewej do prawej na numerze 2.

Przykłady:

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

Te e, foraz rpolecenia mogą być zmieniane przez dodatkowych poleceń Mathemania (które również rozpocząć się 2jako „bazy” liczba) w celu wytworzenia różnych exponentiations, silnię i korzeni poprzez umieszczenie wsporników po funkcji zmienionego i wprowadzania poleceń Mathemania środku.

Na przykład, aby utworzyć sześcian zamiast kwadratu, możesz wstawić polecenie 3po e:

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

UWAGA: w naszym celu polecenie silnia ( f) zaczyna się 2od pojedynczego silnia. Więc jeśli to zrobisz f(efrrc), zostanie to ocenione do podwójnego silnia, a nie potrójnego silnia.

W przypadku nwspółczynników (np. Podwójnych silni = 2-silniak, potrójnego silni = 3-silniak itp.) Liczbę podstawową mnoży się przez liczbę, która jest nmniejsza od niego, i nmniejsza, i tak dalej, aż do ostatecznej liczby nie będzie odejmowane przez nbez stawania się 0lub ujemne.

Na przykład:

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)

Aby uzyskać więcej informacji, zobacz tutaj .

Możesz wstawić go w dowolnym miejscu, a Mathemania potraktuje go jako jedną funkcję:

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

Możesz także zagnieżdżać je w sobie:

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

Aby znaleźć tłumacza kodu Mathemania, kliknij tutaj (na zdrowie, @ BradGilbertb2gills!)

Zadanie:

Twoim zadaniem jest stworzenie programu, który po podaniu dodatniej liczby całkowitej njako sygnału wejściowego generuje program Mathemania, który po uruchomieniu zwraca n.

Jednak programy Mathemania które generują musi być tak małe (grałem), jak to możliwe, a końcowy wynik jest określony przez sumę liczby bajtów w wygenerowanym programów Mathemania próbki, które są liczbami całkowitymi 10,000do 10,100. Najniższy wynik wygrywa.

Zasady i specyfikacje:

  • Twój program musi wypisać prawidłowy program Mathemania dla dowolnej dodatniej liczby całkowitej, ale tylko liczby między 10,000i 10,100zostaną przetestowane.
  • Nie wolno wyprowadzać programów Mathemania, które nie dają liczb całkowitych. Jeśli to zrobisz, Twój program zostanie zdyskwalifikowany.
  • Dla poleceń e, fi rkod Mathemania wewnątrz tych funkcji (na przykład e(efrrc), w przypadku gdy efrrcjest to kod wewnątrz funkcji) musi dawać w wyniku dodatnia powyżej 2. Jeśli twój program nie przestrzega tej zasady, również jest zdyskwalifikowany.
  • Twój program musi zwrócić program Mathemania dla jednej ze 101 liczb całkowitych testowych w najwyżej 30 minut na nowoczesnym laptopie.
  • Twój program musi zwracać to samo rozwiązanie dla dowolnej liczby całkowitej przy każdym uruchomieniu. Na przykład, gdy program otrzymuje dane wejściowe 5i wyświetla dane wyjściowe efrc, musi je wyprowadzać za każdym razem, gdy dane wejściowe 5są podawane.
  • Nie możesz na stałe kodować żadnych rozwiązań dla dodatniej liczby całkowitej.
  • Aby w pełni zmaksymalizować potencjał gry w golfa, twój program powinien być w stanie obsłużyć dowolnie duże liczby całkowite. Nie jest to wymagane, ale powodzenia, jeśli Twój język tego nie obsługuje.

To jest , więc wygrywa najniższy wynik!

clismique
źródło
2
Napisałem ewaluatora dla tego języka w Perlu 6 na TIO Nexus.
Brad Gilbert b2gills
@ BradGilbertb2gills Wow, dzięki! Umieszczę link w wyzwaniu.
clismique
Jeśli dane wejściowe są efna przykład, czy kod może „pomijać” i wyświetlać wynik przed efoperacją?
devRicher,
@devRicher Jeśli masz na myśli, że program „ef” jest wcześniej zakodowany na stałe, to zgodnie z obecnymi zasadami, tak, możesz to zrobić, ponieważ „ef” nie mieści się w zakresie od 10 000 do 10 100. Nie jestem jednak pewien, o co ci chodziło, i mogę zmienić reguły, ponieważ kodowanie sprawia, że ​​wyzwanie jest zbyt łatwe, IMO.
clismique
1
Od kilku godzin piszę program tego wyzwania. Wydaje mi się, że mam działający kod, ale nie mogę go dokładnie przetestować, ponieważ niektóre liczby generowane przez silnie są absolutnie ogromne, a Python (gdzie mam mój program i interpreter) nie może wyliczyć pierwiastka kwadratowego. W tej chwili nie jestem całkiem pewien, co zrobić z programem. Na marginesie, początkowo źle odczytałem i pomyślałem, że WSZYSTKIE przypadki testowe 101 muszą się zmieścić w terminie, co wydawało się prawie niemożliwe. Każdy wydaje się o wiele bardziej rozsądny.
notjagan

Odpowiedzi:

1

Python 3.5, wynik ??

Na razie nie mam danych wyjściowych dla wszystkich 101 danych wejściowych, ale po uruchomieniu programu dla wszystkich przypadków testowych zaktualizuję swój wynik.

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)

Ponadto nie byłem w stanie zweryfikować wyników niektórych przypadków testowych, które wypróbowałem ze względu na samą liczbę liczb, i w tym momencie upłynął limit czasu tłumacza online @ BradGilbertb2gills. Mam nadzieję, że wszystkie wyjścia działają.

notjagan
źródło
Mam interpretera w Pythonie 2 (prawdopodobnie 3), który powinien być w stanie obsłużyć dowolną precyzję tutaj . Skopiuj i wklej go do swojego IDE, aby go uruchomić.
clismique
Jakie były niektóre wyniki, abym mógł to zoptymalizować.
Brad Gilbert b2gills,