1000 – 2000 rep for figuring out how to program with both halves of a Stack Cats program
This bounty needs a bit of background, so bear with me.
Stack Cats is an esolang with fairly strong constraints on its program structure. Specifically, each valid program has to have mirror symmetry, and the commands are designed such that mirroring a character results in the inverse operation. That means that the second half of the program (disregarding the character in the centre) exactly undoes what the first half did. So in a way it's on that central character to change the program state in a meaningful way, such that the undoing part actually results in the program behaviour you want.
Of course, there's only a handful of possible commands that can even be used for that single central character. For the mathematically inclined, this means that programming in Stack Cats is all about finding a conjugate relation that transforms one of 12 built-ins into the program you want to write. Nevertheless, I believe that Stack Cats is in fact Turing-complete.
While I've written non-trivial programs in Stack Cats (for example this primality test), they all rely on a certain construction that essentially works around these limitations, by skipping the entire first half of the program. This lets us put arbitrary "unbalanced" code in the second half, so we don't really have to worry about the conjugation. The basic construction looks like this:
<(...)*(...)>
The ()
are conditionals, which are always false in the first half and always true in the second half, so the first ...
is skipped and the second ...
is executed. The problem is that this is clearly inefficient for golfing: we could be doing useful stuff with both halves of the program, but we're just throwing one half away to be able to make sense of the program in the first place.
For very trivial problems, Sp3000 and I have found some programs that don't use this construction, but even those were usually found by an automated search. Here is an example of that for adding two numbers. In particular, our brute force approaches are usually nowhere near fast enough to find solutions that actually require control flow/loops. As far as I know, the only program that was ever written which uses both halves and contains a loop is this program by feersum (and given that the task was to implement an arbitrary OEIS sequence, it's likely that they just tried some programs with loops until one of them produced a reasonable OEIS sequence).
So, Sp3000 and I will together award 1000 rep to a Stack Cats answer, which:
- Contains non-trivial control flow, i.e.
(...)
and/or {...}
which don't always do the same regardless of program input (in particular, if there's a (...)
it should be executed for some inputs and skipped for others, to make sure that it isn't used to skip unused parts of the code unconditionally).
- Contains an explanation for how one can find such an answer without resorting to automated search (of course, you're perfectly welcome to make use of automated searches to get a better understanding of the structure of Stack Cats programs).
- Can't be easily outgolfed by an answer which uses the
<(...)*(...)>
template or which uses no control flow operations at all (to ensure that the program isn't just a linear solution like the addition program, padded with some loops which don't end up doing anything; and also to ensure that this technique actually makes use of both halves in an efficient way).
To be clear, the explanation is the most important part: this bounty isn't for finding such a solution by serendipity but for understanding how to construct such a solution.
Don't try to find loopholes in these rules — we're in no obligation to actually hand out the bounty, so if we feel like your answer is clearly not in the spirit of this bounty, we won't award it. I'm pretty sure that any answer which actually deserves the bounty, will do so quite obviously. Also, if you can solve several challenges (which are sufficiently different) with your technique — which would be a great proof that it's actually a general technique and not just a way to solve one particular task — we will award another 1000 rep to a second answer.
cat
8.32 \$\endgroup\$