Introduction: Combinatory Logic
Combinatory logic (CL) is based off of things called combinators, which are basically functions. There are two basic "built-in" combinators, S and K, which will be explained later.
Left-associativity
CL is left-associative, which means brackets (containing stuff) which are at the far-left of anther pair of brackets containing it can be removed, with its stuff released. For example, something like this:
((a b) c)
Can be reduced to
(a b c)
Where the (a b) is on the far-left of the bigger bracket ((a b) c), so it can be removed.
A much bigger example of left-association (square brackets are explanations):
((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)]
Brackets can also be reduced when more than one pair wrap around the same objects. Examples:
((((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
CL has two "built-in" combinators, S and K, which can switch objects (single combinators, or a group of combinators / groups wrapped around brackets) around like so:
K x y = x
S x y z = x z (y z)
Where x, y and z can be stand-ins for anything.
An example of S and K are as follows:
(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]
Another example:
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]
The above are examples of normal CL statements, where the statement cannot be evaluated further and achieves an end result in a finite amount of time. There are non-normal statements (which are CL statements that do not terminate and will keep being evaluated forever), but they aren't within the scopes of the challenge and won't need to be covered.
If you want to learn more about CL, read this Wikipedia page.
Task:
Your task is to make extra combinators, given the number of arguments, and what it evaluates to as input, which is given like so:
{amount_of_args} = {evaluated}
Where {amount_of_args} is a positive integer equal to the number of args, and {evaluated} consists of:
- arguments up to the amount of args, with
1being the first argument,2being the second, etcetera.- You are guaranteed that argument numbers above the amount of args (so a
4when{amount_of_args}is only3) won't appear in{evaluated}.
- You are guaranteed that argument numbers above the amount of args (so a
- brackets
()
So examples of inputs are:
3 = 2 3 1
4 = 1 (2 (3 4))
The first input is asking for a combinator (say, R) with three arguments (R 1 2 3), which then evaluates into:
R 1 2 3 -> 2 3 1
The second input asks for this (with a combinator name A):
A 1 2 3 4 -> 1 (2 (3 4))
Given the input in this format, you must return a string of S, K and (), which when substituted with a combinator name and run with arguments, returns the same evaluated statement as the {evaluated} block when the command block is substituted back for that combinator name.
The output combinator statement may have its whitespace removed and the outer brackets removed, so something like (S K K (S S)) can be turned into SKK(SS).
If you want to test your program's outputs, @aditsu has made a combinatory logic parser (which includes S, K, I and even other ones like B and C) here.
Score:
Since this is a metagolf, the aim of this challenge is to achieve the smallest amount of bytes in the output possible, given these 50 test-cases. Please put your results for the 50 test-cases in the answer, or make a pastebin (or something similar) and post a link to that pastebin.
In the event of a tie, the earliest solution wins.
Rules:
- Your answer must return CORRECT output - so given an input, it must return the correct output as per the definition in the task.
- Your answer must output within an hour on a modern laptop for each test case.
- Any hard-coding of solutions is disallowed. However, you are allowed to hard-code up to 10 combinators.
- Your program must return the same solution every time for the same input.
- Your program must return a valid result for any input given, not just test-cases.
1, you can subtract1from everything, and then wrap solution for that answer inK(). Example: Solution for2 -> 1isK, therefore solution for3 -> 2isKK, solution for4 -> 3isK(KK)etc. \$\endgroup\$