Ihre gesamte bijektive Basis gehört uns

25

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 0 i (a 0 ) .

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 .

Dennis
quelle

Antworten:

6

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
aditsu
quelle
Oh, können Sie den regulären Basiskonvertierungsoperator tatsächlich für die erste Basiskonvertierung verwenden? Jetzt bin ich dumm, den ganzen Code zu verwenden, den ich in meiner Lösung habe. :) Ich wusste nicht, dass es mit Werten funktionieren würde, die außerhalb des Bereichs der Basis liegen. Nun, im Nachhinein gibt es keinen guten Grund, warum es nicht sollte.
Reto Koradi
@RetoKoradi ja, das kannst du machen; Eines Tages wird es dokumentiert :)
aditsu
Stört es Sie, wenn ich meine Lösung ändere, um die Basiskonvertierung zu verwenden? Normalerweise versuche ich zu vermeiden, Ideen aus anderen Lösungen zu übernehmen. Aber es nervt mich wirklich, meine mit einem so suboptimalen Ansatz stehen zu lassen. Es ist sehr wahrscheinlich, dass Ihre Lösung noch kürzer ist.
Reto Koradi
@RetoKoradi kein Problem, fahren Sie fort
aditsu
4

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
DLosc
quelle
4

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 1 × k + c 2 × k - 1 + ... + c k × 0

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
>>
Becherglas
quelle
2

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 
}
Samgak
quelle
2

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)
mbomb007
quelle
1
Ich stimme Ihrem Python-Haustier zu.
DLosc
@ DLosc Danke für die Golfhilfe.
mbomb007
ist das Code-Bowling ? : P
Optimizer
Listen haben die .index()Methode .. Warum nicht verwenden, anstatt zu finden? Anstatt sie zu speichern F(b)und F(o)Variablen zuzuweisen, verwenden Sie sie nur einmal und reichen sie bei Bedarf ein. Schließlich 'n'[2::5]ist kürzer als ''.join(n)(ersetzen Sie Apostrophe für Backticks).
Kade
Ich denke auch, dass Sie dies zu kompliziert machen. Die Konvertierung von einer bijektiven Zeichenfolge M-Basis b in eine Dezimalzahl sollte nicht mehr als 35-40 Byte dauern. Die Dezimalstelle zu einer Folge von bijektiven Basis B wird nicht viel mehr sein.
Kade
2

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
Kade
quelle
2

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.
Reto Koradi
quelle