Комбинаторная загадка!

12

Введение: комбинаторная логика

Комбинаторная логика (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 комбинаторов.
  • Ваша программа должна возвращать одно и то же решение каждый раз для одного и того же ввода.
  • Ваша программа должна возвращать действительный результат для любого заданного ввода, а не только для тестовых случаев.
clismique
источник
Как вы можете быть уверены, что люди не украдут комбинаторы, найденные в других ответах?
фатализировать
@Fatalize Это не должно иметь большого значения, так как люди могут черпать вдохновение из ответов других людей и опираться на них, чтобы создавать лучшие ответы.
clismique
Говоря о вдохновении, я заметил, что когда желаемый результат не содержит 1, вы можете вычесть 1все, а затем обернуть решение для этого ответа в K(). Пример: Решение для 2 -> 1is K, следовательно, решение для 3 -> 2is KK, решение для 4 -> 3is K(KK)и т. Д.
Neil

Ответы:

8

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 при выводе, не путая остальную оптимизацию.

{-# LANGUAGE ViewPatterns #-}

import qualified Data.IntMap as I
import qualified Data.List.NonEmpty as N
import System.IO

data Term
  = V Int
  | S
  | K
  | I
  | A (N.NonEmpty (Int, Term, Term))
  deriving (Show, Eq, Ord)

parse :: String -> (Term, String)
parse = parseApp . parse1

parseApp :: (Term, String) -> (Term, String)
parseApp (t, ' ':s) = parseApp (t, s)
parseApp (t, "") = (t, "")
parseApp (t, ')':s) = (t, ')' : s)
parseApp (t1, parse1 -> (t2, s)) =
  parseApp (A (pure (appLen (t1, t2), t1, t2)), s)

parse1 :: String -> (Term, String)
parse1 (' ':s) = parse1 s
parse1 ('(':(parse -> (t, ')':s))) = (t, s)
parse1 ('S':s) = (S, s)
parse1 ('K':s) = (K, s)
parse1 ('I':s) = (I, s)
parse1 (lex -> [(i, s)]) = (V (read i), s)

ruleStrings :: [(String, String)]
ruleStrings =
  [ ("1 3(2 3)", "S1 2 3")
  , ("S(K(S(K1)))(S(K(S(K2)))3)", "S(K(S(K(S(K1)2))))3")
  , ("S(K(S(K1)))(S(K2))", "S(K(S(K1)2))")
  , ("S(K1)(K2)", "K(1 2)")
  , ("S(K1)I", "1")
  , ("S(S(K1)2)(K3)", "S(K(S1(K3)))2")
  , ("S(SI1)I", "S(SSK)1")
  ]

rules :: [(Term, Term)]
rules = [(a, b) | (parse -> (a, ""), parse -> (b, "")) <- ruleStrings]

len :: Term -> Int
len (V _) = 1
len S = 1
len K = 1
len I = 3
len (A ((l, _, _) N.:| _)) = l

appLen :: (Term, Term) -> Int
appLen (t1, S) = len t1 + 1
appLen (t1, K) = len t1 + 1
appLen (K, I) = 2
appLen (t1, t2) = len t1 + len t2 + 2

notA :: Term -> Bool
notA (A _) = False
notA _ = True

alt :: N.NonEmpty Term -> Term
alt ts =
  head $
  N.filter notA ts ++
  [A (N.nub (a N.:| filter (\(l, _, _) -> l <= minLen + 3) aa))]
  where
    a@(minLen, _, _) N.:| aa =
      N.sort $ do
        A b <- ts
        b

match :: Term -> Term -> I.IntMap Term -> [I.IntMap Term]
match (V i) t m =
  case I.lookup i m of
    Just ((/= t) -> True) -> []
    _ -> [I.insert i t m]
match S S m = [m]
match K K m = [m]
match I I m = [m]
match (A a) (A a') m = do
  (_, t1, t2) <- N.toList a
  (_, t1', t2') <- N.toList a'
  m1 <- match t1 t1' m
  match t2 t2' m1
match _ _ _ = []

sub :: I.IntMap Term -> Term -> Term
sub _ S = S
sub _ K = K
sub _ I = I
sub m (V i) = m I.! i
sub m (A a) =
  alt $ do
    (_, t1, t2) <- a
    pure (sub m t1 & sub m t2)

optimize :: Term -> Term
optimize t = alt $ t N.:| [sub m b | (a, b) <- rules, m <- match a t I.empty]

infixl 5 &

(&) :: Term -> Term -> Term
t1 & t2 = optimize (A (pure (appLen (t1, t2), t1, t2)))

elim :: Int -> Term -> Term
elim n (V ((== n) -> True)) = I
elim n (A a) =
  alt $ do
    (_, t1, t2) <- a
    pure (S & elim n t1 & elim n t2)
elim _ t = K & t

paren :: String -> Bool -> String
paren s True = "(" ++ s ++ ")"
paren s False = s

output :: Term -> Bool -> String
output S = const "S"
output K = const "K"
output I = paren "SKK"
output (V i) = \_ -> show i ++ " "
output (A ((_, K, I) N.:| _)) = paren "SK"
output (A ((_, t1, t2) N.:| _)) = paren (output t1 False ++ output t2 True)

convert :: Int -> Term -> Term
convert 0 t = t
convert n t = convert (n - 1) (elim n t)

process :: String -> String
process (lex -> [(n, lex -> [((`elem` ["=", "->"]) -> True, parse -> (t, ""))])]) =
  output (convert (read n) t) False

main :: IO ()
main = do
  line <- getLine
  putStrLn (process line)
  hFlush stdout
  main

Попробуйте онлайн!

Выход

  1. S (KS) К
  2. S (K (СС (К.К.))) (S (КК) С)
  3. S (К (СС)) (S (КК) К)
  4. S (K (СС (К.К.))) (S (КК) (S (KS) (S (K (S (Ск))) К)))
  5. S (K (S (К (СС (СК))))) (S (К (СС (СК))) (S (СКК) (СКК)))
  6. KK
  7. S (K (S (S (KS) (S (K (S (Ск))) К)))) (S (КК) К)
  8. S (K (СС (К (S (КК) (S (СКК) (СКК)))))) (S (ССК (КС)) (S (S (KS) (S (КК) (S (KS) К))) (К (S (K (S (ССК))) К))))
  9. S (K (S (КК))) (S (K (S (S (Ск) (Ск)))) К)
  10. SK
  11. S (KS) (S (КК) (S (К (СС)) (S (КК) К)))
  12. S (K (СС (К (S (КК) К)))) (S (КК) (S (KS) (S (ССК (КС)) (S (К (СС)) (S (КК) К) ))))
  13. S (K (S (K (S (К (СС (К.К.))) (S (КК) С))))) (S (К (СС (К.К.))) (S (КК) (S (KS) (S (K (S (Ск))) К))))
  14. S (K (S (K (S (К (СС (К.К.))) (S (КК) С))))) (S (K (S (Ск))) К)
  15. S (K (S (K (S (KS) К)))) (S (KS) К)
  16. S (K (S (KS) К))
  17. S (K (S (K (S (К (СС (К (S (S (KS) (S (КК) (ССК))) (К (S (Ск) (Ск))))))) (S (КК) (S (KS) К)))))) (S (К (СС (К (ССК)))) (S (КК) (S (KS) (S (КК) (ССК)))) )
  18. SSS (КК)
  19. KK
  20. S (КК) (S (КК) (S (S (KS) К) (S (K (S (Ск))) (S (K (S (Ск))) К))))
  21. S (S (KS) (S (КК) (S (KS) (S (КК) (S (К (СС)) (S (КК) К)))))) (К (S (K (S ( S (KS) (S (K (S (Ск))) К)))) (S (КК) К)))
  22. S (КК)
  23. S (KS) (S (КК) (S (KS) (S (КК) (S (К (СС)) (S (КК) К)))))
  24. S (K (S (K (S (KS) К)))) (S (K (S (S (KS) (S (КК) (S (К (СС)) (S (КК) К))) ))) (S (КК) (S (К (СС)) (S (КК) К))))
  25. S (KS) (S (КК) (S (KS) К))
  26. S (S (KS) (S (КК) (S (KS) (S (КК) (S (K (S (К (СС (К.К.))))) (S (KS) (S (КК) (S (ССК (КС)) (S (KS) (S (СКК) (СКК))))))))))) (К (S (S (KS) (S (K (S (K (S (KS ) (S (K (S (KS) (S (K (S (Ск))) К)))))))) (S (K (S (Ск))) К))) (S (К ( S (K (S (КК) К)))) (S (K (S (Ск))) К))))
  27. S (K (S (K (S (К (СС (К (S (K (S (S (KS) (S (K (S (Ск))) К)))) (S (КК) К)) ))) (S (КК) (S (KS) К)))))) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S ( KK) (S (KS) (S (КК) (S (К (СС)) (S (КК) К))))))
  28. К (S (KK))
  29. S (K (S (K (S (K (S (K (S (KS) К)))) (S (K (S (S (KS) (S (КК) (S (К (СС)) ( S (КК) К)))))) К))))) (S (K (S (S (KS) (S (КК) (S (К (СС)) (S (КК) К))) ))) (S (КК) (S (К (СС)) (S (КК) К))))
  30. S (КК) (S (К (SSS (КК))))
  31. К (SSS (KK))
  32. S (K (СС (К (S (S (KS) (S (КК) (S (KS) К))) (К (S (K (S (Ск))) К)))))) (S (КК) (S (KS) (СС (S (S (KS) (S (КК) (S (KS) (S (K (S (KS) (S (КК) (S (KS) К))) )))))) (КК))))
  33. S (K (S (K (S (K (S (К (СС (К.К.))) (S (КК) С))))))) (S (К (СС (К (S (КК) К) ))) (S (КК) (SSS (КС))))
  34. S (K (S (K (S (КК) К))))
  35. S (K (S (K (S (K (S (К (СС (К (S (K (S (Ск))) К)))) (S (КК) (S (KS) (S (КК) (S (К (СС (К (S (K (S (Ск))) К)))) (S (КК) (S (К (СС)) (S (КК) К))))))) )))))) (S (K (S (S (KS) (S (K (S (Ск))) К)))) (S (КК) К))
  36. S (K (СС (К (S (К (СС (К (S (K (S (Ск))) К)))) (S (КК) (S (KS) (СС (S (S (KS) (S (КК) (S (KS) (S (K (S (Ск))) К))))) (КК)))))))) (S (КК) (S (KS) (S ( KK) (S (K (S (K (S (K (S (K (S (К (СС (К.К.))) (S (КК) С))))))))) (S (К (СС (КК))) (S (КК) (S (KS) (S (K (S (KS) (S (КК) (S (KS) К))))))))))))
  37. S (КК) (S (K (S (K (S (КК) (S (КК) К))))) (СС (СК)))
  38. К (S (К (SSS (КК))))
  39. S (K (S (K (S (K (S (K (S (K (S (K (S (К (СС (К (S (K (S (S (KS) (S (K (S (Ск ))) К)))) (S (КК) К))))) (S (КК) (S (KS) К)))))) (S (К (СС (К (S (К (СС )) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К (СС)) (S ( К. К.) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К (СС)) (S (КК) К)) ))) (S (КК) (S (KS) (S (КК) (S (К (СС)) (S (КК) К))))))
  40. S (K (S (КК))) (S (KS) (S (КК) (S (K (S (КК) (S (КК) К))))))
  41. S (K (СС (К (S (S (KS) (S (КК) (S (KS) К))) (К (S (K (S (Ск))) К)))))) (S (КК) (S (KS) (S (КК) (S (K (S (K (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) К)))))) (S (К (СС (К (S (КК) (S (К (СС)) К))))) (S (КК) (S ( К (СС)) (S (КК) (S (K (S (K (S (КК) (S (KS) К))))) (S (KS) К))))))))))
  42. S (K (S (K (S (K (S (K (S (K (S (K (S (K (S (K (S (К (СС (К (S (K (S (S (KS) (S (K (S (Ск))) К)))) (S (КК) К))))) (S (КК) (S (KS) К)))))) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S ( К (СС)) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) (S (КК) (S (К (СС)) (S (КК) К))))))
  43. К (К (К (К (К (S (КК) (S (КК) (S (К (СС (СК))) (ССК))))))))
  44. S (КК) (S (K (S (КК) (S (КК) (S (КК) (S (КК) К))))))
  45. S (K (S (K (S (K (S (K (S (K (S (K (S (K (S (K (S (K (S (K (S (К (СС (К (S ( К (S (S (KS) (S (K (S (Ск))) К)))) (S (КК) К))))) (S (КК) (S (KS) К)))) )) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S ( К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К ( СС)) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) (S (КК) (S (К (СС)) (S (КК) К))))))
  46. S (K (S (K (S (K (S (K (S (К (СС (К (S (К (СС (К (S (К (СС (К.К.))) (S (КК) (S ( КС) (S (K (S (Ск))) К))))))) (S (КК) (S (KS) (S (КК) (S (ССК (КС)) (S (К (СС )) (S (KK) К)))))))))) (S (КК) (S (KS) (S (КК) (S (К (СС (К (S (КК) (S (KS ) (S (КК) (S (К (СС (К (S (КК) (S (KS) К))))) (S (КК) (S (К (СС)) (S (КК) (S (К (СС (К (S (КК) К)))) (S (КК) С)))))))))))) (S (КК) (S (К (СС)) К)) )))))))) (S (К (СС (К (S (КК) (S (K (S (S (KS) (S (КК) (S (К (СС)) (S (КК) К)))))) (S (КК) (S (К (СС)) (S (КК) К)))))))) (S (КК) С)))))) (S (К (СС (К (S (K (S (S (KS) (S (КК) (S (К (СС)) (S (КК) К)))))) (S (КК) (S (К ( СС)) (S (КК) К))))))) (S (КК) (S (KS) (S (КК) (S (K (S (K (S (KS) (S (КК) ( S (KS) К)))))) (S (KS) (S (КК) (S (К (СС)) (S (КК) К)))))))))
  47. S (K (СС (К (СС (S (S (KS) (S (КК) С))) (КК))))) (S (КК) (S (KS) (S (K (S (К (S (KS) (S (КК) (S (KS) (S (КК) (S (K (S (K (S (К (СС (К (S (K (S (S (KS) (S ( KK) (S (К (СС)) (S (КК) К)))))) (S (КК) (S (К (СС)) (S (КК) К))))))) (S (КК) (S (KS) К)))))))))))))) (S (K (S (S (KS) (S (КК) (S (К (СС)) (S ( KK) (S (K (S (K (S (KS) К)))) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S ( KK) (S (KS) (S (КК) (S (К (СС)) (S (КК) К))))))))))))) (S (КК) (S (K (S (К (S (КК) (S (KS) (S (КК) (S (К (СС (К (S (КК) (S (KS) К))))) (S (КК) (S (К (СС)) К))))))))) (S (KS) (S (КК) (S (К (СС (К (S (КК) К)))) (S (КК) (S ( КС) (S (ССК (КС)) (S (К (СС (К.К.))) (S (КК) (S (KS) (S (K (S (Ск))) К))))))) )))))))))
  48. К (S (K (S (КК) (S (K (S (КК) (S (K (S (КК) (S (КК) К))))))))))
  49. S (КК) (S (K (S (K (S (КК) (S (K (S (K (S (КК) (S (K (S (K (S (КК) (S (K (S ( К (S (КК) (S (K (S (КК))) (S (K (S (Ск))) К)))))) (S (K (S (Ск))) К))) ))) (S (K (S (Ск))) К)))))) (S (K (S (Ск))) К)))))) (S (K (S (Ск))) K))
  50. S (K (S (K (S (K (S (K (S (K (S (КК))) (S (К (СС (К (S (K (S (S (KS) (S (К ( S (Ск))) К)))) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К (СС)) (S (КК) К))))) (S (КК) (S (KS) К))))))) (S (К (СС (К (S (К (СС) ) (S (КК) К))))) (S (КК) (S (KS) (S (КК) (S (K (S (K (S (КК) (S (КК) (S (КК) (S (КК) К))))))) (S (К (СС)) (S (КК) К)))))))
Андерс Касеорг
источник
Можно ли сделать выражения автоматически оптимизируемыми (например S (K x) (K y) = K (x y))?
CalculatorFeline
@CalculatorFeline Я не понимаю вашего вопроса; S (К й ) (К у ) будет автоматически оптимизирован для K ( х ).
Андерс Касеорг
Подождите, эти выражения представлены как частично примененные функции или как-то еще? Если частично применены функции, то, возможно, вы могли бы сделать что-то вроде моего последнего комментария.
CalculatorFeline
@CalculatorFeline Представление выглядит, например, как 3 = 1 (2 3) 2 = S (K1) (S (K2) I) 2 = S (K1) 2 1 = S (S (KS) (S (KK) (K1))) I ↦ 1 = S (S (KS) (K (K1))) I ↦ 1 = S (K (S (K1)))) I ↦ 1 = S (K (S (K1) ))) I ↦ 1 = S (K1) ↦ S (KS) (S (KK) I) ↦ S (KS) K. Как вы можете видеть, мы уже использовали правило S (K x ) (K y ) ↦ K ( xy ) много раз, наряду с другими, в которых я перечислил 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.
Андерс Касеорг
5

Сумма длин решений: 12945 8508 5872

Код на Haskell, который берет входные строки из stdin и не заботится, является ли разделитель =или ->:

data E=S|K|V Int|A E E deriving Eq

instance Show E where
  showsPrec _ S = showChar 'S'
  showsPrec _ K = showChar 'K'
  showsPrec _ (V i) = shows i
  showsPrec p (A e f) = showParen (p>0) $ showsPrec 0 e . showsPrec 1 f

type SRead a = String -> (a,String) -- a simpler variation of ReadS

parse :: String -> E
parse s = let (e,"")=parseList (s++")") in e
parseList :: SRead E
parseList s = let (l,s')=parseL s in (foldl1 A l,s')
parseL :: SRead [E]
parseL (c:s) | c==' ' = parseL s
             | c==')' = ([],s)
parseL s = let (p,s')=parseExp s; (l,s'')=parseL s' in (p:l,s'')
parseExp :: SRead E
parseExp ('(':s) = parseList s
parseExp s = let [(n,s')]=reads s in (V n,s')

k e = A K e
s e f = A (A S e) f
i = s K K
s3 e f g = A (s e f) g
sk = A S K
ssk e f = A (s3 S K e) f

n `invars` (A e f) = n `invars` e || n `invars` f
n `invars` (V m)   = n==m
_ `invars` _       = False

comb (A e f) = comb e && comb f
comb (V _)   = False
comb _       = True

abstract _ (A (A S K) _) = sk
abstract n e | not (n `invars` e) = k e
abstract n (A e (V _)) | not (n `invars` e) = e
abstract n (A (A (V i) e) (V j)) | n==i && n==j =
                                   abstract n (ssk (V i) e)
abstract n (A e (A f g)) | comb e && comb f =
                                   abstract n (s3 (abstract n e) f g)
abstract n (A (A e f) g) | comb e && comb g =
                                   abstract n (s3 e (abstract n g) f)
abstract n (A (A e f) (A g h)) | comb e && comb g && f==h =
                                   abstract n (s3 e g f)
abstract n (A e f) = s (abstract n e) (abstract n f)
abstract n _ = i

abstractAll 0 e = e
abstractAll n e = abstractAll (n-1) $ abstract n e

parseLine :: String -> (Int,E)
parseLine s = let [(n,s')] = reads s
                  s''=dropWhile(`elem` " =->") s'
              in (n, parse s'')

solveLine :: String -> E
solveLine s = let (n,e) = parseLine s in abstractAll n e

main = interact $ unlines . map (show . solveLine) . lines

Он реализует улучшенную абстракцию скобок из раздела 3.2 Джона Тромпа: двоичное лямбда-исчисление и комбинаторная логика, который связан со статьей в Википедии о комбинаторной логике. Наиболее полезные особые случаи используют Sкомбинатор только для заполнения подтермов, чтобы избежать глубокого вложения переменных. Случай, который проверяет равенство некоторых подтерминов, не нужен ни для одного из тестовых случаев. Хотя нет особого случая для обработки Wкомбинатора (см. Ответ Питера), правила работают вместе, чтобы найти более короткое SS(SK)выражение. (Сначала я допустил ошибку, пытаясь оптимизировать внутренние вызовы abstract, но тогда такой Wоптимизации не произошло, и общий результат оказался на 16 байт длиннее.)

И вот результаты тестовых случаев:

S(KS)K
S(K(S(K(SS(KK)))K))S
S(K(S(K(SS))K))K
S(K(S(K(S(K(S(K(SS(KK)))K))S))(S(SKK))))K
S(K(S(K(SS(SK)))))(S(K(SS(SK)))(S(SKK)(SKK)))
KK
S(K(S(K(S(S(K(S(KS)(S(SKK))))K)))K))K
S(K(S(K(SS(K(S(KK)(S(SKK)(SKK))))))(S(KS))))(S(K(S(K(S(K(SS(K(S(K(S(SSK)))K))))K))S))K)
S(K(S(K(S(KK)))(S(S(SKK)(SKK)))))K
SK
S(K(S(K(S(K(S(S(KS)(S(KS)))))K))K))K
S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(KK)K))))K))S))(S(KS))))(SS)))K))K
S(K(S(K(S(K(S(K(SS(KK)))K))S))))(S(K(S(K(S(K(S(K(SS(KK)))K))S))(S(SKK))))K)
S(K(S(K(S(K(S(K(S(K(SS(KK)))K))S))))(S(SKK))))K
S(K(S(K(S(K(S(K(S(K(SS(K(S(KS)K))))K))S))K))S))K
S(K(S(KS)K))
S(S(K(S(KS)(S(K(S(KS)(S(KS)))))))(S(K(S(K(S(K(S(K(S(K(SS(K(S(S(K(S(KS)(S(KS))))(S(K(S(K(S(K(SS(K(S(S(KS)(S(K(SS(K(S(SKK)(SKK)))))K))K))))K))S))K))(S(KK)K)))))K))S))K))S))K))(S(K(S(KK)K))K)
S(KK)(S(KK))
KK
S(K(S(KK)K))(S(S(KS)K)(S(K(S(K(S(SKK)))(S(SKK))))K))
S(K(S(K(S(K(S(S(K(S(K(S(K(S(KS)(S(KS))))(S(S(K(S(KS)(S(SKK))))K))))K))K)))K))K))K
S(KK)
S(K(S(K(S(K(S(K(S(S(KS)(S(K(S(KS)(S(KS))))))))K))K))K))K
S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)K))K))))K))S))(S(K(S(KS)(S(KS)))))))(S(S(KS)(S(KS))))))K))K))K
S(K(S(K(S(KS)K))S))K
S(K(S(K(S(K(S(K(SS(KK)))(S(KS))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(K(S(KS)(S(SKK))))K))))))))(S(SKK))))K)(S(K(S(K(S(K(S(KK)K))))(S(SKK))))K)))))K))S))K))S))K))S))(S(SKK)(SKK)))
S(K(S(K(S(K(S(K(S(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(KS)))))))(S(S(K(S(K(S(K(S(KS)(S(KS))))(S(S(K(S(KS)(S(SKK))))K))))K))K))))K))K))K)))K))K))K))K
K(S(KK))
S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)K))K))))K))S))(S(K(S(KS)(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)K))K))))K))S))(S(K(S(KS)(S(KS)))))))(S(S(KS)(S(KS))))))K))K))K)
S(KK)(S(K(S(KK)(S(KK)))))
K(S(KK)(S(KK)))
S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)))(S(K(S(K(S(K(SS(K(S(K(S(SKK)))K))))K))S))K)))))K))S))K))S))(S(K(S(K(S(K(S(KS)K))S))K)))
S(K(S(K(S(K(S(K(S(K(SS(KK)))K))S))))))(S(K(S(K(S(K(SS(K(S(KK)K))))K))S))(S(KS)))
S(K(S(K(S(KK)K))))
S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(S(K(S(K(S(KS)(S(K(S(K(S(KS)(S(SKK))))K)))))(S(SKK))))K)))K))K))K))))))(S(S(K(S(KS)(S(SKK))))K))))K))K
S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(KK)))K))S))))))))))(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)))(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(K(S(KK)))(S(SKK))))K))))K))S))K))S))(S(SKK))))K)))))K))S))K))S))(S(K(S(K(S(K(S(KS)K))S))K))))
S(K(S(KK)(S(K(S(K(S(KK)K))K)))))(SS(SK))
K(S(K(S(KK)(S(KK)))))
S(K(S(K(S(K(S(K(S(K(S(K(S(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS)))))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS))))))))))(S(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(KS)))))))(S(S(K(S(K(S(K(S(KS)(S(KS))))(S(S(K(S(KS)(S(SKK))))K))))K))K))))K))K))K))))K))K))K))K))))K))K))K))K))K)))K))K))K))K))K))K
S(K(S(K(S(K(S(KK)(S(K(S(K(S(KK)K))K)))))))S))K
S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)K))K))))K))S))(S(K(S(KS)(S(KS)))))))(S(S(K(S(K(S(KS)K))S))K))))K))))(S(K(S(K(S(K(SS(K(S(K(S(SKK)))K))))K))S))K)))))K))S))K))S))K))S))K))S))K))S))K
S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS))))))))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS)))))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS))))))))))(S(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(KS)))))))(S(S(K(S(K(S(K(S(KS)(S(KS))))(S(S(K(S(KS)(S(SKK))))K))))K))K))))K))K))K))))K))K))K))K))))K))K))K))K))K))))K))K))K))K))K))K)))K))K))K))K))K))K))K
K(K(K(K(K(S(K(S(KK)K))(S(K(SS(SK)))(SSK)))))))
S(KK)(S(K(S(K(S(K(S(K(S(KK)K))K))K))K)))
S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS)))))))))))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS))))))))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS)))))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS))))))))))(S(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(KS)))))))(S(S(K(S(K(S(K(S(KS)(S(KS))))(S(S(K(S(KS)(S(SKK))))K))))K))K))))K))K))K))))K))K))K))K))))K))K))K))K))K))))K))K))K))K))K))K))))K))K))K))K))K))K))K)))K))K))K))K))K))K))K))K
S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS))))))))))))))))(S(K(S(K(S(K(S(K(SS(K(S(K(S(K(S(KK)K))K))K))))K))S))(S(K(S(KS)(S(K(S(KS)(S(KS)))))))))))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS)))))))))))))(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)K))K))))K))S))(S(K(S(KS)(S(KS)))))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS))))))))))(S(K(S(K(S(K(S(K(SS(K(S(KK)K))))K))S))(S(KS)))))))(S(S(K(S(KS)(S(KS))))(S(K(S(K(S(K(S(K(SS(KK)))K))S))(S(SKK))))K)))))K))K))K))))K))K))K))K))K))))K))K))K))K))K))K))K)))K))K))K))K))K))K))K))K))K
S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KK)K))K))K))K))K))K))K))))K))S))(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS)))))))))))))))))))(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(K(S(K(S(KK)K))K))K))K))))K))S))(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS)))))))))))))(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)K))K))))K))S))(S(K(S(KS)(S(KS)))))))))))))(S(K(S(K(S(K(S(K(SS(K(S(K(S(KK)K))K))))K))S))(S(K(S(KS)(S(KS)))))))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(K(S(K(S(K(S(KK)K))))))))(S(K(S(K(SS(KK)))K))S)))))K))S))K))S))K))S))K))S))(S(KS))))(S(K(S(K(S(K(S(K(SS(KK)))K))S))(S(SKK))))K))
K(S(K(S(KK)(S(K(S(KK)(S(K(S(K(S(KK)K))K)))))))))
S(K(S(K(S(KK)(S(K(S(K(S(K(S(KK)(S(K(S(K(S(K(S(KK)(S(K(S(K(S(K(S(KK)(S(K(S(K(S(K(S(KK)(S(KK))))(S(SKK))))K)))))(S(SKK))))K)))))(S(SKK))))K)))))(S(SKK))))K)))))(S(SKK))))K
S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KK)(S(K(S(K(S(K(S(K(S(KK)K))K))K))K)))))))))))(S(S(K(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(KS)(S(KS))))))))))(S(S(K(S(K(S(K(S(K(S(KS)(S(K(S(KS)(S(KS)))))))(S(S(K(S(K(S(K(S(KS)(S(KS))))(S(S(K(S(KS)(S(SKK))))K))))K))K))))K))K))K))))K))K))K))K))))K))K))K))K))K
Кристиан Сиверс
источник
3

8486 с использованием S, K, I, W

объяснение

Стандартный алгоритм (как описано , например , в главе 18 издеваться Пересмешником ) использует четыре случая, соответствующий комбинатор S, K, I = SKK, и простой лево-ассоциацию. Я думаю, что это то, что реализует ответ Кристиана. Этого достаточно, но не обязательно оптимально, и, поскольку нам разрешено жестко кодировать до 10 комбинаторов, остается 7 вариантов.

Другие известные комбинаторные комбинаторы

B x y z = x (y z)
C x y z = x z y
W x y = x y y

которые, вместе с K, сделать полную основу . В СК это

B = S (K S) K
C = S (S (K (S (K S) K)) S) (K K)
W = S S (S K)

и SKIправила выводят те же выражения для Bи C, но для Wних выводятся S S (K (S K K)). Поэтому я решил реализовать Wкак особый случай.

Программа (CJam)

e# A tests whether argument is an array
{W=!!}:A;

e# F "flattens" an expression by removing unnecessary parentheses, although if the expression is a primitive
e# it actually wraps it in an array
{
  e# A primitive is already flat, so we only need to process arrays
  _A{
    ee{
      ~
      e# Stack: ... index elt
      e# First recurse to see how far that simplifies the element
      F
      e# If it's an array...
      _A{
        e# ... we can drop a level of nesting if either it's the first one (since combinator application
        e# is left-associative) or if it's a one-element array
        _,1=@!|{
          e# The tricky bit is that it might be a string, so we can't just use ~
          {}/
        }*
      }{
        \;
      }?
    }%
  }{a}?
}:F;


qN%{

e# Parse line of input
"->=()"" [[[]"er']+~
e# Eliminate the appropriate variables in reverse order. E eliminates the variable currently stored in V.
\,:)W%{
  e# Flatten current expression
  F

  e# Identify cases; X holds the eXpression and is guaranteed to be non-primitive
  :X
  [
    XVa=                  e# [V]
    Xe_V&!                e# case V-free expression
    X)_A0{V=}?\e_V&!*     e# case array with exactly one V, which is the last element
    X_e_Ve=~)>[VV]=X,2>*  e# case array with exactly two Vs, which are the last two elements
  ]
  1#
  e# Corresponding combinators
  [
    {;"SKK"}              e# I
    {['K\]}               e# K
    {);}                  e# X (less that final V)
    {););['S 'S "SK"]\a+} e# W special-cased as SS(SK) because the general-case algorithm derives SS(K(SKK))
    {['S\)E\E\]}          e# S (catch-all case)
  ]=~
}:EfV

e# Format for output
F
{
  _A{
    '(\{P}%')
  }*
}:P%

oNo}/

Набор онлайн-тестов

Сгенерированные выходы:

S(KS)K
S(S(KS)(S(KK)S))(KK)
S(K(SS))(S(KK)K)
S(S(KS)(S(KK)(S(KS)(S(K(S(SKK)))K))))(KK)
S(K(S(K(SS(SK)))))(S(K(SS(SK)))(S(SKK)(SKK)))
KK
S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)
S(S(KS)(S(K(S(KS)))(S(S(KS)(S(KK)(S(KS)K)))(K(S(S(KS)(S(K(S(SKK)))K))(K(SKK)))))))(K(S(KK)(S(SKK)(SKK))))
S(K(S(KK)))(S(K(S(S(SKK)(SKK))))K)
K(SKK)
S(K(S(S(KS)(S(KS)))))(S(KK)(S(KK)K))
S(S(KS)(S(KK)(S(KS)(S(K(S(KS)))(S(K(SS))(S(KK)K))))))(K(S(KK)K))
S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(KS)))(S(S(KS)(S(KK)(S(KS)(S(K(S(SKK)))K))))(KK))))))(K(KK))
S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(KS)))(S(K(S(SKK)))K)))))(K(KK))
S(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)K)))))(K(S(KS)K))
S(K(S(KS)))(S(KK))
S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)K)))))(K(S(S(KS)(S(K(S(KS)))(S(S(KS)(S(KK)(S(KS)K)))(K(S(S(KS)(S(S(KS)K)(K(S(SKK)(SKK)))))K)))))(S(KK)K)))))))(S(KK)(S(KK)K))
S(KK)(S(KK))
KK
S(KK)(S(KK)(S(S(KS)K)(S(K(S(SKK)))(S(K(S(SKK)))K))))
S(K(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K))))))(S(KK)(S(KK)K))
S(KK)
S(K(S(S(KS)(S(K(S(KS)))(S(K(S(KS))))))))(S(KK)(S(KK)(S(KK)K)))
S(S(KS)(S(KK)(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(S(KS)(S(KS)))))(S(KK)(S(KK)K))))))))(K(S(KK)(S(KK)K)))
S(KS)(S(KK)(S(KS)K))
S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(SKK)(SKK)))))))))(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(SKK)))))))(S(K(S(K(S(KK)))))(S(K(S(SKK)))K))))))(S(K(S(KK)))(S(K(S(KK)))(S(K(S(SKK)))K))))))))))(K(K(KK)))
S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K))))))(S(KK)(S(KK)K))))))))(S(KK)(S(KK)(S(KK)K)))
K(S(KK))
S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(S(KS)(S(KK)(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(S(KS)(S(KS)))))(S(KK)(S(KK)K))))))))(K(S(KK)(S(KK)K))))))))))(K(K(S(KK)(S(KK)K))))
S(KK)(S(K(S(KK)))(S(K(S(KK)))))
K(S(KK)(S(KK)))
S(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(KS)))(S(KK))))))))))(K(S(K(S(KK)))(S(S(KS)(S(KK)(S(KS)K)))(K(S(K(S(SKK)))K)))))
S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(KK)))))(S(K(S(K(S(KS)))))(S(S(KS)(S(KK)(S(KS)(S(KS)))))(K(S(KK)K))))))))(K(K(KK)))
S(K(S(K(S(KK)))))(S(K(S(KK))))
S(K(S(K(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(SKK)))))(S(K(S(KK)))(S(K(S(SKK)))K)))))))))))(S(K(S(K(S(KK)))))(S(K(S(K(S(KK)))))(S(K(S(K(S(KK)))))(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)))))
S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(KS)))(S(KK))))))))))(K(S(K(S(KK)))(S(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(K(S(SKK)))K))))))(K(S(K(S(KK)))(S(K(S(SKK)))K))))))))))))))(K(K(K(K(KK)))))
S(KK)(S(K(S(KK)))(S(K(S(KK)))(S(K(S(KK)))(SS(SK)))))
K(S(K(S(KK)))(S(K(S(KK)))))
S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K))))))(S(KK)(S(KK)K))))))))(S(KK)(S(KK)(S(KK)K))))))))))(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K)))))
S(K(S(KK)))(S(K(S(K(S(KK)))))(S(K(S(K(S(KK)))))(S(K(S(K(S(KK)))))(S(KS)K))))
S(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)K)))))))))))(K(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(S(KS)(S(KK)(S(KS)K)))))))(S(K(S(KK)))(S(S(KS)(S(KK)(S(KS)K)))(K(S(K(S(SKK)))K)))))))))))(K(K(S(KK)(S(KK)K))))))
S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K))))))(S(KK)(S(KK)K))))))))(S(KK)(S(KK)(S(KK)K))))))))))(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))))(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K))))))
K(K(K(K(K(S(KK)(S(KK)(S(S(KS)(SSK))(K(SKK)))))))))
S(KK)(S(K(S(KK)))(S(K(S(KK)))(S(K(S(KK)))(S(K(S(KK)))(S(KK))))))
S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K))))))(S(KK)(S(KK)K))))))))(S(KK)(S(KK)(S(KK)K))))))))))(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))))(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))))))(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K)))))))
S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(KK)))))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(S(KS)(S(K(S(KS)))(S(S(KS)(S(KK)(S(KS)(S(K(S(SKK)))K))))(KK))))))(S(KK)(S(KK)K))))))))(K(K(S(KK)K))))))))))(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))(K(K(K(S(KK)(S(KK)K))))))))))))))(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))))))(K(K(K(K(S(KK)(S(KK)(S(KK)K))))))))))))))))))(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K))))))))
S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(K(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))))(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(K(S(K(S(K(S(KS)))))))))(S(K(S(K(S(K(S(K(S(K(S(KS)))))))))))(S(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(KK)(S(KS)(S(K(S(KS)))(S(S(KS)(S(KK)(S(KS)(S(K(S(SKK)))K))))(KK))))))))))))(K(S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(K(S(KK)))))))(S(S(KS)(S(KK)S))(KK))))))))))))))(K(K(K(K(S(KK)(S(KK)K))))))))))))))))(K(K(K(K(K(S(KK)(S(KK)K))))))))))))))))))(K(K(K(K(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))))))))))))(K(K(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)(S(KK)K)))))))))
K(S(K(S(KK)))(S(K(S(K(S(KK)))))(S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(KK))))))))))
S(KK)(S(K(S(KK)))(S(K(S(K(S(KK)))))(S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(K(S(K(S(K(S(K(S(KK)))))))))))(S(K(S(K(S(K(S(K(S(K(S(SKK)))))))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(K(S(K(S(K(S(SKK)))))))))(S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(K(S(SKK)))))))(S(K(S(K(S(KK)))))(S(K(S(K(S(SKK)))))(S(K(S(KK)))(S(K(S(SKK)))K))))))))))))))
S(K(S(K(S(K(S(KK)))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(K(S(K(S(K(S(KK)))))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(K(S(K(S(KS)))))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(K(S(KS)))))(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K))))))(S(KK)(S(KK)K))))))))(S(KK)(S(KK)(S(KK)K))))))))))(S(KK)(S(KK)(S(KK)(S(KK)K))))))))))
Питер Тейлор
источник