Dzisiaj będziemy obliczać najbardziej wydajną funkcję binarną. Mówiąc dokładniej, obliczymy funkcję, która po utworzeniu wyrażenia z zastosowania funkcji do stałego wejścia 0 lub własnego wyjścia może reprezentować wszystkie dodatnie liczby całkowite z możliwie najkrótszymi wyrażeniami, nadając wyższy priorytet mniejszym liczbom całkowitym.

Ta funkcja jest zbudowana w następujący sposób:

Dla każdej liczby całkowitej, zaczynając od 1 i idąc w górę, wybierz najkrótsze wyrażenie, któremu jeszcze nie przypisaliśmy wyjścia, i ustaw tę liczbę całkowitą na wyjście tego wyrażenia. Więzi długości wyrażenia zostaną zerwane przez mniejszy lewy argument, a następnie przez mniejszy prawy argument. Oto jak to działa:

• Początkowo 1 jest nieprzypisany. Najkrótsze nieprzypisane wyrażenie to f(0, 0), więc ustawimy to na 1.

• Teraz 2 jest nieprzypisane. Najkrótsze nieprzypisane wyrażenia to f(f(0, 0), 0)= f(1, 0)i f(0, f(0, 0))= f(0, 1). Krawaty są podzielone na mniejsze lewego argumentu, tak f(0, 1) = 2.

• Najkrótszym pozostałym nieprzypisanym wyrażeniem jest f(f(0, 0), 0)= f(1, 0), więc f(1, 0) = 3.

• Teraz brakuje nam wyrażeń z tylko 2 fsi 3 0s, więc będziemy musieli dodać jeszcze jedno z nich. Zerwanie więzi przez lewy argument, a następnie prawy argument, otrzymujemy f(0, 2) = 4, ponieważ f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

• Kontynuując, mamy f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Oto tabela, którą wypełniłem dla pierwszych kilku wartości:

    0  1  2  3  4  5  6  7  8
 /---------------------------
0|  1  2  4  5  9 10 11 12 13
1|  3  6 14 15 37 38 39 40 41
2|  7 16 42 43
3|  8 17 44 45
4| 18 46
5| 19 47
6| 20 48
7| 21 49
8| 22 50

Innym sposobem spojrzenia na to jest to, że każde wyjście ma rozmiar równy sumie wielkości jego danych wejściowych plus jeden. Tabela jest wypełniana w kolejności rosnącej wielkości produkcji, zerwane więzi poprzez zminimalizowanie wejścia lewego i prawego.

Twoim wyzwaniem jest, biorąc pod uwagę dwie nieujemne liczby całkowite jako dane wejściowe, oblicz i wyślij wartość tej funkcji. To jest kod golfowy. Najkrótsze rozwiązanie w bajtach wygrywa. Standardowe luki są zabronione.

Haskell, 110 bajtów

f q=head[i|let c=[(-1,0)]:[[(f a,f b)|n<-[0..k],a<-c!!n,b<-c!!(k-n)]|k<-[0..]],(p,i)<-zip(concat c)[0..],p==q]

Argumentem tutaj jest krotka (x,y). Całkiem podobna do powyższej odpowiedzi, ale lista przeglądowa zawiera tylko pary lewego i prawego wskaźnika zamiast drzew.

Python 3, 154 bajtów

b=lambda n:[(l,r)for k in range(1,n)for l in b(k)for r in b(n-k)]+[0]*(n<2)
def f(x,y):r=sum((b(n)for n in range(1,x+y+3)),[]);return r.index((r[x],r[y]))

Nie jest bardzo szybki ani bardzo golfowy, ale to początek.

Łał! Udało mi się stworzyć wydajny algorytm obliczeniowy. Na początku nie spodziewałem się tego. Rozwiązanie jest dość eleganckie. Wielokrotnie dedukuje coraz więcej, a następnie powtarza się aż do podstawowego przypadku 0. W tej odpowiedzi funkcja C (n) oznacza liczby katalońskie .

Najważniejszym pierwszym krokiem jest potwierdzenie, że istnieją C (0) = 1 wartości długości zero (mianowicie 0), C (1) = 1 wartości długości jeden (mianowicie f (0, 0)), C (2) = 2 wartości długości dwa (f (0, f (0, 0)) if (f (0, 0), 0)).

Oznacza to, że jeśli szukamy n-tego wyrażenia i znajdujemy największe k takie, że C (0) + C (1) + ... + C (k) <= n to wiemy, że n ma długość k .

Ale teraz możemy kontynuować! Ponieważ szukane wyrażenie jest n - C (0) - C (1) - ... - C (k) th w swojej klasie długości.

Teraz możemy użyć podobnej sztuczki, aby znaleźć długość lewego segmentu, a następnie pozycję w podsekcji. A potem wróć na te znalezione przez nas szeregi!

Stwierdzono, że f (5030, 3749) = 1542317211 w mgnieniu oka.

Python, niekonkurujący

def C(n):
    r = 1
    for i in range(n):
        r *= 2*n - i
        r //= i + 1
    return r//(n+1)

def unrank(n):
    if n == 0: return 0

    l = 0
    while C(l) <= n:
        n -= C(l)
        l += 1

    right_l = l - 1
    while right_l and n >= C(l - 1 - right_l) * C(right_l):
        n -= C(l - 1 - right_l) * C(right_l)
        right_l -= 1

    right_num = C(right_l)

    r_rank = n % right_num
    l_rank = n // right_num

    for sz in range(l - 1 - right_l): l_rank += C(sz)
    for sz in range(right_l): r_rank += C(sz)

    return (unrank(l_rank), unrank(r_rank))

def rank(e):
    if e == 0: return 0
    left, right = e

    l = str(e).count("(")
    left_l = str(left).count("(")
    right_l = str(right).count("(")
    right_num = C(right_l)

    n = sum(C(sz) for sz in range(l))
    n += sum(C(sz)*C(l - 1 - sz) for sz in range(left_l))

    n += (rank(left) - sum(C(sz) for sz in range(left_l))) * C(right_l)
    n += rank(right) - sum(C(sz) for sz in range(right_l))

    return n

def f(x, y):
    return rank((unrank(x), unrank(y)))

Jestem całkiem pewien, że robię mnóstwo niepotrzebnych obliczeń i można było usunąć wiele środkowych kroków.