Вступление

В прошлом у нас было несколько проблем с базовым преобразованием, но не так много, предназначенных для работы с числами произвольной длины (то есть с числами, достаточно длинными, чтобы они переполняли целочисленный тип данных), и из них большинство считалось немного сложный. Мне любопытно, как можно добиться такого изменения базового кода.

Вызов

Напишите программу или функцию на выбранном вами языке, которая может преобразовать строку из одной базы в строку из другой базы. Входными данными должны быть число, которое нужно преобразовать (строка), от основания (число от 10 до 10), от основания до (от 10 до 10) и набор символов (строка). Выходными данными должно быть преобразованное число (строка).

Некоторые дополнительные детали и правила заключаются в следующем:

• Число для преобразования будет неотрицательным целым числом (так как -и .может быть в наборе символов). Так тоже будет выходной.
• Ведущие нули (первый символ в наборе символов) должны быть обрезаны. Если результат равен нулю, должна остаться одна нулевая цифра.
• Минимальный поддерживаемый базовый диапазон составляет от 2 до 95, состоящий из печатных символов ascii.
• Входные данные для числа, подлежащего преобразованию, набор символов и выходные данные должны иметь строковый тип данных. Основания должны иметь целочисленный тип данных base-10 (или целочисленные числа с плавающей точкой).
• Длина строки входного номера может быть очень большой. Трудно дать количественную оценку разумного минимума, но ожидайте, что он сможет обрабатывать не менее 1000 символов и завершить ввод 100 символов менее чем за 10 секунд на приличной машине (очень щедро для такой проблемы, но я не хочу скорость, чтобы быть в центре внимания).
• Вы не можете использовать встроенные функции изменения базы.
• Ввод набора символов может быть любым, а не только типичным 0-9a-z ... и т. Д.
• Предположим, что будет использоваться только действительный ввод. Не беспокойтесь об обработке ошибок.

Победитель будет определен по кратчайшему коду, который соответствует критериям. Они будут выбраны не позднее, чем через 7-10 дней, или если / когда будет достаточно заявок. В случае ничьей, код, который работает быстрее, будет победителем. Если достаточно близко по скорости / производительности, ответ, который пришел раньше, выигрывает.

Примеры

Вот несколько примеров ввода и вывода, которые ваш код должен уметь обрабатывать:

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 байта

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

Формат ввода указан input_N alphabet input_B output_Bв отдельной строке.

Запустите все тестовые случаи.

объяснение

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.

Это работает для того же количества байтов:

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

Разница лишь в том, что мы собираем строку вместо того, чтобы собирать все в стек и переворачивать ее.

Python 2 , 115 114 106 105 94 байта

Предложения по игре в гольф приветствуются. Попробуйте онлайн!

Изменить: -9 байт благодаря mbomb007. -2 байта благодаря 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]

Серьезно, 50 байтов

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

Шестнадцатеричный дамп:

30bb2cbc2c32bf2c33bf2c34bfbe6034c0a1bd32c02a2bbb60
4d58bdeebb573b33c0402534c045bd402bbb33c0405c5758bd

Я горжусь этим, несмотря на его длину. Почему? Потому что он отлично работал со второй попытки. Я написал это и отладил буквально за 10 минут. Обычно отладка серьезной программы - это час работы.

Объяснение:

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 (функция) с библиотекой GMP , 260

Это оказалось дольше, чем я надеялся, но это все равно. Материал mpz_*действительно съедает много байтов. Я пытался #define M(x) mpz_##x, но это дало чистый выигрыш в 10 байт.

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

Функция F()является точкой входа. Он преобразует входную строку в mpz_tпоследовательные умножения наfrom -base и добавление индекса данной цифры в список цифр.

Функция O()является рекурсивной функцией вывода. Каждая рекурсия divmods mpz_tпо to-BASE. Поскольку это приводит к выводу цифр в обратном порядке, рекурсия эффективно позволяет хранить цифры в стеке и выводить в правильном порядке.

Тестовый водитель:

Добавлены новые строки и отступы для удобства чтения.

#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 байт

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

В отличие от кода @ Mwr247 (который использует арифметику base-f для деления s на t каждый раз, собирая каждый остаток по мере его поступления), я использую арифметику base-t для умножения ответа на f каждый раз, добавляя каждую цифру s на ходу.

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

Рубин, 113 112 105 98 97 95 87 байт

Я как бы дважды опубликовал свой ответ на Python (как-то), так что вот ответ Ruby. Еще семь байтов благодаря manatwork , еще один байт благодаря Мартину Бюттнеру и еще 8 байтов благодаря 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 байт

{⍺⍺[⍵⍵⍳⍵]}

Это оператор APL. В APL ⍵и ⍺используются для передачи значений, а ⍵⍵и ⍺⍺обычно используются для передачи функций. Я злоупотребляю этим здесь, чтобы иметь 3 аргумента. ⍺⍺левый аргумент, ⍵⍵«внутренний» правый аргумент, и⍵ является «внешним» правым аргументом.

В принципе: ⍺(⍺⍺{...}⍵⍵)⍵

Тогда все, что нужно, это ⍳найти позиции входной строки в таблице «from», а затем использовать []для индексации таблицы «to» с этими позициями.

Пример:

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

JavaScript (ES6), 175 байт

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

Я подумал, что прошло достаточно много времени, и я могу представить сделанный мной пример для создания примеров. Я могу попытаться сыграть немного лучше позже.

Japt, 9 байт

nVîX
sWîX

Попытайся