Ini adalah jenis tantangan kompresi yang berbeda. Dalam tantangan kompleksitas-kolmogorov yang normal , Anda harus membuat ulang daftar dengan tepat. Di sini, Anda diizinkan untuk membulatkan nilai dengan cara apa pun yang Anda inginkan. Apa yang menangkap? Skor Anda dihukum berdasarkan seberapa salah output Anda.
Di bagian bawah pertanyaan ini adalah daftar energi ionisasi pertama untuk 108 elemen pertama. Program Anda, setelah dieksekusi, akan menghasilkan salinan daftar ini yang cukup akurat. Tidak akan ada input atau argumen. Untuk tujuan penilaian, output Anda harus deterministik (keluaran yang sama setiap kali).
Format output
Program / fungsi Anda harus menampilkan daftar nomor 108, diurutkan dalam urutan peningkatan nomor atom. Daftar ini bisa dalam format yang sesuai. Sumber data di bawah ini disediakan dalam urutan yang benar, dari hidrogen hingga hassium.
Mencetak gol
Skor Anda akan menjadi panjang program Anda dalam byte ditambah penalti pembulatan. Denda pembulatan dihitung untuk setiap elemen dan dijumlahkan untuk memberikan total penalti.
Sebagai contoh, mari kita ambil nomornya 11.81381
. Katakanlah program Anda menghasilkan nilai salah 11.81299999
.
Pertama, kedua angka tersebut dikalikan dengan kekuatan yang sama dari 10 sehingga tidak ada lagi titik desimal dalam nilai sebenarnya:
1181381, 1181299.999
. Mengejar nol pada nilai sebenarnya dianggap signifikan.Kemudian, perbedaan mutlak diambil untuk menentukan kesalahan mutlak:
81.001
.Akhirnya, kami menghitung penalti elemen ini sebagai
max(0, log10(err * 4 - 1)) -> 2.50921
. Formula ini dipilih sedemikian sehingga kesalahan <0,5 tidak memberikan penalti (karena jawabannya benar dalam pembulatan), sementara juga memberikan peluang 50% asimptotik bahwa membulatkan angka ke tempat desimal tertentu akan memberikan keuntungan bersih dalam skor (dengan asumsi tidak ada kompresi lainnya).
Berikut ini adalah implementasi Try-It-Online dari program penghitungan penalti. Input untuk program ini disediakan sebagai daftar angka, satu per baris. Output dari program ini adalah penalti total dan rincian skor per elemen.
Data
Daftar angka di bawah ini adalah data target, dalam urutan yang benar dari nomor atom 1 hingga 108.
13.598434005136
24.587387936
5.391714761
9.322699
8.2980190
11.260296
14.53413
13.618054
17.42282
21.564540
5.1390767
7.646235
5.985768
8.151683
10.486686
10.36001
12.96763
15.7596112
4.34066354
6.11315520
6.56149
6.82812
6.746187
6.76651
7.434018
7.9024678
7.88101
7.639877
7.726380
9.3941990
5.9993018
7.899435
9.7886
9.752392
11.81381
13.9996049
4.177128
5.69486720
6.21726
6.63390
6.75885
7.09243
7.11938
7.36050
7.45890
8.33686
7.576234
8.993822
5.7863552
7.343917
8.608389
9.00966
10.45126
12.1298431
3.893905548
5.211664
5.5769
5.5386
5.473
5.5250
5.582
5.64371
5.670385
6.14980
5.8638
5.93905
6.0215
6.1077
6.18431
6.254159
5.425871
6.825069
7.549571
7.86403
7.83352
8.43823
8.96702
8.95883
9.225553
10.437504
6.1082871
7.4166796
7.285516
8.414
9.31751
10.7485
4.0727409
5.278424
5.380226
6.3067
5.89
6.19405
6.2655
6.0258
5.9738
5.9914
6.1978
6.2817
6.3676
6.50
6.58
6.65
4.90
6.01
6.8
7.8
7.7
7.6
Baseline & Tip
Sumber data di atas adalah 906 byte, dengan alat kompresi tertentu bisa mendapatkannya hingga sub-500 byte. Solusi menarik adalah solusi yang berupaya melakukan pembulatan cerdas, menggunakan rumus aljabar, atau teknik lain untuk menghasilkan nilai perkiraan dalam byte yang lebih sedikit daripada kompresi saja. Namun, sulit untuk menilai pengorbanan ini dalam berbagai bahasa: untuk beberapa bahasa kompresi saja mungkin optimal, sementara banyak bahasa lain mungkin tidak memiliki alat kompresi sama sekali, jadi saya mengharapkan variasi skor yang luas antar bahasa. Ini bagus, karena saya mengikuti filosofi "kompetisi dalam bahasa, bukan di antara mereka".
Saya mengantisipasi bahwa mungkin berguna untuk mencoba memanfaatkan tren dalam tabel periodik. Di bawah ini adalah grafik yang saya temukan dari energi ionisasi, sehingga Anda dapat melihat beberapa tren ini.
sumber
Jawaban:
Bersih , 540 byte + 64.396 Hukuman = 604.396
Catatan: demi keterbacaan, saya telah lolos setiap byte dalam
[Char]
literal karena kebanyakan dari mereka tidak dapat dicetak. Namun, mereka dihitung hanya satu byte per escape (kecuali null, quote, dan newlines) karena Clean secara alami mengambil file sumber yang dikodekan secara independen (kecuali nulls).Cobalah online!
Ini adalah tantangan pertama di mana saya bisa memanfaatkan kemampuan kompresi generik Clean (secara teknis tidak benar-benar kompresi, ini adalah serialisasi biner) untuk mendapatkan manfaat yang sebenarnya.
Saya mulai dengan
[Real]
- daftar angka floating-point 64-bit, yang dari pertanyaan. Setelah membuat serial daftar ini, saya menyederhanakan 10 bit teratas (yang sama untuk setiap angka), dan konfigurasi optimal dari 32 bit bagian bawah ke dalam konstanta7<<29+2^62
. 22 bit yang tersisa per angka diterjemahkan masing-masing menjadi 2,75 karakter, dan dikodekan dalam sebuah string.Ini membuat seluruh konstanta yang dikompresi hanya 302 byte , termasuk setiap pelarian!
sumber
Python 3 ,
355 + 202353 byte + 198 penalti = 551Cobalah online!
Saya digunakan
0xffff (65535)
sebagai batas atas karena itu nilai maks yang dapat disimpan dalam karakter unicode 3-byte tunggal.Karena energi ionisasi tertinggi adalah ~ 24,587, itu menghasilkan rasio
2665
.Untuk menghasilkan string itu sendiri, saya menggunakan snippet
''.join([chr(int(round(n*2665)))for n in ionization_energies])
(pada python2 yang perlu Anda gunakanunichr
), konsol Anda mungkin atau mungkin tidak dapat mencetak karakter.4-byte karakter, 462 byte + 99 penalti = 561
Cobalah online!
Gagasan yang sama, tetapi nilai maksimalnya adalah
0x110000
sumber
0x100**2
nilai dan tidak0x100**3
?C, 49 byte + penalti 626.048 = 675.048
Cobalah online!
sumber
f(i){for(i=0;i++<108;)printf("6\n");}
; penalti: 625.173330827107; total = 662,173330827f(i){for(i=0;i<108;)puts("6");}
melakukan hal yang sama dalam 31 byte.i++
(dalam "31"), tetapif(i){for(i=108;i;i--)puts("6");}
32.f(i){for(i=108;i--;)puts("6");}
mendapatkannya kembali ke 31.CJam (389 bytes + 33,09 penalti => 422,09)
disandikan xxd:
Pada dasarnya ini
Ini menggunakan format floating point lebar variabel kustom untuk menyimpan angka. Dua bit sudah cukup untuk eksponen; mantissa dapat dari 5 bit hingga 47 bit, dalam kelipatan 7. Bit tersisa per byte berfungsi sebagai pemisah.
Sepertinya ada beberapa korupsi yang terjadi ketika saya menyalin string ajaib untuk membuat demo online , sehingga skor sekitar 2 poin penalti lebih banyak. Saya harus mencari cara bagaimana membangun URL secara langsung ...
Program pembangkitan:
Demo online
sumber
"
meningkatkan kesalahan terlalu banyak sehingga tidak layak?Jelly ,
379 361360 byte + 0 Hukuman = 360-18 menggunakan pengamatan dari Peter Taylor (urutan 10 nilai memiliki memimpin 1 atau 2, sedangkan nilai urutan 1 tidak).
Cobalah online!
Bagaimana?
Menciptakan dua konstanta ini (AKA nilads):
Kemudian gunakan itu untuk merekonstruksi representasi floating point dari angka-angka.
Program lengkapnya dalam bentuk ini:
(di mana
...
nomor yang disandikan untuk membangun B, dan A)dan berfungsi seperti ini:
sumber
Jelly , 116 byte + 429.796016684433 Penalty = 545.796016684433
Cobalah online!
Tidak ada yang sangat spektakuler, daftar index kode-halaman,
“...‘
(angka antara 0 dan 249), untuk masing-masing kita tambahkan 47 ,+47
dan kemudian bagi dengan 12 ,÷12
.sumber
Jelly , 164 byte + 409.846 = 573.846
Cobalah online!
Ada angka terkompresi di sana yang merupakan gabungan dari tiga digit pertama dari masing-masing energi (termasuk trailing nol). Saya mendapatkan daftar nomor tiga digit ini dengan
Ds3Ḍ
kemudian membaginya masing-masing dengan 100÷³
. Beberapa angka seharusnya hanya dibagi 10, jadi saya kalikan beberapa dengan 10 untuk meningkatkan skor sedikit (×⁵$2R;6r⁵¤¤;15r18¤¤¦
).Versi sebelumnya :
Jelly , hukuman 50 byte + 571.482 = 621.482
Cobalah online!
Membulatkan setiap energi ke integer satu digit terdekat. Disatukan bersama ini memberi
995989999958689999467777788889689999466777777889679999456656666666666657888899996778994556666666666677567888
.“¡9;ẋkñ¬nƑḳ_gÐ.RḊụʠṁṬl⁾l>ɼXZĖSṠƈ;cḶ=ß³ṾAiʠʠɼZÞ⁹’
adalah angka dasar 250 yang menghasilkan ini.DY
bergabung dengan digit nomor ini dengan baris baru.sumber
Java 8, 48 byte + 625.173330827107 Penalty = 673.173330827107
Cobalah online.
Versi awal yang mencetak 108 kali
6
. Akan mencoba meningkatkan dari sini.sumber
J , 390 byte + 183.319 Hukuman = 573.319
Cobalah online!
Saya membulatkan angka menjadi empat angka desimal dan membaginya menjadi satu daftar untuk bagian bilangan bulat, satu daftar untuk 2 digit pecahan pertama dan satu untuk 2 digit pecahan kedua. Saya menyandikan setiap nomor dengan karakter yang dapat dicetak. Untuk mendekode, saya cukup mengekstrak bagian ingerer dan fraksi dari nomor dari daftar karakter terkait dan mengumpulkannya kembali untuk mengapung.
J , 602 byte + 0 Hukuman = 602
Cobalah online!
Kali ini saya menggunakan pendekatan yang sedikit berbeda. Saya membagi angka menjadi 2 aliran - yang pertama berisi bagian integer yang hanya dikodekan dengan satu karakter yang dapat dicetak. Aliran kedua berisi seluruh bagian fraksional. Saya menghapus semua interval antara digit dan menambahkan masing-masing substring dengan panjangnya 1-9 (saya mengubah fraksi pertama, yang panjangnya 13 digit). Kemudian saya menyandikan daftar ini sebagai angka dasar 94, menyajikannya sebagai daftar karakter.
Sekitar 20 byte dapat disimpan jika kata kerjanya ditulis ulang sebagai tacit one.
sumber
Bubblegum , 403 + 9.12 = 412.12
Cobalah online!
sumber