Policiais e ladrões: primazia redigida (fio de ladrão)

9

Este é o fio dos ladrões. A discussão dos policiais está aqui .

Seu desafio é pegar um envio sem rachaduras do tópico da polícia e tentar encontrar o programa original sem reduções. Por favor, comente a submissão do policial quando você tiver decifrado o código.

MD XF
fonte

Respostas:

6

Jo King , filho do cérebro

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

Experimente online!

Isso implementa a peneira de Eratóstenes.

A >>>>>+>,[>++++++[-<-------->]<+>,]entrada inicial de cada dígito como um código de caractere e subtrai 47 para colocá-lo no intervalo de 1 a 10. Isso permite que um valor de célula de 0 denote espaçamento entre números. No +>início desta seção, o número é de pelo menos dois dígitos, o que será importante em breve.

A seguir, e uma das primeiras coisas que descobri, é a seção <[-[[<]<]++++++++++<]>[-]>. Isso aparece várias vezes no código, cada um com diferentes padrões de redação, mas não foi difícil adivinhar que todas essas instâncias provavelmente eram do mesmo código. Esse código requer três zeros à esquerda do número decimal na fita e seu efeito é diminuir o número. A última iteração do loop colocará o valor 10 duas células restantes do número, mas o [-]limpará.

Se o número decimal for 0, não serão criados 10 estranhos e a célula zerada por [-]é o dígito mais significativo. O cabeçote da fita fica no segundo dígito mais significativo (razão pela qual são necessários pelo menos dois dígitos). A maioria das instâncias desse snippet é seguida imediatamente por [<<]>, que coloca o cabeçalho em uma célula diferente de zero em condições normais e uma célula zero se o número decimal original for zero. Parece que, neste programa, a representação decimal de n-1é usada para denotar n, de modo que decrementar para 0é capturado em vez de decrementar para -1.

A próxima parte coloca os números de n-1 (n) até 0 (1) na fita:

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

Agora, esses números estão todos na fita com duas células zero separando-os. <<<<<[<]<<nos coloca na célula final do penúltimo número da fita, que é onde estaremos em todas as iterações do loop. O loop termina quando todos os números, exceto o original, foram tratados.

No início do loop, movemos o número atual (o último ainda na fita) uma célula para a direita para ter espaço para diminuir e, em seguida, prosseguimos e diminuímos:

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

Se esse decréscimo não for insuficiente, procederemos à conversão do número para unário:

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

Observe que este recorte tem um não fechado [. Como resultado, o restante desse loop será ignorado se o número for 0 (representando 1). Depois de converter para unário, limpamos os 10s restantes, arrastando a representação unária conosco para a esquerda:

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

Eu não notei até agora escrever isso, mas o +final deste trecho é separado da representação unária por um único 0. É também uma parte da representação unária: a sequência 1011...11representará 0 mod k. O seguinte <<<<<[<]>nos coloca no início do número k+1, iniciando um novo loop.

O loop interno aqui "marca" cada número na fita com um 1 na célula imediatamente à direita e usa a representação unária como um relógio para determinar de quais números são múltiplos 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
]

A [[-]+>]seção nessa foi a última parte que eu descobri. Antes disso, presumi que o programa estava apenas fazendo divisões de teste, mas não conseguia ver onde o resultado foi usado.

Esse loop termina duas células à esquerda do número da extrema esquerda e >>>[[>]<->>]]remove os marcadores colocados na fita e nos leva ao final da fita novamente. Depois disso, você >[[>]>]<<[[[-]<]<]remove o relógio unário ou, se todo esse segmento foi pulado, os 10s restantes. O loop é definido para sua condição inicial com <<<[<]<<].

Depois disso, basta ler se o número de entrada foi substituído por 1 a qualquer momento:

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

Felizmente, a produção real não foi alterada.

Nitrodon
fonte
"A noite é longa e nunca encontra o dia." Ainda está hoje à noite? : P
Stewie Griffin
@StewieGriffin Eu não consegui fazer isso naquela noite, e então isso simplesmente me escapou. Obrigado pela lembrança.
Nitrodon
Eu não acho que eu poderia ter explicado meu próprio código, assim como você fez aqui. Muito bom trabalho.
Jo rei
5

Língua Wolfram (Mathematica)

Quebra esta resposta .

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

Experimente online!

user202729
fonte
Sem rolagem necessário ler o código :)
user202729
Agradável! Muito diferente da solução pretendida, então ainda não vou revelar isso.
Pavel
@ Pavel E quanto a isso ? Ou ainda "fundamentalmente o mesmo"?
user202729
Aqui vai uma dica: que grande blob contém nem Boolenão PrimeQ.
Pavel
5

Explosão cerebral, MegaTom

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

Experimente online!

Este programa executa divisões de teste de n-2 até 1 e, em seguida, gera 1 se e somente se isso terminar com o fator 1.

Nitrodon
fonte
4

8086 DOS COM por Joshua

xxd representação, devido a codificações e bytes nulos e outras coisas assustadoras:

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

Primeiro desmontei o policial manualmente, depois montei usando yasm. Alguns bytes foram corrompidos pelo conversador usado por Joshua, mas eu os tratei como bytes redigidos. Tenho 99,72% de certeza sobre o conteúdo real. Não demorará muito para corrigi-lo, se eu estiver errado. Desfrutar:

; 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
fonte
A única diferença entre as minhas foi bx < 2terminar em vez de compor. Para sua informação, a corrupção foi causada originalmente por usar X como o caractere de máscara e não consertar tudo corretamente ao mudar para █.
197 Joshua Joshua
@ Josué Também usei o acabamento lá também, mas lembrei que o manuseio correto de 1 é necessário. Sobre a corrupção - que é um dos cenários que eu imaginava
NieDzejkob
3

Geléia

Quebra esta resposta.

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

Experimente online!


Explicação:

Olhando e v, penso em criar uma lista de números, coloque-a em alguma lista e avalie-a.

A maneira "trivial" de verificar a primalidade no Jelly é ÆP, então (se ele pode quebrar a submissão):

  • A lista a ser indexada deve conter Æe P.
  • A lista de índices deve ser modulo congruente 256com [14, 81].

Então ... a lista no início do programa é congruente ao [14, 81, 49]mod 256 ( TIO ) e exibe o último elemento.

user202729
fonte
3

sh + coreutils

Quebra esta resposta .

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

Não Experimente online! desta vez por causa de alguns problemas . No entanto, você pode usar o jdoodle .

Retorna pelo código de saída. 0(sucesso) para prime, 1(erro) para composto.

O comando real executado é

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

Como quebrar

  1. Veja o código, reconheça o Base64.
  2. Aprenda a usar o base64comando.
  3. Saiba que esse +é um caractere base64 válido.
  4. Tente decodificar .
  5. Aplique o invólucro de sh -c "`echo ...|base64 -d`"volta ao programa original .
  6. Gere base64 aninhado a partir de comandos .
user202729
fonte
Método correto. "Alguns problemas" acabam sendo nem todas as máquinas conhecem tail +n. Quando tentei a sua rachadura na máquina no trabalho, ela se queixou. Você desmascara o código correto para que ... :(
Joshua
3

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

Experimente online!

Essa foi engraçada! Eu lutei com isso por um bom par de dias.

A primeira pista foi reconhecer eval([...,'(x)'])como uma construção criando uma chamada para a isprimefunção, como concatenação de intse charvai converter implicitamente a matriz para char, de modo que o ...necessário para ser tanto isprimeou uma matriz que tinha os valores ASCII de isprime, [105, 115, 112, 114, 105, 109, 101].

O resto era apenas documentação lenta para descobrir que reshapepode levar uma dimensão desconhecida [], embora eu suponha que eu poderia ter feito reshape(...,2, 7)na mesma contagem de bytes.

Usar +'e'(101) em vez de +'d'(100) foi um toque agradável que me impressionou por mais alguns minutos, até que notei que os últimos dígitos (não ofuscados) eram 00mais do que 01, e com isso foi fácil.

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

Experimente online!

De alguma forma, duvido que isso seja exatamente o que você tinha em mente, mas funciona.

MegaTom
fonte
2

> <> , Esolanging frutas

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

para

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

Experimente online!

O uso inteligente de editar uma nova linha me confundiu um pouco. Não parece funcionar para 1 ou 2 embora.

Brincadeira
fonte
Agradável. Qualquer uma ^, v, /, ou \ para o segundo em branco poderia ter trabalhado lá. Agora eu gostaria de ter coberto o *lugar do /.
Esolanging Fruit 06/02
2

Java (OpenJDK 8) , urna de polvo mágico

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

Experimente online!

O código é retirado do RosettaCode e explicado no SO .

ovs
fonte
Não tinha idéia de que era tão popular hah! Tinha isso no meu bolso de trás por um longo tempo. Eu honestamente o roubei de um arquivo utilitário que eu tenho desde ... Caramba ... 2014?
Magic Octopus Urn
2

Python 3 , 44 bytes, osuka_

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

Experimente online!

Não funciona quando x <2. O or 0pode ser substituído por >0{2 spaces}ou até 4 espaços

Para o problema x <2, já que i>=xdeve ser colocado na frente (caso contrário, haverá um loop infinito), e os i>=xretornos serão verdadeiros imediatamente quando x <2, então acho que isso não é uma solução.

Shieru Asakoto
fonte
Portanto, meu código também não funciona com x <2. Opa (Eu provavelmente só testei com intervalo (2, ...), porque eu sou estúpido)
osuka_
2

M, dylnan

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

Esta provavelmente não foi a solução pretendida.

Experimente online!

Como funciona

ÆP é o teste de primalidade embutido.

øseres uma nova cadeia niládica. Como o valor de retorno anterior (o resultado de ÆP) fica fora do escopo, ele é impresso implicitamente.

“;;“»avalia a lista de strings ["< Aalst" ""]e Vtenta avaliá- las. stenta dividir seu argumento em pedaços de comprimento 0 , o que causa uma falha no interpretador M, suprimindo mais saídas.

Dennis
fonte
Solução não pretendida, mas agradável. Atualizará a postagem para rachada em breve. Se eu dissesse a palavra "zoológico", isso levaria você a outra solução possível?
dylnan
Hum, isso soa como infinito complexo.
Dennis
1

Python 3 , usuário71546

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

Experimente online!

Nitrodon
fonte