Berdasarkan pertanyaan Math.SE ini ; nomor yang disalin dari jawaban ini . Nomor awalnya dari video Numberphile , tentu saja.
Tugas Anda adalah untuk menghasilkan nomor utama 1350 digit berikut:
888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888111111111111111111111111888888111111111111111111111111888888111111811111111118111111888888111118811111111118811111888888111188811111111118881111888888111188811111111118881111888888111888811111111118888111888888111888881111111188888111888888111888888111111888888111888888111888888888888888888111888888111888888888888888888111888888111888888888888888888111888888811188888888888888881118888188811188888888888888881118881188881118888888888888811188881118888111888888888888111888811111888811118888888811118888111111188881111111111111188881111111118888111111111111888811111111111888811111111118888111111111111188881111111188881111111111111118888811118888811111111111111111888881188888111111111111111111118888888811111111111111111111111888888111111111111111111111111118811111111111111111111111111111111111111111111062100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Anda dapat menyertakan baris baru dalam output.
Aturan
- Ini adalah kolmogorov-kompleksitas , jadi tidak ada input.
- Program Anda harus berakhir dalam satu jam di komputer standar - jika sudah dekat, saya akan menggunakan program saya untuk pengujian. Jika program Anda berjalan lebih dari satu menit, atau tidak berakhir pada TIO, harap sertakan waktu di komputer Anda.
- Ini adalah kode-golf , jadi kode terpendek, dalam byte, menang.
code-golf
kolmogorov-complexity
primes
Stephen
sumber
sumber
Jawaban:
Jelly ,
7471696866 byteCobalah online!
Bagaimana itu bekerja
Literal tersebut
“©ạ-3ṗÇñ"ỤḍV8żṢ?ḤsMVE[,Ṃƭ"ḞÇsẇʂ(ụFsẠʂẆŀṣ’
menggantikan semua karakter dengan poin kode mereka di halaman kode Jelly dan menafsirkan hasilnya sebagai nomor (basis) 250-bijective, menghasilkan bilangan bulat berikut.Kemudian,
ḃ19
ubah angka ini menjadi basis bijektif 19, menghasilkan array digit berikut.Sekarang,
ĖŒṙ
sebutkan digit dan lakukan decoding run-length, menghasilkan array berikut.Kemudian,
ị⁾81
indeks ke string 81 , mengganti angka ganjil dengan karakter 8 , angka genap dengan karakter 1 . Setelah itu,s30
bagi hasil menjadi potongan-potongan dengan panjang 30. Menampilkan satu potongan per baris, hasilnya terlihat sebagai berikut.Sekarang,
m0
gabungkan array bongkahan dengan salinan dirinya yang terbalik. Setelah itu,Z
ritsleting hasilnya, transpos baris dan kolom.0
adalah nilad yang tidak dapat diparsing, sehingga hasil dari sebelumnya dicetak (tanpa jeda baris) dan nilai kembali diatur ke 0 .62
adalah nilad yang tidak dapat diparsing, sehingga hasil dari sebelum ( 0 ) dicetak dan nilai pengembalian diatur ke 62 .ȷ446
adalah nilad yang tidak dapat dipecahkan. 62 dicetak dan nilai kembali diatur ke 10 446 .Akhirnya,
‘
tambahkan hasilnya. Hasil akhir ( 10 446 +1 ) dicetak saat program selesai.sumber
[8, 1]
... Oh, itu pintar! Saya mencuri trik ini. Saya harap Anda tidak keberatan :))) dan kemudian ya tambahkan semua barang-barang aneh 06210..01. bagus :)SOGL V0.12 ,
81787573 byteCoba Di Sini!
Penjelasan:
sumber
Jelly , 136 byte
Cobalah online!
Penjelasan (angka disingkat)
-121 byte berkat Dennis yang menggunakan
“...’
literal alih-alih angka normalsumber
“...’
literal menyimpan banyak byte. tio.run/…0;6;2;1;
tampaknya sangat bertele-tele.Jelly ,
133 8473 byteCobalah online! (footer memformat angka desimal dengan dimensi yang menghasilkan lambang).
Bagaimana?
Bentuk jangka panjang yang disandikan dari format biner sisi kiri lambang
8
dan1
hingga baris sebelum yang mulai0621
tercermin dengan yang0621
ditambahkan dan kemudian dikalikan dengan 10 446 dan bertambah.sumber
Arang ,
10710498968779 byteCobalah online! Tautan ke kode verbose untuk penjelasan
sumber
Proton , 368 byte
Cobalah online!
sumber
Ruby , 180 byte
Cobalah online!
178 byte + 2 byte untuk
-Kn
(memaksa pengkodean ASCII.)43 sebagian besar karakter yang tidak dapat dicetak di antara kutipan pertama. Hexdump:
Bagaimana?
Semua orang melakukan pengkodean run length, jadi saya ingin mencoba sesuatu yang berbeda.
Versi "gambar" yang diformat dari prime dapat dipisahkan menjadi dua bagian - kotak 30x30 dari 8 dan 1, dan bagian kedua sebagian besar nol yang dapat dikodekan dengan keras. Berfokus pada bagian pertama, kami mengamati bahwa bagian tengahnya simetris, jadi jika kami dapat menghasilkan setengah bagian kiri maka kami hanya dapat mencetak setengah dari setiap baris dengan terbalik.
Setengah dari satu baris adalah 15 karakter. Jika kita mengganti angka 8 dengan nol, setiap baris dapat diartikan sebagai angka biner 15-bit. Mudahnya, sebagian besar jarak edit antara setiap baris berturut-turut kecil, jadi saya memutuskan untuk mengimplementasikan solusi saya dengan menyimpan baris pertama
s
(888888888888888
, yang hanya menjadi 0) dan menerapkan serangkaian operasi pembalikan bit padas
, mencetak hasilnya setiap kali .Karena setiap baris memiliki panjang 15 bit, saya menyandikan operasi ini sebagai digit heksadesimal - misalnya, jika operasinya adalah
b
(atau 11), maka kami membalik bit 11. Beberapa baris berbeda lebih dari satu bit, sehingga mereka memerlukan string heksadesimal digit. Kami memiliki satu bit tersisa (f
) sehingga kami dapat menggunakannya sebagai pembatas antara string ini, dan juga sebagai nilai "tidak melakukan apa-apa". Contoh di bawah ini (Anda dapat melihat baris ini di pos yang dirujuk dalam pertanyaan):Untuk menyatukan semua itu, kita akan menyandikan
0123456789ab
, lalu berpisah denganf
, tidak melakukan apa-apaf
, lalu5
. Ini berfungsi karena kita akan melakukan.split(?f)
nanti untuk mendapatkan setiap rangkaian operasi dengan baris, yang akan menghasilkan["0123456789ab", "", "5"]
, dan""
akan menjadi no-op.Perbedaan antara baris 3 dan 4 di atas sejauh ini merupakan suntingan terpanjang, dan jarak edit antara dua baris berturut-turut biasanya 0-2, jadi saya akan mengatakan bahwa pengkodean ini cukup murah, meskipun saya yakin itu bisa ditingkatkan.
Seluruh string yang dikodekan akhirnya menjadi
fff0123456789abff5f6f7ff8f4f3f012fff8bfef7af69df458cf01237bf6af59f48f237f16f045f3f12f0
(86 byte), yang akan mendapatkan seluruh grid 30x30. Tapi kita belum selesai ...Digit heksadesimal dapat diwakili oleh 4 bit (
b
->1100
, dll.) Itu berarti bahwa jika kita bersedia untuk mengkodekan string kita 4 bit sekaligus daripada menggunakan byte, kita dapat memotong panjang string menjadi dua. Jadi itulah yang saya lakukan - hexdump menunjukkan string yang diwakili dalam 43 byte. Setelah itu, tinggal menggunakan String # unpack dengan Ruby yang bagusH*
(diartikan sebagai hex string, high nibble first) untuk memperluas string 43-byte ke versi 86-byte yang kita kenal dan cintai, dan mengulangi setiap rangkaian operasi flipping bits - untuk string yang disimpans
dan operasi yangc
kami lakukans ^ 2**c.to_i(16)
untuk membalik bit yang sesuai.Setelah setiap set pengeditan selesai, kami pad biner yang dihasilkan menjadi 15 bit, alihkan semua kembali 0 ke 8, dan cetak hasilnya dan kebalikannya. Seperti disebutkan sebelumnya, bagian dari angka setelah kisi 30x30 dapat di-hardcode, jadi kami melakukannya
puts'0621'+?0*445+?1
.String yang disandikan akhir tidak memiliki kemungkinan untuk bekerja pada TIO, jadi versi TIO menggunakan escapes, yang masih berfungsi tetapi lebih lama.
sumber
Python 2 ,
760523329205196 byte-237 bytes terima kasih kepada Stephen. -124 bytes berkat Jonathan Frech.
Cobalah online!
sumber
8
dan1
dan menggabungkan621
621
. Terima kasih!CJam,
532412340231210209 byteCobalah secara Online
Pengkodean run-length diperluas dari basis 92 (Basis 250 menyebabkan karakter multibyte sehingga harus menyesuaikan). Juga,
4341089843357287864910309744850519376
diperluas dari basis 92 dan dikonversi ke biner. A 1 berarti run-length adalah dua digit, 0 berarti itu satu digit. Sebagai contoh, 4 digit pertama dari representasi biner adalah 1101 karena empat run pertama adalah[93,8],[24,1],[6,8],[24,1]
(93 8, 24 1, dll ...)sumber
JavaScript,
454450332207204 byte-4 byte terima kasih kepada Stephen. -125 byte berkat Shaggy dan Dom Hastings.
Ada banyak muatan yang tidak terpecahkan dalam jawaban ini, jadi inilah hexdump:
sumber
+'1'
karena sudah menjadiString
dan+'0621'
bisa+0+621
![...`]
membuat saya sangat marahJavaScript (ES6),
206205204203198197194 byteDatang dengan ini saat bekerja pada solusi i cri everytim , pikir itu cukup berbeda untuk menjamin posting itu sendiri.
Ini termasuk beban dari unsintables antara
]
dan,
karenanya ikuti tautan TIO di bawah ini untuk melihatnya dengan Unicode escapes (setiap urutan\u
diikuti dengan 4 digit dihitung sebagai 1 byte).Cobalah online
sumber
MATLAB / Oktaf ,
319318 byteIni adalah upaya pertama saya untuk tantangan ini. Masih agak besar dan mungkin ada cara yang lebih efisien untuk melakukannya, tapi saya pikir saya tetap akan mempostingnya karena metode ini lebih menarik daripada sekadar meng-zip.
Cobalah online!
Metode yang digunakan di sini adalah dengan menggunakan skema Run-Length-Encoding.
Kami mulai dengan nomor asli dan menghitung jumlah digit berturut-turut. Ini ditulis dalam hasil di bawah ini sebagai penghitungan diikuti secara langsung oleh digit (ruang dipisahkan untuk kejelasan).
Jika salah satu nilai lebih besar dari 95, kami memecahnya menjadi beberapa potongan 95 atau kurang - ini hanya terjadi untuk 445 0 yang sebaliknya menjadi empat set 95 0 dan satu set 65 0. Kami juga menghitung jumlah yang kurang dari 10 dengan 0 untuk membuat semua elemen panjang tiga karakter. Ini menghasilkan dengan ruang yang dihapus:
Kalau dipikir-pikir pada titik ini saya bisa melakukan langkah ini sebelum menggabungkan semuanya, tetapi bagaimana Anda hidup dan belajar. Kami melakukan sesuatu yang pintar yaitu mengambil hitungan untuk setiap grup (2 digit) dan kami menambahkan 31. Karena semuanya adalah <96, angka yang dihasilkan adalah nilai ASCII untuk karakter yang dapat dicetak (32 hingga 126). Memberi kami jumlah:
Setelah sedikit membentuk kembali di MATLAB untuk membuatnya lebih menguntungkan untuk decoding, dan kemudian juga melarikan diri
'
karakter dengan''
(jika tidak, MATLAB membagi string string di sana), kita dibiarkan dengan string pintar:Itu adalah akar kode. Dalam kode yang kemudian saya lakukan adalah membentuk kembali array menjadi string 2D dengan 128 pasang karakter. Untuk setiap pasangan, karakter pertama dikurangi 31, dan kemudian karakter kedua ditampilkan berulang kali.
Hasilnya adalah prime asli:
Suntingan:
sumber
05AB1E , 76 byte
Cobalah online!
Mencuri ini dari Dennis:
Melihatnya selalu bergantian antara 8 dan 1, jadi saya menghitung panjang setiap lari (Basis 20):
Bergabung bersama semuanya, dan mengubahnya menjadi basis-10 integer:
Dikompresi lebih jauh ke base-255:
Kemudian, setelah membuat bit terkompresi ... Kita hanya perlu memanipulasinya kembali ke aslinya ..
Hasil akhir:
sumber
C (gcc) , 277 byte
Saya mendapatkan perasaan bahwa string dapat dipersingkat entah bagaimana.
Cobalah online!
sumber
Perl 5 , 307 byte
Cobalah online!
sumber
Bubblegum , 88 byte
Cobalah online!
sumber
Ruby , 194 byte
Bagian atas adalah RLE-encoded, sisanya hanya hardcoded.
Cobalah online!
sumber
Kotlin , 339 byte
Cobalah online!
sumber
CJam (
10881 byte)Demo online
Dalam kasus pengkodean karakter borks di atas, ini adalah xxd-encoded:
Run awal 8s dan 1s dibagi menjadi hanya setengah kiri dan run-length dikodekan hanya sebagai panjang berjalan bergantian. Run lebih dari 24 dibagi menjadi run paling banyak 24, dipisahkan oleh run 0, sehingga panjangnya dapat di-base-25 di-encode dan kemudian base-256 di-encode untuk mengemasnya.
sumber
JavaScript (ES2017), 287 byte
Menggunakan pendekatan yang sedikit berbeda dengan jawaban @icrieverytim . -10 byte berkat saran @Shaggy untuk menggunakan
replace
alih-alihmatch
!sumber
/// , 260 byte
Cobalah online!
Tidak ada yang sangat menarik, hanya beberapa kompresi.
sumber
Mathematica, 192 byte
Lihat: http://reference.wolfram.com/language/ref/Compress.html
sumber
Python 2 ,
191190188 byteCobalah online!
Prinsipal yang sama dengan jawaban saya di sini
sumber