All your bijective base are belong to us

Question

Background

A bijective base b numeration, where b is a positive integer, is a bijective positional notation that makes use of b symbols with associated values of 1 to b.

Unlike its non-bijective counterpart, no symbol has a value of 0. This way, each non-negative integer n has a unique representation in bijective base b.

Popular bijective numerations include unary, bijective base 2 (used in bzip2's run-length encoding) and bijective base 26 (used to number columns in spreadsheets).

Definition

In this challenge, we define the set M of symbols as

123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz<=>

and a function i from M to the natural number such that i('1') = 1, …, i('>') = 64.

Given a base b between 1 and 64 (both inclusive), we define that each non-negative integer n corresponds to the string a_k…a₀, consisting of symbols of M, such that n = b^ki(a_k)+…+b⁰i(a₀).

This correspondence is well-defined and bijective. Since an empty sum is defined as 0, the integer 0 can be encoded as an empty string.

Task

Accept three strings as input:

• An input base b between 1 and 64, encoded as a bijective base 64 string.

• A non-negative integer n, encoded as a bijective base b string.

• An output base B between 1 and 64, encoded as a bijective base 64 string.

Given these three inputs, encode n as a bijective base B string.

Test cases

All test cases specify the input in the order b, n, B.

Input:  "4" "" "8"
Output: ""

Input:  "A" "16" "2"
Output: "1112"

Input:  "2" "122" "A"
Output: "A"

Input:  "3" "31" "1"
Output: "1111111111"

Input:  ">" "Fe" "a"
Output: "RS"

Rules

• You may read the three strings in any convenient order, as such, an array of strings, a string representation thereof, concatenated or separated by single-character delimiters of your choice.

• If you choose to print the output to STDOUT, you may only print the symbols and (optionally) a trailing newline.

• Base conversion built-ins of all kinds are allowed.

• Standard code-golf rules apply.

Answer 1

CJam, 43

qA,s"?[a{A<":,:^+:Mf#):B;(bLa{(Bmd)M=\j\+}j

3 bytes eradicated with help from Dennis :) Try it online

Explanation:

The input is taken as bnB, concatenated into a single string.

q           read the input
A,s         make an array of numbers from 0 to 9 and convert to string
"?[a{A<"    push this string, which contains the ends of 3 character ranges:
             uppercase letters: ['A'…'[')
             lowercase letters: ['a'…'{')
             "<=>": ['<'…'?')
             they're in a special order for the symmetric difference below
:,          for each character, make a range of all characters smaller than it
:^          fold/reduce these 6 ranges using symmetric difference
+           concatenate with the digits before
:M          save in M; this is like the M from the statement,
             except it starts with a zero (for matching indexes)
f#          find the indexes in M of all characters from the input string
)           take out the last value from the array
:B;         save it in B and pop it
(           take out the first value
b           use it as a base and convert the remaining array to a number
             this works even if some of the digits are not in the "normal" range
La{…}j      calculate with memoized recursion, using an empty string for value 0
  (         decrement the number
  Bmd       divide by B and get the quotient and remainder
  )         increment the remainder (this is the last digit in bijective base B)
  M=        get the corresponding character from M
  \j        swap with the quotient, and convert the quotient recursively
  \+        swap again and concatenate

Answer 2

Pip, 84 80 78 bytes

m:J[,tAZLCAZ"<=>"]p:$+(m@?^b)*(m@?a)**RV,#bs:m@?cWn:px:(mn-(p:n//s-!n%s)*s).xx

GitHub repository for Pip

Algorithms adapted from the Wikipedia article. Here's the explanation for a slightly ungolfed earlier version:

                 Implicit: initialize a,b,c from cmdline args; t=10;
                 AZ=uppercase alphabet; x=""
m:               Build lookup table m:
 (J,t)             0123456789 (i.e. join(range(10)))...
 .AZ               plus A-Z...
 .LCAZ             plus lowercase a-z...
 ."<=>"            plus <=>
f:{              Define f(a,b) to convert a from bijective base b to decimal:
 $+                Sum of...
  (m@?^a)            list of index of each character of a in m
  *                  multiplied item-wise by 
  b**RV,#a           b to the power of each number in reverse(range(len(a)))
}
t:{              Define t(a,b) to convert a from decimal to bijective base b:
 x:""              Reset x to empty string (not needed if only calling the function once)
 Wa{               While a is not zero:
  p:a//b-!a%b        p = ceil(a/b) - 1 (= a//b if a%b!=0, a//b-1 otherwise)
  x:m@(a-p*b).x      Calculate digit a-p*b, look up the corresponding character in m, and
                     prepend to x
  a:p                p becomes the new a
 }
 x                 Return x
}
(t               Return result of calling t with these arguments:
 (f                Result of calling f with these arguments:
  b                  2nd cmdline arg
  m@?a)              1st cmdline arg's decimal value
 m@?c              3rd cmdline arg's decimal value
)
                 Print (implicit)

Sample run:

dlosc@dlosc:~/golf$ python pip.py bijectivebase.pip ">" "Fe" "a"
RS

Answer 3

Octave, 166 bytes

function z=b(o,x,n)
M=['1':'9','A':'Z','a':'z','<=>'];N(M)=1:64;n=N(n);x=polyval(N(x),N(o));z='';while x>0 r=mod(x,n);t=n;if r t=r;end;z=[M(t),z];x=fix(x/n)-(r<1);end

Multi-line version:

function z=b(o,x,n)
   M=['1':'9','A':'Z','a':'z','<=>'];
   N(M)=1:64;
   n=N(n);
   x=polyval(N(x),N(o));
   z='';
   while x>0
      r=mod(x,n);
      t=n;if r t=r;end;
      z=[M(t),z];
      x=fix(x/n)-(r<1);
   end
%end // implicit - not included above

Rather than create a map to convert a character to an index value, I just created the inverse lookup table N for ascii values 1..'z' and populated it with the indices at the appropriate values.

polyval evaluates the equation

c₁x^k + c₂x^k-1 + ... + c_kx⁰

using the decimal-converted input value as the vector of coefficients c and the original base as x. (Unfortunately, Octave's base2dec() rejects symbols out of the normal range.)

Once we have the input value in base 10, calculation of the value in the new base is straightforward.

Test driver:

% script bijecttest.m
a=b('4','','8');
disp(a);
a=b('A','16','2');
disp(a);
a=b('2','122','A');
disp(a);
a=b('3','31','1');
disp(a);
a=b('>','Fe','a');
disp(a);

Results:

>> bijecttest

1112
A
1111111111
RS
>>

Answer 4

Perl, 261 248 229 bytes

sub t{$b=0;$b*=$_[1],$b+=ord($1=~y/0-9A-Za-z<=>/\0-A/r)while$_[0]=~/(.)/g;return$b}sub r{$n=$_[0];$n-=$m=($n-1)%$_[1]+1,$d=(chr$m)=~y/\0-A/0-9A-Za-z<=>/r.$d,$n/=$_[1]while$n;print$d}@a=split/,/,<>;r(t(@a[1],t@a[0],64),t@a[2],64)

multi-line, while loops ungolfed:

sub t{ # convert bijective base string to number
    $b=0;
    while($_[0]=~/(.)/g)
        {$b*=$_[1];$b+=ord($1=~y/0-9A-Za-z<=>/\0-A/r)}
    return$b}
sub r{ # convert number to bijective base string
    $n=$_[0];
    while($n)
        {$n-=$m=($n-1)%$_[1]+1;$d=(chr$m)=~y/\0-A/0-9A-Za-z<=>/r.$d;$n/=$_[1]}
    print$d}
@a=split/,/,<>; # parse input
r(t(@a[1],t@a[0],64),t@a[2],64)

t is a function to parse a number from a bijective-base string of a given base. r is a function to generate a bijective-base string of a given base from a number. The 3 comma-separated parameters are parsed from stdin and the functions are called as needed.

Converting a positive number to a bijective base string is similar to a normal base. However where you would do something like this for a normal base:

string s = ""
while(n)
{
    c = (n % base)
    s = (c + '0') + s
    n -= c // not necessary because the division will take care of it
    n /= base 
}

you adjust the mod to give a range from 1 to base instead of 0 to base - 1:

string s = ""
while(n)
{
    c = (((n-1) % base)+1)
    s = (c + '0') + s
    n -= c  // necessary in the case c = base
    n /= base 
}

Answer 5

CJam, 73 70 69 55 51 48 bytes

Latest version uses the CJam base conversion operator for the conversion from the source base, which I hadn't thought of until I saw @aditsu's solution. It also applies a recent tip by @Dennis for constructing the "digit" string (https://codegolf.stackexchange.com/a/54348/32852), as well as some other ideas shared on chat.

lA,s'[,_el^+"<=>"+:Lf#Ll#bLl#:K;{(Kmd)L=\}hs-]W%

Input format is the value, followed by the source and destination base, with each of them on a separate line. For the empty string, leave the first line empty. Example input:

122
2
A

Try it online

Explanation:

l       Get and interpret value from input.
A,s     Build the list of 64 "digits". Start with [0..9]
'[,     Build character sequence from \0 to Z.
_el     Lower case copy of the same sequence.
^       Symmetric set difference gives only letters from both sequences.
+       Concatenate with sequence of decimal digits, creating [0..9A..Za..z].
"<=>"   Remaining 4 characters.
+       Concatenate, resulting in full 64 character "digit" string.
:L      ... and store it in variable L for repeated use.
f#      Look up input characters in digit list.
Ll#     Get source base from input, and look up value in digit list.
b       Base conversion. This produces the input value.
Ll#     Get destination base from input, and look up value in digit list.
:K;     Store it in variable K for use in loop, and pop it off stack.
{       Loop for generating output digits.
  (       Decrement to get ceiling minus 1 after division.
  Kmd     Calculate divmod of current value with destination base.
  )       Increment mod to get 1-based value for digit.
  L=      Look up digit character for digit value.
  \       Swap. Digit stays on stack for output, remaining value is processed
          in next loop iteration until it is 0.
}h      End of loop for generating output digits.
s       Final value is 0. Covert it to a string.
-       And subtract it from second but last value. This eliminates the 0,
        as well as the second but last value if it was a \0 character.
]       Wrap digits in array.
W%      Reverse array, to get result from MSB to LSB.

Answer 6

Python 2, ... 317 307 298 311 bytes

Definitely golfable. I really hate how strings have no item assignment and lists have no find. I'll look into a better way than my fast fix that I have now.

My method is to convert the input to a decimal number, then to the output base, then convert that to the bijective base.

Edit: Found that my program didn't work when converting to Unary. It cost 13 bytes to fix with e=F(o)<2, etc.

Try it here

R=range;M="".join(map(chr,R(48,58)+R(65,91)+R(97,123)))+"<=>"
b,s,o=input()
F=M.find
e=F(o)<2
B=lambda n:n and B(n/F(o)-e)+M[n%F(o)+e]or""
n=B(sum(F(s[~j])*F(b)**j for j in R(len(s))))
i=n.find('0')
n=list(n)
while-~i:n=n[:i-1]+[M[F(n[i-1])-1]]+[o]+n[i+1:];n=n["0"==n[0]:];i="".join(n).find('0')
print"".join(n)

Answer 7

Python 2, 167 Bytes

No special tricks in here really, except for the [2::5] slicing to get the charset at a lower byte count.

x=range;A=`map(chr,x(49,58)+x(65,91)+x(97,123))`[2::5]+'<=>'
r=A.find
b,n,B=input()
B=r(B)+1
d=0;s=''
for c in n:d=d*-~r(b)+r(c)+1
while d:d-=1;s=A[d%B]+s;d/=B
print s

Tests:

"4","","8"     >>> (empty string)
">","Fe","a"   >>> RS
"3","31","1"   >>> 1111111111
"A","16","2"   >>> 1112
"2","122","A"  >>> A

Answer 8

Jelly, 22 bytes

ØBḊ;“<=>”
i@€€¢ḅḃ2ƭ/ị¢

Try it online!