Introdução

Temos alguns desafios básicos de conversão aqui no passado, mas não muitos projetados para lidar com números arbitrários de comprimento (ou seja, números longos o suficiente para transbordar o tipo de dados inteiro) e, dentre eles, mais pareceu um pouco complicado. Estou curioso para saber como é possível obter uma alteração no código base como essa.

Desafio

Escreva um programa ou função no idioma de sua escolha que possa converter uma sequência de uma base em uma sequência de outra base. A entrada deve ser o número a ser convertido (sequência), da base (número da base 10), para a base (número da base 10) e o conjunto de caracteres (sequência). A saída deve ser o número convertido (string).

Alguns detalhes e regras adicionais são os seguintes:

• O número a ser convertido será um número inteiro não negativo (uma vez -e .pode ser no conjunto de caracteres). Assim também será a saída.
• Os zeros à esquerda (o primeiro caractere no conjunto de caracteres) devem ser aparados. Se o resultado for zero, um único dígito zero deve permanecer.
• O intervalo base mínimo suportado é de 2 a 95, consistindo nos caracteres ascii imprimíveis.
• A entrada para o número a ser convertido, o conjunto de caracteres e a saída devem todos ser do tipo de dados da sequência. As bases devem ser do tipo de dados inteiro da base 10 (ou números inteiros flutuantes).
• O comprimento da sequência do número de entrada pode ser muito grande. É difícil quantificar um mínimo sensato, mas esperamos que ele consiga lidar com pelo menos 1000 caracteres e concluir a entrada de 100 caracteres em menos de 10 segundos em uma máquina decente (muito generosa para esse tipo de problema, mas não quero velocidade para ser o foco).
• Você não pode usar funções integradas de mudança de base.
• A entrada do conjunto de caracteres pode estar em qualquer disposição, não apenas no típico 0-9a-z ... etc.
• Suponha que apenas a entrada válida será usada. Não se preocupe com o tratamento de erros.

O vencedor será determinado pelo código mais curto que atender aos critérios. Eles serão selecionados em pelo menos 7 dias-base-10, ou se / quando houver envios suficientes. Em caso de empate, o código que correr mais rápido será o vencedor. Se perto o suficiente em velocidade / desempenho, a resposta que veio antes vence.

Exemplos

Aqui estão alguns exemplos de entrada e saída que seu código deve poder manipular:

F("1010101", 2, 10, "0123456789")
> 85

F("0001010101", 2, 10, "0123456789")
> 85

F("85", 10, 2, "0123456789")
> 1010101

F("1010101", 10, 2, "0123456789")
> 11110110100110110101

F("bababab", 2, 10, "abcdefghij")
> if

F("10", 3, 2, "0123456789")
> 11

F("<('.'<)(v'.'v)(>'.'>)(^'.'^)", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? ")
> !!~~~~~~~!!!~!~~!!!!!!!!!~~!!~!!!!!!~~!~!~!!!~!~!~!!~~!!!~!~~!!~!!~~!~!!~~!!~!~!!!~~~~!!!!!!!!!!!!~!!~!~!~~~~!~~~~!~~~~~!~~!!~~~!~!~!!!~!~~

F("~~~~~~~~~~", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? ")
> ~

F("9876543210123456789", 10, 36, "0123456789abcdefghijklmnopqrstuvwxyz")
> 231ceddo6msr9

F("ALLYOURBASEAREBELONGTOUS", 62, 10, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
> 6173180047113843154028210391227718305282902

F("howmuchwoodcouldawoodchuckchuckifawoodchuckcouldchuckwood", 36, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? ")
> o3K9e(r_lgal0$;?w0[`<$n~</SUk(r#9W@."0&}_2?[n

F("1100111100011010101010101011001111011010101101001111101000000001010010100101111110000010001001111100000001011000000001001101110101", 2, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? ")
> this is much shorter

CJam, 34 bytes

0ll:Af#lif{@*+}~li:X;{XmdA=\}h;]W%

O formato de entrada está input_N alphabet input_B output_Bcada um em uma linha separada.

Execute todos os casos de teste.

Explicação

0     e# Push a zero which we'll use as a running total to build up the input number.
l     e# Read the input number.
l:A   e# Read the alphabet and store it in A.
f#    e# For each character in the input number turn it into its position in the alphabet,
      e# replacing characters with the corresponding numerical digit value.
li    e# Read input and convert to integer.
f{    e# For each digit (leaving the base on the stack)...
  @*  e#   Pull up the running total and multiply it by the base.
  +   e#   Add the current digit.
}
~     e# The result will be wrapped in an array. Unwrap it.
li:X; e# Read the output base, store it in X and discard it.
{     e# While the running total is not zero yet...
  Xmd e#   Take the running total divmod X. The modulo gives the next digit, and
      e#   the division result represents the remaining digits.
  A=  e#   Pick the corresponding character from the alphabet.
  \   e#   Swap the digit with the remaining value.
}h
;     e# We'll end up with a final zero on the stack which we don't want. Discard it.
]W%   e# Wrap everything in an array and reverse it, because we've generated the 
      e# digits from least to most significant.

Isso funciona para a mesma contagem de bytes:

L0ll:Af#lif{@*+}~li:X;{XmdA=@+\}h;

A única diferença é que estamos construindo uma string em vez de coletar tudo na pilha e revertê-la.

Python 2 , 115 114 106 105 94 bytes

Sugestões de golfe são bem-vindas. Experimente online!

Edit: -9 bytes graças a mbomb007. -2 bytes graças ao FlipTack.

def a(n,f,t,d,z=0,s=''):
 for i in n:z=z*f+d.find(i)
 while z:s=d[z%t]+s;z/=t
 print s or d[0]

Ungolfed:

def arbitrary_base_conversion(num, b_from, b_to, digs, z=0, s=''):
    for i in num:
        z = z * b_from + digs.index(i)
    while z:
        s = digs[z % b_to] + s
        z = z / t
    if s:
        return s
    else:
        return d[0]

Sério, 50 bytes

0╗,╝,2┐,3┐,4┐╛`4└í╜2└*+╗`MX╜ε╗W;3└@%4└E╜@+╗3└@\WX╜

Hex Dump:

30bb2cbc2c32bf2c33bf2c34bfbe6034c0a1bd32c02a2bbb60
4d58bdeebb573b33c0402534c045bd402bbb33c0405c5758bd

Estou orgulhoso deste, apesar de seu comprimento. Por quê? Porque funcionou perfeitamente na segunda tentativa. Eu escrevi e depurei em literalmente 10 minutos. Normalmente, a depuração de um programa Sério é uma hora de trabalho.

Explicação:

0╗                                                  Put a zero in reg0 (build number here)
  ,╝,2┐,3┐,4┐                                       Put evaluated inputs in next four regs
             ╛                                      Load string from reg1
              `         `M                          Map over its chars
               4└                                   Load string of digits
                 í                                  Get index of char in it.
                  ╜                                 Load number-so-far from reg0
                   2└*                              Multiply by from-base
                      +                             Add current digit.
                       ╗                            Save back in reg0
                          X                         Discard emptied string/list.
                           ╜                        Load completed num from reg0
                            ε╗                      Put empty string in reg0
                              W                W    While number is positive
                               ;                    Duplicate
                                3└@%                Mod by to-base.
                                    4└E             Look up corresponding char in digits
                                       ╜@+          Prepend to string-so-far.
                                                      (Forgetting this @ was my one bug.)
                                          ╗         Put it back in reg0
                                           3└@\     integer divide by to-base.
                                                X   Discard leftover 0
                                                 ╜  Load completed string from reg0
                                                    Implicit output.

C (função) com biblioteca GMP , 260

Isso acabou mais do que eu esperava, mas aqui está assim mesmo. O mpz_*material realmente consome muitos bytes. Eu tentei #define M(x) mpz_##x, mas isso deu um ganho líquido de 10 bytes.

#include <gmp.h>
O(mpz_t N,int t,char*d){mpz_t Q,R;mpz_inits(Q,R,0);mpz_tdiv_qr_ui(Q,R,N,t);mpz_sgn(Q)&&O(Q,t,d);putchar(d[mpz_get_ui(R)]);}F(char*n,int f,int t,char*d){mpz_t N;mpz_init(N);while(*n)mpz_mul_ui(N,N,f),mpz_add_ui(N,N,strchr(d,*n++)-d);O(N,t,d);}

A função F()é o ponto de entrada. Ele converte a sequência de entrada em uma mpz_tmultiplicação sucessiva pela frombase-e adição do índice do dígito fornecido na lista de dígitos.

A função O()é uma função de saída recursiva. Cada recursão divide o mpz_tpela tobase. Como isso gera os dígitos de saída na ordem inversa, a recursão efetivamente permite que os dígitos sejam armazenados na pilha e saídos na ordem correta.

Driver de teste:

Novas linhas e recuo adicionados para facilitar a leitura.

#include <stdio.h>
#include <string.h>

#include <gmp.h>
O(mpz_t N,int t,char*d){
  mpz_t Q,R;
  mpz_inits(Q,R,0);
  mpz_tdiv_qr_ui(Q,R,N,t);
  mpz_sgn(Q)&&O(Q,t,d);
  putchar(d[mpz_get_ui(R)]);
}
F(char*n,int f,int t,char*d){
  mpz_t N;
  mpz_init(N);
  while(*n)
    mpz_mul_ui(N,N,f),mpz_add_ui(N,N,strchr(d,*n++)-d);
  O(N,t,d);
}

int main (int argc, char **argv) {
  int i;

  struct test_t {
    char *n;
    int from_base;
    int to_base;
    char *digit_list;
  } test[] = {
    {"1010101", 2, 10, "0123456789"},
    {"0001010101", 2, 10, "0123456789"},
    {"85", 10, 2, "0123456789"},
    {"1010101", 10, 2, "0123456789"},
    {"bababab", 2, 10, "abcdefghij"},
    {"10", 3, 2, "0123456789"},
    {"<('.'<)(v'.'v)(>'.'>)(^'.'^)", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? "},
    {"~~~~~~~~~~", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? "},
    {"9876543210123456789", 10, 36, "0123456789abcdefghijklmnopqrstuvwxyz"},
    {"ALLYOURBASEAREBELONGTOUS", 62, 10, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"},
    {"howmuchwoodcouldawoodchuckchuckifawoodchuckcouldchuckwood", 36, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? "},
    {"1100111100011010101010101011001111011010101101001111101000000001010010100101111110000010001001111100000001011000000001001101110101", 2, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? "},
    {0}
  };

  for (i = 0; test[i].n; i++) {
    F(test[i].n, test[i].from_base, test[i].to_base, test[i].digit_list);
    puts("");
  }

  return 0;
}

JavaScript (ES6), 140 bytes

(s,f,t,m)=>[...s].map(c=>{c=m.indexOf(c);for(i=0;c||i<r.length;i++)r[i]=(n=(r[i]|0)*f+c)%t,c=n/t|0},r=[0])&&r.reverse().map(c=>m[c]).join``

Ao contrário do código de @ Mwr247 (que usa aritmética base-f para dividir s por t de cada vez, coletando cada restante conforme ele avança), eu uso a aritmética base-t para multiplicar a resposta por f cada vez, adicionando cada dígito de s à medida que vou.

Ungolfed:

function base(source, from, to, mapping) {
    result = [0];
    for (j = 0; j < s.length; s++) {
        carry = mapping.indexOf(s[j]);
        for (i = 0; carry || i < result.length; i++) {
            next = (result[i] || 0) * from + carry;
            result[i] = next % to;
            carry = Math.floor(next / to);
         }
    }
    string = "";
    for (j = result.length; j --> 0; )
        string += mapping[result[j]];
    return string;
}

Ruby, 113 112 105 98 97 95 87 bytes

Eu meio que publiquei duas vezes minha resposta em Python (de alguma forma), então aqui está uma resposta em Ruby. Mais sete bytes graças ao manatwork , outro byte a Martin Büttner e mais 8 bytes a cia_rana .

->n,f,t,d{z=0;s='';n.chars{|i|z=z*f+d.index(i)};(s=d[z%t]+s;z/=t)while z>0;s[0]?s:d[0]}

Ungolfed:

def a(n,f,t,d)
  z=0
  s=''
  n.chars do |i|
    z = z*f + d.index(i)
  end
  while z>0 
    s = d[z%t] + s
    z /= t
  end
  if s[0]   # if n not zero
    return s
  else
    return d[0]
  end
end

APL, 10 bytes

{⍺⍺[⍵⍵⍳⍵]}

Este é um operador de APL. No APL, ⍵e ⍺são usados ​​para passar valores, enquanto ⍵⍵e ⍺⍺geralmente são usados ​​para passar funções. Estou abusando disso aqui para ter 3 argumentos. ⍺⍺é o argumento da esquerda, ⍵⍵é o argumento da direita "interior" e⍵ é o argumento da direita "externo".

Basicamente: ⍺(⍺⍺{...}⍵⍵)⍵

Então, tudo o que é necessário é ⍳encontrar as posições da string de entrada na tabela "de" e, em seguida, use []para indexar na tabela "para" com essas posições.

Exemplo:

    ('012345'{⍺⍺[⍵⍵⍳⍵]}'abcdef')'abcabc'
012012

JavaScript (ES6), 175 bytes

(s,f,t,h)=>eval('s=[...s].map(a=>h.indexOf(a));n=[];while(s.length){d=m=[],s.map(v=>((e=(c=v+m*f)/t|0,m=c%t),e||d.length?d.push(e):0)),s=d,n.unshift(m)}n.map(a=>h[a]).join``')

Achei que já faz tempo suficiente para que eu possa enviar o que fiz para criar os exemplos. Posso tentar jogar um pouco melhor depois.

Japonês, 9 bytes

nVîX
sWîX

Tente