Aujourd'hui, nous allons calculer la fonction binaire la plus efficace. Plus précisément, nous calculerons la fonction qui, lorsqu'une expression est créée en appliquant la fonction à l'entrée constante 0 ou à sa propre sortie, peut représenter tous les entiers positifs avec les expressions les plus courtes possibles, en accordant une priorité plus élevée aux plus petits entiers.

Cette fonction est construite comme suit:

Pour chaque entier, en commençant à 1 et en remontant, choisissez l'expression la plus courte à laquelle nous n'avons pas encore attribué de sortie, et faites de cet entier la sortie de cette expression. Les liens de longueur d'expression seront rompus par un argument de gauche plus petit, puis par un argument de droite plus petit. Voici comment ça fonctionne:

• Initialement, 1 n'est pas affecté. L'expression non affectée la plus courte est f(0, 0), nous allons donc la mettre à 1.

• Maintenant, 2 n'est pas affecté. Les expressions non affectées les plus courtes sont f(f(0, 0), 0)= f(1, 0)et f(0, f(0, 0))= f(0, 1). Les liens sont rompus vers un argument de gauche plus petit, donc f(0, 1) = 2.

• L'expression non affectée la plus courte restante est f(f(0, 0), 0)= f(1, 0), donc f(1, 0) = 3.

• Maintenant, nous n'avons plus d'expressions avec seulement 2 fs et 3 0s, nous devons donc en ajouter un de plus. Briser les liens par l'argument de gauche, puis l'argument de droite, nous obtenons f(0, 2) = 4, depuis f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

• En continuant, nous avons f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Voici un tableau que j'ai rempli pour les premières valeurs:

    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

Une autre façon de voir les choses est que chaque sortie a une taille, égale à la somme des tailles de ses entrées plus une. Le tableau est rempli par ordre croissant de taille de sortie, liens rompus en minimisant l'entrée gauche puis l'entrée droite.

Votre défi est, étant donné deux entiers non négatifs en entrée, calculer et sortir la valeur de cette fonction. C'est le golf de code. La solution la plus courte, en octets, gagne. Les failles standard sont interdites.

Haskell, 110 octets

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]

L'argument ici est considéré comme le tuple (x,y). Assez similaire à la réponse ci-dessus, mais la liste de recherche contient uniquement les paires d'indices gauche et droit au lieu des arbres.

Python 3, 154 octets

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

Ce n'est pas très rapide ni très golfique, mais c'est un début.

Hou la la! J'ai réussi à créer un algorithme de calcul efficace. Je ne m'attendais pas à cela au début. La solution est assez élégante. Il en déduit de plus en plus, puis revient jusqu'au cas de base de 0. Dans cette réponse, la fonction C (n) désigne les nombres catalans .

La première étape cruciale consiste à reconnaître qu'il existe C (0) = 1 valeurs de longueur zéro (à savoir 0 lui-même), C (1) = 1 valeurs de longueur un (à savoir f (0, 0)), C (2) = 2 valeurs de longueur deux (f (0, f (0, 0)) et f (f (0, 0), 0)).

Cela signifie que si nous recherchons la nième expression, et que nous trouvons le plus grand k tel que C (0) + C (1) + ... + C (k) <= n alors nous savons que n a la longueur k .

Mais maintenant, nous pouvons continuer! Parce que l'expression que nous recherchons est la n - C (0) - C (1) - ... - C (k) ème expression dans sa classe de longueur.

Maintenant, nous pouvons utiliser une astuce similaire pour trouver la longueur du segment gauche, puis le rang dans cette sous-section. Et puis recurse sur ces rangs que nous avons trouvés!

Il a constaté que f (5030, 3749) = 1542317211 en un clin d'œil.

Python, non compétitif

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

Je suis assez certain de faire un tas de calculs inutiles et de nombreuses étapes intermédiaires pourraient être supprimées.