Mengonversi Angka ke “Sistem nilai tidak terlalu”

11

Mari kita membuat sistem angka di mana digit terbesar di nilai tempat ke-n (menghitung dari kanan ke kiri) dari panjang angka m selalu sama dengan m - n + 1. Untuk memberikan contoh angka 5 digit terbesar yang dapat diekspresikan dalam sistem ini ditulis 12345. Terlepas dari jumlah digit yang tersedia untuk digunakan di tempat tertentu yang dibatasi, semua penambahan lainnya adalah standar. Yaitu ketika sebuah angka melampaui batas digitnya, kami menambahkan satu ke digit berikutnya.

Di sini adalah bagaimana penghitungan akan diwakili dalam sistem ini:

1; 10; 11; 12; 100; 101; 102; 103; 110; 111; 112; 113; 120; 121; 122; 123; 1000; 1001 ...

Tugas Anda adalah menulis fungsi yang menggunakan nomor basis 10 standar dan mengubahnya menjadi sistem penomoran saya.

Kode yang lebih pendek lebih disukai. Bonne Chance!

** Jika Anda membutuhkan digit setelah 9 (Anda harus), Anda dapat memilih untuk menggunakan huruf, atau Anda dapat mengembalikan angka 2 digit sebagai elemen dari daftar.

Uji Kasus

10 -> 111
20 -> 1003
30 -> 1023
50 -> 1123
100 -> 10035
23116 -> 1234567
21977356 -> 123456789A

Kasus terakhir mungkin sangat lambat untuk dijalankan tergantung pada bagaimana Anda menerapkannya. Anda tidak perlu menjalankannya jika terlalu lama atau menggunakan terlalu banyak memori. Namun perhatikan bahwa ada cara untuk menjalankannya dengan cepat dan menggunakan sedikit memori.

Ando Bando
sumber
Diberikan komentar terakhir Anda, apakah boleh jika kami selalu mengembalikan daftar dengan digit?
Greg Martin
Ya, itu cara yang masuk akal untuk memberikan hasil, asalkan angkanya benar
Ando Bando
1
Saya mendapatkan, 100 -> 10035bukan 100 -> 10033, bisakah Anda memverifikasi?
Greg Martin
@GregMartin 10035 sepertinya benar. Saya melakukan perhitungan saya dengan pena dan bukan program dan karenanya membuat kesalahan perhitungan. Saya kira kita memiliki komputer untuk pengarahan kembali
Ando Bando

Jawaban:

4

Mathematica, 64 byte

Part[Join@@Array[Tuples@Join[{{1}},Array[Range,#-1,3]-1]&,#],#]&

Fungsi tanpa nama mengambil argumen bilangan bulat positif dan mengembalikan daftar bilangan bulat.

Join[{{1}},Array[Range,#-1,3]-1]mengembalikan daftar bersarang { {1}, {0,1,2}, {0,1,2,3}, ..., {0,1,...,#} }. Kemudian Tuplesmengembalikan set (diurutkan) dari semua tupel yang elemen pertamanya terletak {1}, elemen kedua yang terletak {0,1,2}, dan seterusnya; ini adalah #angka -digit dalam sistem penomoran ini. Join@@Array[...,#]mengembalikan array dari semua angka dalam sistem penomoran ini dengan paling banyak #digit, dan Part[...,#]mengekstraksi #nomor tersebut.

Ini sangat lambat! Ini berjalan dengan baik untuk input hingga 9. Untuk input yang lebih besar, uji dengan mengganti akhirnya ,#],#]&dengan ,Ceiling[0.9Log[#]]],#]&; ini menempatkan batasan yang lebih realistis pada jumlah digit yang diperlukan untuk melangkah cukup jauh dalam sistem penomoran untuk menemukan yang kita inginkan.

Greg Martin
sumber
3

Mathematica, 93 byte

Nest[#/.{x___,y_}:>{x,y+1}//.x:{y___,z_:0,w_,v___}/;w>Tr[1^x]-Tr[1^{v}]:>{y,z+1,0,v}&,{0},#]&

Fungsi murni dengan argumen pertama #. Jika bilangan bulat negatif diberikan, itu akan menampilkan daftar digit yang benar (bahkan menangani 0dengan benar!).

Penjelasan

Nest[f,expr,n]memberikan hasil dari penerapan funtuk expr nkali. Dalam hal ini, expradalah daftar {0}dan nbilangan bulat input #. Fungsinya frumit:

# (* Starting with the input # *)
 /. (* Apply the following rule *)
   {x___,y_} (* If you see a list of the form {x___,y} *)
            :> (* replace it with *)
              {x,y+1} (* this *)
                     //. (* Now apply the following rule repeatedly until nothing changes *)
                        x:{y___,z_:0,w_,v___} (* If you see a list x starting with a sequence y of 0 or more elements, 
                                                 followed by an optional element z (default value of 0),
                                                 followed by an element w,
                                                 followed by a sequence v of 0 or more elements *)
                                             /; (* such that *)
                                               w>Tr[1^x]-Tr[1^{v}] (* w is greater than the length of x minus the length of {v} *)
                                                                  :> (* replace it with *)
                                                                    {y,z+1,0,v}& (* this *)
ngenisis
sumber
Penggunaan yang bagus y___,z_:0untuk menambah panjang daftar!
Greg Martin
2
@GregMartin JungHwan Min menggunakannya dalam masalah yang sama kemarin.
ngenisis
3

Perl 6 , 38 byte

{map({|[X] 1,|map ^*,3..$_},1..*)[$_]}

Mengambil bilangan bulat positif, dan menampilkan daftar bilangan bulat yang mewakili digit.

Penjelasan:

{                                    }  # a lambda

 map({                    },1..*)       # for each number length from 0 to infinity,
                                        # offset by 1 to avoid a +1 in next step...

           1,|map ^*,3..$_              # generate the digit ranges, e.g.:
                                        #     length 0  ->  (1)  # bogus, but irrelevant
                                        #     length 1  ->  (1)
                                        #     length 2  ->  (1, 0..2)
                                        #     length 3  ->  (1, 0..2, 0..3)
                                        #     length 4  ->  (1, 0..2, 0..3, 0..4)

       [X]                              # take the cartesian product

      |                                 # slip the results into the outer sequence

                                 [$_]   # Index the sequence generated this way
seseorang
sumber
2

Pyth - 14 byte

Cukup kembalikan nthnilai yang cocok dengan "pola nilai kurang dari tempat".

e.f.A.eghkbjZT

Test Suite .

Maltysen
sumber
2
Apakah ini bekerja pada input 2018967, di mana digit terakhir sama dengan 10?
Greg Martin
1

Haskell, 65 byte

i(x:r)|x>length r=0:i r|1<2=1+x:r
i[]=[1]
reverse.(iterate i[]!!)

imeningkatkan angka dalam sistem angka dengan digit dalam urutan terbalik. iteratemembuat daftar tak terbatas semua angka-angka ini dimulai dengan nol yang diwakili oleh []. Maka yang harus dilakukan adalah mengambil ( !!) nomor yang diminta dan reverseitu.

Baris terakhir adalah fungsi, bukan definisi fungsi, sehingga tidak dapat muncul seperti dalam file kode sumber. Alih-alih, hanya letakkan baris lain dalam kode sumber dan gunakan baris terakhir pada penerjemah (atau ikat fungsi ke nama dengan mengawali f=ke baris terakhir).

Contoh penggunaan:

*Main> reverse.(iterate i[]!!) $ 100
[1,0,0,3,5]

(8 byte dapat disimpan jika [5,3,0,0,1]representasi yang diizinkan dari hasil.)

Sievers Kristen
sumber
1

Haskell, 49 byte

x=[1]:[n++[d]|n<-x,d<-[0..length n+1]]
(x!!).pred

Baris pertama adalah definisi tambahan, dan yang kedua mengevaluasi suatu fungsi. Dibutuhkan integer dan mengembalikan daftar integer. Cobalah online!

Penjelasan

Saya mendefinisikan xsebagai daftar representasi tak terbatas yang disebutkan dalam teks tantangan; fungsi utama hanya mengurangi argumennya dan mengindeksnya menjadi x. Baris pertama berfungsi seperti ini:

x=                     -- The list of lists x contains
 [1]:                  -- the list [1], followed by
 [n++[d]|              -- integer d appended to list n, where
  n<-x,                -- n is drawn from x, and
  d<-[0..length n+1]]  -- the new "digit" d is drawn from this range.

Anda lihat itu xdidefinisikan dari segi dirinya sendiri, tetapi Haskell malas, jadi ini bukan masalah.

Zgarb
sumber