Konversi di antara basis yang seimbang!

13

Basis seimbang:

Basis seimbang pada dasarnya sama dengan basis normal, kecuali bahwa digit bisa positif atau negatif, sedangkan dalam basis normal digit hanya bisa positif.

Dari sini, basis basa yang seimbang bdapat direpresentasikan sebagai balb- basa yang seimbang 4 = bal4.

Dalam definisi tantangan ini, rentang angka dalam basis basis yang seimbang badalah dari -(k - 1)ke b - k, di mana

k = ceil(b/2)

Contoh rentang angka di berbagai basis seimbang:

bal10:
  k = ceil(10/2) = 5
  range = -(5 - 1) to 10 - 5 = -4 to 5
        = -4, -3, -2, -1, 0, 1, 2, 3, 4, 5
bal5:
  k = ceil(5/2) = 3
  range = -(3 - 1) to 5 - 3 = -2 to 2
        = -2, -1, 0, 1, 2

Representasi angka dalam basis seimbang pada dasarnya sama dengan basis normal. Misalnya, representasi angka 27(basis 10) ke bal4(basis seimbang 4) adalah 2 -1 -1, karena

  2 -1 -1 (bal4)
= 2 * 4^2 + -1 * 4 + -1 * 1
= 32 + (-4) + (-1)
= 27 (base 10)

Tugas:

Tugas Anda adalah, diberi tiga input:

  • nomor yang akan dikonversi ( n)
    • input ini bisa fleksibel, lihat "Fleksibilitas I / O"
  • basis yang nsaat ini ada di ( b)
  • basis yang nakan dikonversi menjadi ( c)

Mana 2 < b, c < 1,000.

Kembalikan angka dalam crepresentasi basis seimbang n. Outputnya juga bisa fleksibel.

Program / fungsi harus menentukan panjang dari ninput itu sendiri.

Fleksibilitas I / O:

Input ndan output Anda dapat direpresentasikan dengan cara berikut:

  • definisi bahasa Anda tentang sebuah array
  • string, dengan karakter apa saja sebagai pemisah (mis. spasi, koma)

Contoh:

Perhatikan bahwa ini menggunakan array Python sebagai ndan output. Anda dapat menggunakan apa pun yang cocok dengan bahasa Anda, asalkan sesuai dengan definisi "I / O Fleksibilitas".

[2, -1, -1] 4 7 = [1, -3, -1]
[1, 2, 3, 4] 9 5 = [1, 2, 2, -1, 2]
[10, -9, 10] 20 5 = [1, 1, 1, -2, 1, 0]

Ini adalah kode-golf , jadi kode terpendek dalam byte menang!

code-golf math base-conversion clismique
sumber
Dalam jawaban pertama Anda, 4 bukan angka bal7 legal; Saya percaya jawabannya harus [1, -3, -1]. Dan saya mendapatkan jawaban berbeda untuk test case kedua ([1,2,2, -1,2]) dan test case ketiga ([1,1,0, -2,1,0]) juga ...?
Greg Martin
@GregMartin Ah, whoops - Saya menghitungnya dengan tangan, jadi pasti ada beberapa masalah. Terima kasih telah memperhatikan! Bisakah Anda memeriksa ulang solusi Anda, untuk berjaga-jaga?
clismique
@GregMartin @ Qwerp-Derp Test case ketiga adalah[1,1,1,-2,1,0]
ngenisis

Jawaban:

2

Mathematica, 85 byte

#~FromDigits~#2~IntegerDigits~#3//.{p___,a_:0,b_,q___}/;b>⌊#3/2⌋:>{p,a+1,b-#3,q}&

Penjelasan

#~FromDigits~#2

Konversi #1(1 tersirat - input 1, daftar digit) menjadi basis integer #2(input 2).

... ~IntegerDigits~#3

Ubah integer yang dihasilkan menjadi basis #3(input 3), buat daftar digit.

... //.{p___,a_:0,b_,q___}/;b>⌊#3/2⌋:>{p,a+1,b-#3,q}

Berganti-ganti daftar digit; jika angka lebih besar dari lantai ( #3/ 2), maka kurangi #3dari itu dan tambahkan 1ke digit ke kiri. Jika tidak ada apa-apa di sebelah kiri, masukkan 0dan tambahkan 1.

JungHwan Min
sumber
Biasanya disarankan untuk sedikit membicarakan solusi Anda, dan jelaskan untuk orang yang mungkin tidak tahu Mathematica.
ATaco
@ATaco Menambahkan penjelasan!
JungHwan Min
Saya sedikit bingung dengan ini. Saya belum pernah melihat pola opsional yang digunakan di mana pun selain definisi fungsi. Anda tidak perlu bagian luar {...}karena hanya ada satu aturan penggantian.
ngenisis
1
@JungHwanMin Benar, saya kira yang membingungkan saya adalah bagaimana hal ini memengaruhi pertandingan p___. Apakah ini menemukan yang terpendek p___diikuti oleh salah satu a_,b_atau b_, atau apakah itu memeriksa seluruh pola yang memerlukan masing-masing pola opsional dan kemudian secara progresif menjatuhkan pola-pola opsional sampai menemukan kecocokan (atau beberapa opsi ketiga)?
ngenisis
1
@ngenisis Saya yakin saya salah dalam komentar sebelumnya (dihapus), mengamati hasilnya FixedPointList[k=#3;#/.{p___,a_:0,b_,q___}/;b>⌊k/2⌋:>{p,a+1,b-k,q}&, #~FromDigits~#2~IntegerDigits~#3]&. {p___,a_,b_,q___}dicocokkan terlebih dahulu (untuk semua kemungkinan p), dan kemudian {p___,b_,q___}dicocokkan. Penggantian kedua hanya berlaku ketika bberada di awal karena jika ada bdi tengah yang memenuhi syarat, {p___,a_,b_,q___}akan cocok dengan itu sebagai gantinya.
JungHwan Min
1

Perl 6 , 121 byte

->\n,\b,\c{sub f{sum [R,](@^n)Z*($^b X**0..*)}
first {f(b,n)==f c,$_},map {[$_-($_>floor c/2)*c for .base(c).comb]},0..*}

Solusi brute-force lambat.

Bagaimana itu bekerja:

  • map {[ .base(c).comb]}, 0..*- Hasilkan urutan malas dari bilangan asli dalam basis c, dengan masing-masing angka direpresentasikan sebagai array angka.
  • $_ - ($_ > floor c/2) * c- Transformasikan dengan mengurangi cdari setiap digit yang lebih besar dari lantai (c / 2).
  • first { f(b, n) == f(c, $_) }, ...- Dapatkan larik pertama dari urutan itu yang ketika ditafsirkan sebagai cnomor basis , sama dengan array input yang nditafsirkan sebagai basisb nomor .
  • sub f { sum [R,](@^n) Z* ($^b X** 0..*) }- Fungsi helper yang mengubah array @^nmenjadi angka dalam basis $^b, dengan mengambil jumlah produk yang dihasilkan dengan cara zip array terbalik dengan urutan kekuatan basis.
seseorang
sumber
1

JavaScript (ES6), 89 byte

(n,b,c,g=(n,d=n%c,e=d+d<c)=>[...(n=n/c+!e|0)?g(n):[],e?d:d-c])=>g(n.reduce((r,d)=>r*b+d))

100 byte bekerja untuk nilai negatif dari n.

(n,b,c,g=(n,d=(n%c+c)%c)=>[...(n-=d,n/=c,d+d<c||(d-=c,++n),n?g(n):[]),d])=>g(n.reduce((r,d)=>r*b+d))
Neil
sumber
0

Mathematica, 118 114 byte

IntegerDigits[#3~FromDigits~#2,k=⌊#/2⌋;#]//.{{a_,x___}/;a>k:>{1,a-#,x},{x___,a_,b_,y___}/;b>k:>{x,a+1,b-#,y}}&

⌊dan ⌋adalah karakter 3-byte U+230Adan U+230B, masing-masing. Konversi #3ke basis 10dari basis #2, lalu dikonversi ke basis #(sehingga urutan argumen dibalik dari contoh). Jika ada digit yang lebih besar dari digit maksimum yang diizinkan k=⌊#/2⌋, kurangi digit itu dengan #dan tambah digit berikutnya ke atas (mungkin perlu dituliskan sebelumnya 1). Terus lakukan ini sampai semua digit kurang dari k.

ngenisis
sumber