Сегодня мы будем вычислять наиболее эффективную двоичную функцию. Более конкретно, мы будем вычислять функцию, которая при создании выражения на основе применения функции к постоянному входу 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
с и 30
с, поэтому нам нужно добавить еще по одному для каждого. Разрывая связи левым аргументом, затем правый аргумент, мы получаем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
Другой способ взглянуть на это состоит в том, что каждый выход имеет размер, равный сумме размеров его входов плюс один. Таблица заполняется в порядке увеличения размера выходных данных, связи прерываются при минимизации левого и правого входов.
Ваша задача состоит в том, чтобы при вводе двух неотрицательных целых чисел вычислить и вывести значение этой функции. Это код гольф. Самое короткое решение, в байтах, выигрывает. Стандартные лазейки запрещены.
((0, (0, (0, 0))), 0)
лексикографически меньше, чем(((0, 0), 0), (0, 0))
, однако последний имеет меньшую левую сторону.Ответы:
Haskell, 110 байт
Аргумент здесь принимается за кортеж
(x,y)
. Очень похоже на ответ выше, но список поиска содержит только пары левого и правого индексов вместо деревьев.источник
head[...]
есть[...]!!0
и(p,i)<-zip(concat c)[0..]
может быть сокращено до(i,p)<-zip[0..]$id=<<c
.id=<<
в репертуар :)Python 3, 154 байта
Это не очень быстро и не очень гольф, но это начало.
источник
Вот это да! Мне действительно удалось сделать эффективный алгоритм вычислений. Сначала я этого не ожидал. Решение довольно элегантное. Он многократно выводит все больше и больше, затем повторяется вплоть до базового случая 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, неконкурентоспособный
Я вполне уверен, что я делаю кучу ненужных вычислений, и многие средние шаги могут быть удалены.
источник