Hintergrund

Eine bijektive Basis- b- Nummerierung , wobei b eine positive ganze Zahl ist, ist eine bijektive Positionsnotation, die b- Symbole mit zugeordneten Werten von 1 bis b verwendet .

Im Gegensatz zu seinem nicht-bijektiven Gegenstück hat kein Symbol den Wert 0 . Auf diese Weise hat jede nicht negative ganze Zahl n eine eindeutige Darstellung in der bijektiven Basis b .

Zu den gängigen bijektiven Numerierungen gehören die unäre bijektive Basis 2 (die in der Lauflängencodierung von bzip2 verwendet wird ) und die bijektive Basis 26 (die zum Nummerieren von Spalten in Tabellen verwendet wird).

Definition

In dieser Herausforderung definieren wir die Menge M von Symbolen als

123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz<=>

und eine Funktion i von M zu der natürlichen Zahl, so dass i ('1') = 1,…, i ('>') = 64 .

Bei einer Basis b zwischen 1 und 64 (beide inklusive) definieren wir, dass jede nicht negative ganze Zahl n der Zeichenkette a _k … a _{0 entspricht} , die aus Symbolen von M besteht , so dass n = b ^k i (a _k ) + ist … + B ⁰ i (a ₀ ) .

Diese Entsprechung ist klar definiert und bijektiv. Da eine leere Summe als 0 definiert ist , kann die Ganzzahl 0 als leere Zeichenfolge codiert werden.

Aufgabe

Akzeptiere drei Zeichenketten als Eingabe:

• Eine Eingabebasis b zwischen 1 und 64 , codiert als bijektive Basis 64- Zeichenfolge.

• Eine nicht negative ganze Zahl n , die als bijektive Basis b codiert ist .

• Eine Ausgangsbasis B zwischen 1 und 64 , codiert als bijektive Basis 64- Zeichenfolge.

Codieren Sie bei diesen drei Eingaben n als bijektiven Basis- B- String.

Testfälle

Alle Testfälle spezifizieren die Eingabe in der Reihenfolge , 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"

Regeln

• Sie können die drei Zeichenfolgen in beliebiger Reihenfolge lesen, z. B. als Array von Zeichenfolgen, als Zeichenfolgendarstellung, verkettet oder durch Trennzeichen Ihrer Wahl getrennt.

• Wenn Sie die Ausgabe auf STDOUT drucken möchten, können Sie nur die Symbole und (optional) eine nachgestellte Newline drucken.

• Grundkonvertierungs-Built-Ins aller Art sind erlaubt.

• Es gelten die Standardregeln für Code-Golf .

CJam, 43

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

3 Bytes mit Hilfe von Dennis beseitigt :) Probieren Sie es online

Erläuterung:

Die Eingabe wird als bnBzu einer einzelnen Zeichenfolge verkettet betrachtet.

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

GitHub-Repository für Pip

Algorithmen aus dem Wikipedia-Artikel angepasst. Hier ist die Erklärung für eine etwas ungolfed frühere Version:

                 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)

Probelauf:

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

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

Mehrzeilige Version:

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

Anstatt eine Map zum Konvertieren eines Zeichens in einen Indexwert zu erstellen, habe ich gerade die inverse Lookup-Tabelle Nfür ASCII-Werte erstellt 1..'z'und sie mit den Indizes an den entsprechenden Werten gefüllt.

polyval wertet die Gleichung aus

c ₁ × ^k + c ₂ × ^{k - 1} + ... + c _k × ⁰

Verwenden des dezimal konvertierten Eingabewerts als Koeffizientenvektor cund der ursprünglichen Basis als x. (Leider weist Octave base2dec()Symbole außerhalb des normalen Bereichs zurück.)

Sobald wir den Eingabewert in Basis 10 haben, ist die Berechnung des Werts in der neuen Basis einfach.

Testfahrer:

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

Ergebnisse:

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

mehrzeilig, während Loops ungolfed:

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)

tist eine Funktion zum Parsen einer Zahl aus einer bijektiven Basiszeichenfolge einer gegebenen Basis. rist eine Funktion zum Erzeugen einer bijektiven Basiszeichenfolge einer gegebenen Basis aus einer Zahl. Die 3 durch Kommas getrennten Parameter werden von stdin analysiert und die Funktionen werden nach Bedarf aufgerufen.

Das Umwandeln einer positiven Zahl in eine bijektive Basiszeichenfolge ähnelt einer normalen Basis. Aber wo würden Sie so etwas für eine normale Basis tun:

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 
}

Sie passen den Mod so an, dass er einen Bereich von 1 bis zur Basis anstelle von 0 bis zur Basis - 1 angibt:

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

Auf jeden Fall golfen. Ich hasse es wirklich, wenn Strings keine Itemzuordnung haben und Listen keine find. Ich werde nach einem besseren Weg Ausschau halten als nach meiner schnellen Lösung, die ich jetzt habe.

Meine Methode besteht darin, die Eingabe in eine Dezimalzahl und dann in die Ausgabebasis umzuwandeln und diese dann in die bijektive Basis umzuwandeln.

Bearbeiten : Ich habe festgestellt, dass mein Programm beim Konvertieren nach Unary nicht funktioniert hat. Das Reparieren mit e=F(o)<2usw. kostet 13 Bytes .

Probieren Sie es hier aus

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

Hier gibt es wirklich keine besonderen Tricks, außer das [2::5]Aufteilen, um den Zeichensatz mit einer niedrigeren Byteanzahl zu erhalten.

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

Tests:

"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

Die neueste Version verwendet den CJam Base-Konvertierungsoperator für die Konvertierung von der Quellbasis, an die ich erst gedacht hatte, als ich @ aditsus Lösung sah. Es wird auch ein neuer Tipp von @Dennis für die Erstellung der Zeichenfolge "digit" ( https://codegolf.stackexchange.com/a/54348/32852 ) sowie einige andere im Chat geteilte Ideen verwendet.

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

Das Eingabeformat ist der Wert, gefolgt von der Quell- und Zielbasis, wobei sich jede in einer separaten Zeile befindet. Lassen Sie für die leere Zeichenfolge die erste Zeile leer. Beispiel Eingabe:

122
2
A

Probieren Sie es online aus

Erläuterung:

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.

Jelly , 22 Bytes

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

Probieren Sie es online!