Cops and Robbers: Redacted Primality (Robbers' Thread)

Question

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.

Answer 1

brainfuck, Jo King

>>>>>+>,[>++++++[-<-------->]<+>,]<[-[█<█<]++++++++++<]>[-]>>██[>█>>█>]+[<]<<[<]>█<<+>>[>]█>[>]█+[<]<<[<]>-█>]>>[->]<[-[[<]<]++++++++++<]>[-]>[<█]>]>[>]<[[█]<]<<<<<[<]<<██>>[>]<█[->+<]<█>>[>]<[-[[<]<]++++++++++<]>███>[<<]>[[[>]>████[<]<[-[[<]<]++++++++++<]>[-]>[█<]>]>[>]<[[-]>+[>]<-<[<]<]+<<<<<[<]>[[>]+[[>]>]>[>]>[-<+>]<[<]<[>+[<]>>-<<<<<[[<]<]>>███████>[[█]>]<]<[[<]<]<[█]>]>>>[[>]<->>]]>[[>]>]<<[[[█]<]<]<<<[█]<<█>>>[>]█[-[[<]<]++++++++++<]>>[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]>[>]+[------->++<]>++.++.---------.++++.--------.
>>>>>+>,[>++++++[-<-------->]<+>,]<[-[[<]<]++++++++++<]>[-]>>[[[>]>>[>]+[<]<<[<]>[<<+>>[>]>>[>]<+[<]<<[<]>-]>]>>[->]<[-[[<]<]++++++++++<]>[-]>[<<]>]>[>]<[[-]<]<<<<<[<]<<[>>>[>]<[[->+<]<]>>[>]<[-[[<]<]++++++++++<]>[-]>[<<]>[[[>]>[>]+[<]<[-[[<]<]++++++++++<]>[-]>[<<]>]>[>]<[[-]>+[>]<-<[<]<]+<<<<<[<]>[[>]+[[>]>]>[>]>[-<+>]<[<]<[>+[<]>>-<<<<<[[<]<]>>[[-]+>]>[[>]>]<]<[[<]<]<[<]>]>>>[[>]<->>]]>[[>]>]<<[[[-]<]<]<<<[<]<<]>>>[>]<[-[[<]<]++++++++++<]>>[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]>[>]+[------->++<]>++.++.---------.++++.--------.

Try it online!

This implements the sieve of Eratosthenes.

The initial >>>>>+>,[>++++++[-<-------->]<+>,] 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 +> 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 <[-[[<]<]++++++++++<]>[-]>. 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 [<<]>, 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:

>[                      until the number reaches zero:
  [                     for each digit:
    [>]>>[>]+[<]<<[<]>  create a placeholder for the next copy
    [                   while the original value of the digit is nonzero:
      <<+               add 1 to copy two cells left (to keep one copy)
      >>[>]>>[>]<+      go to new copy and increment that cell
      [<]<<[<]>-        go back to original digit and decrement
    ]                   (this is effectively the same as [<+>>+<-] but with the cells at variable locations)
  >]                    next digit
  >>[->]                cancel the placeholder 1s that were used for the new copy
  <[-[[<]<]++++++++++<]>[-]>[<<]> decrement
]
>[>]<[[-]<]      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. <<<<<[<]<< 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:

[>>>[>]<[[->+<]<]>>[>]<[-[[<]<]++++++++++<]>[-]>[<<]>

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

[[[>]>[>]+[<]<[-[[<]<]++++++++++<]>[-]>[<<]>]

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:

>[>]<[[-]>+[>]<-<[<]<]+

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 <<<<<[<]> 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.

[
  [>]+             mark the current decimal number
  [[>]>]           move to end of decimal part of tape
  >[>]             move to 0 in middle of unary "clock"
  >[-<+>]          move the following 1 to the left if possible
  <[<]<            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):
    >+[<]>>-       reset to original position
    <<<<<[[<]<]>>  go to number that was just marked
    [[-]+>]        replace digits with 0s (cell value 1)
    >[[>]>]<       go back to where we would be without this conditional
  ]
  <[[<]<]<[<]>     return to first unmarked number
]

The [[-]+>] 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 >>>[[>]<->>]] removes the markers placed on the tape and gets us to the end of the tape again. After that >[[>]>]<<[[[-]<]<] removes either the unary clock or, if this entire segment was skipped, the leftover 10s. The loop is set to its starting condition with <<<[<]<<].

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

>>>[>]<[-[[<]<]++++++++++<]>>                      do the check
[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]      conditionally print "not "
>[>]+[------->++<]>++.++.---------.++++.--------.  unconditionally print "prime"

Fortunately, the actual output was not redacted at all.

Answer 2

Wolfram Language (Mathematica)

Cracks this answer.

f[x_]:=(p=ToString@Boole@PrimeQ@x;StringMatchQ[p&@@Infinity,RegularExpression@"(\
\n{}\b+, )?1"])

Try it online!

Answer 3

Brain-Flak, MegaTom

(({████){██[████)█>(({}))<>}<>{}███{}((██({}))█████{}]██)({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})██[██()██(()█[()]██{}██}{}<>{})
(({})<>){([[]]{})<>(({}))<>}<>{}{}{{}(([]({}))[({}[{}])])({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})}([][()])((){[()](<{}>)}{}<>{})

Try it online!

This program performs trial divisions from n-2 down to 1, then outputs 1 if and only if this terminated with the factor 1.

Answer 4

8086 DOS COM by Joshua

xxd representation, because of encodings and null bytes and other scary stuffs:

00000000: 31c0 b90a 0031 dbbe 8100 ac3c 0d74 3c3c  1....1.....<.t<<
00000010: 2075 f7ac 3c0d 7410 2c30 7c2f 3c09 7f2b   u..<.t.,0|/<..+
00000020: 93f7 e193 01c3 ebeb 83fb 027c 19c6 0653  ...........|...S
00000030: 0159 b902 0039 d974 1289 d831 d2f7 f109  .Y...9.t...1....
00000040: d274 0341 ebef c606 5301 4eb4 09ba 5301  .t.A....S.N...S.
00000050: cd21 c341 0d0a 24                        .!.A..$

First disassembled the cop manually, then assembled using yasm. Some bytes have been corrupted by the conerter Joshua used, but I've just treated them like redacted bytes. I'm 99.72% certain about their actual content. It shouldn't take long to fix it if I'm wrong, though. Enjoy:

; A COM file is just a 16-bit flat binary
; loaded at 0x100 in some segment by DOS

org 0x100
bits 16

; Unsurprisingly, we start by converting
; the commandline string to a number. During
; the conversion, SI is a pointer to the
; string, CX is the base, and BX holds the
; partial result
parse_input:
; We'll read the input character by character
; into AL, but we need the resulting digit as
; a 16-bit number. Therefore, initialise AX to
; zero.
    xor ax, ax
    mov cx, 10
    xor bx, bx
; When a DOS program is loaded, it's preceded
; in memory by the Program Segment Prefix,
; which holds the commandline arguments at
; offset 0x81, terminated by a carriage return
    mov si, 0x81

.skip_prog_name:
; Load a character and move the pointer
    lodsb
; If we find the terminator here, the program
; was not given any arguments.
    cmp al, 13
    je finish

    cmp al, ' '
    jne .skip_prog_name

.input_loop:
    lodsb
    cmp al, 13
    je got_input

; If the ASCII value of the character is less
; than the one of '0', error out. Adjust the
; value in AL so that it holds the digit
; itself. This exploits the fact that the
; comparison instruction is just a subtraction
; that throws away the actual result.
    sub al, '0'
    jl finish

; If we have a value larger than 9, this
; character wasn't a digit.
    cmp al, 9
    jg finish

; Multiply the intermediate result by 10 and
; add the new digit to it.

    xchg ax, bx
    mul cx
    xchg ax, bx
    add bx, ax
    jmp .input_loop

got_input:
; The loop below would go haywire when given a
; zero or a one, so make them a special case.
    cmp bx, 2
    jl composite

; Patch the output string to say that it's
; prime
    mov byte[outstr], 'Y'

; BX = number being checked
; CX = loop counter, potential divisor of BX
    mov cx, 2

.loop:
; If CX = BX, we looked everywhere and couldn't
; find a divisor, therefore the number is prime
    cmp cx, bx
    je finish

; DIV takes DX:AX as a 32-bit number for the
; dividend. We don't want nor need the extra
; precision, so we set DX to 0.
    mov ax, bx
    xor dx, dx
    div cx

; DX now contains the remainder. To check if
; it's 0, we perform some noop operation, that
; happens to set the flags appropriately. AND
; and OR are commonly used for this purpose.
; Because of what's presumably a bug in the
; encoder used by Joshua, I do not yet know
; which for certain. However, I can make an
; educated guess. All other instances of the
; bug happened with a codepoint below 32.
; Moreover, no other bytes from that range
; occur in the code. Because an AND would be
; encoded as an exclamation mark, while OR -
; - as a tab, I am highly confident that Joshua
; used an OR.
    or dx, dx
    jz composite

; Increment the counter and loop again!
    inc cx
    jmp .loop

composite:
    mov byte[outstr], 'N'

finish:
    mov ah, 9
    mov dx, outstr
    int 0x21
    ret

outstr:
    db 'A', 13, 10, '$'

Answer 5

Jelly

Cracks this answer.

25██26█966836897364918299█0█1█65849159233270█02█837903312854349029387313█ị██v

250126,9668368973649182994001,658491592332700020837903312854349029387313ṖịØJv

Try it online!

---

Explanation:

Looking at ị and v, I think of building a list of numbers, ịndex it into some list and evaluate it.

The "trivial" way of checking primality in Jelly is ÆP, so (if it can cracks the submission):

• The list to be indexed to must contains Æ and P.
• The list of indices must be congruent modulo 256 with [14, 81].

So... the list at the start of the program congruent to [14, 81, 49] mod 256 (TIO) and Ṗ pops the last element.

Answer 6

sh + coreutils

Cracks this answer.

e█ec█s█ █c "██████WyAkKHNoIC1jICJg█WNobyBabUZqZEc5eWZIUnlJQ2█2SnlBblhHNG5m██JoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K█b█se6███d`"

exec sh -c "`echo WyAkKHNoIC1jICJgZWNobyBabUZqZEc5eWZIUnlJQ2M2SnlBblhHNG5mSFJoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K|base64 -d`"

No Try it online! this time because of some issues. However you can use jdoodle.

Returns by exit code. 0 (success) for prime, 1 (error) for composite.

The actual command executed is

factor|tr ':' '\n'|tail +2|wc -w

How to crack

1. Look at the code, recognize Base64.
2. Learn how to use base64 command.
3. Know that + is a valid base64 character.
4. Try to decode.
5. Apply the wrapper sh -c "`echo ...|base64 -d`" back to the original program.
6. Generate nested base64 from commands.

Answer 7

Octave, 86 bytes, Stewie Griffin.

@(x)eval([(str2num(cell2mat([cellstr(reshape('0█1███1█0█0█00',████))])')█'█')','(x)'])
@(x)eval([(str2num(cell2mat([cellstr(reshape('04141113040800',2,[]))])')+'e')','(x)'])

Try it online!

This was a fun one! I struggled with this for a good couple of days.

The first clue was recognizing eval([...,'(x)']) as a construction creating a call to the isprime function, as concatenation of ints and char will implicitly convert the array to char, so the ... needed to be either isprime or an array that had the ASCII values of isprime, [105, 115, 112, 114, 105, 109, 101].

The rest of it was just slogging through documentation to figure out that reshape can take one unknown dimension with [], although I suppose I could have done reshape(...,2, 7) at the same byte count.

Using +'e' (101) instead of +'d' (100) was a nice touch that threw me for another few minutes until I noticed the last digits (unobfuscated) were 00 rather than 01, and with that it was easy.

Answer 8

JavaScript

x=>{if(x<4)return(!0);for(y=x>>>Math.log10(p=████;--y-1;(p=x/y%1)████if(██&&(███))break████return(███)}
x=>{if(x<4)return(!0);for(y=x>>>Math.log10(p=2-1);--y-1;(p=x/y%1)){;;if(!p&&(1<2))break;;;}return(!!p)}

Try it online!

I somehow doubt this is exactly what you had in mind, but it works.

Answer 9

><>, Esolanging fruit

:1@v>~~:?1n;█$-1<█?=2:}*{█@:$@:

to

:1@v>~~:?1n;
$-1</?=2:}*{%@:$@:

Try it online!

Clever use of redacting a newline confused me for a bit. Doesn't seem to work for 1 or 2 though.

Answer 10

Java (OpenJDK 8), Magic Octopus Urn

class X{public static void main(String[]args){System.out.println(new String(████████[Integer.parseInt(args[0])]).matches("█████████████")?███);}}
class X{public static void main(String[]args){System.out.println(new String(new char[Integer.parseInt(args[0])]).matches(".?|(..+?)\\1+")?0:1);}}

Try it online!

The code is taken from RosettaCode and explained on SO.

Answer 11

Python 3, 44 bytes, osuka_

p=lambda x,i=2:i>=x or(x%i and p(x,i+1))or 0

Try it online!

Does not work when x<2. The or 0 can be replaced with >0{2 spaces} or even 4 spaces

For the x<2 problem, since i>=x must be put at the front (otherwise there will be an infinite loop), and the i>=x returns true immediately when x<2, so I think that's no fix with that.

Answer 12

M, dylnan

ÆPø“;;“»VOḣ2S⁵++3Ọ;”Pv

This probably wasn't the intended solution.

Try it online!

How it works

ÆP is the built-in primality test.

ø beings a new, niladic chain. Since the previous return value (the result of ÆP) goes out of scope, this prints it implicitly.

“;;“» evaluates to the list of strings ["< Aalst" ""], and V tries to eval them. s tries to split its argument into chunks of length 0, which causes the M interpreter to crash, suppressing further output.

Answer 13

Pyth, Mr. Xcoder

q]tQ #aQ{*MyP

Answer 14

Python 3, user71546

import random
def f(z):
 if z<4:return z>>1
 d,s,n,e,c=~-z,0,z,0,50
 while not d&1:d//=2;s+=1
 while n>0:n//=2;e+=1
 random.seed()
 while c>0:
  a=0
  while a<2or a>z-1:
   a,b=0,e
   while b>0:a=a*2+random.randint(0,1);b-=1
  x,r=pow(a,d,z),~-s
  if ~-x and x!=~-z:
   while r>0:
    x,r=pow(x,2,z),~-r
    if not ~-x:return 0
    elif x==~-z:break
   else:return 0
  c-=1
 else:return 1

Try it online!