Cops and Robbers: Redacted Primality (Robbers' Thread) This is the robbers' thread. The cops' thread is here.

Your challenge is to take an uncracked submission from the cops' thread and try to find the original unredacted program. Please comment on the cop's submission when you've cracked their code.
brainfuck, Jo King

&gt;&gt;&gt;&gt;&gt;+&gt;,[&gt;++++++[-&lt;--------&gt;]&lt;+&gt;,]&lt;[-[█&lt;█&lt;]++++++++++&lt;]&gt;[-]&gt;&gt;██[&gt;█&gt;&gt;█&gt;]+[&lt;]&lt;&lt;[&lt;]&gt;█&lt;&lt;+&gt;&gt;[&gt;]█&gt;[&gt;]█+[&lt;]&lt;&lt;[&lt;]&gt;-█&gt;]&gt;&gt;[-&gt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;[&lt;█]&gt;]&gt;[&gt;]&lt;[[█]&lt;]&lt;&lt;&lt;&lt;&lt;[&lt;]&lt;&lt;██&gt;&gt;[&gt;]&lt;█[-&gt;+&lt;]&lt;█&gt;&gt;[&gt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;███&gt;[&lt;&lt;]&gt;[[[&gt;]&gt;████[&lt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;[█&lt;]&gt;]&gt;[&gt;]&lt;[[-]&gt;+[&gt;]&lt;-&lt;[&lt;]&lt;]+&lt;&lt;&lt;&lt;&lt;[&lt;]&gt;[[&gt;]+[[&gt;]&gt;]&gt;[&gt;]&gt;[-&lt;+&gt;]&lt;[&lt;]&lt;[&gt;+[&lt;]&gt;&gt;-&lt;&lt;&lt;&lt;&lt;[[&lt;]&lt;]&gt;&gt;███████&gt;[[█]&gt;]&lt;]&lt;[[&lt;]&lt;]&lt;[█]&gt;]&gt;&gt;&gt;[[&gt;]&lt;-&gt;&gt;]]&gt;[[&gt;]&gt;]&lt;&lt;[[[█]&lt;]&lt;]&lt;&lt;&lt;[█]&lt;&lt;█&gt;&gt;&gt;[&gt;]█[-[[&lt;]&lt;]++++++++++&lt;]&gt;&gt;[[&gt;]+[-------&gt;++&lt;]&gt;.+.+++++.[----&gt;+&lt;]&gt;+++.&gt;&gt;]&gt;[&gt;]+[-------&gt;++&lt;]&gt;++.++.---------.++++.--------.
&gt;&gt;&gt;&gt;&gt;+&gt;,[&gt;++++++[-&lt;--------&gt;]&lt;+&gt;,]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;&gt;[[[&gt;]&gt;&gt;[&gt;]+[&lt;]&lt;&lt;[&lt;]&gt;[&lt;&lt;+&gt;&gt;[&gt;]&gt;&gt;[&gt;]&lt;+[&lt;]&lt;&lt;[&lt;]&gt;-]&gt;]&gt;&gt;[-&gt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;[&lt;&lt;]&gt;]&gt;[&gt;]&lt;[[-]&lt;]&lt;&lt;&lt;&lt;&lt;[&lt;]&lt;&lt;[&gt;&gt;&gt;[&gt;]&lt;[[-&gt;+&lt;]&lt;]&gt;&gt;[&gt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;[&lt;&lt;]&gt;[[[&gt;]&gt;[&gt;]+[&lt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;[&lt;&lt;]&gt;]&gt;[&gt;]&lt;[[-]&gt;+[&gt;]&lt;-&lt;[&lt;]&lt;]+&lt;&lt;&lt;&lt;&lt;[&lt;]&gt;[[&gt;]+[[&gt;]&gt;]&gt;[&gt;]&gt;[-&lt;+&gt;]&lt;[&lt;]&lt;[&gt;+[&lt;]&gt;&gt;-&lt;&lt;&lt;&lt;&lt;[[&lt;]&lt;]&gt;&gt;[[-]+&gt;]&gt;[[&gt;]&gt;]&lt;]&lt;[[&lt;]&lt;]&lt;[&lt;]&gt;]&gt;&gt;&gt;[[&gt;]&lt;-&gt;&gt;]]&gt;[[&gt;]&gt;]&lt;&lt;[[[-]&lt;]&lt;]&lt;&lt;&lt;[&lt;]&lt;&lt;]&gt;&gt;&gt;[&gt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;&gt;[[&gt;]+[-------&gt;++&lt;]&gt;.+.+++++.[----&gt;+&lt;]&gt;+++.&gt;&gt;]&gt;[&gt;]+[-------&gt;++&lt;]&gt;++.++.---------.++++.--------.


Try it online!

This implements the sieve of Eratosthenes.

The initial &gt;&gt;&gt;&gt;&gt;+&gt;,[&gt;++++++[-&lt;--------&gt;]&lt;+&gt;,] inputs each digit as an character code and subtracts 47 to put it in the range 1-10.  This allows a cell value of 0 to denote spacing between numbers.  The +&gt; near the beginning of this section forces the number to be at least two digits, which will be important soon.

Next, and one of the first things I figured out, is the section &lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;.  This appears several times in the code, each with different patterns of redaction, but it was not hard to guess that all of those instances were probably the same code.  This code requires three zeros to the left of the decimal number on the tape, and its effect is to decrement the number.  The last iteration of the loop will put the value 10 two cells left of the number, but the [-] cleans it up.

If the decimal number was 0, there is no extraneous 10 created, and the cell zeroed by [-] is the most significant digit.  The tape head is then at the second-most significant digit (which is why at least two digits are necessary).  Most instances of this snippet are immediately followed by [&lt;&lt;]&gt;, which places the head on a nonzero cell in normal conditions and a zero cell if the original decimal number was zero.  It seems that in this program, the decimal representation of n-1 is used to denote n, so that decrementing to 0 is caught instead of decrementing to -1.

The next part puts the numbers from n-1 (n) down to 0 (1) on the tape:

&gt;[                      until the number reaches zero:
  [                     for each digit:
    [&gt;]&gt;&gt;[&gt;]+[&lt;]&lt;&lt;[&lt;]&gt;  create a placeholder for the next copy
    [                   while the original value of the digit is nonzero:
      &lt;&lt;+               add 1 to copy two cells left (to keep one copy)
      &gt;&gt;[&gt;]&gt;&gt;[&gt;]&lt;+      go to new copy and increment that cell
      [&lt;]&lt;&lt;[&lt;]&gt;-        go back to original digit and decrement
    ]                   (this is effectively the same as [&lt;+&gt;&gt;+&lt;-] but with the cells at variable locations)
  &gt;]                    next digit
  &gt;&gt;[-&gt;]                cancel the placeholder 1s that were used for the new copy
  &lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;[&lt;&lt;]&gt; decrement
]
&gt;[&gt;]&lt;[[-]&lt;]      clean up the trash 10s on the tape while ending at a known location relative to the last number


Now, these numbers are all on the tape with two zero cells separating them.  &lt;&lt;&lt;&lt;&lt;[&lt;]&lt;&lt; puts us at the final cell of the penultimate number on the tape, which is where we will be in every iteration of the loop.  The loop terminates when all numbers except the original have been handled.

At the start of the loop, we move the current number (last one still on the tape) one cell right to have room to decrement, and then go ahead and decrement:

[&gt;&gt;&gt;[&gt;]&lt;[[-&gt;+&lt;]&lt;]&gt;&gt;[&gt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;[&lt;&lt;]&gt;


If this decrement didn't underflow, we proceed to convert the number to unary:

[[[&gt;]&gt;[&gt;]+[&lt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;[-]&gt;[&lt;&lt;]&gt;]


Note that this snipped has an unclosed [.  As a result, the rest of this loop is skipped if the number was 0 (representing 1).  After converting to unary, we clear out the leftover 10s, dragging the unary representation with us to the left:

&gt;[&gt;]&lt;[[-]&gt;+[&gt;]&lt;-&lt;[&lt;]&lt;]+


I didn't notice until just now writing this, but the + at the end of this snippet is separated from the unary representation by a single 0.  It is also a part of the unary representation: the sequence 1011...11 will represent 0 mod k.  The following &lt;&lt;&lt;&lt;&lt;[&lt;]&gt; puts us at the beginning of the number k+1, starting a new loop.

The inner loop here "marks" every number on the tape with a 1 on the cell immediately right, and uses the unary representation as a clock to determine which numbers are multiples of k.

[
  [&gt;]+             mark the current decimal number
  [[&gt;]&gt;]           move to end of decimal part of tape
  &gt;[&gt;]             move to 0 in middle of unary "clock"
  &gt;[-&lt;+&gt;]          move the following 1 to the left if possible
  &lt;[&lt;]&lt;            if a 1 was moved this will bring us back to a zero before the start of this "clock";
                   otherwise the looped move command doesn't move us at all and we are at the final 1
  [                if there was no gap (happens every kth iteration):
    &gt;+[&lt;]&gt;&gt;-       reset to original position
    &lt;&lt;&lt;&lt;&lt;[[&lt;]&lt;]&gt;&gt;  go to number that was just marked
    [[-]+&gt;]        replace digits with 0s (cell value 1)
    &gt;[[&gt;]&gt;]&lt;       go back to where we would be without this conditional
  ]
  &lt;[[&lt;]&lt;]&lt;[&lt;]&gt;     return to first unmarked number
]


The [[-]+&gt;] in that section was the last part I figured out.  Before that, I assumed the program was just doing trial divisions, but I couldn't see where the result was used.

This loop ends two cells left of the far left number, and &gt;&gt;&gt;[[&gt;]&lt;-&gt;&gt;]] removes the markers placed on the tape and gets us to the end of the tape again.  After that &gt;[[&gt;]&gt;]&lt;&lt;[[[-]&lt;]&lt;] removes either the unary clock or, if this entire segment was skipped, the leftover 10s.  The loop is set to its starting condition with &lt;&lt;&lt;[&lt;]&lt;&lt;].

After this is just reading whether the input number was replaced by 1 at any point:

&gt;&gt;&gt;[&gt;]&lt;[-[[&lt;]&lt;]++++++++++&lt;]&gt;&gt;                      do the check
[[&gt;]+[-------&gt;++&lt;]&gt;.+.+++++.[----&gt;+&lt;]&gt;+++.&gt;&gt;]      conditionally print "not "
&gt;[&gt;]+[-------&gt;++&lt;]&gt;++.++.---------.++++.--------.  unconditionally print "prime"


Fortunately, the actual output was not redacted at all.