Oblicz najbardziej wydajną funkcję binarną

13

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.

isaacg
źródło
Wygląda podobnie do A072766 , ale różni się od f (3, 1).
kennytm
2
To pierwsze wyzwanie od jakiegoś czasu, które zastanawia mnie nieco, aby efektywnie obliczyć. Wierzę, że coś jest możliwe z liczbami katalońskimi, ale nie mogę od razu wymyślić rozwiązania. Hmm ...
lub
2
W porządku, więc nie sądzę, że byłaby to dobra odpowiedź na golfa, ale to, co możesz zrobić, aby uczynić go dość wydajnym, to kilkakrotnie odejmować liczby katalońskie od argumentów funkcji, aż będą mniejsze niż kolejna liczba katalońska. Potem znalazłeś długość ich wyrażeń. Następnie możesz skorzystać z funkcji rankingowych / nierankingowych z tego dokumentu , z modyfikacją, aby obliczyć wynik. Być może po zrobieniu wszystkiego możliwe jest „skasowanie” fragmentów kodu w środku i znalezienie dość eleganckiego rozwiązania.
orlp
W rzeczywistości podejście z mojego poprzedniego komentarza nie działa. ((0, (0, (0, 0))), 0)jest leksykograficznie mniejszy (((0, 0), 0), (0, 0)), ale ten drugi ma mniejszą lewą stronę.
orlp

Odpowiedzi:

6

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.

halfflat
źródło
1
Niezła odpowiedź! head[...]jest [...]!!0i (p,i)<-zip(concat c)[0..]może być skrócony (i,p)<-zip[0..]$id=<<c.
Laikoni
Dzięki za ulepszenia! Zdecydowanie dodanie id=<<do repertuaru :)
halfflat
5

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.

orlp
źródło
5

Ł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.

orlp
źródło