Wprowadzenie

W przeszłości mieliśmy tutaj kilka podstawowych wyzwań związanych z konwersją, ale niewiele z nich zaprojektowano tak, aby poradzić sobie z liczbami o dowolnej długości (to znaczy liczbami, które są na tyle długie, że przekraczają typ danych liczb całkowitych). skomplikowane. Jestem ciekawy, jak można uzyskać taką zmianę kodu podstawowego.

Wyzwanie

Napisz program lub funkcję w wybranym języku, który może przekonwertować ciąg jednej bazy na ciąg innej bazy. Dane wejściowe powinny być liczbą do konwersji (ciąg znaków), z bazy (liczba bazy 10), na bazę (liczba bazy 10) oraz zestaw znaków (łańcuch znaków). Dane wyjściowe powinny być konwertowaną liczbą (ciągiem).

Niektóre dalsze szczegóły i zasady są następujące:

• Liczba do konwersji będzie nieujemną liczbą całkowitą (ponieważ -i .może znajdować się w zestawie znaków). Podobnie będzie wynik.
• Zera wiodące (pierwszy znak w zestawie znaków) powinny zostać przycięte. Jeśli wynik wynosi zero, powinna pozostać pojedyncza cyfra zero.
• Minimalny obsługiwany zakres podstawowy wynosi od 2 do 95, składający się z drukowalnych znaków ascii.
• Dane wejściowe dla liczby do konwersji, zestaw znaków i dane wyjściowe muszą być typu danych ciągu. Podstawy muszą być typu danych liczb całkowitych typu base-10 (lub liczby całkowite zmiennoprzecinkowe).
• Długość ciągu liczb wejściowych może być bardzo duża. Trudno oszacować rozsądne minimum, ale spodziewaj się, że będzie w stanie obsłużyć co najmniej 1000 znaków i wypełnić 100 znaków w mniej niż 10 sekund na przyzwoitej maszynie (bardzo hojny dla tego rodzaju problemu, ale nie chcę prędkość, na której należy się skupić).
• Nie można używać wbudowanych funkcji zmiany bazy.
• Zestaw znaków może być wprowadzany w dowolnym układzie, nie tylko typowym 0-9a-z ... itd.
• Załóż, że zostaną użyte tylko prawidłowe dane wejściowe. Nie martw się obsługą błędów.

Zwycięzca zostanie określony na podstawie najkrótszego kodu spełniającego kryteria. Zostaną oni wybrani w ciągu co najmniej 7 dni bazowych-10, lub jeśli / kiedy będzie wystarczająco dużo zgłoszeń. W przypadku remisu zwycięży kod, który działa szybciej. Jeśli wystarczająco blisko prędkości / wydajności, odpowiedź, która nadeszła wcześniej, wygrywa.

Przykłady

Oto kilka przykładów danych wejściowych i wyjściowych, które Twój kod powinien obsługiwać:

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 bajty

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

Format wejściowy jest input_N alphabet input_B output_Bw osobnej linii.

Uruchom wszystkie przypadki testowe.

Wyjaśnienie

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.

Działa to dla tej samej liczby bajtów:

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

Jedyna różnica polega na tym, że budujemy ciąg zamiast zbierać wszystko ze stosu i odwracać go.

Python 2 , 115 114 106 105 94 bajtów

Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

Edycja: -9 bajtów dzięki mbomb007. -2 bajty dzięki 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]

Nie golfowany:

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]

Poważnie, 50 bajtów

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

Hex Dump:

30bb2cbc2c32bf2c33bf2c34bfbe6034c0a1bd32c02a2bbb60
4d58bdeebb573b33c0402534c045bd402bbb33c0405c5758bd

Jestem z tego dumny pomimo jego długości. Dlaczego? Ponieważ zadziałało idealnie przy drugiej próbie. Napisałem to i debugowałem w dosłownie 10 minut. Zwykle debugowanie programu Poważnie zajmuje godzinę.

Wyjaśnienie:

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 (funkcja) z biblioteką GMP , 260

Okazało się to dłużej, niż się spodziewałem, ale i tak jest. mpz_*Rzeczy naprawdę zjada dużo bajtów. Próbowałem #define M(x) mpz_##x, ale to dało zysk netto 10 bajtów.

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

Funkcja F()jest punktem wejścia. Konwertuje ciąg wejściowy na mpz_tkolejne mnożenie przez from-base i dodanie indeksu danej cyfry na liście cyfr.

Ta funkcja O()jest rekurencyjną funkcją wyjściową. Każda rekurencja zmienia się mpz_twedług to-base. Ponieważ daje to cyfry wyjściowe w odwrotnej kolejności, rekurencja skutecznie umożliwia zapisanie cyfr na stosie i wyjście w prawidłowej kolejności.

Kierowca testowy:

Dodano nowe linie i wcięcia dla czytelności.

#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 bajtów

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

W przeciwieństwie do kodu @ Mwr247 (który używa arytmetyki base-f do dzielenia s za każdym razem za każdym razem, zbierając resztę w miarę upływu czasu) Używam arytmetyki base-t do pomnożenia odpowiedzi za każdym razem za każdym razem, dodając każdą cyfrę s w miarę upływu czasu.

Nie golfowany:

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 bajtów

W pewnym sensie podwoiłem swoją odpowiedź w Pythonie (jakoś), więc oto odpowiedź Ruby. Siedem dodatkowych bajtów dzięki manatwork , kolejny bajt dzięki Martinowi Büttnerowi i 8 kolejnych bajtów dzięki 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]}

Nie golfowany:

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 bajtów

{⍺⍺[⍵⍵⍳⍵]}

To jest operator APL. W APL ⍵i ⍺są używane do przekazywania wartości, podczas gdy ⍵⍵i ⍺⍺są zwykle używane do przekazywania funkcji. Nadużywam tego, aby mieć 3 argumenty. ⍺⍺jest lewym argumentem, ⍵⍵jest „wewnętrznym” prawym argumentem i⍵ prawym „zewnętrznym” argumentem.

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

Następnie wystarczy ⍳znaleźć pozycje ciągu wejściowego w tabeli „z”, a następnie użyć[] do indeksowania do tabeli „do” z tymi pozycjami.

Przykład:

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

JavaScript (ES6), 175 bajtów

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

Zrozumiałem, że już wystarczająco długo mogę przesłać ten, który stworzyłem, aby stworzyć przykłady. Może później spróbuję zagrać w golfa.

Japt, 9 bajtów

nVîX
sWîX

Spróbuj