Mixed Base Conversion
CJam, 45
q~_,@m>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>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 should be O I D
.
Examples:
$ 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]
""
""
How it works
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. ";
CJam, 62 61 59 57 bytes
q~Wf%~UX@{1$*@+\@(+_W=@*@\}/;\;{\(+_W=@\md@@}h;;]W%_0=!>p
Reads the input arrays as [O I D]
from STDIN. Try it online.
How it works
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. ";
Test cases
$ 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] ]'
""
Note that empty strings and empty arrays are indistinguishable to CJam, so []p
prints ""
.
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 [])
I messed up the order of the arguments by accident, so I had to reverse them. I will work on the slice-fu to get the lists to work in the other direction later, I already wasted my entire lunch break :p
Fixed