Heute werden wir die effizienteste Binärfunktion berechnen. Im Einzelnen berechnen wir die Funktion, die, wenn ein Ausdruck durch Anwenden der Funktion auf die konstante Eingabe 0 oder ihre eigene Ausgabe erstellt wird, alle positiven Ganzzahlen mit den kürzestmöglichen Ausdrücken darstellen kann, wobei den kleineren Ganzzahlen eine höhere Priorität eingeräumt wird.

Diese Funktion ist wie folgt aufgebaut:

Wählen Sie für jede Ganzzahl ab 1 den kürzesten Ausdruck, dem wir noch keine Ausgabe zugewiesen haben, und machen Sie diese Ganzzahl zur Ausgabe dieses Ausdrucks. Gleichheit in Ausdruckslänge wird durch kleineres linkes Argument und dann durch kleineres rechtes Argument getrennt. So funktioniert das:

• Zu Beginn ist 1 nicht zugewiesen. Der kürzeste nicht zugewiesene Ausdruck ist f(0, 0), also setzen wir ihn auf 1.

• Jetzt ist 2 nicht zugewiesen. Die kürzesten nicht zugewiesenen Ausdrücke sind f(f(0, 0), 0)= f(1, 0)und f(0, f(0, 0))= f(0, 1). Die Krawatten werden also in Richtung kleinerer linker Argumente gebrochen f(0, 1) = 2.

• Der kürzeste nicht zugewiesene verbleibende Ausdruck ist f(f(0, 0), 0)= f(1, 0), also f(1, 0) = 3.

• Jetzt haben wir keine Ausdrücke mehr mit nur 2 fs und 3 0s, also müssen wir von jedem einen weiteren hinzufügen. Das Brechen von Bindungen durch linkes Argument, dann rechtes Argument, bekommen wir f(0, 2) = 4da f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

• Weiter, haben wir f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Hier ist eine Tabelle, die ich für die ersten Werte ausgefüllt habe:

    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

Eine andere Sichtweise ist, dass jeder Ausgang eine Größe hat, die der Summe der Größen seiner Eingänge plus eins entspricht. Die Tabelle wird in der Reihenfolge der Vergrößerung der Ausgabe ausgefüllt, wobei die Bindungen durch Minimierung der linken Eingabe und der rechten Eingabe aufgehoben werden.

Ihre Herausforderung besteht darin, bei zwei nicht negativen Ganzzahlen als Eingabe den Wert dieser Funktion zu berechnen und auszugeben. Das ist Code Golf. Die kürzeste Lösung in Bytes gewinnt. Standardlücken sind verboten.

Haskell, 110 Bytes

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]

Das Argument hier ist das Tupel (x,y). Ähnlich wie die Antwort oben, aber die Nachschlageliste enthält nur die linken und rechten Indexpaare anstelle der Bäume.

Python 3, 154 Bytes

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]))

Es ist weder sehr schnell noch sehr golfen, aber es ist ein Anfang.

Beeindruckend! Ich habe es tatsächlich geschafft, einen effizienten Berechnungsalgorithmus zu erstellen. Das habe ich zunächst nicht erwartet. Die Lösung ist ziemlich elegant. Es leitet immer wieder mehr ab und kehrt dann bis zum Grundfall 0 zurück. In dieser Antwort bezeichnet die C (n) -Funktion die katalanischen Zahlen .

Der entscheidende erste Schritt ist das Bestätigen, dass es C (0) = 1 Werte der Länge Null gibt (nämlich 0 selbst), C (1) = 1 Werte der Länge Eins (nämlich f (0, 0)), C (2) = 2 Werte der Länge zwei (f (0, f (0, 0)) und f (f (0, 0), 0)).

Das heißt, wenn wir nach dem n-ten Ausdruck suchen und das größte k so finden, dass C (0) + C (1) + ... + C (k) <= n, dann wissen wir, dass n die Länge k hat .

Aber jetzt können wir weitermachen! Weil der gesuchte Ausdruck der n-C (0) -C (1) -C (k) -te Ausdruck in seiner Längenklasse ist.

Jetzt können wir einen ähnlichen Trick anwenden, um die Länge des linken Segments und dann den Rang innerhalb dieses Unterabschnitts zu ermitteln. Und dann greifen Sie auf die Reihen zurück, die wir gefunden haben!

Es wurde festgestellt, dass f (5030, 3749) = 1542317211 im Handumdrehen.

Python, nicht konkurrierend

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)))

Ich bin mir ziemlich sicher, dass ich eine Menge unnötiger Berechnungen vornehme und viele Zwischenschritte entfernt werden könnten.