We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.

Return to Revisions

Stack Cats, 8 + 4 = 12 bytes

]_:]_!<X

Run with the -mn flags. Try it online!

Golfing in Stack Cats is highly counterintuitive, so this program above was found with a few days of brute forcing. For comparison, a more intuitive, human-written solution using the *(...)> template is two bytes longer

*(>-_:[:)>

with the -ln flags instead.

Explanation

Here's a primer on Stack Cats:

• Stack Cats is a reversible esoteric language where the mirror of a snippet undoes the effect of the original snippet. Programs must also be mirror images of itself — necessarily, this means that even-length programs are either no-ops or infinite loops, and all non-trivial terminating programs are of odd length (and are essentially a conjugation of the central operator).
• Since half the program is always implied, one half can be left out with the -m or -l flag. Here the -m flag is used, so the half program above actually expands to ]_:]_!<X>!_[:_[.
• As its name suggests, Stack Cats is stack-based, with the stacks being bottomless with zeroes (i.e. operations on an otherwise empty stack return 0). Stack Cats actually uses a tape of stacks, e.g. < and > move one stack left and one stack right respectively.
• Zeroes at the bottom of the stack are swallowed/removed.
• All input is pushed to an initial input stack, with the first input at the top and an extra -1 below the last input. Output is done at the end, using the contents of the current stack (with an optional -1 at the bottom being ignored). -n denotes numeric I/O.

And here's a trace of the expanded full program, ]_:]_!<X>!_[:_[:

 Initial state (* denotes current stack):
 ... [] [-1 b a]* [] [] ...
] Move one stack right, taking the top element with you
 ... [] [-1 b] [a]* [] ...
_ Reversible subtraction, performing [x y] -> [x x-y] (uses an implicit zero here)
 ... [] [-1 b] [-a]* [] ...
: Swap top two
 ... [] [-1 b] [-a 0]* [] ...
] Move one stack right, taking the top element with you
 ... [] [-1 b] [-a] []* ...
_ Reversible subtraction (0-0, so no-op here)
! Bit flip top element, x -> -x-1
 ... [] [-1 b] [-a] [-1]* ...
< Move one stack left
 ... [] [-1 b] [-a]* [-1] ...
X Swap the stack to the left and right
 ... [] [-1] [-a]* [-1 b] ...
> Move one stack right
 ... [] [-1] [-a] [-1 b]* ...
! Bit flip
 ... [] [-1] [-a] [-1 -b-1]* ...
_ Reversible subtraction
 ... [] [-1] [-a] [-1 b]* ...
[ Move one stack left, taking the top element with you
 ... [] [-1] [-a b]* [-1] ...
: Swap top two
 ... [] [-1] [b -a]* [-1] ...
_ Reversible subtraction
 ... [] [-1] [b a+b]* [-1] ...
[ Move one stack left, taking the top element with you
 ... [] [-1 a+b]* [b] [-1] ...

a+b is then outputted, with the base -1 ignored.

---

Just for fun, here's the full list of related solutions of the same length found (list might not be complete):

]_:]^!<X
]_:]_!<X
]_:]!^<X
]_:!]^<X
[_:[^!>X
[_:[_!>X
[_:[!^>X
[_:![^>X