Enigma Combinado!

12

Introdução: Lógica Combinatória

A lógica combinatória (CL) é baseada em coisas chamadas combinadores , que são basicamente funções. Existem dois combinadores "internos" básicos Se K, que serão explicados mais adiante.

Associatividade esquerda

CL é associativo à esquerda , o que significa que colchetes (que contêm material) que estão na extremidade esquerda do par de parêntesis que o contêm podem ser removidos, com o material liberado. Por exemplo, algo como isto:

((a b) c)

Pode ser reduzido para

(a b c)

Onde (a b)está na extremidade esquerda do suporte maior ((a b) c), para que possa ser removido.

Um exemplo muito maior de associação à esquerda (colchetes são explicações):

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

Os colchetes também podem ser reduzidos quando mais de um par envolve os mesmos objetos. Exemplos:

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

Builtins

O CL possui dois combinadores "internos" Se K, que podem alternar objetos (combinadores únicos ou um grupo de combinadores / grupos entre colchetes) entre os seguintes:

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

Onde x, ye zpode ser stand-ins para qualquer coisa.

Um exemplo de Se Ksão os seguintes:

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

Outro exemplo:

  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]

Os exemplos acima são exemplos de instruções CL normais, nas quais a instrução não pode ser avaliada mais e alcança um resultado final em um período finito de tempo. Existem instruções não normais (que são declarações de CL que não terminam e continuarão sendo avaliadas para sempre), mas não estão no escopo do desafio e não precisam ser cobertas.

Se você quiser saber mais sobre CL, leia esta página da Wikipedia .

Tarefa:

Sua tarefa é criar combinadores extras, dado o número de argumentos e o que ele avalia como entrada, que é dada assim:

{amount_of_args} = {evaluated}

Onde {amount_of_args}é um número inteiro positivo igual ao número de args e {evaluated}consiste em:

  • argumentos até a quantidade de argumentos, 1sendo o primeiro argumento, 2o segundo, etc.
    • Você tem certeza de que os números dos argumentos acima da quantidade de args (portanto, somente 4quando ) não aparecerão .{amount_of_args}3{evaluated}
  • colchetes ()

Portanto, exemplos de entradas são:

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

A primeira entrada está solicitando um combinador (digamos R) com três argumentos ( R 1 2 3), que é avaliado em:

R 1 2 3 -> 2 3 1

A segunda entrada solicita isso (com um nome combinador A):

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

Dada a entrada nesse formato, você deve retornar uma sequência de S, Ke ()que, quando substituída por um nome de combinador e executada com argumentos, retorna a mesma instrução avaliada que o {evaluated}bloco quando o bloco de comando é substituído novamente por esse nome de combinador.

A declaração do combinador de saída pode ter seu espaço em branco removido e os colchetes externos removidos, para que algo como (S K K (S S))possa ser transformado SKK(SS).

Se você quiser testar as saídas do seu programa, @aditsu fez um analisador lógica combinatória (que inclui S, K, Ie até mesmo outras gosto Be C) aqui .

Ponto:

Como esse é um , o objetivo desse desafio é atingir a menor quantidade de bytes possível na saída, considerando esses 50 casos de teste . Coloque os resultados para os 50 casos de teste na resposta ou faça uma pastebin (ou algo semelhante) e poste um link para essa pastebin.

Em caso de empate, a solução mais antiga vence.

Regras:

  • Sua resposta deve retornar a saída CORRETA - portanto, dada uma entrada, ela deve retornar a saída correta conforme a definição na tarefa.
  • Sua resposta deve ser exibida dentro de uma hora em um laptop moderno para cada caso de teste.
  • Qualquer codificação de soluções não é permitida. No entanto, você pode codificar até 10 combinadores.
  • Seu programa deve retornar sempre a mesma solução para a mesma entrada.
  • Seu programa deve retornar um resultado válido para qualquer entrada fornecida, não apenas para casos de teste.
clismique
fonte
Como você pode garantir que as pessoas não roubem os combinadores encontrados em outras respostas?
Fatalize
@Fatalize Isso não deve importar muito, pois as pessoas podem se inspirar nas respostas de outras pessoas e aproveitar isso para criar melhores respostas.
Clismique
Falando em inspiração, noto que, quando o resultado desejado não contém a 1, você pode subtrair 1tudo e, em seguida, agrupar a solução para essa resposta K(). Exemplo: Solução para 2 -> 1é K, por conseguinte, para a solução 3 -> 2é KK, solução para 4 -> 3é K(KK)etc
Neil

Respostas:

8

Haskell , pontuação 5017

Isso combina o algoritmo mais estúpido possível para a eliminação da abstração ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M ) (λ x . N ) ) com um otimizador de olho mágico usado após cada aplicação. A regra de otimização mais importante é S (K x ) (K y ) ↦ K ( xy ), que impede o algoritmo de explodir sempre exponencialmente.

O conjunto de regras é configurado como uma lista de pares de cordas, para que seja fácil brincar com novas regras. Como um bônus especial de reutilizar o analisador de entrada para esse fim, S, K e I também são aceitos nos combinadores de entrada.

Regras não são aplicadas incondicionalmente; em vez disso, as versões antiga e nova são mantidas, e as versões sub-ótimas são removidas apenas quando o comprimento excede o da melhor versão em mais do que uma constante (atualmente 3 bytes).

A pontuação é ligeiramente melhorada tratando I como um combinador fundamental até que o estágio de saída a reescreva para SKK. Dessa forma, KI = K (SKK) pode ser reduzido em 4 bytes para SK na saída sem confundir o restante das otimizações.

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

Experimente online!

Resultado

  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 (SK (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 (KS) (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 (SK (SK))) 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 (K (S)) (S (K (S (K (S (KS))) ) (S (K (S (KS) (S (K (S (SKK))) K)))))))) (S (K (S (SK (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 (SKK))) K)))) (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))))))
  28. K (S (KK))
  29. S (K (S (K (S (K (S (K (S (KS) K)))) (S (K (S (S (K (S)) (S (KK) (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 (SK (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 (KK) S))))))))) (S (K (SS (K (S (K (S)) 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 (K (S (SKK))) K)))) (S (KK) (S (KS) (S (KK)) (S (K (SS (K (S (K (S (SK))) 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))) K))) (S (KK) (S (KS) (SS (S (S (KS))) (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 (KK) S))))))))) (S (K (SS (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 (SS))) (S ( KK) K))))) (S (KK) (S (KS) K))))))) (S (K (SS (K (S (K (SS (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 (SK (S (SKK))) K))))) (S (KK) (S (KS) (S (KK) (S (K (S (K (S (K (SS (K (S (K (SS)) (S (KK) K))))) (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 (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 (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)) (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 (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))) 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) K))))))) (S (K (SS (K (S (K (SS))) (S (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))) 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 (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 (KS) (S (KK) (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) (S (KK) S))) (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 (K (S (K (S (S (K (S)))) KK) (S (K (SS)) (S (KK) K)))))) (S (KK) (S (K (SS)) (S (KK) K)))))) (S (KK) (S (KS) K)))))))))))))) (S (K (S (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 (KS) 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 (KK)) (S (K (S (K (S (KK)) (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 (SK ()))) K))
  50. S (K (S (K (S (K (S (K (S (K (S (KK))) (S (K (SS (K (S (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))) ) (S (KK) K))))) (S (KK) (S (KS) (S (KK) (S (K (S (K (S (K (S (KK) (S (KK) (S (KK))) (S (KK) K))))))) (S (K (SS)) (S (KK) K)))))))
Anders Kaseorg
fonte
Seria possível fazer as expressões otimizar automaticamente (por exemplo S (K x) (K y) = K (x y))?
CalculatorFeline
@CalculatorFeline Não entendi sua pergunta; S (K x ) (K y ) é automaticamente otimizado para K ( xy ).
Anders Kaseorg
Espere, essas expressões são representadas como funções parcialmente aplicadas ou algo mais? Se funções parcialmente aplicadas, talvez você possa fazer algo como o meu último comentário.
CalculatorFeline
@CalculatorFeline A representação parece, por exemplo, 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. Como você pode ver, já usamos a regra S (K x ) (K y ) x K ( xy ) muitas vezes, juntamente com as outras em que listei ruleStrings. Se não o fizéssemos, a saída seria exponencialmente maior: neste pequeno exemplo, teríamos obtido 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))) em vez de S (KS) K.
Anders Kaseorg
5

Soma dos comprimentos da solução: 12945 8508 5872

Código Haskell que recebe linhas de entrada do stdin e não se importa se o separador é =ou ->:

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

Ele implementa a abstração de colchete aprimorada da seção 3.2 de John Tromp: Cálculo binário lambda e lógica combinatória, que está vinculada ao artigo da Wikipedia sobre lógica combinatória. Os casos especiais mais úteis usam apenas o Scombinador para sufocar subtermos, a fim de evitar o agrupamento profundo de variáveis. O caso que verifica a igualdade de alguns subtermos não é necessário para nenhum dos casos de teste. Embora não haja um caso especial para lidar com o Wcombinador (consulte a resposta de Peter), as regras trabalham juntas para encontrar a SS(SK)expressão mais curta . (Cometi um erro ao tentar otimizar as chamadas internas para abstract, então essa Wotimização não aconteceu e o resultado geral foi 16 bytes mais longo.)

E aqui estão os resultados dos casos de teste:

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
Peneiradores cristãos
fonte
3

8486 usando S, K, I, W

Explicação

O algoritmo de padrão (por exemplo, como descrito no capítulo 18 de Para Mock um Mockingbird ) utiliza quatro casos, correspondente aos combinadores S, K, I = SKK, e deixou-simples associação. Eu acho que é isso que a resposta de Christian implementa. Isso é suficiente, mas não necessariamente ideal, e como podemos codificar até 10 combinadores, deixa 7 opções.

Outros combinadores combinatórios bem conhecidos são

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

que, juntamente com K, formam uma base completa . No SK, esses são

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

e as SKIregras derivam essas mesmas expressões para Be C, mas para Welas derivam S S (K (S K K)). Por isso, decidi implementar Wcomo um caso especial.

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

Conjunto de testes online

Saídas geradas:

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
fonte