Вычислить наиболее эффективную двоичную функцию

13

Сегодня мы будем вычислять наиболее эффективную двоичную функцию. Более конкретно, мы будем вычислять функцию, которая при создании выражения на основе применения функции к постоянному входу 0 или ее собственному выходу может представлять все положительные целые числа с кратчайшими возможными выражениями, уделяя большее внимание меньшим целым числам.

Эта функция построена следующим образом:

Для каждого целого числа, начиная с 1 и восходящего, выберите самое короткое выражение, которому мы еще не присвоили вывод, и сделайте это целое число выводом этого выражения. Связи в длине выражения будут нарушены меньшим левым аргументом, а затем меньшим правым аргументом. Вот как это работает:

  • Первоначально 1 не назначен. Самое короткое неназначенное выражение есть f(0, 0), поэтому мы установим его на 1.

  • Теперь 2 не назначено. Самые короткие неназначенные выражения: f(f(0, 0), 0)= f(1, 0)и f(0, f(0, 0))= f(0, 1). Связи разрываются в сторону меньшего левого аргумента, так что f(0, 1) = 2.

  • Самое короткое неназначенное оставшееся выражение - f(f(0, 0), 0)= f(1, 0), поэтому f(1, 0) = 3.

  • Теперь у нас нет выражений, у которых всего 2 fс и 3 0с, поэтому нам нужно добавить еще по одному для каждого. Разрывая связи левым аргументом, затем правый аргумент, мы получаем f(0, 2) = 4, так как f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

  • Продолжая, у нас есть f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Вот таблица, которую я заполнил для первых нескольких значений:

    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

Другой способ взглянуть на это состоит в том, что каждый выход имеет размер, равный сумме размеров его входов плюс один. Таблица заполняется в порядке увеличения размера выходных данных, связи прерываются при минимизации левого и правого входов.

Ваша задача состоит в том, чтобы при вводе двух неотрицательных целых чисел вычислить и вывести значение этой функции. Это код гольф. Самое короткое решение, в байтах, выигрывает. Стандартные лазейки запрещены.

isaacg
источник
Похож на A072766 , но отличается, начиная с f (3, 1).
Kennytm
2
Это первая задача за некоторое время, которая несколько озадачивает меня, чтобы эффективно рассчитать. Я верю, что что-то возможно с каталонскими числами, но не могу сразу придумать решение. Хм ...
orlp
2
Хорошо, я не думаю, что это даст хороший гольф-ответ, но то, что вы можете сделать, чтобы сделать его достаточно эффективным, - это многократно вычитать каталонские числа из аргументов функции, пока они не станут меньше, чем следующий каталонский номер. Тогда вы нашли длину их выражений. Затем вы можете использовать функции ранжирования / отстранения от этой статьи , с модификацией, чтобы вычислить результат. Возможно, выполнив все это, можно «отменить» фрагменты кода в середине и найти достаточно элегантное решение.
orlp
На самом деле, подход из моего предыдущего комментария не работает. ((0, (0, (0, 0))), 0)лексикографически меньше, чем (((0, 0), 0), (0, 0)), однако последний имеет меньшую левую сторону.
orlp

Ответы:

6

Haskell, 110 байт

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]

Аргумент здесь принимается за кортеж (x,y). Очень похоже на ответ выше, но список поиска содержит только пары левого и правого индексов вместо деревьев.

halfflat
источник
1
Хороший ответ! head[...]есть [...]!!0и (p,i)<-zip(concat c)[0..]может быть сокращено до (i,p)<-zip[0..]$id=<<c.
Лайкони
Спасибо за улучшения! Определенно добавляя id=<<в репертуар :)
halfflat
5

Python 3, 154 байта

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

Это не очень быстро и не очень гольф, но это начало.

orlp
источник
5

Вот это да! Мне действительно удалось сделать эффективный алгоритм вычислений. Сначала я этого не ожидал. Решение довольно элегантное. Он многократно выводит все больше и больше, затем повторяется вплоть до базового случая 0. В этом ответе функция C (n) обозначает каталонские числа .

Важным первым шагом является признание того, что существует C (0) = 1 значение нулевой длины (а именно 0), C (1) = 1 значение длины 1 (а именно f (0, 0)), C (2) = 2 значения длины два (f (0, f (0, 0)) и f (f (0, 0), 0)).

Это означает, что если мы ищем n-е выражение и находим наибольшее k, такое что C (0) + C (1) + ... + C (k) <= n, то мы знаем, что n имеет длину k ,

Но теперь мы можем продолжить! Поскольку выражение, которое мы ищем, является выражением n - C (0) - C (1) - ... - C (k) в его классе длины.

Теперь мы можем использовать аналогичный прием, чтобы найти длину левого сегмента, а затем ранг в этом подразделе. А потом вербуйся по тем разрядам, которые мы нашли!

Было обнаружено, что f (5030, 3749) = 1542317211 в мгновение ока.

Python, неконкурентоспособный

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

Я вполне уверен, что я делаю кучу ненужных вычислений, и многие средние шаги могут быть удалены.

orlp
источник