fundo

A numeração bijetiva da base b , onde b é um número inteiro positivo, é uma notação posicional bijetiva que utiliza símbolos b com valores associados de 1 a b .

Diferentemente de sua contraparte não-bijetiva, nenhum símbolo tem o valor 0 . Dessa forma, cada número inteiro não negativo n tem uma representação exclusiva na base bijetiva b .

As numerações bijetivas populares incluem a base bijetiva unária 2 (usada na codificação de comprimento de execução do bzip2 ) e a base bijetiva 26 (usada para numerar colunas em planilhas).

Definição

Neste desafio, definimos o conjunto M de símbolos como

123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz<=>

e uma função i de M para o número natural tal que i ('1') = 1,…, i ('>') = 64 .

Dada uma base b entre 1 e 64 (ambos inclusive), definimos que cada número inteiro não negativo n corresponde à sequência a _k … a ₀ , composta por símbolos de M , de modo que n = b ^k i (a _k ) + … + B ⁰ i (a ₀ ) .

Essa correspondência é bem definida e bijetiva. Como uma soma vazia é definida como 0 , o número inteiro 0 pode ser codificado como uma sequência vazia.

Tarefa

Aceite três strings como entrada:

• Uma base de entrada b entre 1 e 64 , codificada como uma sequência 64 de base bijetiva .

• Um número inteiro não negativo n , codificado como uma sequência bijetiva de base b .

• Uma base de saída B entre 1 e 64 , codificada como uma sequência 64 de base bijetiva .

Dadas essas três entradas, codifique n como uma seqüência B de base bijetiva .

Casos de teste

Todos os casos de teste especificar a entrada na ordem 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"

Regras

• Você pode ler as três strings em qualquer ordem conveniente, como tal, uma matriz de strings, uma representação de strings, concatenada ou separada por delimitadores de caractere único de sua escolha.

• Se você optar por imprimir a saída em STDOUT, poderá imprimir apenas os símbolos e (opcionalmente) uma nova linha à direita.

• Todos os tipos de conversão de base são permitidos.

• Aplicam-se as regras de código-golfe padrão .

CJam, 43

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

3 bytes erradicados com a ajuda de Dennis :) Experimente online

Explicação:

A entrada é tomada como bnBconcatenada em uma única sequência.

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

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

Repositório do GitHub para Pip

Algoritmos adaptados do artigo da Wikipedia. Aqui está a explicação para uma versão anterior levemente não destruída:

                 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)

Exemplo de execução:

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

Oitava, 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

Versão multilinhas:

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

Em vez de criar um mapa para converter um caractere em um valor de índice, criei a tabela de pesquisa inversa Npara valores ascii 1..'z'e a preenchi com os índices nos valores apropriados.

polyval avalia a equação

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

usando o valor de entrada convertido decimal como o vetor de coeficientes ce a base original como x. (Infelizmente, o Octave base2dec()rejeita símbolos fora do intervalo normal.)

Depois de termos o valor de entrada na base 10, o cálculo do valor na nova base é direto.

Driver de teste:

% 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);

Resultados:

>> bijecttest

1112
A
1111111111
RS
>>

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)

várias linhas, enquanto os loops não foram destruídos:

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é uma função para analisar um número de uma cadeia de base bijetiva de uma determinada base. ré uma função para gerar uma cadeia de base bijetiva de uma determinada base a partir de um número. Os três parâmetros separados por vírgula são analisados ​​a partir de stdin e as funções são chamadas conforme necessário.

A conversão de um número positivo em uma cadeia de base bijetiva é semelhante a uma base normal. No entanto, onde você faria algo assim para uma base normal:

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 
}

você ajusta o mod para dar um intervalo de 1 a base em vez de 0 a 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 
}

Python 2, ... 317 307 298 311 bytes

Definitivamente jogável. Eu realmente odeio como as strings não têm atribuição de itens e as listas não find. Vou procurar uma maneira melhor do que minha solução rápida que tenho agora.

Meu método é converter a entrada em um número decimal, depois na base de saída e depois convertê-la na base bijetiva.

Edit : Verificou que meu programa não funcionava ao converter para Unary. Custou 13 bytes para corrigir e=F(o)<2, etc.

Experimente aqui

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)

Python 2, 167 bytes

Não há truques especiais aqui, exceto o [2::5]fatiamento para obter o conjunto de caracteres com uma contagem de bytes mais baixa.

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

Testes:

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

CJam, 73 70 69 55 51 48 bytes

A versão mais recente usa o operador de conversão de base CJam para a conversão da base de origem, que eu não pensava até ver a solução do @ aditsu. Também aplica uma dica recente de @Dennis para a construção da string "digit" ( /codegolf//a/54348/32852 ), além de outras idéias compartilhadas no bate-papo.

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

Formato de entrada é o valor, seguido pela base de origem e destino, com cada um deles em uma linha separada. Para a sequência vazia, deixe a primeira linha vazia. Exemplo de entrada:

122
2
A

Experimente online

Explicação:

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.

Gelatina , 22 bytes

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

Experimente online!