Basis besar, digit kecil

19

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 XbYuntuk Xangka dan Ystring alfanumerik apa pun, maka J akan mengartikannya Ysebagai angka dasar X, di mana 0melalui 9memiliki makna biasa dan amelalui zmewakili 10 hingga 35.

Dan ketika saya mengatakan Xangka apa pun, maksud saya nomor apa pun . Untuk keperluan pertanyaan ini, saya akan membatasi Xuntuk 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) Nantara 1 dan 4.294.967.295 (= 2 32 -1) sebagai input, dan menampilkan / mengembalikan representasi terpendek dari formulir XbY, di mana Xbilangan bulat positif, Yadalah string yang terdiri dari alfanumerik (0-9 dan az, peka huruf besar kecil), dan Yditafsirkan dalam basis Xsama dengan N.

Jika panjang setiap representasi XbYrepresentasi lebih besar dari atau sama dengan jumlah digit N, maka output Nsebagai 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":87brgzptdan 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 Nkurang 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 , Nakan paling banyak dua digit di basis B , jadi pertama kali Anda akan mendapatkan sesuatu dengan digit pertama yang valid adalah sekitar BN/ 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 35bzzzzzzuntuk 1.892.332.260 menggunakan angka yang tidak biasa untuk pangkalan itu, tetapi 36bvan8x0memiliki panjang yang sama.
algoritme hiu
sumber
Lol, 1557626714 = 420blaze ^ _ ^
DrQuarius

Jawaban:

9

JavaScript (ES6), 103 101 byte

Mengambil input sebagai string.

n=>[...Array(7e4)].reduce(p=>p[(r=++b+(g=x=>x?g(x/b|0)+(x%b).toString(36):'b')(n)).length]?r:p,n,b=2)

Uji kasus

NB: Jumlah iterasi dalam fungsi snippet dibatasi hingga 600 sehingga kasus uji selesai lebih cepat. (Jika tidak, butuh beberapa detik.)

Arnauld
sumber
Jika nomor saya terlalu besar untuk digunakan, bagaimana saya memperbaikinya? Meningkatkan iterasi sepertinya tidak membantu.
FrownyFrog
N<232
Pencarian "Pernicious numbers", 2136894800297704.
FrownyFrog
@FrownyFrog Anda mungkin dapat memprosesnya dengan meningkatkan jumlah iterasi dan menggunakan Math.floor(x/b)alih-alih x/b|0. (Tapi saya tidak mengujinya.)
Arnauld
1
itu berhasil! Terima kasih.
FrownyFrog
3

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 digitsbuiltin untuk mendapatkan digit, tetapi sejak itu dimulai dengan digit paling tidak signifikan terlebih dahulu kita harus reversemendapatkannya 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 7e4untuk menghemat waktu, tetapi itu membutuhkan tambahan byte, jadi mengapa repot-repot?

->n{([n.to_s]+(9..n).map{|b|d=n.digits b;"#{b}b"+d.reverse.map{|i|i.to_s 36}*''if d.all?{|i|i<36}}-[p]).min_by &:size}

Cobalah online!

Cobalah online dg sqrt sehingga semuanya selesai tepat waktu

Nilai Tinta
sumber
1

05AB1E , 37 byte

[¼35ݾãvtîEyNβQižhA«yèJ'bìNìDgIg@i\}q

Harus bekerja secara teori, tetapi waktu habis untuk semua kasus uji non-sepele, bahkan 10000000. Produk kartesius builtin ãsangat lambat untuk4..

Tanpa 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:

[              # Start an infinite loop:
 ¼             #  Increase the counter variable by 1 (0 by default)
 35Ý           #  Push a list in the range [0, 35]
 ¾ã            #  Take the cartesian product of this list with itself,
               #  with chunks-sizes equal to the counter variable
 v             #  Loop `y` over each of these lists:
  t            #   Take the square-root of the (implicit) input-integer
   î           #   Ceil it
  E            #   Loop `N` in the range [1, ceil(square(input))]:
   yNβ         #    Convert list `y` to base-`N`
   Qi          #    If it's equal to the (implicit) input-integer:
     žh        #     Push string "0123456789"
       A«      #     Append the lowercase alphabet
     yè        #     Index each value in list `y` into this string
     J         #     Join the characters to a single string
     'bì      '#     Prepend a "b"
        Nì     #     Prepend the number `N`
     D         #     Duplicate it
      g        #     And pop and push the length of this string
       Ig      #     Also push the length of the input
         @i }  #     If the length of the string is >= the input-length:
           \   #      Discard the duplicated string
     q         #     Stop the program
               #     (after which the result is output implicitly;
               #      or if the string was discarded and the stack is empty, it will
               #      implicitly output the implicit input as result instead)
Kevin Cruijssen
sumber
1
Jawaban yang mengesankan! Saya pikir Anda kehilangan aturan, meskipun: "Jika panjang setiap representasi XbYrepresentasi lebih besar atau sama dengan jumlah digit N, maka output Nsebagai gantinya." Meskipun Anda memiliki 10 juta angka pertama yang dicakup, saya menduga bahwa input 10000031akan memberikan sesuatu seperti 26blmoof. Jumlahnya valid, tetapi panjangnya sama dengan input, jadi harus mengembalikan input.
Value Ink
@ NilaiTinta Ah oops. Terima kasih telah memperhatikan! Harus diperbaiki sekarang dengan biaya beberapa byte.
Kevin Cruijssen