Cops and Rabbers: Redacted Primality (Thread rabusiów)

9

To wątek złodziei. Wątek gliniarzy jest tutaj .

Wyzwanie polega na pobraniu nieprzetartego materiału z wątku gliniarzy i próbie znalezienia oryginalnego niezreagowanego programu. Skomentuj przesłanie gliniarza, gdy złamiesz jego kod.

MD XF
źródło

Odpowiedzi:

6

pieprzenie mózgu , Jo King

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

Wypróbuj online!

To realizuje sito Eratostenesa.

Początkowa >>>>>+>,[>++++++[-<-------->]<+>,]wprowadza każdą cyfrę jako kod znakowy i odejmuje 47, aby umieścić ją w zakresie 1-10. Umożliwia to wartości komórki 0 oznaczenie odstępów między liczbami. +>Blisko początku tego rozdziału sił liczba powinna wynosić co najmniej dwie cyfry, które będą ważne wkrótce.

Następnie, i jedną z pierwszych rzeczy, które wymyśliłem, jest sekcja <[-[[<]<]++++++++++<]>[-]>. Pojawia się to kilkakrotnie w kodzie, każdy z innym wzorcem redakcji, ale nietrudno było zgadnąć, że wszystkie te wystąpienia były prawdopodobnie tym samym kodem. Ten kod wymaga trzech zer po lewej stronie liczby dziesiętnej na taśmie, a jego efektem jest zmniejszenie liczby. Ostatnia iteracja pętli umieści wartość 10 dwie komórki po lewej stronie liczby, ale [-]wyczyści ją.

Jeśli liczba dziesiętna wynosiła 0, nie jest tworzone żadne dodatkowe 10, a komórka zerowana przez [-]jest najbardziej znaczącą cyfrą. Głowica taśmy znajduje się wtedy na drugiej najbardziej znaczącej cyfrze (dlatego potrzebne są co najmniej dwie cyfry). Po większości przypadków tego fragmentu kodu następuje natychmiast [<<]>, co umieszcza głowę na niezerowej komórce w normalnych warunkach i komórce zerowej, jeśli pierwotna liczba dziesiętna wynosiła zero. Wygląda na to, że w tym programie dziesiętna reprezentacja n-1jest używana do oznaczenia n, tak że 0przechwytywanie do jest wychwytywane zamiast zmniejszania do -1.

Następna część umieszcza na taśmie liczby od n-1 (n) do 0 (1):

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

Teraz wszystkie te liczby znajdują się na taśmie, oddzielając je dwoma zerowymi komórkami. <<<<<[<]<<umieszcza nas w ostatniej komórce przedostatniego numeru na taśmie, czyli tam, gdzie będziemy w każdej iteracji pętli. Pętla kończy się, gdy wszystkie liczby oprócz oryginału zostaną obsłużone.

Na początku pętli przesuwamy bieżącą liczbę (ostatnią wciąż na taśmie) o jedną komórkę w prawo, aby mieć miejsce na zmniejszenie, a następnie kontynuujemy i zmniejszamy:

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

Jeśli to zmniejszenie się nie wyczerpało, przystępujemy do konwersji liczby na unary:

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

Pamiętaj, że ten wycięty ma niezamknięty [. W rezultacie reszta tej pętli jest pomijana, jeśli liczba wynosiła 0 (co oznacza 1). Po przejściu na jedność usuwamy pozostałe 10s, przeciągając z nami jednoargumentację w lewo:

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

Dopiero teraz zauważyłem, że to piszę, ale +na końcu tego fragmentu oddzielony jest od jednostkowej reprezentacji pojedynczym 0. Jest to również część jedności: sekwencja 1011...11będzie reprezentować 0 mod k. Poniżej <<<<<[<]>umieszczamy nas na początku numeru k+1, rozpoczynając nową pętlę.

Wewnętrzna pętla tutaj „zaznacza” każdą liczbę na taśmie cyfrą 1 bezpośrednio w komórce i wykorzystuje jednoargumentową reprezentację jako zegar do ustalenia, które liczby są wielokrotnościami 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
]

Ta [[-]+>]sekcja była ostatnią częścią, którą wymyśliłem. Wcześniej zakładałem, że program robi tylko podziały próbne, ale nie mogłem zobaczyć, gdzie wykorzystano wynik.

Ta pętla kończy dwie komórki na lewo od skrajnie lewej cyfry i >>>[[>]<->>]]usuwa markery umieszczone na taśmie i ponownie prowadzi nas do końca taśmy. Następnie >[[>]>]<<[[[-]<]<]usuwa jeden zegar lub, jeśli cały segment został pominięty, pozostałe 10s. Pętla jest ustawiona w stan początkowy za pomocą <<<[<]<<].

Po tym czytam tylko, czy numer wejściowy został zastąpiony przez 1 w dowolnym momencie:

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

Na szczęście rzeczywista produkcja nie została w ogóle zredagowana.

Nitrodon
źródło
„Noc jest długa, która nigdy nie znajduje dnia”. Czy wciąż jest dziś wieczorem? : P
Stewie Griffin
@StewieGriffin Nie byłem w stanie tego zrobić tej nocy, a potem to po prostu wpadło mi do głowy. Dzięki za przypomnienie.
Nitrodon
Nie sądzę, żebym mógł wyjaśnić mój własny kod tak dobrze, jak tutaj. Bardzo dobra robota.
Jo King
5

Wolfram Language (Mathematica)

Łamie tę odpowiedź .

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

Wypróbuj online!

użytkownik202729
źródło
Nie trzeba przewijać, aby odczytać kod :)
user202729
Miły! Zupełnie różni się od zamierzonego rozwiązania, więc jeszcze tego nie ujawnię.
Pavel
@Pavel Co z tym ? Czy nadal „zasadniczo to samo”?
user202729,
Oto podpowiedź: ta duża kropelka nie zawiera żadnej Boolenie PrimeQ.
Pavel
5

Brain-Flak, MegaTom

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

Wypróbuj online!

Ten program wykonuje próbne podziały od n-2 do 1, a następnie wyprowadza 1 wtedy i tylko wtedy, gdy zakończy się to współczynnikiem 1.

Nitrodon
źródło
4

8086 DOS COM Joshua

xxd reprezentacja, z powodu kodowania i pustych bajtów i innych przerażających rzeczy:

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

Najpierw zdemontowałem gliniarza ręcznie, a następnie zmontowano za pomocą yasm. Niektóre bajty zostały uszkodzone przez konwerter Joshua, ale właśnie potraktowałem je jak zredagowane bajty. Jestem 99,72% pewien ich rzeczywistej zawartości. Naprawdę nie powinno to zająć dużo czasu, jeśli się mylę. Cieszyć się:

; 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
źródło
Jedyną różnicą między mną było bx < 2wykończenie, a nie kompozyt. FYI uszkodzenie było spowodowane pierwotnym użyciem X jako postaci maski i niepoprawnym naprawieniem wszystkiego po przełączeniu na █.
Joshua
@Joshua Na początku też tam użyłem wykończenia, ale potem przypomniałem sobie, że wymagana jest poprawna obsługa 1. O korupcji - to jeden ze scenariuszy, jakie sobie wyobrażałem
NieDzejkob
3

Galareta

Łamie odpowiedź.

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

Wypróbuj online!


Wyjaśnienie:

Patrząc na i vmyślę o zbudowaniu listy liczb, dodaj ją do jakiejś listy i oceń.

„Trywialny” sposób sprawdzania pierwotności w galaretce jest ÆPtaki, że (jeśli może złamać przesłanie):

  • Lista do indeksowania musi zawierać Æi P.
  • Lista indeksów musi być zgodna 256z modulo [14, 81].

Więc ... lista na początku programu przystająca do [14, 81, 49]mod 256 ( TIO ) i wyskakuje ostatni element.

użytkownik202729
źródło
3

sh + coreutils

Łamie tę odpowiedź .

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

Nie Wypróbuj online! tym razem z powodu niektórych problemów . Możesz jednak użyć jdoodle .

Zwraca kod zakończenia. 0(sukces) dla liczby pierwszej, 1(błąd) dla kompozytu.

Rzeczywiste wykonane polecenie to

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

Jak złamać

  1. Spójrz na kod, rozpoznaj Base64.
  2. Dowiedz się, jak korzystać z base64polecenia.
  3. Wiedz, że +jest to prawidłowy znak base64.
  4. Spróbuj dekodować .
  5. Ponownie zastosuj opakowanie sh -c "`echo ...|base64 -d`"do oryginalnego programu .
  6. Wygeneruj zagnieżdżony base64 z poleceń .
użytkownik202729
źródło
Prawidłowa metoda Okazało się, że „niektóre problemy” nie są znane wszystkim maszynom tail +n. Kiedy próbowałem twojego pęknięcia na maszynie w pracy, narzekało na to. Zdemaskowałeś poprawny kod, więc ... :(
Joshua
3

Oktawa , 86 bajtów, 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)'])

Wypróbuj online!

To była świetna zabawa! Walczyłem z tym przez dobre kilka dni.

Pierwszą wskazówką był uznając eval([...,'(x)'])jako konstrukcja tworząc połączenie do isprimefunkcji, jak konkatenacji intsi charniejawnie przekonwertować tablicę do char, więc ...musiał być isprimealbo tablicą, która miała wartości ASCII isprime, [105, 115, 112, 114, 105, 109, 101].

Reszta po prostu przeglądała dokumentację, aby dowiedzieć się, że reshapemożna wziąć jeden nieznany wymiar [], chociaż przypuszczam, że mógłbym to zrobić reshape(...,2, 7)przy tej samej liczbie bajtów.

Używanie +'e'(101) zamiast +'d'(100) było miłym akcentem, który rzucił mnie na kolejne kilka minut, aż zauważyłem, że ostatnie cyfry (nieobjawione) były 00raczej 01, a przy tym było łatwe.

Giuseppe
źródło
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)}

Wypróbuj online!

W jakiś sposób wątpię, aby dokładnie to miałeś na myśli, ale działa.

MegaTom
źródło
2

> <> , Esolanging fruit

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

do

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

Wypróbuj online!

Sprytne użycie redagowania nowej linii nieco mnie zdezorientowało. Wydaje się jednak, że nie działa dla 1 lub 2.

Jo King
źródło
Miły. Każda z ^, v, /, lub \ dla drugiego wykroju mogło tam pracowali. Teraz żałuję, że nie *pokryłem /.
Esolanging Fruit
2

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

Wypróbuj online!

Kod pochodzi z RosettaCode i wyjaśniono na SO .

ovs
źródło
Nie miałem pojęcia, że ​​to popularne hah! Długo miałem to w tylnej kieszeni. Szczerze to ukradłem z pliku narzędziowego, który miałem odtąd jak ... Jezu ... 2014?
Magic Octopus Urn
2

Python 3 , 44 bajty, osuka_

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

Wypróbuj online!

Nie działa, gdy x <2. or 0Można zastąpić >0{2 spaces}lub nawet 4 obowiązuje

W przypadku problemu x <2, ponieważ i>=xnależy go umieścić z przodu (w przeciwnym razie pojawi się nieskończona pętla), a i>=xzwroty będą prawdziwe natychmiast, gdy x <2, więc myślę, że to nie jest poprawne.

Shieru Asakoto
źródło
Jak się okazuje, mój kod też nie działa z x <2. Ups (Prawdopodobnie właśnie przetestowałem to z zakresem (2, ...), ponieważ jestem głupi)
osuka_
2

M, dylnan

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

Prawdopodobnie nie było to zamierzone rozwiązanie.

Wypróbuj online!

Jak to działa

ÆP jest wbudowanym testem pierwszeństwa.

øjest nowym, niladycznym łańcuchem. Ponieważ poprzednia zwracana wartość (wynik ÆP) wykracza poza zakres, powoduje to jej niejawne wydrukowanie.

“;;“»sprawdza listę ciągów ["< Aalst" ""]i Vpróbuje je ewaluować . spróbuje podzielić swój argument na części o długości 0 , co powoduje awarię interpretera M, co tłumi dalsze dane wyjściowe.

Dennis
źródło
Nie zamierzone rozwiązanie, ale fajne. Wkrótce zaktualizuje post do cracked. Gdybym powiedział słowo „zoo”, czy doprowadziłoby cię to do innego możliwego rozwiązania?
dylnan
Hm, to brzmi jak złożona nieskończoność.
Dennis
1

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

Wypróbuj online!

Nitrodon
źródło