Bahasa J memiliki sintaks yang sangat konyol untuk menentukan konstanta . Saya ingin fokus pada satu fitur keren pada khususnya: kemampuan untuk menulis dalam basis sewenang-wenang.
Jika Anda menulis XbY
untuk X
angka dan Y
string alfanumerik apa pun, maka J akan mengartikannya Y
sebagai angka dasar X
, di mana 0
melalui 9
memiliki makna biasa dan a
melalui z
mewakili 10 hingga 35.
Dan ketika saya mengatakan X
angka apa pun, maksud saya nomor apa pun . Untuk keperluan pertanyaan ini, saya akan membatasi X
untuk menjadi bilangan bulat positif, tetapi dalam J Anda dapat menggunakan apa saja: bilangan negatif, pecahan, bilangan kompleks, apa pun.
Yang aneh adalah bahwa Anda hanya dapat menggunakan angka dari 0 hingga 35 sebagai basis-apa pun digit Anda, karena koleksi simbol yang dapat digunakan hanya terdiri dari 0-9 dan az.
Masalah
Saya ingin sebuah program membantu saya angka-angka ajaib golf seperti 2.933.774.030.998 menggunakan metode ini. Baiklah, oke, mungkin tidak sebesar itu, aku akan memudahkanmu. Begitu...
Tugas Anda adalah menulis program atau fungsi yang mengambil angka desimal (biasanya besar)
N
antara 1 dan 4.294.967.295 (= 2 32 -1) sebagai input, dan menampilkan / mengembalikan representasi terpendek dari formulirXbY
, di manaX
bilangan bulat positif,Y
adalah string yang terdiri dari alfanumerik (0-9 dan az, peka huruf besar kecil), danY
ditafsirkan dalam basisX
sama denganN
.Jika panjang setiap representasi
XbY
representasi lebih besar dari atau sama dengan jumlah digitN
, maka outputN
sebagai gantinya. Dalam semua ikatan lainnya, Anda dapat menampilkan subset nonempty dari representasi terpendek.
Ini kode golf, jadi lebih pendek lebih baik.
Uji kasus
Input | Acceptable outputs (case-insensitive)
------------+-------------------------------------------------------
5 | 5
|
10000000 | 79bkmom 82bibhi 85bgo75 99bauua 577buld
| 620bq9k 999baka
|
10000030 | 85bgo7z
|
10000031 | 10000031
|
12345678 | 76bs9va 79bp3cw 82bmw54 86bjzky 641buui
|
34307000 | 99bzzzz
|
34307001 | 34307001
|
1557626714 | 84bvo07e 87brgzpt 99bglush 420blaze
|
1892332260 | 35bzzzzzz 36bvan8x0 37brapre5 38bnxkbfe 40bij7rqk
| 41bgdrm7f 42bek5su0 45bablf30 49b6ycriz 56b3onmfs
| 57b38f9gx 62b244244 69b1expkf 71b13xbj3
|
2147483647 | 36bzik0zj 38br3y91l 39bnvabca 42bgi5of1 48b8kq3qv
(= 2^31-1) | 53b578t6k 63b2akka1 1022b2cof 1023b2661 10922bio7
| 16382b8wv 16383b8g7 32764b2gv 32765b2ch 32766b287
| 32767b241
|
2147483648 | 512bg000 8192bw00
|
4294967295 | 45bnchvmu 60b5vo6sf 71b2r1708 84b12mxf3 112brx8iv
(= 2^32-1) | 126bh5aa3 254b18owf 255b14640 1023b4cc3 13107bpa0
| 16383bgwf 21844b9of 21845b960 32765b4oz 32766b4gf
| 32767b483 65530b1cz 65531b1ao 65532b18f 65533b168
| 65534b143 65535b120
Jika Anda tidak yakin apakah representasi sama dengan angka, Anda dapat menggunakan juru bahasa apa pun, seperti yang ada di Try It Online . Cukup ketik stdout 0":87brgzpt
dan J akan meludahkan kembali 1557626714
. Perhatikan bahwa J hanya menerima huruf kecil, meskipun masalah ini tidak peka huruf besar-kecil.
Beberapa teori yang mungkin membantu
- Untuk semua yang
N
kurang dari 10.000.000, representasi desimal sama pendeknya dengan yang lain dan karenanya merupakan satu-satunya hasil yang dapat diterima. Untuk menyimpan apa pun, Anda harus setidaknya empat digit lebih pendek di pangkalan baru, dan bahkan lebih jika pangkalan lebih besar dari 99. - Itu sudah cukup untuk memeriksa basis hingga langit-langit akar kuadrat
N
. Untuk setiap basis B yang lebih besar ,N
akan paling banyak dua digit di basis B , jadi pertama kali Anda akan mendapatkan sesuatu dengan digit pertama yang valid adalah sekitar B ≈N
/ 35. Tetapi pada ukuran itu Anda akan selalu setidaknya sebesar representasi desimal, jadi tidak ada gunanya mencoba. Itu dalam pikiran, ceil (sqrt (jumlah terbesar saya akan meminta Anda untuk menyelesaikan masalah ini)) = 65536. - Jika Anda memiliki representasi dalam basis kurang dari 36, maka representasi basis 36 setidaknya akan sesingkat. Jadi Anda tidak perlu khawatir tentang solusi pendek yang tidak disengaja di pangkalan kurang dari 36. Misalnya, representasi
35bzzzzzz
untuk 1.892.332.260 menggunakan angka yang tidak biasa untuk pangkalan itu, tetapi36bvan8x0
memiliki panjang yang sama.
sumber
Jawaban:
JavaScript (ES6),
103101 byteMengambil input sebagai string.
Uji kasus
NB: Jumlah iterasi dalam fungsi snippet dibatasi hingga 600 sehingga kasus uji selesai lebih cepat. (Jika tidak, butuh beberapa detik.)
Tampilkan cuplikan kode
sumber
Math.floor(x/b)
alih-alihx/b|0
. (Tapi saya tidak mengujinya.)Ruby , 118 byte
Ini ditautkan dalam pertanyaan lain dan saya perhatikan tidak ada banyak jawaban di sini, jadi saya memutuskan untuk mencobanya.
Telusuri semua pangkalan hingga dan termasuk input untuk membangun semua konstruksi nomor J yang valid. Itu melompat 1-8 meskipun, karena tidak mungkin mereka akan lebih pendek daripada representasi basis-10. Ini adalah solusi yang cukup naif, semua hal dipertimbangkan, karena ia memanggil
digits
builtin untuk mendapatkan digit, tetapi sejak itu dimulai dengan digit paling tidak signifikan terlebih dahulu kita harusreverse
mendapatkannya untuk mendapatkan angka aktual, sehingga mungkin dapat ditingkatkan.Itu lambat. Jadi, soooooo sangat lambat. TIO habis pada 34307000, misalnya. Kita bisa menggunakan root kuadrat atau bahkan pilihan Arnauld
7e4
untuk menghemat waktu, tetapi itu membutuhkan tambahan byte, jadi mengapa repot-repot?Cobalah online!
Cobalah online dg sqrt sehingga semuanya selesai tepat waktu
sumber
05AB1E , 37 byte
Harus bekerja secara teori, tetapi waktu habis untuk semua kasus uji non-sepele, bahkan≥ 4 ..
10000000
. Produk kartesius builtinã
sangat lambat untukTanpa pernyataan if-final
DgIg@i\}
, masih dapat diuji untuk nilai yang lebih rendah, untuk memverifikasi bahwa itu benar-benar berfungsi: Coba online.Akan melihat apakah saya dapat datang dengan (mungkin lebih lama tapi) solusi yang lebih efisien nanti.
Penjelasan:
sumber
XbY
representasi lebih besar atau sama dengan jumlah digitN
, maka outputN
sebagai gantinya." Meskipun Anda memiliki 10 juta angka pertama yang dicakup, saya menduga bahwa input10000031
akan memberikan sesuatu seperti26blmoof
. Jumlahnya valid, tetapi panjangnya sama dengan input, jadi harus mengembalikan input.