12
\$\begingroup\$

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]     []
\$\endgroup\$
  • \$\begingroup\$ May I require an infinite list as a base description, or I have to infinitify it myself? \$\endgroup\$ – John Dvorak Sep 17 '14 at 14:24
  • \$\begingroup\$ @JanDvorak You mean if you can expect the base lists to already have a sufficient number of repetitions to cover all digits? No, you'll have to do the wrapping around or repeating yourself. \$\endgroup\$ – Martin Ender Sep 17 '14 at 14:25
  • \$\begingroup\$ I assume getting an empty list as a base is UB, but may we assume that list of digits is non-empty? Also, what's the policy on trailing zeroes? \$\endgroup\$ – John Dvorak Sep 17 '14 at 14:39
  • \$\begingroup\$ Namely, I don't mind an empty list on input, but I'd like to produce [] if the input is [0] \$\endgroup\$ – John Dvorak Sep 17 '14 at 14:40
  • \$\begingroup\$ May I request and produce a list of digits in the reverse order (LSD first)? \$\endgroup\$ – John Dvorak Sep 17 '14 at 14:44
6
\$\begingroup\$

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. ";
\$\endgroup\$
  • \$\begingroup\$ I've got to stop using array rotation just because CJam has it... That _{}? trick is really neat. \$\endgroup\$ – Dennis Sep 17 '14 at 20:38
  • \$\begingroup\$ @sudo {}e| is the same. \$\endgroup\$ – jimmy23013 Nov 23 '14 at 10:51
  • \$\begingroup\$ Would you mind adding an explanation for the version using j? :) \$\endgroup\$ – Martin Ender Nov 23 '14 at 12:05
  • \$\begingroup\$ @MartinBüttner Done. \$\endgroup\$ – jimmy23013 Nov 23 '14 at 12:57
3
\$\begingroup\$

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 "".

\$\endgroup\$
  • 4
    \$\begingroup\$ OMG Never seen a 62 bytes CJam program :D \$\endgroup\$ – Optimizer Sep 17 '14 at 18:37
  • \$\begingroup\$ @Optimizer This is probably my longest CJam submission. \$\endgroup\$ – Esolanging Fruit May 9 '17 at 1:33
  • \$\begingroup\$ @Challenger5 codegolf.stackexchange.com/a/51238/12012 \$\endgroup\$ – Dennis May 9 '17 at 1:55
  • \$\begingroup\$ @Dennis That wasn't code-golf, was it? \$\endgroup\$ – Esolanging Fruit May 9 '17 at 1:58
  • \$\begingroup\$ @Challenger5 It wasn't, but I doubt a golfed version would be shorter than 200 bytes. \$\endgroup\$ – Dennis May 9 '17 at 6:05
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Don't say "waste" ;) \$\endgroup\$ – Martin Ender Sep 17 '14 at 19:01
  • \$\begingroup\$ You should be able to golf it down to 286 bytes: repl.it/JbIk \$\endgroup\$ – Zacharý Jul 20 '17 at 18:12
  • \$\begingroup\$ @Zacharý This was my first golf I think, I'm sure it can be much shorter than that! Feersum's answer demonstrates that quite well I think. If you want you can edit this answer, but I'm afraid I'm not particularly motivated to improve it. \$\endgroup\$ – FryAmTheEggman Jul 20 '17 at 19:36
2
\$\begingroup\$

APL, 78

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

Examples:

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
\$\endgroup\$
  • \$\begingroup\$ Just for general education – with built-ins: {{⍵↓⍨1⍳⍨×⍵}(99⍴⎕)⊤⍵⊥⍨⎕⍴⍨⍴⍵} takes D as right argument, then asks for I and O. \$\endgroup\$ – Adám Mar 23 '16 at 16:35
2
\$\begingroup\$

Python 2 - 122

Very straightforward, didn't manage to find any special golf tricks on this one.

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

Ungolfed:

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

Edit: 116-byte program version thanks to 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

This version accepts comma-separated input e.g. [1,9,0,3,1,5], [2,10], [10]

\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman I'm not sure how it could accept input with quotes but separating the arrays with commas works. \$\endgroup\$ – feersum Sep 18 '14 at 20:51
1
\$\begingroup\$

k2 - 83 74 char

Function taking one argument. This was just a lot better suited for K than J, which is why I'm not using J. It would just be a load of boxing/unboxing garbage, and nobody wants that. This is in the k2 dialect (may require some adaptation to work in the open source implementation Kona), but I'll change this to k4 if I can golf it down shorter there.

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

I will note that I take a stand for pickiness here and say that one item lists have to be input as such. ,2 is a list of one item, that item being the scalar 2. Often scalars and 1-item lists are interchangable, but there is logic in this golf that relies on the assumption of list arguments.

To explain the golf, I'll break it into two parts. F is the golf, L is the main loop that calculates the output. The exact mechanism of the looping is that L is applied to its arguments repeatedly until the second argument is zero, then that result is returned. (This is the .[L]/ part.)

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

By explosion:

{_(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

In action:

  {:[#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
 ()
 ())
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 67 bytes

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

Try it

Expanded:

{  # 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
}

In case you aren't sure what triangle reduce does:

[\*] 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

If I could take the inputs reversed, and output the reverse, it would be 47 bytes.

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

Try it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.