Semua basis kata sifat Anda adalah milik kami

25

Latar Belakang

Sebuah basis bijective b penomoran , di mana b adalah bilangan bulat positif, adalah notasi posisional bijective yang menggunakan b simbol dengan nilai-nilai terkait dari 1 ke b .

Tidak seperti mitra non-bijektifnya, tidak ada simbol yang memiliki nilai 0 . Dengan cara ini, setiap bilangan bulat n -negatif memiliki representasi unik dalam basis kata sifat b .

Angka bijective populer termasuk unary, basis bijective 2 (digunakan dalam pengkodean run-length bzip2 ) dan basis bijective 26 (digunakan untuk memberi nomor kolom dalam spreadsheet).

Definisi

Dalam tantangan ini, kita mendefinisikan himpunan M simbol sebagai

123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz<=>

dan fungsi i dari M ke bilangan asli sedemikian sehingga i ('1') = 1,…, i ('>') = 64 .

Mengingat basis b antara 1 dan 64 (keduanya inklusif), kita mendefinisikan bahwa setiap bilangan bulat non-negatif n bersesuaian dengan string yang k ... a 0 , yang terdiri dari simbol M , sehingga n = b k i (a k ) + … + B 0 i (a 0 ) .

Korespondensi ini didefinisikan dengan baik dan bijektif. Karena jumlah kosong didefinisikan sebagai 0 , bilangan bulat 0 dapat dikodekan sebagai string kosong.

Tugas

Terima tiga string sebagai input:

  • Basis input b antara 1 dan 64 , dikodekan sebagai string basis 64 kata sifat .

  • Sebuah bilangan bulat non-negatif n , dikodekan sebagai dasar bijective b tali.

  • Basis keluaran B antara 1 dan 64 , dikodekan sebagai basis bijective 64 string.

Dengan ketiga input ini, enkode n sebagai string B berbasis kata sifat bi .

Uji kasus

Semua kasus uji menentukan input dalam urutan b , n , B .

Input:  "4" "" "8"
Output: ""

Input:  "A" "16" "2"
Output: "1112"

Input:  "2" "122" "A"
Output: "A"

Input:  "3" "31" "1"
Output: "1111111111"

Input:  ">" "Fe" "a"
Output: "RS"

Aturan

  • Anda dapat membaca tiga string dalam urutan yang mudah, dengan demikian, array string, representasi stringnya, digabungkan atau dipisahkan oleh pembatas karakter tunggal pilihan Anda.

  • Jika Anda memilih untuk mencetak output ke STDOUT, Anda hanya dapat mencetak simbol dan (opsional) baris baru.

  • Basis konversi bawaan semua jenis diperbolehkan.

  • Aturan standar berlaku.

Dennis
sumber

Jawaban:

6

CJam, 43

qA,s"?[a{A<":,:^+:Mf#):B;(bLa{(Bmd)M=\j\+}j

3 byte dimusnahkan dengan bantuan dari Dennis :) Cobalah online

Penjelasan:

Input diambil sebagai bnB, disatukan menjadi string tunggal.

q           read the input
A,s         make an array of numbers from 0 to 9 and convert to string
"?[a{A<"    push this string, which contains the ends of 3 character ranges:
             uppercase letters: ['A'…'[')
             lowercase letters: ['a'…'{')
             "<=>": ['<'…'?')
             they're in a special order for the symmetric difference below
:,          for each character, make a range of all characters smaller than it
:^          fold/reduce these 6 ranges using symmetric difference
+           concatenate with the digits before
:M          save in M; this is like the M from the statement,
             except it starts with a zero (for matching indexes)
f#          find the indexes in M of all characters from the input string
)           take out the last value from the array
:B;         save it in B and pop it
(           take out the first value
b           use it as a base and convert the remaining array to a number
             this works even if some of the digits are not in the "normal" range
La{…}j      calculate with memoized recursion, using an empty string for value 0
  (         decrement the number
  Bmd       divide by B and get the quotient and remainder
  )         increment the remainder (this is the last digit in bijective base B)
  M=        get the corresponding character from M
  \j        swap with the quotient, and convert the quotient recursively
  \+        swap again and concatenate
aditsu
sumber
Oh, Anda benar-benar dapat menggunakan operator konversi basis biasa untuk konversi basis pertama? Sekarang saya merasa konyol untuk menggunakan semua kode yang saya miliki dalam solusi saya. :) Saya tidak menyadari bahwa itu akan bekerja dengan nilai-nilai yang berada di luar jangkauan basis. Nah, kalau dipikir-pikir, tidak ada alasan bagus mengapa tidak.
Reto Koradi
@RetoKoradi ya, Anda bisa melakukannya; suatu hari nanti akan didokumentasikan :)
aditsu
Apakah Anda keberatan jika saya mengubah solusi saya untuk menggunakan konversi basis? Saya biasanya mencoba menghindari mengambil ide dari solusi lain. Tapi itu benar-benar mengganggu saya untuk membiarkan saya bertahan dengan pendekatan yang kurang optimal. Kemungkinan besar solusi Anda masih lebih pendek.
Reto Koradi
@RetoKoradi tidak masalah, silakan
aditsu
4

Pip, 84 80 78 byte

m:J[,tAZLCAZ"<=>"]p:$+(m@?^b)*(m@?a)**RV,#bs:m@?cWn:px:(mn-(p:n//s-!n%s)*s).xx

Repositori GitHub untuk Pip

Algoritma diadaptasi dari artikel Wikipedia. Berikut ini penjelasan untuk versi sebelumnya yang sedikit tidak ungolfed:

                 Implicit: initialize a,b,c from cmdline args; t=10;
                 AZ=uppercase alphabet; x=""
m:               Build lookup table m:
 (J,t)             0123456789 (i.e. join(range(10)))...
 .AZ               plus A-Z...
 .LCAZ             plus lowercase a-z...
 ."<=>"            plus <=>
f:{              Define f(a,b) to convert a from bijective base b to decimal:
 $+                Sum of...
  (m@?^a)            list of index of each character of a in m
  *                  multiplied item-wise by 
  b**RV,#a           b to the power of each number in reverse(range(len(a)))
}
t:{              Define t(a,b) to convert a from decimal to bijective base b:
 x:""              Reset x to empty string (not needed if only calling the function once)
 Wa{               While a is not zero:
  p:a//b-!a%b        p = ceil(a/b) - 1 (= a//b if a%b!=0, a//b-1 otherwise)
  x:m@(a-p*b).x      Calculate digit a-p*b, look up the corresponding character in m, and
                     prepend to x
  a:p                p becomes the new a
 }
 x                 Return x
}
(t               Return result of calling t with these arguments:
 (f                Result of calling f with these arguments:
  b                  2nd cmdline arg
  m@?a)              1st cmdline arg's decimal value
 m@?c              3rd cmdline arg's decimal value
)
                 Print (implicit)

Contoh dijalankan:

dlosc@dlosc:~/golf$ python pip.py bijectivebase.pip ">" "Fe" "a"
RS
DLosc
sumber
4

Oktaf, 166 byte

function z=b(o,x,n)
M=['1':'9','A':'Z','a':'z','<=>'];N(M)=1:64;n=N(n);x=polyval(N(x),N(o));z='';while x>0 r=mod(x,n);t=n;if r t=r;end;z=[M(t),z];x=fix(x/n)-(r<1);end

Versi multi-baris:

function z=b(o,x,n)
   M=['1':'9','A':'Z','a':'z','<=>'];
   N(M)=1:64;
   n=N(n);
   x=polyval(N(x),N(o));
   z='';
   while x>0
      r=mod(x,n);
      t=n;if r t=r;end;
      z=[M(t),z];
      x=fix(x/n)-(r<1);
   end
%end // implicit - not included above

Daripada membuat peta untuk mengkonversi karakter ke nilai indeks, saya hanya membuat tabel pencarian terbalik Nuntuk nilai ascii 1..'z'dan mengisinya dengan indeks pada nilai yang sesuai.

polyval mengevaluasi persamaan

c 1 x k + c 2 x k-1 + ... + c k x 0

menggunakan nilai input yang dikonversi dengan desimal sebagai vektor koefisien cdan basis asalnya x. (Sayangnya, Octave base2dec()menolak simbol di luar kisaran normal.)

Setelah kami memiliki nilai input pada basis 10, perhitungan nilai pada basis baru menjadi mudah.

Tes driver:

% script bijecttest.m
a=b('4','','8');
disp(a);
a=b('A','16','2');
disp(a);
a=b('2','122','A');
disp(a);
a=b('3','31','1');
disp(a);
a=b('>','Fe','a');
disp(a);

Hasil:

>> bijecttest

1112
A
1111111111
RS
>>
gelas kimia
sumber
2

Perl, 261 248 229 byte

sub t{$b=0;$b*=$_[1],$b+=ord($1=~y/0-9A-Za-z<=>/\0-A/r)while$_[0]=~/(.)/g;return$b}sub r{$n=$_[0];$n-=$m=($n-1)%$_[1]+1,$d=(chr$m)=~y/\0-A/0-9A-Za-z<=>/r.$d,$n/=$_[1]while$n;print$d}@a=split/,/,<>;r(t(@a[1],t@a[0],64),t@a[2],64)

multi-line, sedangkan loop tidak disatukan:

sub t{ # convert bijective base string to number
    $b=0;
    while($_[0]=~/(.)/g)
        {$b*=$_[1];$b+=ord($1=~y/0-9A-Za-z<=>/\0-A/r)}
    return$b}
sub r{ # convert number to bijective base string
    $n=$_[0];
    while($n)
        {$n-=$m=($n-1)%$_[1]+1;$d=(chr$m)=~y/\0-A/0-9A-Za-z<=>/r.$d;$n/=$_[1]}
    print$d}
@a=split/,/,<>; # parse input
r(t(@a[1],t@a[0],64),t@a[2],64)

tadalah fungsi untuk mengurai angka dari string bijective-base dari basis yang diberikan. radalah fungsi untuk menghasilkan string bijective-base dari basis yang diberikan dari angka. 3 parameter yang dipisahkan koma diurai dari stdin dan fungsinya disebut sesuai kebutuhan.

Mengonversi angka positif ke string basis bijective mirip dengan basis normal. Namun di mana Anda akan melakukan sesuatu seperti ini untuk basis normal:

string s = ""
while(n)
{
    c = (n % base)
    s = (c + '0') + s
    n -= c // not necessary because the division will take care of it
    n /= base 
}

Anda menyesuaikan mod untuk memberikan rentang dari 1 ke basis, bukan 0 ke basis - 1:

string s = ""
while(n)
{
    c = (((n-1) % base)+1)
    s = (c + '0') + s
    n -= c  // necessary in the case c = base
    n /= base 
}
samgak
sumber
2

Python 2, ... 317 307 298 311 byte

Jelas golf. Saya benar-benar benci bagaimana string tidak memiliki tugas item dan daftar tidak memiliki find. Saya akan mencari cara yang lebih baik daripada perbaikan cepat yang saya miliki sekarang.

Metode saya adalah mengonversi input ke angka desimal, lalu ke basis output, lalu mengonversinya ke basis bijective.

Sunting : Ditemukan bahwa program saya tidak berfungsi saat mengonversi ke Unary. Biayanya 13 byte untuk diperbaiki e=F(o)<2, dll.

Coba di sini

R=range;M="".join(map(chr,R(48,58)+R(65,91)+R(97,123)))+"<=>"
b,s,o=input()
F=M.find
e=F(o)<2
B=lambda n:n and B(n/F(o)-e)+M[n%F(o)+e]or""
n=B(sum(F(s[~j])*F(b)**j for j in R(len(s))))
i=n.find('0')
n=list(n)
while-~i:n=n[:i-1]+[M[F(n[i-1])-1]]+[o]+n[i+1:];n=n["0"==n[0]:];i="".join(n).find('0')
print"".join(n)
mbomb007
sumber
1
Saya setuju dengan kencing hewan peliharaan Python Anda.
DLosc
@Dosc, Terima kasih atas bantuan golfnya.
mbomb007
Apakah ini bowling ? : P
Optimizer
Daftar memiliki .index()metode .. Mengapa tidak menggunakannya daripada mencari? Selain itu, alih-alih menyimpan F(b)dan F(o)ke variabel, Anda hanya menggunakannya sekali, jadi hanya subkan jika diperlukan. Akhirnya, 'n'[2::5]lebih pendek dari ''.join(n)(ganti apostrof untuk backticks).
Kade
Juga, saya pikir Anda terlalu mempersulit ini .. Konversi dari basis kata string M ke b desimal seharusnya tidak lebih dari 35-40 byte. Desimal ke untaian bijective base B tidak akan lebih dari itu.
Kade
2

Python 2, 167 Bytes

Tidak ada trik khusus di sini, kecuali untuk [2::5]memotong untuk mendapatkan charset dengan jumlah byte yang lebih rendah.

x=range;A=`map(chr,x(49,58)+x(65,91)+x(97,123))`[2::5]+'<=>'
r=A.find
b,n,B=input()
B=r(B)+1
d=0;s=''
for c in n:d=d*-~r(b)+r(c)+1
while d:d-=1;s=A[d%B]+s;d/=B
print s

Tes:

"4","","8"     >>> (empty string)
">","Fe","a"   >>> RS
"3","31","1"   >>> 1111111111
"A","16","2"   >>> 1112
"2","122","A"  >>> A
Kade
sumber
2

CJam, 73 70 69 55 51 48 byte

Versi terbaru menggunakan operator konversi basis CJam untuk konversi dari basis sumber, yang saya tidak memikirkan sampai saya melihat solusi @ aditsu. Ini juga menerapkan tip terbaru oleh @Dennis untuk membuat string "digit" ( /codegolf//a/54348/32852 ), serta beberapa ide lain yang dibagikan dalam obrolan.

lA,s'[,_el^+"<=>"+:Lf#Ll#bLl#:K;{(Kmd)L=\}hs-]W%

Format input adalah nilainya, diikuti oleh basis sumber dan tujuan, dengan masing-masingnya pada baris terpisah. Untuk string kosong, biarkan baris pertama kosong. Input contoh:

122
2
A

Cobalah online

Penjelasan:

l       Get and interpret value from input.
A,s     Build the list of 64 "digits". Start with [0..9]
'[,     Build character sequence from \0 to Z.
_el     Lower case copy of the same sequence.
^       Symmetric set difference gives only letters from both sequences.
+       Concatenate with sequence of decimal digits, creating [0..9A..Za..z].
"<=>"   Remaining 4 characters.
+       Concatenate, resulting in full 64 character "digit" string.
:L      ... and store it in variable L for repeated use.
f#      Look up input characters in digit list.
Ll#     Get source base from input, and look up value in digit list.
b       Base conversion. This produces the input value.
Ll#     Get destination base from input, and look up value in digit list.
:K;     Store it in variable K for use in loop, and pop it off stack.
{       Loop for generating output digits.
  (       Decrement to get ceiling minus 1 after division.
  Kmd     Calculate divmod of current value with destination base.
  )       Increment mod to get 1-based value for digit.
  L=      Look up digit character for digit value.
  \       Swap. Digit stays on stack for output, remaining value is processed
          in next loop iteration until it is 0.
}h      End of loop for generating output digits.
s       Final value is 0. Covert it to a string.
-       And subtract it from second but last value. This eliminates the 0,
        as well as the second but last value if it was a \0 character.
]       Wrap digits in array.
W%      Reverse array, to get result from MSB to LSB.
Reto Koradi
sumber
0

Jelly , 22 byte

ØBḊ;“<=>”
i@€€¢ḅḃ2ƭ/ị¢

Cobalah online!

Erik the Outgolfer
sumber