Return to Answer

• 1

• 198.2k
• 67
• 455
• 998

• 198.2k
• 67
• 455
• 998

Stack Cats, 62 + 4 = 66 bytes

*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]

Needs to be run with the -ln command-line flags (hence +4 bytes). Prints 0 for composite numbers and 1 for primes.

Try it online!

I think this is the first non-trivial Stack Cats program.

Explanation

A quick Stack Cats introduction:

• Stack Cats operates on an infinite tape of stacks, with a tape head pointing at a current stack. Every stack is initially filled with an infinite amount of zeros. I will generally ignore these zeros in my wording, so when I say "the bottom of stack" I mean the lowest non-zero value and if I say "the stack is empty" I mean there's only zeros on it.

• Before the program starts, a -1 is pushed onto the initial stack, and then the entire input is pushed on top of that. In this case, due to the -n flag, the input is read as a decimal integer.

• At the end of the program, the current stack is used for output. If there's a -1 at the bottom, it will be ignored. Again, due to the -n flag, the values from the stack are simply printed as linefeed-separated decimal integers.

• Stack Cats is a reversible program language: every piece of code can be undone (without Stack Cats keeping track of an explicit history). More specifically, to reverse any piece of code, you simply mirror it, e.g. <<(\-_) becomes (_-/)>>. This design goal places fairly severe restrictions on what kinds of operators and control flow constructs exist in the language, and what sorts of functions you can compute on the global memory state.

• To top it all off, every Stack Cats program has to be self-symmetric. You might notice that this is not the case for the above source code. This is what the -l flag is for: it implicitly mirrors the code to the left, using the first character for the centre. Hence the actual program is:

   [<(*>=*(:)*[(>*{[[>[:<[>>_(_-<<(-!>)>(>-)):]<^:>!->}<*)*[^:<)*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]
  

Programming effectively with the entire code is highly non-trivial and unintuitive and haven't really figured out yet how a human can possibly do it. We've brute forced such program for simpler tasks, but wouldn't have been able to get anywhere near that by hand. Luckily, we've found a basic pattern which allows you to ignore one half of the program. While this is certainly suboptimal, it's currently the only known way to program effectively in Stack Cats.

So in this answer, the template of said pattern is this (there's some variability in how it's executed):

[<(...)*(...)>]

When the program starts, the stack tape looks like this (for input 4, say):

 4 
... -1 ...
 0
 ^

The [ moves the top of the stack to the left (and the tape head along) - we call this "pushing". And the < moves the tape head alone. So after the first two commands, we've got this situation:

... 4 -1 ...
 0 0 0
 ^

Now the (...) is a loop which can be used quite easily as a conditional: the loop is entered and left only when the top of the current stack is positive. Since, it's currently zero, we skip the entire first half of the program. Now the centre command is *. This is simply XOR 1, i.e. it toggles the least significant bit of the top of the stack, and in this case turns the 0 into a 1:

... 1 4 -1 ...
 0 0 0
 ^

Now we encounter the mirror image of the (...). This time the top of the stack is positive and we do enter the code. Before we look into what goes on inside the parentheses, let me explain how we'll wrap up at the end: we want to ensure that at the end of this block, we have the tape head on a positive value again (so that the loop terminates after a single iteration and is used simply as a linear conditional), that the stack to the right holds the output and that the stack right of that holds a -1. If that's the case, we do leave the loop, > moves onto the output value and ] pushes it onto the -1 so we have a clean stack for output.

That's that. Now inside the parentheses we can do whatever we want to check the primality as long as we ensure that we set things up as described in the previous paragraph at the end (which can easily done with some pushing and tape head moving). I first tried solving the problem with Wilson's theorem but ended up well over 100 bytes, because the squared factorial computation is actually quite expensive in Stack Cats (at least I haven't found a short way). So I went with trial division instead and that indeed turned out much simpler. Let's look at the first linear bit:

>:^]

You've already seen two of those commands. In addition, : swaps the top two values of the current stack and ^ XORs the second value into the top value. This makes :^ a common pattern to duplicate a value on an empty stack (we pull a zero on top of the value and then turn the zero into 0 XOR x = x). So after this, section our tape looks like this:

 4 
... 1 4 -1 ...
 0 0 0
 ^

The trial division algorithm I've implemented doesn't work for input 1, so we should skip the code in that case. We can easily map 1 to 0 and everything else to positive values with *, so here's how we do that:

*(*...)

That is we turn 1 into 0, skip a big part of the code if we get indeed 0, but inside we immediately undo the * so that we get our input value back. We just need to make sure again that we end on a positive value at the end of the parentheses so that they don't start looping. Inside the conditional, we move one stack right with the > and then start the main trial division loop:

{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}

Braces (as opposed to parentheses) define a different kind of loop: it's a do-while loop, meaning it always runs for at least one iteration. The other difference is the termination condition: when entering the loop Stack Cat remembers the top value of the current stack (0 in our case). The loop will then run until this same value is seen again at the end of an iteration. This is convenient for us: in each iteration we simply compute the remainder of the next potential divisor and move it onto this stack we're starting the loop on. When we find a divisor, the remainder is 0 and the loop stops. We will try divisors starting at n-1 and then decrement them down to 1. That means a) we know this will terminate when we reach 1 at the latest and b) we can then determine whether the number is prime or not by inspecting the last divisor we tried (if it's 1, it's a prime, otherwise it isn't).

Let's get to it. There's a short linear section at the beginning:

<-!<:^>[:

You know what most of those things do by now. The new commands are - and !. Stack Cats does not have increment or decrement operators. However it has - (negation, i.e. multiply by -1) and ! (bitwise NOT, i.e. multiply by -1 and decrement). These can be combined into either an increment, !-, or decrement -!. So we decrement the copy of n on top of the -1, then make another copy of n on the stack to the left, then fetch the new trial divisor and put it beneath n. So on the first iteration, we get this:

 4 
 3 
... 1 4 -1 ...
 0 0 0
 ^

On further iterations, the 3 will replaced with the next test divisor and so on (whereas the two copies of n will always be the same value at this point).

((-<)<(<!-)>>-_)

This is the modulo computation. Since loops terminate on positive values, the idea is to start from -n and repeatedly add the trial divisor d to it until we get a positive value. Once we do, we subtract the result from d and this gives us the remainder. The tricky bit here is that we can't just have put a -n on top of the stack and start a loop that adds d: if the top of the stack is negative, the loop won't be entered. Such are the limitations of a reversible programming language.

So to circumvent this issue, we do start with n on top of the stack, but negate it only on the first iteration. Again, that sounds simpler than it turns out to be...

(-<)

When the top of the stack is positive (i.e. only on the first iteration), we negate it with -. However, we can't just do (-) because then we wouldn't be leaving the loop until - was applied twice. So we move one cell left with < because we know there's a positive value there (the 1). Okay, so now we've reliably negated n on the first iteration. But we have a new problem: the tape head is now in a different position on the first iteration than in every other one. We need to consolidate this before we move on. The next < moves the tape head left. The situation on the first iteration:

 -4 
 3 
... 1 4 -1 ...
 0 0 0 0
 ^

And on the second iteration (remember we've added d once into -n now):

 -1 
 3 
... 1 4 -1 ...
 0 0 0
 ^

The next conditional merges these paths again:

(<!-)

On the first iteration the tape head points at a zero, so this is skipped entirely. On further iterations, the tape head points at a one though, so we do execute this, move to the left and increment the cell there. Since we know the cell starts from zero, it will now always be positive so we can leave the loop. This ensures we always end up two stack left of the main stack and can now move back with >>. Then at the end of the modulo loop we do -_. You already know -. _ is to subtraction what ^ is to XOR: if the top of the stack is a and the value underneath is b it replaces a with b-a. Since we first negated a though, -_ replaces a with b+a, thereby adding d into our running total.

After the loop ends (we've reached a positive) value, the tape looks like this:

 2 
 3 
... 1 1 4 -1 ...
 0 0 0 0
 ^

The left-most value could be any positive number. In fact, it's the number of iterations minus one. There's another short linear bit now:

_<<]>:]<]]

Like I said earlier we need to subtract the result from d to obtain the actual remainder (3-2 = 1 = 4 % 3), so we just do _ once more. Next, we need to clean up the stack that we've been incrementing on the left: when we try the next divisor, it needs to be zero again, for the first iteration to work. So we move there and push that positive value onto the other helper stack with <<] and then move back onto our operational stack with another >. We pull up d with : and push it back onto the -1 with ] and then we move the remainder onto our conditional stack with <]]. That's the end of the trial division loop: this continues until we get a zero remainder, in which case the stack to the left contains n's greatest divisor (other than n).

After the loop ends, there's just *< before we join paths with the input 1 again. The * simply turns the zero into a 1, which we'll need in a bit, and then we move to the divisor with < (so that we're on the same stack as for input 1).

At this point it helps to compare three different kinds of inputs. First, the special case n = 1 where we haven't done any of that trial division stuff:

 0 
... 1 1 -1 ...
 0 0 0
 ^

Then, our previous example n = 4, a composite number:

 2 
 1 2 1 
... 1 4 -1 1 ...
 0 0 0 0
 ^

And finally, n = 3, a prime number:

 3 
 1 1 1 
... 1 3 -1 1 ...
 0 0 0 0
 ^

So for prime numbers, we have a 1 on this stack, and for composite numbers we either have a 0 or a positive number greater than 2. We turn this situation into the 0 or 1 we need with the following final piece of code:

]*(:)*=<*

] just pushes this value to the right. Then * is used to simplify the conditional situation greatly: by toggling the least significant bit, we turn 1 (prime) into 0, 0 (composite) into the positive value 1, and all other positive values will still remain positive. Now we just need to distinguish between 0 and positive. That's where we use another (:). If the top of the stack is 0 (and the input was a prime), this is simply skipped. But if the top of the stack is positive (and the input was a composite number) this swaps it with the 1, so that we now have 0 for composite and 1 for primes - only two distinct values. Of course, they are the opposite of what we want to output, but that is easily fixed with another *.

Now all that's left is to restore the pattern of stacks expected by our surrounding framework: tape head on a positive value, result on top of the stack to the right, and a single -1 on the stack right of that. This is what =<* is for. = swaps the tops of the two adjacent stacks, thereby moving the -1 to the right of the result, e.g. for input 4 again:

 2 0 
 1 3 
... 1 4 1 -1 ...
 0 0 0 0 0
 ^

Then we just move left with < and turn that zero into a one with *. And that's that.