Nomor braket menyediakan cara sederhana untuk mengekspresikan bilangan bulat besar hanya dengan menggunakan braket kiri, spasi, dan braket kanan ( [ ]
).
Nomor braket didefinisikan sebagai string dari satu atau lebih pasangan tanda kurung yang [...]
disebut potongan , yang masing-masing dipisahkan dari tetangganya dengan nol atau lebih spasi.
Jumlah ruang di antara setiap chunk mendefinisikan hyperoperation di antara mereka. Tidak ada spasi berarti penambahan, 1 spasi berarti multiplikasi, 2 spasi berarti eksponensial, 3 spasi berarti tetrasi , dan sebagainya. Urutan tinggi hiperoperasi diutamakan, sehingga tetrasi terjadi sebelum eksponensial, eksponensial terjadi sebelum multiplikasi, dll. Mereka juga asosiatif-kanan, jadi a^b^c
dihitung sebagai a^(b^c)
. (Tapi a^b*c
tetap saja (a^b)*c
.)
Setiap chunk bisa kosong ( []
) atau mengandung nomor braket lain. Potongan kosong memiliki nilai 0. Potongan tidak kosong memiliki nilai nomor braket yang terkandung ditambah 1.
Contoh: ( ^^
adalah tetrasi, ^^^
adalah pentasi )
[[]]
memiliki nilai 1 karena 0 ([]
) bertambah 1[[[]]]
memiliki nilai 2 tetapi demikian juga[[]][[]]
karena dua yang ([[]]
) ditambahkan[[[]]] [[[[]]] [[[[]]]]][[[]]]
memiliki nilai 20 = (2 * ((2 ^ 3) +1)) + 2[[[]]] [[[[]]]]
memiliki nilai 65536 = 2 ^^^ 3 = 2 ^^ (2 ^^ 2) = 2 ^^ 4 == 2 ^ (2 ^ (2 ^ 2))[[[[]]]] [[[]]] [[]]
memiliki nilai 7625597484987 = 3 ^^^ (2 ^^^ 1) = 3 ^^^ 2 = 3 ^^ 3 = 3 ^ (3 ^ 3)
Dalam angka braket yang valid:
- Tidak akan pernah ada ruang depan atau belakang.
- Akan selalu ada setidaknya sepasang kurung yang cocok.
- Semua braket kiri akan memiliki braket kanan yang cocok.
- Sebuah ruang tidak akan pernah muncul langsung ke kanan
[
atau ke kiri]
. - Nilai selalu bilangan bulat non-negatif.
Tantangan
Perhatikan bahwa mungkin ada banyak bentuk untuk nomor braket yang memberikan nilai yang sama. [[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]
dan [[[]]] [[[[]]]]
keduanya mewakili 16, tetapi yang terakhir jauh lebih pendek.
Tantangan Anda adalah menulis algoritma yang mencoba menemukan representasi nomor braket terpendek dari nilai yang diberikan. Sebagai contoh, saya percaya cara terpendek untuk mewakili 16 adalah dengan 17 karakter sebagai [[[]]] [[[[]]]]
.
Penilaian (Diperbarui)
Misalkan S adalah himpunan bilangan bulat dari 1 hingga 256 (inklusif) serta sepuluh nilai berikut:
8191 13071 524287 2147483647 1449565302 1746268229 126528612 778085967 1553783038 997599288
(4 yang pertama adalah bilangan prima Mersenne, sisanya acak.)
Kiriman yang menghasilkan set nomor braket terpendek untuk semua yang ada di S akan menang. Skor Anda adalah jumlah dari panjang nomor braket Anda untuk semua nilai dalam S (lebih kecil lebih baik).
Dengan kode Anda, silakan kirimkan daftar nomor braket Anda untuk semua S , urutan pastinya tidak terlalu penting. misalnya:
1=[[]]
2=[[[]]]
3=[[[[]]]]
...
2147483647=[...]
...
(Saya tahu ini bukan metode penilaian yang optimal tapi saya tidak siap untuk menjalankan banyak tes heuristik acak pada setiap pengiriman. Maaf :()
Aturan
- Anda tidak boleh membuat hardcode nomor braket selain solusi tambahan sepele (
[], [[]], [[[]]], ...
). Program Anda sebenarnya harus mencari representasi pendek yang optimal. (Meskipun hasilnya mungkin suboptimal.) - Algoritme Anda harus bekerja untuk semua bilangan bulat non-negatif di bawah 2.147.483.648 (2 ^ 31). Anda mungkin tidak secara khusus fokus pada nilai-nilai dalam S .
- Untuk input tertentu, algoritma Anda harus berjalan paling lama 10 menit pada komputer modern yang layak (~ prosesor 2.5Ghz, ~ 6GB RAM).
- Dalam (yang tampaknya) kesempatan langka dari dasi, pengajuan dengan suara tertinggi akan menang.
- Jika Anda menyalin solusi lain atau merevisinya tanpa atribusi Anda akan didiskualifikasi.
sumber
Jawaban:
Python 11455b
Solusi ini mengambil pendekatan serakah untuk menemukan cara untuk menjabarkan bilangan prima, daripada pendekatan yang lengkap. Saya perlu 9875b untuk 1-256 dibandingkan dengan 8181 untuk solusi Martin yang mungkin optimal di ruang itu.
Tabel multiplikasi dan hasil eksponensial yang lebih besar menghasilkan sedikit peningkatan pada kasus uji yang lebih besar. Solusi di bawah ini memakan waktu sekitar 7 menit. Meningkatkan runtime melebihi 30 menit memiliki dampak minimal pada output.
Saya, seperti Martin, memiliki masalah dengan prioritas. Solusi saya dalam membatasi pemilihan operasi mungkin tidak optimal.
Keluaran:
sumber
Mathematica
catatan: Algoritma ini tidak akan pernah bisa mendekati angka tes yang lebih besar. Saya membutuhkan pendekatan yang jauh berbeda, jadi saya akan membiarkannya seperti yang lain untuk memeriksa angka yang lebih rendah. Anda dapat menganggap kiriman ini tidak valid.
Ini adalah awal untuk 256 angka pertama (yang lain ditambahkan setelah saya mulai, dan saya mungkin perlu menemukan solusi terpisah untuk itu)
Panjang total 256 angka pertama adalah 7963 karakter. Saya tidak tahu apakah ini optimal.
Mengabaikan penambahan, hasil untuk 8191 dan 13071 ditemukan dalam beberapa detik dan 524387 dalam beberapa menit sebagai
di 164 karakter bersama-sama.
Ini kodenya:
Saya menggunakan pencarian lengkap hingga eksponensial. Tidak ada operasi tetrasi atau tingkat tinggi. Saya baru saja mencoba operasi tingkat tinggi secara manual, dan hanya ada beberapa kombinasi yang benar-benar menghasilkan angka di bawah 2 31 , jadi saya hanya melakukan hardcode pada mereka yang berfungsi.
Sunting: Solusi saya sebelumnya tidak peduli tentang presedensi, itu hanya menyatukan semuanya.
Sekarang saya pikir kode baru saya memperbaikinya,tetapi bukan dari 256 angka pertama telah berubah, juga tidak ada 8191 (yang berlaku sebelumnya, saya periksa) ... dan sudah terlambat bagi saya untuk memberi tahu sekarang jika kode saya benar-benar memperbaikinya . Saya akan melihat lagi besok dan juga menambahkan penjelasan, karena sekarang dengan pemeriksaan diutamakan agak berbelit-belit (mudah-mudahan ini akan mengurangi waktu pencarian).Sunting: Oke, ada beberapa bug seperti yang diharapkan. Saya pikir saya memperbaikinya sekarang, meningkatkan panjang total untuk 1 - 256 menjadi 7963 . Saya tidak yakin ini lebih optimal lagi, karena dimungkinkan untuk menemukan solusi yang lebih pendek dari bagian suboptimal jika mereka memungkinkan operasi tingkat tinggi. Penjelasan akan mengikuti ketika saya berhasil sedikit membersihkan kode.
sumber
Python 9219b
Ini adalah entri kedua saya. Saya mulai dari awal dan mencoba pengaturan data baru, termasuk menggunakan paket blist untuk daftar dan dict yang diurutkan, dan beberapa pendekatan baru untuk menemukan solusi besar. Saya pikir saya punya 1-256 yang optimal. Meningkatkan runtime dari 30s menjadi 4m mempersingkat kasus uji besar sekitar 30 byte.
Keluaran:
7944b untuk 1-256
1275b untuk kasing besar
sumber