Policías y ladrones: Primalidad redactada (Hilo de ladrones)

9

Este es el hilo de los ladrones. El hilo de la policía está aquí .

Su desafío es tomar una presentación sin descifrar del hilo de la policía e intentar encontrar el programa original no editado. Comenta sobre el envío del policía cuando hayas descifrado su código.

MD XF
fuente

Respuestas:

6

brainfuck , Jo King

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

Pruébalo en línea!

Esto implementa el tamiz de Eratóstenes.

La entrada inicial >>>>>+>,[>++++++[-<-------->]<+>,]ingresa cada dígito como un código de caracteres y resta 47 para ponerlo en el rango 1-10. Esto permite que un valor de celda de 0 denote el espacio entre números. La +>cerca del comienzo de esta sección fuerzas que el número sea al menos dos dígitos, que será pronto importante.

A continuación, y una de las primeras cosas que descubrí, es la sección <[-[[<]<]++++++++++<]>[-]>. Esto aparece varias veces en el código, cada uno con diferentes patrones de redacción, pero no fue difícil adivinar que todas esas instancias eran probablemente el mismo código. Este código requiere tres ceros a la izquierda del número decimal en la cinta, y su efecto es disminuir el número. La última iteración del bucle pondrá el valor 10 dos celdas a la izquierda del número, pero lo [-]limpiará.

Si el número decimal era 0, no se crea un 10 extraño, y la celda puesta a cero [-]es el dígito más significativo. El cabezal de la cinta se encuentra en el segundo dígito más significativo (por lo que se necesitan al menos dos dígitos). La mayoría de las instancias de este fragmento son seguidas de inmediato [<<]>, lo que coloca la cabeza en una celda distinta de cero en condiciones normales y una celda cero si el número decimal original era cero. Parece que en este programa, la representación decimal de n-1se utiliza para denotar n, por lo que se reduce la disminución a en 0lugar de disminuir a -1.

La siguiente parte pone los números de n-1 (n) a 0 (1) en la cinta:

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

Ahora, estos números están todos en la cinta con dos celdas cero que los separan. <<<<<[<]<<nos coloca en la celda final del penúltimo número de la cinta, que es donde estaremos en cada iteración del bucle. El ciclo termina cuando se han manejado todos los números, excepto el original.

Al comienzo del ciclo, movemos el número actual (el último todavía en la cinta) una celda hacia la derecha para tener espacio para disminuir, y luego avanzamos y disminuimos:

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

Si este decremento no se desborda, procedemos a convertir el número a unario:

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

Tenga en cuenta que este recortado tiene un no cerrado [. Como resultado, el resto de este ciclo se omite si el número era 0 (que representa 1). Después de convertir a unario, limpiamos los 10 sobrantes, arrastrando la representación unaria con nosotros hacia la izquierda:

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

No me di cuenta hasta ahora de escribir esto, pero el +final de este fragmento está separado de la representación unaria por un solo 0. También es parte de la representación unaria: la secuencia 1011...11representará 0 mod k. Lo siguiente <<<<<[<]>nos pone al comienzo del número k+1, comenzando un nuevo ciclo.

El bucle interno aquí "marca" cada número en la cinta con un 1 en la celda inmediatamente a la derecha, y usa la representación unaria como un reloj para determinar qué números son múltiplos de 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
]

En [[-]+>]esa sección fue la última parte que descubrí. Antes de eso, asumí que el programa solo estaba haciendo divisiones de prueba, pero no podía ver dónde se usaba el resultado.

Este bucle termina dos celdas a la izquierda del número del extremo izquierdo, y >>>[[>]<->>]]elimina los marcadores colocados en la cinta y nos lleva al final de la cinta nuevamente. Después de eso, se >[[>]>]<<[[[-]<]<]elimina el reloj unario o, si se omitió todo este segmento, los 10 sobrantes. El bucle se establece en su condición inicial con <<<[<]<<].

Después de esto, solo se lee si el número de entrada se reemplazó por 1 en algún momento:

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

Afortunadamente, el resultado real no fue redactado en absoluto.

Nitrodon
fuente
"La noche es larga que nunca encuentra el día". ¿Todavía es esta noche? : P
Stewie Griffin
@StewieGriffin No pude hacerlo esa noche, y luego se me pasó por la cabeza. Gracias por el recordatorio.
Nitrodon
No creo que podría haber explicado mi propio código tan bien como lo hiciste aquí. Muy buen trabajo.
Jo King
5

Wolfram Language (Mathematica)

Rompe esta respuesta .

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

Pruébalo en línea!

usuario202729
fuente
No es necesario desplazarse para leer el código :)
user202729
¡Agradable! Muy diferente de la solución prevista, por lo que aún no lo revelaré.
Pavel
@Pavel ¿Qué hay de esto ? ¿O todavía "fundamentalmente igual"?
user202729
Aquí hay una pista: la gran bolsa contiene ni Booleno PrimeQ.
Pavel
5

Brain-Flak, MegaTom

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

Pruébalo en línea!

Este programa realiza divisiones de prueba desde n-2 hasta 1, luego genera 1 si y solo si esto terminó con el factor 1.

Nitrodon
fuente
4

8086 DOS COM por Joshua

xxd representación, debido a codificaciones y bytes nulos y otras cosas de miedo:

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..$

Primero desmontó el policía manualmente, luego lo ensambló usando yasm. Algunos bytes han sido corrompidos por el conerter Joshua utilizado, pero los he tratado como bytes redactados. Estoy 99.72% seguro de su contenido real. Sin embargo, no debería llevar mucho tiempo solucionarlo si me equivoco. Disfrutar:

; 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, '$'
NieDzejkob
fuente
La única diferencia entre la mía fue bx < 2terminar en lugar de compuesto. Para su información, la corrupción se debió originalmente a usar X como el personaje de la máscara y no arreglar todo correctamente al cambiar a █.
Joshua
@Joshua Solía ​​terminar allí al principio también, pero luego recordé que se requiere manejar 1 correctamente. Sobre la corrupción: ese es uno de los escenarios que imaginé
NieDzejkob
3

Jalea

Rompe esta respuesta.

25██26█966836897364918299█0█1█65849159233270█02█837903312854349029387313█ị██v
250126,9668368973649182994001,658491592332700020837903312854349029387313ṖịØJv

Pruébalo en línea!


Explicación:

Mirando y v, pienso en construir una lista de números, indexarla en alguna lista y evaluarla.

La forma "trivial" de verificar la primalidad en Jelly es ÆP, entonces (si puede descifrar el envío):

  • La lista a indexar debe contener Æy P.
  • La lista de índices debe ser un módulo congruente 256con [14, 81].

Entonces ... la lista al comienzo del programa congruente con el [14, 81, 49]mod 256 ( TIO ) y muestra el último elemento.

usuario202729
fuente
3

sh + coreutils

Rompe esta respuesta .

eecs c "██████WyAkKHNoIC1jICJg█WNobyBabUZqZEc5eWZIUnlJQ2█2SnlBblhHNG5m██JoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K█b█se6███d`"
exec sh -c "`echo WyAkKHNoIC1jICJgZWNobyBabUZqZEc5eWZIUnlJQ2M2SnlBblhHNG5mSFJoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K|base64 -d`"

No ¡ Pruébelo en línea! Esta vez debido a algunos problemas . Sin embargo, puedes usar jdoodle .

Devoluciones por código de salida. 0(éxito) para primo, 1(error) para compuesto.

El comando real ejecutado es

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

Cómo romper

  1. Mire el código, reconozca Base64.
  2. Aprende a usar el base64comando.
  3. Sepa que +es un carácter base64 válido.
  4. Intenta decodificar .
  5. Aplique el contenedor sh -c "`echo ...|base64 -d`"nuevamente al programa original .
  6. Generar base64 anidada a partir de comandos .
usuario202729
fuente
Método correcto Resulta que "algunos problemas" no son conocidos por todas las máquinas tail +n. Cuando probé tu crack en la máquina en el trabajo, se quejó de ello. Desenmascaraste el código correcto, así que ... :(
Joshua
3

Octava , 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)'])

Pruébalo en línea!

¡Esto fue divertido! Luché con esto por un buen par de días.

La primera pista se reconoce eval([...,'(x)'])como una construcción creación de una llamada a la isprimefunción, como concatenación de intsy charva a convertir implícitamente a la matriz char, por lo que la ...necesaria para ser isprimeo una matriz que tenía los valores ASCII de isprime, [105, 115, 112, 114, 105, 109, 101].

El resto fue solo revisar la documentación para descubrir que reshapepuede tomar una dimensión desconocida [], aunque supongo que podría haberlo hecho reshape(...,2, 7)con el mismo número de bytes.

Usar +'e'(101) en lugar de +'d'(100) fue un buen toque que me arrojó durante unos minutos más hasta que noté que los últimos dígitos (no ofuscados) estaban en 00lugar de 01, y con eso fue fácil.

Giuseppe
fuente
2

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)}

Pruébalo en línea!

De alguna manera dudo que esto sea exactamente lo que tenía en mente, pero funciona.

MegaTom
fuente
2

> <> , Fruta Esolanging

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

a

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

Pruébalo en línea!

El uso inteligente de redactar una nueva línea me confundió un poco. Sin embargo, no parece funcionar para 1 o 2.

Jo King
fuente
Agradable. Cualquiera de ^, v, /, o \ para el segundo blanco podría haber trabajado allí. Ahora desearía haber cubierto el en *lugar del /.
Esolanging Fruit
2

Java (OpenJDK 8) , Urna mágica de pulpo

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);}}

Pruébalo en línea!

El código se toma de RosettaCode y se explica en SO .

ovs
fuente
No tenía idea de que era tan popular ¡ja! Tenía esto en mi bolsillo trasero durante mucho tiempo. Honestamente lo robé de un archivo de utilidad que he tenido desde entonces como ... Dios ... 2014?
Urna mágica de pulpo
2

Python 3 , 44 bytes, osuka_

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

Pruébalo en línea!

No funciona cuando x <2. El or 0puede ser reemplazado con >0{2 spaces}o incluso 4 espacios

Para el problema x <2, ya que i>=xdebe colocarse al frente (de lo contrario, habrá un bucle infinito), y el i>=xresultado es verdadero inmediatamente cuando x <2, por lo que creo que eso no tiene solución.

Shieru Asakoto
fuente
Resulta que mi código tampoco funciona con x <2. Ups (Probablemente lo acabo de probar con rango (2, ...), porque soy estúpido)
osuka_
2

M, dylnan

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

Probablemente esta no sea la solución prevista.

Pruébalo en línea!

Cómo funciona

ÆP es la prueba de primalidad incorporada.

øSeres una nueva cadena niládica. Como el valor de retorno anterior (el resultado de ÆP) está fuera de alcance, esto lo imprime implícitamente.

“;;“»evalúa la lista de cadenas ["< Aalst" ""]e Vintenta evaluarlas. sintenta dividir su argumento en fragmentos de longitud 0 , lo que hace que el intérprete M se bloquee, suprimiendo la salida adicional.

Dennis
fuente
Solución no prevista pero agradable. Actualizará la publicación a crackeado pronto. Si dijera la palabra "zoológico", ¿eso te llevaría a otra posible solución?
dylnan
Hm, eso suena como un infinito complejo.
Dennis
1

Python 3 , usuario71546

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

Pruébalo en línea!

Nitrodon
fuente