Mixed Base Conversion Background

Most people on here should be familiar with several base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, the number 1234516 would represent

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


Note that we're usually not expecting the base (here, 16) to change from digit to digit.

A generalisation of these usual positional systems allows you to use a different numerical base for each digit. E.g. if we were alternating between decimal and binary system (starting with base 10 in the least significant digit), the number 190315[2,10] would represent

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


We denote this base as [2,10]. The right-most base corresponds to the least significant digit. Then you go through the bases (to the left) as you go through the digits (to the left), wrapping around if there are more digits than bases.

For further reading, see Wikipedia.

The Challenge

Write a program or function which, given a list of digits D an input base I and an output base O, converts the integer represented by D from base I to base O. You may take input via STDIN, ARGV or function argument and either return the result or print it to STDOUT.

You may assume:


that the numbers in I and O are all greater than 1.
the I and O are non-empty.
that the input number is valid in the given base (i.e., no digit larger than its base).


D could be empty (representing 0) or could have leading zeroes. Your output should not contain leading zeroes. In particular, a result representing 0 should be returned as an empty list.

You must not use any built-in or 3rd-party base conversion functions.

This is code golf, the shortest answer (in bytes) wins.

Examples

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]     []
CJam, 45

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


Finally I found a good use of j.

How it works

Long ArrayList Block j executes the block which takes an integer as the parameter, and Long j will call this block recursively in the block. It will also store the values returned by the block in an internal array, which is initialized by the array parameter. It will not execute the block if the input is already in the array, and the value in the array is returned instead.

So if I initialize it with an array of an empty array, the empty array will be returned for input 0, and the block will be executed for any other input.

q~_,@m&gt;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&gt;0@{@(:T+@T*@+}/\;{\)_@+@@md@@}h;;_{}?]W%`


Input should be O I D.

Examples:

$ while read; do &lt;&lt;&lt;$REPLY ./cjam-0.6.2.jar &lt;(echo 'q~_,@m&gt;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]
""
""


How it works

q~           “ Read the input and evaluate. ";
_,@m&gt;        " 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. ";