Introducción

Hemos tenido algunos desafíos de conversión de base aquí en el pasado, pero no muchos diseñados para abordar números de longitud arbitrarios (es decir, números que son lo suficientemente largos como para desbordar el tipo de datos entero), y de ellos, la mayoría se sintió un poco Complicado. Tengo curiosidad por saber cómo se puede obtener un cambio de código base como este.

Desafío

Escriba un programa o función en el idioma de su elección que pueda convertir una cadena de una base en una cadena de otra base. La entrada debe ser el número a convertir (cadena), desde-base (número base 10), a base (número base 10) y el conjunto de caracteres (cadena). La salida debe ser el número convertido (cadena).

Algunos detalles y reglas adicionales son los siguientes:

• El número a ser convertido será un número entero no negativo (ya que -y .puede estar en el juego de caracteres). Así también será la salida.
• Los ceros iniciales (el primer carácter en el conjunto de caracteres) se deben recortar. Si el resultado es cero, debe quedar un solo dígito cero.
• El rango base mínimo admitido es de 2 a 95, que consiste en los caracteres ascii imprimibles.
• La entrada para el número a convertir, el juego de caracteres y la salida deben ser del tipo de datos de cadena. Las bases deben ser del tipo de datos entero de base 10 (o flotantes enteros).
• La longitud de la cadena del número de entrada puede ser muy grande. Es difícil cuantificar un mínimo razonable, pero se espera que pueda manejar al menos 1000 caracteres y completar la entrada de 100 caracteres en menos de 10 segundos en una máquina decente (muy generoso para este tipo de problema, pero no quiero velocidad para ser el foco).
• No puede utilizar funciones integradas de cambio de base.
• La entrada del juego de caracteres puede estar en cualquier disposición, no solo en el típico 0-9a-z ... etc.
• Suponga que solo se utilizará una entrada válida. No te preocupes por el manejo de errores.

El ganador será determinado por el código más corto que cumpla con los criterios. Se seleccionarán en al menos 7 días de base 10, o si / cuando ha habido suficientes envíos. En caso de empate, el código que se ejecute más rápido será el ganador. Si está lo suficientemente cerca en velocidad / rendimiento, la respuesta que vino antes gana.

Ejemplos

Aquí hay algunos ejemplos de entrada y salida que su código debería poder manejar:

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%

El formato de entrada es input_N alphabet input_B output_Bcada uno en una línea separada.

Ejecute todos los casos de prueba.

Explicación

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.

Esto funciona para el mismo número de bytes:

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

La única diferencia es que estamos construyendo una cadena en lugar de recolectar todo en la pila y revertirlo.

Python 2 , 115 114 106 105 94 bytes

Sugerencias de golf bienvenidas. Pruébalo en línea!

Editar: -9 bytes gracias a mbomb007. -2 bytes gracias a 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]

Sin golf:

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]

En serio, 50 bytes

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

Hex Dump:

30bb2cbc2c32bf2c33bf2c34bfbe6034c0a1bd32c02a2bbb60
4d58bdeebb573b33c0402534c045bd402bbb33c0405c5758bd

Estoy orgulloso de este a pesar de su longitud. ¿Por qué? Porque funcionó perfectamente en el segundo intento. Lo escribí y lo depuré en literalmente 10 minutos. Por lo general, la depuración de un programa en serio es una hora de trabajo.

Explicación:

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 (función) con biblioteca GMP , 260

Esto resultó más de lo que esperaba, pero aquí está de todos modos. El mpz_*material realmente consume muchos bytes. Lo intenté #define M(x) mpz_##x, pero eso me dio una ganancia neta 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);}

La función F()es el punto de entrada. Convierte la cadena de entrada en una mpz_tpor multiplicaciones sucesivas porfrom base y la adición del índice del dígito dado en la lista de dígitos.

La función O()es una función de salida recursiva. Cada recursión divmods mpz_tpor elto base. Debido a que esto produce los dígitos de salida en orden inverso, la recursión efectivamente permite que los dígitos se almacenen en la pila y se impriman en el orden correcto.

Conductor de prueba:

Se agregaron nuevas líneas y sangría para facilitar la lectura.

#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``

A diferencia del código de @ Mwr247 (que usa la aritmética de base-f para dividir s entre t cada vez, recolectando cada resto a medida que avanza) Yo uso la aritmética de base-t para multiplicar la respuesta por f cada vez, agregando cada dígito de s a medida que avanzo.

Sin golf:

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;
}

Rubí, 113 112 105 98 97 95 87 bytes

De alguna manera publiqué mi respuesta de Python (de alguna manera), así que aquí hay una respuesta de Ruby. Siete bytes más gracias a manatwork , otro byte gracias a Martin Büttner y 8 bytes más gracias 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]}

Sin golf:

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 es un operador APL. En APL, ⍵y ⍺se usan para pasar valores, mientras que ⍵⍵y ⍺⍺generalmente se usan para pasar funciones. Estoy abusando de esto aquí para tener 3 argumentos. ⍺⍺es el argumento izquierdo, ⍵⍵es el argumento derecho "interno" y⍵ es el argumento derecho "externo".

Básicamente: ⍺(⍺⍺{...}⍵⍵)⍵

Entonces todo lo que se necesita es ⍳encontrar las posiciones de la cadena de entrada en la tabla "desde" y luego usar[] para indexar en la tabla "hasta" con estas posiciones.

Ejemplo:

    ('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``')

Supuse que ya había pasado el tiempo suficiente para enviar el que hice para crear los ejemplos. Puedo intentar jugarlo un poco mejor más tarde.

Japt, 9 bytes

nVîX
sWîX

Intentalo