Saya memiliki angka tertentu dalam pikiran, tetapi ini adalah bagian dari tantangan yang saya lakukan, dan saya tidak ingin orang melakukan (semua) pekerjaan untuk saya.
Berikut adalah angka yang memiliki angka yang sama, tetapi dikocok:
5713167915926167134578399473447223554460066674314639815391281352328315313091488448321843
8892917486601064146636679920143691047671721184150386045081532202458651561779976236919751
5521854951599379666116678853267398393892536121049731949764192014193648608210652358947001
6332620900065461061195026191178967128001712341637591690941978871368243245270800684616029
6679555942849366434586090627998161441134473428845367022486230724219981658438108844675033
4461550796750244527407413996606134735852639191026103378962082622204359677030054592798927
4145951979523473408718011778751084514127053772614511042703365596651912104541233491744530
87457854312602843967491787086250478422477028164189
Angka tersebut memiliki 666 digit (desimal). Karena saya menggunakan Python, bilangan bulat (atau secara teknis rindu) secara otomatis bignum.
Saya memiliki 255 karakter untuk digunakan, dan saya perlu menjelaskan nomor yang sama. Deskripsi ini dimaksudkan untuk dijalankan melalui eval () untuk menghasilkan nomor asli.
Strategi apa yang harus saya perhatikan?
code-golf
kolmogorov-complexity
tips
python
compression
Christian Sonne
sumber
sumber
Jawaban:
Pengodean Basis
Teknik standar untuk mengompresi angka adalah mengekspresikannya dalam basis besar dan menyandikan digit sebagai karakter. Misalnya, jika Anda menyandikan angka dalam basis 256, itu hanya akan memiliki 277 digit:
Atau dinyatakan sebagai string
(Ditambah beberapa karakter yang tidak patut dicetak yang dilucuti oleh SE.)
Tentu saja, itu masih terlalu lama untuk tunjangan 255 karakter Anda. Jika Anda benar-benar berbicara tentang karakter (dibandingkan dengan byte), Anda dapat masuk ke Unicode dan menggunakan basis yang jauh lebih besar. Bagaimana dengan 2 16 ? Itu hanya 139 digit:
(Saya tidak dapat memasukkan string aktual di sini, karena berisi beberapa karakter CJK yang dilarang oleh SE.)
Sekarang sepertinya lebih bisa dilakukan. Anda hanya perlu mendekodekannya dalam 116 karakter. Jika tidak bisa, Unicode memiliki lebih dari 2 16 karakter, jadi Anda bisa mencoba menggunakan basis yang lebih besar.
sumber
Faktorisasi Perdana
Jika nomor tersebut tidak memiliki fitur yang menarik, pengkodean basis adalah cara terbaik untuk melakukannya. Hal selanjutnya yang harus dilakukan adalah mencari fitur menarik dari nomor tersebut. Yang pertama terlintas dalam pikiran adalah bahwa ia mungkin memiliki faktor bilangan prima kecil (2,3,5,7, dll) dinaikkan ke kekuatan yang cukup besar. JIKA Anda tidak memiliki hal lain untuk dilanjutkan, teruslah berusaha untuk membagi dengan bilangan prima kecil dan lihat apa yang terjadi. Jika faktor-faktornya meliputi
2**4
,,3**4
dan7**4
, Anda dapat menulisbig number *42**4
yang beberapa byte lebih pendek daribig number * 3111696
sumber
n
perdana, Anda dapat menyimpan satu atau dua digit per perdana dengan menyimpan indeksnya alih-alih perdana itu sendiri.Penghapusan rekursif persegi terbesar
Pendekatan ini menghapus angka kuadrat terbesar dari N, berulang kali, hingga tidak ada nilai untuk melanjutkan.
Jika Anda mengabaikan karakter "** 2 +", yang ini rata-rata sekitar angka yang sama dengan angka aslinya, rata-rata. Mengganti 4 karakter ekstra per iterasi membutuhkan sedikit keberuntungan. Dalam hal nomor Anda, hasilnya memiliki 670 digit angka kuadrat, ditambah 7x "** 2+", kegagalan lain:
Dengan hampir mencapai titik impas rata-rata, algoritma ini cocok untuk digunakan bersama dengan algoritma lain (atau bahkan sendiri) untuk lebih mengurangi angka dalam ekspresi (dengan biaya beberapa tanda kurung). Algoritme lain itu bisa lebih mahal, karena akan beroperasi pada angka yang jauh lebih kecil daripada yang asli. Dalam contoh yang diberikan, keuntungan bersih dapat diperoleh jika algoritma yang lebih mahal dan efektif dapat memotong 25% karakter
33300095205899066129442737321270515378501483166974896029394675779096351509514355500527819871697116193238261137790928953798777695127752032484956608505929119246433389165
(nilai besar kedua dalam hasil)sumber
Kekuatan besar terdekat
Pendekatan ini mencari [relatif] angka kecil yang dinaikkan ke sejumlah daya yang mendekati jumlah target. Dalam kebanyakan kasus menyatakan kembali N sebagai A ** B + C tidak akan menjadi perbaikan, tetapi dalam beberapa kasus itu akan menjadi perbaikan.
10000
adalah konstanta arbitrer. Kondisi bail-out juga bisa didasarkan pada beberapa targetmindiff
.Dalam hal jumlah sampel Anda N dengan 666 digit, fungsi ini (dengan tutup 10k sedikit meningkat) mendapati bahwa
N ~= 165661162**81.0000000025
, demikianN-165661162**81
juga dengan angka 659 digit, memotong 7 digit dari angka yang akan ditangani dengan biaya 14 karakter ekspresi , sebuah kegagalan.sumber