Polisi dan Perampok: Primality Redacted (Robbers 'Thread)

9

Ini adalah utas perampok. Utas polisi ada di sini .

Tantangan Anda adalah mengambil kiriman yang tidak terputus dari utas polisi dan mencoba menemukan program yang tidak dikerjakan yang asli. Berikan komentar tentang pengiriman polisi ketika Anda telah memecahkan kode mereka.

MD XF
sumber

Jawaban:

6

brainfuck , Jo King

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

Cobalah online!

Ini menerapkan saringan Eratosthenes.

>>>>>+>,[>++++++[-<-------->]<+>,]Input awal setiap digit sebagai kode karakter dan kurangi 47 untuk memasukkannya dalam rentang 1-10. Ini memungkinkan nilai sel 0 untuk menunjukkan jarak antar angka. The +>dekat awal bagian pasukan ini jumlahnya menjadi setidaknya dua digit, yang akan segera penting.

Berikutnya, dan salah satu hal pertama yang saya ketahui, adalah bagian <[-[[<]<]++++++++++<]>[-]>. Ini muncul beberapa kali dalam kode, masing-masing dengan pola redaksi yang berbeda, tetapi tidak sulit untuk menebak bahwa semua contoh itu mungkin kode yang sama. Kode ini membutuhkan tiga angka nol di sebelah kiri angka desimal pada kaset, dan efeknya adalah mengurangi angka tersebut. Iterasi terakhir dari loop akan menempatkan nilai 10 dua sel tersisa dari angka, tetapi [-]membersihkannya.

Jika angka desimal adalah 0, tidak ada 10 asing yang dibuat, dan sel yang [-]diberi nol oleh adalah angka yang paling signifikan. Kepala pita kemudian berada pada digit kedua yang paling signifikan (itulah sebabnya diperlukan setidaknya dua digit). Sebagian besar cuplikan ini segera diikuti oleh [<<]>, yang menempatkan kepala pada sel bukan nol dalam kondisi normal dan sel nol jika angka desimal aslinya nol. Tampaknya dalam program ini, representasi desimal n-1digunakan untuk menunjukkan n, sehingga decrementing ke 0ditangkap alih-alih decrementing ke -1.

Bagian selanjutnya menempatkan angka-angka dari n-1 (n) ke bawah ke 0 (1) pada kaset:

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

Sekarang, angka-angka ini semuanya ada di pita dengan dua sel nol memisahkan mereka. <<<<<[<]<<menempatkan kita di sel terakhir dari nomor kedua dari belakang pada pita, yang merupakan tempat kita akan berada di setiap iterasi dari loop. Loop berakhir ketika semua nomor kecuali yang asli telah ditangani.

Di awal perulangan, kami memindahkan angka saat ini (yang terakhir masih di pita) satu sel yang tepat untuk memiliki ruang untuk pengurangan, dan kemudian melanjutkan dan mengurangi:

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

Jika penurunan ini tidak underflow, kami melanjutkan untuk mengonversi nomor menjadi unary:

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

Perhatikan bahwa potongan ini tidak tertutup [. Akibatnya, sisa dari loop ini dilewati jika jumlahnya 0 (mewakili 1). Setelah mengonversi ke unary, kami menghapus 10-an sisa, menyeret representasi unary dengan kami ke kiri:

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

Saya tidak melihat sampai saat ini menulis ini, tetapi +pada akhir cuplikan ini dipisahkan dari representasi unary oleh satu 0. Ini juga merupakan bagian dari representasi unary: urutannya 1011...11akan mewakili 0 mod k. Berikut ini <<<<<[<]>menempatkan kami di awal angka k+1, memulai loop baru.

Lingkaran dalam di sini "menandai" setiap angka pada pita dengan angka 1 pada sel segera di sebelah kanan, dan menggunakan representasi unary sebagai jam untuk menentukan angka mana yang merupakan kelipatan 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
]

Di [[-]+>]bagian itu adalah bagian terakhir yang saya temukan. Sebelumnya, saya berasumsi program itu hanya melakukan pembagian percobaan, tetapi saya tidak bisa melihat di mana hasilnya digunakan.

Lingkaran ini mengakhiri dua sel di kiri nomor paling kiri, dan >>>[[>]<->>]]menghilangkan penanda yang ditempatkan pada pita dan membawa kita ke ujung pita lagi. Setelah itu >[[>]>]<<[[[-]<]<]menghapus jam unary atau, jika seluruh segmen ini dilewati, sisa 10-an. Loop diatur ke kondisi awal dengan <<<[<]<<].

Setelah ini baru dibaca apakah nomor input diganti dengan 1 di titik mana pun:

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

Untungnya, output yang sebenarnya tidak dihapus sama sekali.

Nitrodon
sumber
"Malam itu panjang dan tidak pernah menemukan hari itu." Apakah masih malam ini? : P
Stewie Griffin
@StewieGriffin Saya tidak bisa melakukannya malam itu, dan kemudian itu hilang begitu saja. Terima kasih atas pengingatnya.
Nitrodon
Saya tidak berpikir saya bisa menjelaskan kode saya sendiri seperti yang Anda lakukan di sini. Kerja yang sangat bagus.
Jo King
5

Bahasa Wolfram (Mathematica)

Retak jawaban ini .

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

Cobalah online!

pengguna202729
sumber
Tidak perlu menggulir untuk membaca kode :)
user202729
Bagus! Cukup berbeda dari solusi yang dimaksudkan, jadi saya belum akan mengungkapkannya.
Pavel
@Pavel Bagaimana dengan ini ? Atau masih "pada dasarnya sama"?
user202729
Berikut ini petunjuk: yang gumpalan besar berisi tidak Booletidak PrimeQ.
Pavel
5

Brain-Flak, MegaTom

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

Cobalah online!

Program ini melakukan pembagian percobaan dari n-2 ke 1, kemudian menghasilkan 1 jika dan hanya jika ini diakhiri dengan faktor 1.

Nitrodon
sumber
4

8086 DOS COM oleh Joshua

xxd representasi, karena penyandian dan byte nol dan hal-hal menakutkan lainnya:

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

Pertama membongkar polisi secara manual, kemudian dirakit menggunakan yasm. Beberapa byte telah rusak oleh Joshua conerter yang digunakan, tetapi saya baru saja memperlakukan mereka seperti byte yang dihapus. Saya 99,72% yakin tentang konten mereka yang sebenarnya. Seharusnya tidak butuh waktu lama untuk memperbaikinya jika saya salah. Nikmati:

; 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
sumber
Satu-satunya perbedaan antara tambang saya adalah bx < 2selesai daripada komposit. FYI korupsi itu karena awalnya menggunakan X sebagai karakter topeng dan tidak memperbaiki semuanya dengan benar ketika beralih ke █.
Joshua
@ Yosua saya menggunakan selesai di sana pada awalnya juga, tapi kemudian saya ingat bahwa penanganan 1 dengan benar diperlukan. Tentang korupsi - itulah salah satu skenario yang saya bayangkan
NieDzejkob
3

Jeli

Retak jawaban ini .

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

Cobalah online!


Penjelasan:

Melihat dan v, saya berpikir untuk membangun daftar angka, memasukkannya ke dalam daftar dan mengevaluasinya.

Cara "sepele" untuk memeriksa keaslian di Jelly adalah ÆP, jadi (jika itu dapat memecahkan kiriman):

  • Daftar yang akan diindeks harus berisi Ædan P.
  • Daftar indeks harus kongruen 256dengan modulo [14, 81].

Jadi ... daftar di awal program kongruen ke [14, 81, 49]mod 256 ( TIO ) dan muncul elemen terakhir.

pengguna202729
sumber
3

sh + coreutils

Retak jawaban ini .

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

Tidak, Coba online! kali ini karena beberapa masalah . Namun Anda dapat menggunakan jdoodle .

Kembali dengan kode keluar. 0(sukses) untuk prima, 1(kesalahan) untuk komposit.

Perintah aktual yang dieksekusi adalah

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

Bagaimana cara memecahkannya

  1. Lihatlah kodenya, kenali Base64.
  2. Pelajari cara menggunakan base64perintah.
  3. Ketahuilah bahwa itu +adalah karakter base64 yang valid.
  4. Cobalah untuk memecahkan kode .
  5. Terapkan pembungkus sh -c "`echo ...|base64 -d`"kembali ke program aslinya .
  6. Hasilkan base64 bersarang dari perintah .
pengguna202729
sumber
Metode yang benar. "Beberapa masalah" ternyata tidak semua mesin ketahui tail +n. Ketika saya mencoba celah Anda pada mesin di tempat kerja itu mengeluhkannya. Anda membuka kedok kode yang benar sehingga ... :(
Joshua
3

Oktaf , 86 byte, 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)'])

Cobalah online!

Ini menyenangkan! Saya berjuang dengan ini selama beberapa hari.

Petunjuk pertama mengakui eval([...,'(x)'])sebagai konstruksi menciptakan panggilan ke isprimefungsi, sebagai gabungan dari intsdan charsecara implisit akan mengkonversi array untuk char, sehingga ...dibutuhkan untuk menjadi baik isprimeatau array yang memiliki nilai-nilai ASCII dari isprime, [105, 115, 112, 114, 105, 109, 101].

Sisanya hanya melalui dokumentasi untuk mencari tahu yang reshapedapat mengambil satu dimensi yang tidak diketahui [], meskipun saya kira saya bisa melakukannya reshape(...,2, 7)pada jumlah byte yang sama.

Menggunakan +'e'(101) alih-alih +'d'(100) adalah sentuhan yang bagus yang melemparkan saya selama beberapa menit sampai saya melihat angka terakhir (tidak dikontrol) 00lebih daripada 01, dan dengan itu mudah.

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

Cobalah online!

Entah bagaimana saya ragu ini persis apa yang ada dalam pikiran Anda, tetapi itu berhasil.

MegaTom
sumber
2

> <> , Buah esolanging

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

untuk

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

Cobalah online!

Penggunaan cerdas untuk membuat ulang baris baru sedikit membingungkan saya. Tampaknya tidak berfungsi untuk 1 atau 2.

Jo King
sumber
Bagus. Salah ^, v, /, atau \ untuk kosong kedua bisa bekerja di sana. Saya sekarang berharap saya telah menutupi *bukan /.
Buah Esolanging
2

Java (OpenJDK 8) , Magic Gurita Guci

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

Cobalah online!

Kode diambil dari RosettaCode dan dijelaskan pada SO .

ovs
sumber
Tidak tahu bahwa itu populer hah! Punya ini di saku belakang saya untuk waktu yang lama. Jujur saya mencurinya dari file utilitas saya sudah seperti ... Astaga ... 2014?
Magic Gurita Guci
2

Python 3 , 44 byte, osuka_

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

Cobalah online!

Tidak berfungsi saat x <2. The or 0bisa diganti dengan >0{2 spaces}atau bahkan 4 spasi

Untuk masalah x <2, karena i>=xharus diletakkan di bagian depan (jika tidak akan ada loop yang tak terbatas), dan i>=xhasilnya akan langsung benar ketika x <2, jadi saya pikir itu tidak bisa diperbaiki dengan itu.

Shieru Asakoto
sumber
Jadi ternyata, kode saya juga tidak berfungsi dengan x <2. Ups. (Saya mungkin hanya mengujinya dengan rentang (2, ...), karena saya bodoh)
osuka_
2

M, dylnan

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

Ini mungkin bukan solusi yang dimaksudkan.

Cobalah online!

Bagaimana itu bekerja

ÆP adalah tes primality bawaan.

ømenjadi rantai niladik baru. Karena nilai pengembalian sebelumnya (hasil ÆP) keluar dari ruang lingkup, ini mencetaknya secara implisit.

“;;“»mengevaluasi ke daftar string ["< Aalst" ""], dan Vmencoba untuk mengevaluasi mereka. smencoba untuk memecah argumennya menjadi potongan-potongan dengan panjang 0 , yang menyebabkan penerjemah M crash, menekan output lebih lanjut.

Dennis
sumber
Bukan solusi yang dimaksudkan tetapi bagus. Akan memperbarui pos untuk segera retak. Jika saya mengatakan kata "kebun binatang" apakah itu akan membawa Anda ke solusi lain yang mungkin?
dylnan
Hm, itu terdengar seperti infinity yang kompleks.
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

Cobalah online!

Nitrodon
sumber