Введение: комбинаторная логика
Комбинаторная логика (CL) основана на вещах, называемых комбинаторами , которые в основном являются функциями. Есть два основных «встроенных» комбинатора, Sи K, которые будут объяснены позже.
Левая ассоциативность
CL является левоассоциативным , что означает, что скобки (содержащие материал), находящиеся в крайнем левом углу от другой пары скобок, могут быть удалены с освобождением его содержимого. Например, что-то вроде этого:
((a b) c)
Может быть уменьшено до
(a b c)
Где (a b)находится в крайнем левом углу большей скобки ((a b) c), так что его можно удалить.
Гораздо больший пример левой ассоциации (квадратные скобки являются пояснениями):
((a b) c ((d e) f (((g h) i) j)))
= (a b c ((d e) f (((g h) i) j))) [((a b) c...) = (a b c...)]
= (a b c (d e f (((g h) i) j))) [((d e) f...) = (d e f...)]
= (a b c (d e f ((g h i) j))) [((g h) i) = (g h i)]
= (a b c (d e f (g h i j))) [((g h i) j) = (g h i j)]
Скобки также могут быть уменьшены, если несколько пар обернуты вокруг одного и того же объекта. Примеры:
((((a)))) -> a
a ((((b)))) -> a b
a (((b c))) -> a (b c) [(b c) is still a group, and therefore need brackets.
Note that this doesn't reduce to `a b c`, because
`(b c)` is not on the left.]
Встроенные команды
CL имеет два «встроенных» комбинатора Sи K, которые могут переключать объекты (одиночные комбинаторы или группу комбинаторов / групп, заключенных в квадратные скобки) следующим образом:
K x y = x
S x y z = x z (y z)
Где x, yи zможет быть дублеров для чего - нибудь.
Примером Sи Kявляются следующие:
(S K K) x [x is a stand-in for anything]
= S K K x [left-associativity]
= K x (K x) [S combinator]
= x [K combinator]
Другой пример:
S a b c d
= a c (b c) d [combinators only work on the n objects to the right of it,
where n is the number of "arguments" n is defined to have -
S takes 3 arguments, so it only works on 3 terms]
Выше приведены примеры обычных операторов CL, где оператор не может быть оценен дальше и достигает конечного результата за конечное время. Существуют ненормальные операторы (которые представляют собой операторы CL, которые не заканчиваются и будут оцениваться вечно), но они не входят в рамки задачи и не должны покрываться.
Если вы хотите узнать больше о CL, прочитайте эту страницу Википедии .
Задача:
Ваша задача - создать дополнительные комбинаторы, учитывая количество аргументов и то, что он оценивает как входные данные, которые даются примерно так:
{amount_of_args} = {evaluated}
Где {amount_of_args}положительное целое число, равное количеству аргументов, и {evaluated}состоит из:
- аргументы вплоть до количества аргументов,
1причем первый аргумент2является вторым, и так далее.- Вам гарантировано, что числа аргументов, превышающие количество аргументов (то есть,
4когда{amount_of_args}is только3), не появятся в{evaluated}.
- Вам гарантировано, что числа аргументов, превышающие количество аргументов (то есть,
- скобки
()
Итак, примеры входных данных:
3 = 2 3 1
4 = 1 (2 (3 4))
Первый вход запрашивает комбинатор (скажем, R) с тремя аргументами ( R 1 2 3), который затем оценивается в:
R 1 2 3 -> 2 3 1
Второй вход запрашивает это (с именем комбинатора A):
A 1 2 3 4 -> 1 (2 (3 4))
С учетом ввода в этом формате, вы должны вернуть строку S, Kи (), что при подстановке с именем комбинатора и работать с аргументами, возвращает то же оцененное заявление в качестве {evaluated}блока , когда командный блок замещено назад для этого имени комбинатора.
У оператора комбинатора вывода могут быть удалены пробельные символы и удалены внешние скобки, так что что-то подобное (S K K (S S))можно превратить в SKK(SS).
Если вы хотите , чтобы проверить выходы вашей программы, @aditsu сделал комбинаторной логики анализатор (который включает в себя S, K, Iи даже те , и другие любят Bи C) здесь .
Гол:
Поскольку это метагольф , целью этой задачи является достижение наименьшего количества байтов в выходных данных, учитывая эти 50 тестовых случаев . Пожалуйста, поместите ваши результаты для 50 тестовых случаев в ответ, или сделайте пастин (или что-то подобное) и опубликуйте ссылку на эту пастинку.
В случае ничьей выигрывает самое раннее решение.
Правила:
- Ваш ответ должен возвращать ПРАВИЛЬНЫЙ вывод - поэтому, учитывая входные данные, он должен возвращать правильный вывод в соответствии с определением в задаче.
- Ваш ответ должен выводиться в течение часа на современный ноутбук для каждого теста.
- Любое жесткое кодирование решений запрещено. Однако вам разрешено жестко кодировать до 10 комбинаторов.
- Ваша программа должна возвращать одно и то же решение каждый раз для одного и того же ввода.
- Ваша программа должна возвращать действительный результат для любого заданного ввода, а не только для тестовых случаев.
источник
1, вы можете вычесть1все, а затем обернуть решение для этого ответа вK(). Пример: Решение для2 -> 1isK, следовательно, решение для3 -> 2isKK, решение для4 -> 3isK(KK)и т. Д.Ответы:
Haskell , оценка 5017
Это объединяет самый тупой возможный алгоритм исключения абстракции ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M ) (λ x . N ) ) с оптимизатором глазка, используемым после каждого применения. Наиболее важным правилом оптимизации является S (K x ) (K y ) ↦ K ( xy ), которое останавливает алгоритм от взрыва всегда в геометрической прогрессии.
Набор правил настроен как список пар строк, поэтому с новыми правилами легко поиграться. В качестве специального бонуса повторного использования анализатора ввода для этой цели S, K и I также принимаются в комбинаторах ввода.
Правила не применяются безоговорочно; скорее, старые и новые версии сохраняются, а неоптимальные версии удаляются только тогда, когда их длина превышает длину лучшей версии более чем на некоторую константу (в настоящее время 3 байта).
Счет немного улучшается, если рассматривать I как фундаментальный комбинатор, пока выходной каскад не переписывает его в SKK. Таким образом, KI = K (SKK) может быть сокращено на 4 байта до SK при выводе, не путая остальную оптимизацию.
Попробуйте онлайн!
Выход
источник
S (K x) (K y) = K (x y))?ruleStrings. Если бы мы этого не сделали, результат был бы экспоненциально длиннее: для этого крошечного примера мы получили бы S (S (KS) (S (S (KS) (S (KK) (KS)))) (S (S (КС) (S (КК) (КК))) (S (КК) (СКК))))) (S (S (KS) (S (S (KS) (S (КК) (КС))) ( S (S (KS) (S (KK) (KK))) (SK)))) (S (KK) (SK))) вместо S (KS) K.Сумма длин решений:
12945 85085872Код на Haskell, который берет входные строки из stdin и не заботится, является ли разделитель
=или->:Он реализует улучшенную абстракцию скобок из раздела 3.2 Джона Тромпа: двоичное лямбда-исчисление и комбинаторная логика, который связан со статьей в Википедии о комбинаторной логике. Наиболее полезные особые случаи используют
Sкомбинатор только для заполнения подтермов, чтобы избежать глубокого вложения переменных. Случай, который проверяет равенство некоторых подтерминов, не нужен ни для одного из тестовых случаев. Хотя нет особого случая для обработкиWкомбинатора (см. Ответ Питера), правила работают вместе, чтобы найти более короткоеSS(SK)выражение. (Сначала я допустил ошибку, пытаясь оптимизировать внутренние вызовыabstract, но тогда такойWоптимизации не произошло, и общий результат оказался на 16 байт длиннее.)И вот результаты тестовых случаев:
источник
8486 с использованием S, K, I, W
объяснение
Стандартный алгоритм (как описано , например , в главе 18 издеваться Пересмешником ) использует четыре случая, соответствующий комбинатор
S,K,I = SKK, и простой лево-ассоциацию. Я думаю, что это то, что реализует ответ Кристиана. Этого достаточно, но не обязательно оптимально, и, поскольку нам разрешено жестко кодировать до 10 комбинаторов, остается 7 вариантов.Другие известные комбинаторные комбинаторы
которые, вместе с
K, сделать полную основу . В СК этои
SKIправила выводят те же выражения дляBиC, но дляWних выводятсяS S (K (S K K)). Поэтому я решил реализоватьWкак особый случай.Программа (CJam)
Набор онлайн-тестов
Сгенерированные выходы:
источник