Konversi Basis Campuran

12

Latar Belakang

Kebanyakan orang di sini harus terbiasa dengan beberapa sistem dasar: desimal, biner, heksadesimal, oktal. Misalnya dalam sistem heksadesimal, angka 12345 16 akan mewakili

1*16^4 + 2*16^3 + 3*16^2 + 4*16^1 + 5*16^0

Perhatikan bahwa kami biasanya tidak mengharapkan basis (di sini, 16) berubah dari digit ke digit.

Generalisasi dari sistem posisi yang biasa ini memungkinkan Anda untuk menggunakan basis numerik yang berbeda untuk setiap digit. Misalnya jika kita berganti-ganti antara sistem desimal dan biner (dimulai dengan basis 10 dalam digit paling signifikan), angka 190315 [2,10] akan mewakili

1*10*2*10*2*10 + 9*2*10*2*10 + 0*10*2*10 + 3*2*10 + 1*10 + 5 = 7675

Kami menyatakan basis ini sebagai [2,10]. Basis paling kanan sesuai dengan digit paling tidak signifikan. Kemudian Anda pergi melalui basis (ke kiri) saat Anda pergi melalui digit (ke kiri), membungkus jika ada lebih banyak digit daripada basis.

Untuk bacaan lebih lanjut, lihat Wikipedia .

Tantangan

Tulis program atau fungsi yang, dengan memberikan daftar Dbasis input Idan basis output O, mengubah bilangan bulat yang diwakili oleh Ddari basis Ike basis O. Anda dapat mengambil input melalui STDIN, ARGV atau argumen fungsi dan mengembalikan hasilnya atau mencetaknya ke STDOUT.

Anda mungkin berasumsi:

  • bahwa angka-angka Idan Osemua lebih besar dari 1.
  • yang Idan Onon-kosong.
  • bahwa nomor input valid dalam basis yang diberikan (yaitu, tidak ada digit lebih besar dari basisnya).

Dbisa kosong (mewakili 0) atau bisa memimpin nol. Output Anda tidak boleh mengandung nol terkemuka. Secara khusus, hasil yang mewakili 0harus dikembalikan sebagai daftar kosong.

Anda tidak boleh menggunakan fungsi konversi basis bawaan atau pihak ketiga.

Ini kode golf, jawaban terpendek (dalam byte) menang.

Contohnya

D               I                  O        Result
[1,0,0]         [10]               [2]      [1,1,0,0,1,0,0]
[1,0,0]         [2]                [10]     [4]
[1,9,0,3,1,5]   [2,10]             [10]     [7,6,7,5]
[1,9,0,3,1,5]   [2,10]             [4,3,2]  [2,0,1,1,0,1,3,0,1]
[52,0,0,0,0]    [100,7,24,60,60]   [10]     [3,1,4,4,9,6,0,0]
[0,2,10]        [2,4,8,16]         [42]     [1,0]
[]              [123,456]          [13]     []
[0,0]           [123,456]          [13]     []
Martin Ender
sumber
Bolehkah saya memerlukan daftar tak terbatas sebagai deskripsi dasar, atau saya harus infinitify sendiri?
John Dvorak
@ JanDvorak Maksud Anda jika Anda dapat mengharapkan daftar basis sudah memiliki jumlah pengulangan yang cukup untuk mencakup semua digit? Tidak, Anda harus melakukan balutan atau mengulangi sendiri.
Martin Ender
Saya menganggap mendapatkan daftar kosong sebagai basis adalah UB, tetapi dapatkah kita berasumsi bahwa daftar angka tidak kosong? Juga, apa kebijakan untuk membuntuti nol?
John Dvorak
Yaitu, saya tidak keberatan daftar kosong pada input, tapi saya ingin menghasilkan []jika inputnya[0]
John Dvorak
Bolehkah saya meminta dan menghasilkan daftar angka dalam urutan terbalik (LSD dulu)?
John Dvorak

Jawaban:

6

CJam, 45

q~_,@m>0@{@(:T+@T*@+}/\;La{\)_@+@@md@@j@+}jp;

Akhirnya saya menemukan penggunaan yang bagus j.

Bagaimana itu bekerja

Long ArrayList Block jmengeksekusi blok yang mengambil integer sebagai parameter, dan Long jakan memanggil blok ini secara rekursif di blok. Ini juga akan menyimpan nilai-nilai yang dikembalikan oleh blok dalam array internal, yang diinisialisasi oleh parameter array. Ini tidak akan menjalankan blok jika input sudah ada dalam array, dan nilai dalam array dikembalikan sebagai gantinya.

Jadi jika saya menginisialisasi dengan array dari array kosong, array kosong akan dikembalikan untuk input 0, dan blok akan dieksekusi untuk input lainnya.

q~_,@m>0@{@(:T+@T*@+}/\;     " See below. Stack: O decoded-D ";
La                           " Initialized the value with input 0 as empty list. ";
{
  \)_@+@@md@@                " See below. Stack: remainder O quotient ";
  j                          " Call this block recursively except when the same quotient has
                               appeared before, which is impossible except the 0.
                               Stack: remainder O returned_list ";
  @+                         " Append the remainder to the list. ";
}j
p;                           " Format and output, and discard O. ";

CJam, 49 48

q~_,@m>0@{@(:T+@T*@+}/\;{\)_@+@@md@@}h;;_{}?]W%`

Input seharusnya O I D.

Contoh:

$ while read; do <<<$REPLY ./cjam-0.6.2.jar <(echo 'q~_,@m>0@{@(:T+@T*@+}/\;{\)_@+@@md@@}h;;_{}?]W%`');echo; done
[2] [10] [1 0 0]
[10] [2] [1 0 0]
[10] [2 10] [1 9 0 3 1 5]
[4 3 2] [2 10] [1 9 0 3 1 5]
[10] [100 7 24 60 60] [52 0 0 0 0]
[42] [2 4 8 16] [0 2 10]
[13] [123 456] []
[13] [123 456] [0 0]
[1 1 0 0 1 0 0]
[4]
[7 6 7 5]
[2 0 1 1 0 1 3 0 1]
[3 1 4 4 9 6 0 0]
[1 0]
""
""

Bagaimana itu bekerja

q~           “ Read the input and evaluate. ";
_,@m>        " Rotate I to the right by the length of D. ";
0@{          " For each item in D, with the result initialized to 0: ";
  @(:T+      " Rotate I to the left, and set the original first item to T. ";
  @T*@+      " Calculate result * T + current. ";
}/
\;           " Discard I. ";
{            " Do: ";
  \)_@+      " Rotate O to the right, and get a copy of the original last item. ";
  @@md       " Calculate divmod. ";
  @@         " Move O and the quotient to the top of the stack. ";
}h           " ...while the quotient is not 0. ";
;;           " Discard O and the last 0. ";
_{}?         " If the last item is still 0, discard it. ";
]W%          " Collect into an array and reverse. ";
`            " Turn the array into its string representation. ";
jimmy23013
sumber
Saya harus berhenti menggunakan rotasi array hanya karena CJam memilikinya ... _{}?Trik itu benar-benar rapi.
Dennis
@udo {}e|adalah sama.
jimmy23013
Maukah Anda menambahkan penjelasan untuk versi yang digunakan j? :)
Martin Ender
@ MartinBüttner Selesai.
jimmy23013
3

CJam, 62 61 59 57 byte

q~Wf%~UX@{1$*@+\@(+_W=@*@\}/;\;{\(+_W=@\md@@}h;;]W%_0=!>p

Membaca array input [O I D]dari STDIN. Cobalah online.

Bagaimana itu bekerja

q~         " Read from STDIN and evaluate the input. Result: [O I D]                      ";
Wf%~       " Reverse each of the three arrays and dump them on the stack.                 ";
UX@        " Push U (0) and X (1); rotate D on top of both.                               ";
{          " For each N in D:                                                             ";
  1$*      "   N *= X                                                                     ";
  @+       "   U += N                                                                     ";
  \@(+     "   I := I[1:] + I[:1]                                                         ";
  _W=@*    "   X *= I[-1]                                                                 ";
  @\       "   ( U I X ) ↦ ( I U X )                                                      ";
}/         "                                                                              ";
;\;        " Discard I and X.                                                             ";
{          " R := []; Do:                                                                 ";
  \(+      "   O := O[1:] + O[:1]                                                         ";
  _W=@\md  "   R += [U / O[-1]], U %= O[-1]                                               ";
  @@       "   ( O U R[-1] ) ↦ ( R[-1] O U )                                              ";
}/         " While U                                                                      ";
;;]        " Discard U and O.                                                             ";
W%         " Reverse R.                                                                   ";
_0=!>      " Execute R := R[!R[0]:] to remove a potential leading zero.                   ";
p          " Print a string presentation of R.                                            ";

Uji kasus

$ cjam mixed-base.cjam <<< '[ [2]     [10]             [1 0 0]       ]'
[1 1 0 0 1 0 0]
$ cjam mixed-base.cjam <<< '[ [10]    [2]              [1 0 0]       ]'
[4]
$ cjam mixed-base.cjam <<< '[ [10]    [2 10]           [1 9 0 3 1 5] ]'
[7 6 7 5]
$ cjam mixed-base.cjam <<< '[ [4 3 2] [2 10]           [1 9 0 3 1 5] ]'
[2 0 1 1 0 1 3 0 1]
$ cjam mixed-base.cjam <<< '[ [10]    [100 7 24 60 60] [52 0 0 0 0]  ]'
[3 1 4 4 9 6 0 0]
$ cjam mixed-base.cjam <<< '[ [42]    [2 4 8 16]       [0 2 10]      ]'
[1 0]
$ cjam mixed-base.cjam <<< '[ [13]    [123 456]        []            ]'
""
$ cjam mixed-base.cjam <<< '[ [13]    [123 456]        [0 0]         ]'
""

Perhatikan bahwa string kosong dan array kosong bisa dibedakan ke CJam, sehingga []pcetakan "".

Dennis
sumber
4
OMG Tidak pernah melihat program CJam 62 byte: D
Optimizer
@Optimizer Ini mungkin pengiriman CJam terlama saya.
Buah Esolanging
@ Dennis Itu bukan kode-golf , bukan?
Buah Esolanging
@ Challenger5 Bukan, tapi saya ragu versi golf akan lebih pendek dari 200 byte.
Dennis
2

Python 2 - 318

from operator import *
d,i,o=input()
c=len
def p(l):return reduce(mul,l,1)
n=sum(x[1]*p((i[-x[0]%c(i)-1:]+x[0]/c(i)*i)[1:]) for x in enumerate(d[::-1]))
r=[]
j=1
t=[]
k=c(o)
while p(t)*max(o)<=n:t=(o[-j%k-1:]+j/k*o)[1:];j+=1
while j:j-=1;t=(o[-j%k-1:]+j/k*o)[1:];r+=[n/p(t)];n%=p(t)
print (r if r[0] else [])

Saya mengacaukan urutan argumen secara tidak sengaja, jadi saya harus membalikkannya. Saya akan bekerja pada slice-fu untuk mendapatkan daftar untuk bekerja di arah lain nanti, saya sudah membuang seluruh istirahat makan siang saya: p

Tetap

FryAmTheEggman
sumber
Jangan katakan "buang";)
Martin Ender
Anda harus dapat golf ke 286 byte: repl.it/JbIk
Zacharý
@ Zacharý Ini golf pertama saya, saya pikir, saya yakin ini bisa lebih pendek dari itu! Jawaban Feersum menunjukkan hal itu dengan cukup baik menurut saya. Jika mau, Anda dapat mengedit jawaban ini, tetapi saya khawatir saya tidak terlalu termotivasi untuk memperbaikinya.
FryAmTheEggman
2

APL, 78

{1↓(⊃1⌷⍺)({t←⍺[(⍴⍺)|⍴⍵]
(⌊0⌷⍵÷t)(t|0⌷⍵),1↓⍵}⍣{0=0⌷⍵}),+/(0,⍵)×⌽×\1,(⍴⍵)⍴⌽⊃0⌷⍺}

Contoh:

f←{1↓(⊃1⌷⍺)({t←⍺[(⍴⍺)|⍴⍵]
  (⌊0⌷⍵÷t)(t|0⌷⍵),1↓⍵}⍣{0=0⌷⍵}),+/(0,⍵)×⌽×\1,(⍴⍵)⍴⌽⊃0⌷⍺}
(,10)(,2) f 1 0 0
1 1 0 0 1 0 0
(,2)(,10) f 1 0 0
4
(2 10)(,10) f 1 9 0 3 1 5
7 6 7 5
(2 10)(4 3 2) f 1 9 0 3 1 5
2 0 1 1 0 1 3 0 1
(100 7 24 60 60)(,10) f 52 0 0 0 0
3 1 4 4 9 6 0 0
(2 4 8 16)(,42) f 0 2 10
1 0
(123 456)(,13) f ⍬

⍴(123 456)(,13) f ⍬
0
(123 456)(,13) f 0 0

⍴(123 456)(,13) f 0 0
0
jimmy23013
sumber
Hanya untuk pendidikan umum - dengan built-in: {{⍵↓⍨1⍳⍨×⍵}(99⍴⎕)⊤⍵⊥⍨⎕⍴⍨⍴⍵}menganggap D sebagai argumen yang benar, lalu meminta I dan O.
Adám
2

Python 2 - 122

Sangat mudah, tidak berhasil menemukan trik golf khusus yang satu ini.

def f(D,I,O):
 n,i,l=0,-len(D),[]
 for d in D:n=n*I[i%len(I)]+d;i+=1
 while n:i-=1;b=O[i%len(O)];l=[n%b]+l;n/=b
 return l

Tidak Disatukan:

def f(D,I,O):
    n = 0
    for i in range(len(D)):
        dn = len(D) - i
        n = n * I[-dn % len(I)] + D[i]
    l = []
    i = 0
    while n:
        i -= 1
        b = O[i%len(O)]
        l = [n%b] + l
        n /= b
    return l

Sunting: versi program 116-byte berkat FryAmTheEggman

D,I,O=input()
n,i,l=0,-len(D),[]
for d in D:n=n*I[i%len(I)]+d;i+=1
while n:i-=1;b=O[i%len(O)];l=[n%b]+l;n/=b
print l

Versi ini menerima input yang dipisahkan koma, mis [1,9,0,3,1,5], [2,10], [10]

feersum
sumber
@FryAmTheEggman Saya tidak yakin bagaimana bisa menerima input dengan tanda kutip tetapi memisahkan array dengan koma berfungsi.
feersum
1

k2 - 83 74 char

Berfungsi mengambil satu argumen. Ini jauh lebih cocok untuk K daripada J, itulah sebabnya saya tidak menggunakan J. Itu hanya akan menjadi sampah tinju / unboxing, dan tidak ada yang menginginkan itu. Ini dalam dialek k2 (mungkin memerlukan beberapa adaptasi untuk bekerja dalam implementasi open source Kona), tapi saya akan mengubahnya ke k4 jika saya dapat menurunkannya lebih pendek di sana.

{:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}

Saya akan perhatikan bahwa saya mengambil sikap pilih-pilih di sini dan mengatakan bahwa satu daftar barang harus dimasukkan sebagai masukan. ,2adalah daftar satu item, item tersebut adalah skalar 2. Seringkali daftar skalar dan 1-item dapat dipertukarkan, tetapi ada logika dalam golf ini yang bergantung pada asumsi argumen daftar.

Untuk menjelaskan golf, saya akan memecahnya menjadi dua bagian. Fadalah golf, Ladalah loop utama yang menghitung output. Mekanisme yang tepat dari perulangan adalah yang Lditerapkan pada argumennya berulang kali hingga argumen kedua adalah nol, maka hasilnya dikembalikan. (Ini .[L]/bagiannya.)

L: {_(x,y!*z;y%*z;1!z)}
F: {:[#x@:|&~&\~x;|*{x 1}.[L]/(();+/x*1*\(1-#x)#y;|z);()]}

Dengan ledakan:

{_(x,y!*z;y%*z;1!z)}  /function, args x y z
  (      ;    ;   )   / update each arg as follows:
               1!z    /  new z: rotate z left
            *z        /  head of z (current base digit)
          y%          /  y divided by that
 _                    /  new y: floor of that
     y!*z             /  y modulo head of z
   x,                 /  new x: append that to old x

{:[#x@:|&~&\~x;|*{x 1}.[L]/(();+/x*1*\(1-#x)#y;|z);()]}  /function, args x y z
            ~x                                           /find the 0s in x
          &\                                             /find leading zeros
        &~                                               /indices of digits that aren't
    x@ |                                                 /those items from x, reverse order
    x :                                                  /assign to x
 :[#          ;                                      ]   /if length is 0:
                                                   ()    / return empty list
                                                  ;      /else:
                      .[L]/                              / loop L repeatedly
                 {x 1}                                   / until y = 0
                           (  ;               ;  )       / starting with args:
                            ()                           /  Lx: empty list
                                       1-#x              /  number of input digits, minus 1
                                      (    )#y           /  cyclically extend base leftward
                                   1*\                   /  running product, start at 1
                                 x*                      /  multiply digits by these
                               +/                        /  Ly: sum of the above
                                               |z        /  Lz: out base, reverse order
               |*                                        / first elem of result, reversed

Beraksi:

  {:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}[1 0 0; ,10; ,2]
1 1 0 0 1 0 0
  f:{:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}
  f[1 0 0; ,2; ,10]
,4
  f .' ((1 9 0 3 1 5; 2 10;           ,10)  /f apply each
>       (1 9 0 3 1 5; 2 10;           4 3 2)
>       (52 0 0 0 0;  100 7 24 60 60; ,10)
>       (0 2 10;      2 4 8 16;       ,42)
>       (();          123 456;        ,13)
>       (0 0;         123 456;        ,13))
(7 6 7 5
 2 0 1 1 0 1 3 0 1
 3 1 4 4 9 6 0 0
 1 0
 ()
 ())
algoritme hiu
sumber
0

Perl 6 , 67 byte

{[R,] [+]([R,](@^a)Z*1,|[\*] |[R,](@^b)xx*).polymod: |[R,](@^c)xx*}

Cobalah

Diperluas:

{  # bare block lambda with placeholder parameters @a,@b,@c

  [R,]    # reduce the following using reverse meta op 「R」 combined with 「,」 op
          # (shorter than 「reverse」)

    [+](  # sum

        [R,](@^a) # reverse of first argument

      Z[*]        # zipped using &infix:<*> with the following

        1,
        |                    # slip the following in (flattens)
          [\*]               # triangle reduce

            |[R,](@^b) xx*   # reverse of second argument repeated infinitely
    )

    .polymod: |[R,](@^c) xx* # moduli the reverse of third argument repeated
}

Jika Anda tidak yakin apa yang dilakukan pengurangan segitiga:

[\*] 1,2,3,4,5
# 1, 1*2, 1*2*3, 1*2*3*4, 1*2*3*4*5
# 1,   2,     6,      24,       120

Jika saya bisa mengambil input terbalik, dan output sebaliknya, itu akan menjadi 47 byte.

{[+](@^a Z*1,|[\*] |@^b xx*).polymod: |@^c xx*}

Cobalah

Brad Gilbert b2gills
sumber