Zagadka kombinacyjna!

12

Wprowadzenie: Logika kombinacyjna

Logika kombinacyjna (CL) opiera się na rzeczach zwanych kombinatorami , które są w zasadzie funkcjami. Istnieją dwa podstawowe „wbudowane” kombinatory Si K, które zostaną wyjaśnione później.

Lewicowe skojarzenie

CL jest lewostronnie asocjatywny , co oznacza, że ​​nawiasy (zawierające elementy) znajdujące się po lewej stronie innej pary nawiasów zawierających je można usunąć, po zwolnieniu elementów. Na przykład coś takiego:

((a b) c)

Można zredukować do

(a b c)

Gdzie (a b)jest po lewej stronie większego wspornika ((a b) c), aby można go było usunąć.

Znacznie większy przykład lewostronnego skojarzenia (wyjaśnienia w nawiasach kwadratowych):

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

Wsporniki można również zmniejszyć, gdy więcej niż jedna para owija te same obiekty. Przykłady:

((((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.]

Wbudowane

CL ma dwa „wbudowane” kombinatory Si K, które mogą przełączać obiekty (pojedyncze kombinatory lub grupa kombinacji / grup owiniętych wokół nawiasów) w taki sposób:

K x y = x
S x y z = x z (y z)

Gdzie x, yi zmoże być stand-in do niczego.

Przykład Si Ksą następujące:

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

Inny przykład:

  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]

Powyższe są przykładami normalnych instrukcji CL, w których instrukcja nie może być dalej oceniana i osiąga wynik końcowy w skończonym czasie. Istnieją niestandardowe instrukcje (które są instrukcjami CL, które nie kończą się i będą podlegać ciągłej ocenie), ale nie mieszczą się w zakresie wyzwania i nie trzeba ich obejmować.

Jeśli chcesz dowiedzieć się więcej o CL, przeczytaj tę stronę w Wikipedii .

Zadanie:

Twoim zadaniem jest stworzenie dodatkowych kombinatorów, biorąc pod uwagę liczbę argumentów i to, co ocenia jako dane wejściowe, które podaje się w następujący sposób:

{amount_of_args} = {evaluated}

Gdzie {amount_of_args}jest dodatnią liczbą całkowitą równą liczbie argumentów i {evaluated}składa się z:

  • argumenty do ilości argumentów, przy 1czym pierwszy argument, 2drugi argument itd.
    • Masz gwarancję, że liczby argumentów powyżej ilości argumentów (więc 4kiedy {amount_of_args}jest tylko 3), nie pojawią się w {evaluated}.
  • nawiasy klamrowe ()

Przykładami danych wejściowych są:

3 = 2 3 1
4 = 1 (2 (3 4))

Pierwszym wejściem jest prośba o kombinator (powiedzmy R) z trzema argumentami ( R 1 2 3), który następnie przekształca się w:

R 1 2 3 -> 2 3 1

Drugie wejście wymaga tego (z nazwą kombinacji A):

A 1 2 3 4 -> 1 (2 (3 4))

Ze względu na wejście w tym formacie, musisz wrócić ciąg S, Ka (), który po zastąpieniu nazwy combinator i biegać z argumentów, zwraca ten sam oceniany jako oświadczenie {evaluated}bloku, gdy blok poleceń jest podstawiony z powrotem do tej nazwy combinator.

Wyjściowa instrukcja kombinatora może mieć usunięte białe spacje i zewnętrzne nawiasy, więc (S K K (S S))można zamienić coś podobnego SKK(SS).

Jeśli chcesz przetestować wyjścia Twój program, @aditsu dokonał rachunek kombinatorów parsera (co obejmuje S, K, Ia nawet inne te lubią Bi C) tutaj .

Wynik:

Ponieważ jest to , celem tego wyzwania jest osiągnięcie jak najmniejszej możliwej liczby bajtów na wyjściu, biorąc pod uwagę te 50 przypadków testowych . Podaj swoje wyniki dla 50 przypadków testowych w odpowiedzi lub utwórz pastebin (lub coś podobnego) i opublikuj link do tego pastebinu.

W przypadku remisu wygrywa najwcześniejsze rozwiązanie.

Zasady:

  • Twoja odpowiedź musi zwracać PRAWIDŁOWE wyjście - więc biorąc pod uwagę dane wejściowe, musi zwracać prawidłowe dane wyjściowe zgodnie z definicją w zadaniu.
  • Twoja odpowiedź musi pojawić się w ciągu godziny na nowoczesnym laptopie dla każdego przypadku testowego.
  • Wszelkie kodowanie rozwiązań jest niedozwolone. Możesz jednak zakodować na stałe do 10 kombinacji.
  • Twój program musi za każdym razem zwracać to samo rozwiązanie dla tego samego wejścia.
  • Twój program musi zwrócić poprawny wynik dla każdego podanego wejścia, a nie tylko przypadków testowych.
clismique
źródło
Jak możesz się upewnić, że ludzie nie będą kraść kombinatorów znalezionych w innych odpowiedziach?
Fatalize
@Fatalize To nie powinno mieć większego znaczenia, ponieważ ludzie mogą czerpać inspirację z odpowiedzi innych ludzi i wykorzystywać je do tworzenia lepszych odpowiedzi.
clismique
Mówiąc o natchnieniu, zauważam, że gdy pożądany wynik nie zawiera a 1, możesz odjąć 1wszystko, a następnie zapakować rozwiązanie dla tej odpowiedzi K(). Przykład: Rozwiązanie dla 2 -> 1jest K, więc rozwiązanie dla 3 -> 2jest KK, rozwiązanie dla 4 -> 3jest K(KK)itd.
Neil

Odpowiedzi:

8

Haskell , wynik 5017

Łączy to najgłupszy możliwy algorytm eliminacji abstrakcji ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M N ) (λ x . N ) ) z optymalizatorem wizjera używanym po każdej aplikacji. Najważniejszą regułą optymalizacji jest S (K x ) (K y ) ↦ K ( xy ), która powstrzymuje algorytm przed wysadzaniem w sposób wykładniczy.

Zestaw reguł jest skonfigurowany jako lista par ciągów, dzięki czemu można łatwo bawić się nowymi regułami. Jako specjalny bonus ponownego użycia parsera wejściowego do tego celu, S, K i I są również akceptowane w kombinatorach wejściowych.

Reguły nie są bezwarunkowo stosowane; raczej zachowywane są zarówno stara, jak i nowa wersja, a wersje nieoptymalne są przycinane tylko wtedy, gdy ich długość przekracza długość najlepszej wersji o więcej niż pewną stałą (obecnie 3 bajty).

Wynik jest nieznacznie poprawiany przez traktowanie I jako podstawowego kombinatora, dopóki stopień wyjściowy nie przepisuje go do SKK. W ten sposób KI = K (SKK) można skrócić o 4 bajty do SK na wyjściu, nie myląc pozostałych optymalizacji.

{-# 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

Wypróbuj online!

Wynik

  1. S (KS) K
  2. S (K (SS (KK))) (S (KK) S)
  3. S (K (SS)) (S (KK) K)
  4. S (K (SS (KK))) (S (KK) (S (KS) (S (K (S (SKK))) K)))
  5. S (K (S (K (SS (SK))))) (S (K (SS (SK))) (S (SKK) (SKK)))
  6. KK
  7. S (K (S (S (KS)) (S (K (S (SKK))) K)))) (S (KK) K)
  8. S (K (SS (K (S (KK)) (S (SKK) (SKK)))))) (S (SSK (KS)) (S (S (KS) (S (KK) (S (KS)) K))) (K (S (K (S (SSK))) K))))
  9. S (K (S (KK))) (S (K (S (S (SKK) (SKK)))) K)
  10. SK
  11. S (KS) (S (KK) (S (K (SS)) (S (KK) K)))
  12. S (K (SS (K (S (KK) K))))) (S (KK) (S (KS) (S (SSK (KS)) (S (K (SS)) (S (KK) K) ))))
  13. S (K (S (K (S (K (SS (KK)))) (S (KK) S))))) (S (K (SS (KK)))) (S (KK) (S (KS) (S (K (S (SKK))) K))))
  14. S (K (S (K (S (K (SS (KK))))) (S (KK) S))))) (S (K (S (SKK))) K)
  15. S (K (S (K (S (KS) K)))) (S (KS) K)
  16. S (K (S (KS) K))
  17. S (K (S (K (S (K (SS (K (S (S)) (S (KK) (SSK))) (K (S (SKK) (SKK))))))) (S (KK) (S (KS) K)))))) (S (K (SS (K (SSK))))) (S (KK) (S (KS) (S (KK) (SSK)))) )
  18. SSS (KK)
  19. KK
  20. S (KK) (S (KK) (S (S (KS) K) (S (K (S (SKK)))) (S (K (S (SKK))) K))))
  21. S (S (KS) (S (KK) (S (KS) (S (KK) (S (K (SS))) (S (KK) K)))))) (K (S (K (S ( S (KS) (S (K (S (SKK))) K)))) (S (KK) K)))
  22. S (KK)
  23. S (KS) (S (KK) (S (KS) (S (KK) (S (K (SS)) (S (KK) K)))))
  24. S (K (S (K (S (KS) K)))) (S (K (S (S (KS)) (S (KK) (S (K (SS)) (S (KK) K))) ))) (S (KK) (S (K (SS)) (S (KK) K))))
  25. S (KS) (S (KK) (S (KS) K))
  26. S (S (KS) (S (KK) (S (KS) (S (KK) (S (K (S (K (SS (KK))))) (S (KS) (S (KK) (S (SSK (KS)) (S (KS) (S (SKK) (SKK))))))))))) (K (S (S (KS)) (S (K (S (K (S (KS) ) (S (K (S (KS) (S (K (S (SKK)))))))))) (S (K (S (SKK))) K))) (S (K ( S (K (S (KK) K)))) (S (K (S (SKK))) K))))
  27. S (K (S (K (S (K (SS (K (S (K (S (S (KS)) (S) K) S (S) K) S (K) S (K) S (K) S) S ))) (S (KK) (S (KS) K)))))) (S (K (SS (K (S (K (SS))) (S (KK) K))))) (S ( KK) (S (KS) (S (KK) (S (K (SS)) (S (KK) K))))))
  28. K (S (KK))
  29. S (K (S (K (S (K (S (K (S (KS) K) S)) (S (K))) (S (K (S (S (KS) (S (K)) (S (K (SS)) ( S (KK) K))))) K))))) (S (K (S (S (KS)) (S (KK) (S (K (SS)) (S (KK) K))) ))) (S (KK) (S (K (SS)) (S (KK) K))))
  30. S (KK) (S (K (SSS (KK))))
  31. K (SSS (KK))
  32. S (K (SS (K (S (S (KS)) (S (KK) (S (KS) K)))) (K (S (K (S (SKK))) K)))))) (S (KK) (S (KS) (SS (S (S (KS)) (S (KK) (S (KS) (S (K (S (KS) (S (KK)) (S (KS) K))) )))))) (KK))))
  33. S (K (S (K (S (K (S (K (SS (KK) S) K)) (S (KK) S))))))) (S (K (SS (K (S (KK) K)) ))) (S (KK) (SSS (KS))))
  34. S (K (S (K (S (KK) K)))))
  35. S (K (S (K (S (K (S (K (SS (K)) (S (KK) (S (KS) (S (KK)) (S (K (SS (K (S (K (S (SKK))) K)))) (S (KK) (S (K (SS)) (S (KK) K))))))) )))))) (S (K (S (S (KS)) (S (K (S (SKK))) K)))) (S (KK) K))
  36. S (K (SS (K (S (K (SS (K (S (K (S (SKK)) (S) K)) S (K) S) (S) K) S (K (S (K) S)) (S (K (S)) (S (KK) (S (KS) (S (K (S (SKK))) K))))) (KK))))))) (S (KK) (S (KS) (S ( KK) (S (K (S (K (S (K (S (K (S (K (SS (KK) S) K) (S) K) S (K) S (K) S) K) K) S (KK))) (S (KK) (S (KS) (S (K (S (KS)) (S (KK) (S (KS) K))))))))))))))
  37. S (KK) (S (K (S (K (S (KK)) (S (KK) K))))) (SS (SK)))
  38. K (S (K (SSS (KK))))
  39. S (k (S (k (S (k (S (k (S (k (S (k (S (k (SS (k (S (k (S (S (KS) (S (k (S (SKK ))) K)))) (S (KK) K))))) (S (KK) (S (KS) K)))))) (S (K (SS (K (S (K (SS) )) (S (KK) K))))) (S (KK) (S (KS) K)))))))) (S (K (SS (K (S (K (SS))) KK) K))))) (S (KK) (S (KS) K))))))) (S (K (SS (K (S (K (SS))) (S (KK) K)) ))) (S (KK) (S (KS) (S (KK) (S (K (SS)) (S (KK) K))))))
  40. S (K (S (KK))) (S (KS) (S (KK) (S (K (S (KK) (S (KK) K))))))
  41. S (K (SS (K (S (S (KS)) (S (KK) (S (KS) K)))) (K (S (K (S (SKK))) K)))))) (S (KK) (S (KS) (S (KK) (S (K (S (K (S (K (SS (K (S (K (S) K) S)) (K) S) (K) S)) (S (KK) (S (KS) K)))))) (S (K (SS (K (S (KK)) (S (K (SS)) K))))) (S (KK) (S ( K (SS)) (S (KK) (S (K (S (K (S (K (KK)) (S (KS) K)))))) (S (KS) K))))))))))
  42. S (K (S (K (S (K (S (K (S (K (S (K (S (K (S (K (S (K (SS (K (SS (S (K (S (SKK))) K)))) (S (KK) K))))) (S (KK) (S (KS) K)))))) (S (K (SS (K (S (K (SS)) (S (KK) K))))) (S (KK) (S (KS) K))))))) (S (K (SS (K (S ( K (SS)) (S (KK) K))))) (S (KK) (S (KS) K))))))) (S (K (SS (K (S (K (SS))) (S (KK) K))))) (S (KK) (S (KS) K)))))))) (S (K (SS (K (S (K (SS))) (S (KK) K))))) (S (KK) (S (KS) (S (KK) (S (K (SS)) (S (KK) K))))))
  43. K (K (K (K (K (S (KK)) (S (KK)) (S (K (SS (SK))) (SSK))))))))
  44. S (KK) (S (K (S (KK) (S (KK)) (S (KK) (S (KK) K))))))
  45. 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 (S (KS) (S (K (S (SKK)))))) (S (KK) K))))) (S (KK) (S (KS) K)))) )) (S (K (SS (K (S (K (SS))) (S (KK) K))))) (S (KK) (S (KS) K))))))) (S ( K (SS (K (S (K (SS))) (S (KK) K))))) (S (KK) (S (KS) K))))))) (S (K (SS (K (S (K (SS)) (S (KK) K))))) (S (KK) (S (KS) K))))))) (S (K (SS (K (S (K ( SS)) (S (KK) K))))) (S (KK) (S (KS) K)))))))) (S (K (SS (K (S (K (SS))) (KK) K))))) (S (KK) (S (KS) (S (KK) (S (K (SS)) (S (KK) K))))))
  46. S (k (S (k (S (k (S (k (S (k (SS (k (S (k (SS (k (S (k (SS (KK))) (S (KK) (S ( KS) (S (K (S (SKK))) K))))))) (S (KK) (S (KS) (S (KK) (S (SSK (KS)) (S (K (SS )) (S (KK) K)))))))))) (S (KK) (S (KS) (S (KK) (S (K (SS (K (S (KK)) (S (KS) ) (S (KK) (S (K (SS (K (S (K (KK)) (S (KS) K)))))) (S (KK) (S (K (SS))) (S (KK) (S (K (SS (K (S (KK) K))))) (S (KK) S)))))))))))) (S (KK) (S (K (SS)) K)) )))))))) (S (K (SS (K (S (KK)) (S (K (S) (S)) (S (K (SS)) (S (KK) K)))))) (S (KK) (S (K (SS)) (S (KK) K)))))))) (S (KK) S)))))) (S (K (SS (K (S (K (S (S (KS)) (S (KK) (S (K (SS))) (S (KK) K)))))) (S (KK) (S (K ( SS)) (S (KK) K))))))) (S (KK) (S (KS) (S (KK) (S (K (S (K (S (KS)) (S (KK)) ( S (KS) K)))))) (S (KS) (S (KK) (S (K (SS)) (S (KK) K)))))))))))
  47. S (K (SS (K (SS (S (S (KS)))) (KK))))) (S (KK) (S (KS) (S (K (S (K (S (KS) (S (KK) (S (KS) (S (KK)) (S (K (S (K (S (K (SS (K (SS KK) (S (K (SS)) (S (KK) K)))))) (S (KK) (S (K (SS)) (S (KK) K))))))) (KK) (S (KS) K)))))))))))))) (S (K (S (S (KS)) (S (KK) (S (K (SS))) (S ( KK) (S (K (S (K (S (KS) K))))) S (K (SS (K (S (K (SS))) (S (KK) K))))) (S ( KK) (S (KS) (S (KK) (S (K (SS)) (S (KK) K)))))))))))) (S (KK) (S (K (S (K (S (KK) (S (KS)) (S (KK) (S (K (SS (K (S (KK) (S)) K)))) (S (KK) (S (K (SS)) K))))))))) (S (KS) (S (KK) (S (K (SS (K (S (KK) K)))) (S (KK) (S ( KS) (S (SSK (KS)) (S (K (SS (KK)))) (S (KK) (S (KS) (S (K (S (SKK))) K))))))) )))))))))
  48. K (S (K (S (KK)) (S (K (S (KK)) S (K (S (KK) (S (KK) K)))))))))))
  49. S (KK) (S (K (S (K (S (KK)) (S (K (S (K)) (S (K (S (K (S (K (S (K (S) K (S (KK) (S (K (S (KK)))) (S (K (S (SKK))) K))))) (S (K (S (SKK))) K))) ))) (S (K (S (SKK))) K)))))) (S (K (S (SKK))) K)))))) (S (K (S (SKK))) K))
  50. S (K (S (K (S (K (S (K (S (K (S (KK) S) K) S (K) S (K) S (K (S (K)) S (SKK))) K)))) (S (KK) K))))) (S (KK) (S (KS) K))))))) (S (K (SS (K (S (K (SS)) (S (KK) K))))) (S (KK) (S (KS) K))))))) (S (K (SS (K (S (K (SS)) ) (S (KK) K))))) (S (KK) (S (KS) (S (KK) (S (K (S (K (S (K (S)) (S (KK)) (S (KK) (S (KK) K))))))) (S (K (SS)) (S (KK) K)))))))
Anders Kaseorg
źródło
Czy możliwe byłoby automatyczne zoptymalizowanie wyrażeń (np. S (K x) (K y) = K (x y))?
CalculatorFeline
@CalculatorFeline Nie rozumiem twojego pytania; S (K x ) (K y ) jest automatycznie optymalizowane do K ( xy ).
Anders Kaseorg,
Zaraz, czy te wyrażenia są reprezentowane jako częściowo zastosowane funkcje czy coś innego? Jeśli funkcje częściowo zastosowane, to możesz zrobić coś takiego jak mój ostatni komentarz.
CalculatorFeline
@CalculatorFeline Przedstawienie wygląda na przykład 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. Jak widać, już wiele razy używaliśmy reguły S (K x ) (K y ) ↦ K ( xy ), wraz z innymi wymienionymi w ruleStrings. Gdybyśmy tego nie zrobili, wynik byłby wykładniczo dłuższy: dla tego małego przykładu otrzymalibyśmy S (S (KS) (S (S (KS) (S (KK) (KS))) (S (S (KS) (S (KK) (KK))) (S (KK) (SKK))))) (S (S (KS) (S (S (KS) (S (KK) (KS))) ( S (S (KS) (S (KK) (KK))) (SK)))) (S (KK) (SK))) zamiast S (KS) K.
Anders Kaseorg,
5

Suma długości roztworów: 12945 8508 5872

Kod Haskell, który pobiera linie wejściowe ze standardowego wejścia i nie dba o to, czy separatorem jest =czy ->:

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

Implementuje ulepszoną abstrakcję nawiasów z sekcji 3.2 John Tromp: Binary Lambda Calculus and Combinatory Logic, która jest powiązana z artykułem Wikipedii na temat logiki kombinatorycznej. Najbardziej przydatne przypadki specjalne używają Skombinatora tylko do przechwytywania subtermów w celu uniknięcia głębokiego zagnieżdżania zmiennych. Sprawa, która sprawdza równość niektórych podtermów, nie jest potrzebna dla żadnego z przypadków testowych. Chociaż nie ma specjalnego przypadku obsługi Wkombinatora (patrz odpowiedź Piotra), reguły współdziałają w celu znalezienia krótszego SS(SK)wyrażenia. (Najpierw popełniłem błąd, próbując zoptymalizować wewnętrzne wywołania abstract, a następnie ta Woptymalizacja nie doszła do skutku, a ogólny wynik był o 16 bajtów dłuższy.)

A oto wyniki z przypadków testowych:

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
Christian Sievers
źródło
3

8486 przy użyciu S, K, I, W

Wyjaśnienie

Standardowy algorytm (jak opisano na przykład w rozdziale 18 MOCK przedrzeźniacz ) wykorzystuje cztery przypadki, odpowiadających złożone jest S, K, I = SKKi proste lewej związek. Myślę, że to właśnie realizuje odpowiedź Christiana. Jest to wystarczające, ale niekoniecznie optymalne, a ponieważ wolno nam na stałe zakodować do 10 kombinacji, pozostawia 7 opcji.

Inne znane kombinatory kombinatoryczne to

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

które wraz z K, wykonać pełną podstawę . W SK są to

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

i SKIreguły wywodzą te same wyrażenia dla Bi C, ale dla Wwywodzą S S (K (S K K)). Dlatego postanowiłem wdrożyć Wjako specjalny przypadek.

Program (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}/

Zestaw testów online

Wygenerowane wyniki:

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))))))))))
Peter Taylor
źródło