Große Basis, kleine Ziffern

19

Die J-Sprache hat eine sehr alberne Syntax zum Angeben von Konstanten . Ich möchte mich auf ein cooles Feature konzentrieren: die Fähigkeit, in beliebigen Basen zu schreiben.

Wenn Sie XbYfür eine Xbeliebige Nummer schreiben undY beliebige alphanumerische Zeichenfolge , interpretiert J Yals Basiszahl X, wobei 0through 9die übliche Bedeutung hat und athrough z10 bis 35 darstellt.

Und wenn ich Xirgendeine Zahl sage , meine ich irgendeine Zahl. Für die Zwecke dieser Frage beschränke ich mich Xdarauf, eine positive ganze Zahl zu sein, aber in J können Sie alles verwenden: negative Zahlen, Brüche, komplexe Zahlen, was auch immer.

Das Seltsame ist das Sie nur die Zahlen von 0 bis 35 als Basis verwenden können, unabhängig von den Ziffern, da Ihre Sammlung verwendbarer Symbole nur aus 0-9 und az besteht.

Das Problem

Ich möchte ein Programm, mit dem ich magische Zahlen wie Golf spielen kann hilft, mit dieser Methode 2.933.774.030.998 zu spielen . Na gut, vielleicht nicht so groß, ich werde dich schonen. So...

Ihre Aufgabe ist es, ein Programm oder eine Funktion zu schreiben, die eine (normalerweise große) Dezimalzahl Nzwischen 1 und 4.294.967.295 (= 2 32 -1) als Eingabe verwendet und die kürzeste Darstellung des Formulars ausgibt / zurückgibt XbY, wobei Xes sich um eine positive Ganzzahl Yhandelt Eine Zeichenfolge, die aus alphanumerischen Zeichen (0-9 und az, ohne Berücksichtigung der Groß- und Kleinschreibung) besteht und Yin XBasisgleichungen interpretiert wird N.

Wenn die Länge jeder Repräsentationsrepräsentation XbYgrößer oder gleich der Anzahl der Stellen von ist N, wird Nstattdessen ausgegeben . Bei allen anderen Verbindungen können Sie eine beliebige nicht leere Teilmenge der kürzesten Darstellungen ausgeben.

Dies ist Codegolf, also ist kürzer besser.

Testfälle

      Input | Acceptable outputs (case-insensitive)
------------+-------------------------------------------------------
          5 | 5
            |
   10000000 | 79bkmom  82bibhi  85bgo75  99bauua  577buld
            | 620bq9k  999baka
            |
   10000030 | 85bgo7z
            |
   10000031 | 10000031
            |
   12345678 | 76bs9va  79bp3cw  82bmw54  86bjzky  641buui
            |
   34307000 | 99bzzzz
            |
   34307001 | 34307001
            |
 1557626714 | 84bvo07e  87brgzpt  99bglush  420blaze
            |
 1892332260 | 35bzzzzzz  36bvan8x0  37brapre5  38bnxkbfe  40bij7rqk
            | 41bgdrm7f  42bek5su0  45bablf30  49b6ycriz  56b3onmfs
            | 57b38f9gx  62b244244  69b1expkf  71b13xbj3
            |
 2147483647 | 36bzik0zj  38br3y91l  39bnvabca  42bgi5of1  48b8kq3qv
 (= 2^31-1) | 53b578t6k  63b2akka1  1022b2cof  1023b2661  10922bio7
            | 16382b8wv  16383b8g7  32764b2gv  32765b2ch  32766b287
            | 32767b241
            |
 2147483648 | 512bg000  8192bw00
            |
 4294967295 | 45bnchvmu  60b5vo6sf  71b2r1708  84b12mxf3  112brx8iv
 (= 2^32-1) | 126bh5aa3  254b18owf  255b14640  1023b4cc3  13107bpa0
            | 16383bgwf  21844b9of  21845b960  32765b4oz  32766b4gf
            | 32767b483  65530b1cz  65531b1ao  65532b18f  65533b168
            | 65534b143  65535b120

Wenn Sie sich nicht sicher sind, ob eine Darstellung einer bestimmten Zahl entspricht, können Sie einen beliebigen J-Interpreter verwenden, wie den auf Try It Online . Tippen Sie einfach ein stdout 0":87brgzptund J wird wieder ausspucken 1557626714. Beachten Sie, dass J nur Kleinbuchstaben akzeptiert, obwohl bei diesem Problem die Groß- und Kleinschreibung nicht beachtet wird.

Einige möglicherweise hilfreiche Theorie

  • Für alle N weniger als 10.000.000 ist die Dezimaldarstellung so kurz wie jede andere und daher die einzig akzeptable Ausgabe. Um etwas zu speichern, müssten Sie in der neuen Basis mindestens vier Stellen kürzer sein, und noch mehr, wenn die Basis größer als 99 ist.
  • Es reicht aus, die Sockel bis zur Decke der Quadratwurzel von zu überprüfen N. Bei jeder größeren Basis B sind Nhöchstens zwei Stellen in der Basis B enthalten , sodass das erste Mal, dass Sie etwas mit einer gültigen ersten Stelle erhalten, bei etwa BN/ 35 liegt. Aber bei dieser Größe sind Sie immer mindestens so groß wie die Dezimaldarstellung. Es macht also keinen Sinn, es zu versuchen. Diesbezüglich ist ceil (sqrt (größte Zahl, für die ich Sie bitten werde, dieses Problem zu lösen)) = 65536.
  • Wenn Sie in einer Basis weniger als 36 Darstellungen haben, ist die Darstellung der Basis 36 mindestens so kurz. Sie müssen sich also nicht um versehentlich kurze Lösungen in weniger als 36 Basen kümmern. Die Darstellung 35bzzzzzzfür 1.892.332.260 verwendet beispielsweise eine ungewöhnliche Ziffer für diese Basis, 36bvan8x0hat jedoch dieselbe Länge.
algorithmshark
quelle
Lol, 1557626714 = 420blaze ^ _ ^
DrQuarius

Antworten:

9

JavaScript (ES6), 103 bis 101 Byte

Übernimmt die Eingabe als Zeichenfolge.

n=>[...Array(7e4)].reduce(p=>p[(r=++b+(g=x=>x?g(x/b|0)+(x%b).toString(36):'b')(n)).length]?r:p,n,b=2)

Testfälle

Hinweis: Die Anzahl der Iterationen in der Snippet-Funktion ist auf 600 begrenzt, damit die Testfälle schneller abgeschlossen werden. (Andernfalls würde es einige Sekunden dauern.)

Arnauld
quelle
Wenn meine Nummer zu groß ist, um damit zu arbeiten, wie kann ich das beheben? Das Erhöhen der Iterationen scheint nicht zu helfen.
FrownyFrog
N<232
Suche nach "schädlichen Zahlen", 2136894800297704.
FrownyFrog
@FrownyFrog Sie können es verarbeiten können , indem die Anzahl der Iterationen zu erhöhen und unter Verwendung Math.floor(x/b)anstelle von x/b|0. (Aber ich habe es nicht getestet.)
Arnauld
1
es funktionierte! Vielen Dank.
FrownyFrog
3

Ruby , 118 Bytes

Dies hing mit einer anderen Frage zusammen und ich bemerkte, dass es hier nicht viele Antworten gibt, also beschloss ich, es einmal zu versuchen.

Gehen Sie alle Basen bis einschließlich der Eingabe durch, um alle gültigen J-Zahlenkonstruktionen zu konstruieren. Es werden jedoch 1-8 übersprungen, da diese sowieso nicht kürzer als die Basis-10-Darstellung sein werden. Alles in allem ist es eine ziemlich naive Lösung, da sie das digitsBuilt-In aufruft, um die Ziffern abzurufen, aber da dies mit der am wenigsten signifikanten Ziffer beginnt, müssen wir reversesie zuerst verwenden, um die tatsächliche Zahl abzurufen , sodass sie möglicherweise verbessert werden könnte.

Es ist langsam. Also soooooo unglaublich langsam. TIO läuft beispielsweise bei 34307000 ab. Wir könnten uns für die Quadratwurzel entscheiden oder sogar für Arnauld 7e4, um Zeit zu sparen, aber das kostet zusätzliche Bytes. Warum also die Mühe machen?

->n{([n.to_s]+(9..n).map{|b|d=n.digits b;"#{b}b"+d.reverse.map{|i|i.to_s 36}*''if d.all?{|i|i<36}}-[p]).min_by &:size}

Probieren Sie es online!

Probieren Sie es online mit sqrt aus, damit alles pünktlich fertig wird

Wert Tinte
quelle
1

05AB1E , 37 Bytes

[¼35ݾãvtîEyNβQižhA«yèJ'bìNìDgIg@i\}q

Sollte theoretisch funktionieren, aber für alle nicht-trivialen Testfälle auch mal raus 10000000. Das kartesische Produkt ãist extrem langsam für4..

Ohne die endgültige if-Anweisung DgIg@i\}kann es immer noch auf niedrigere Werte getestet werden, um sicherzustellen, dass es tatsächlich funktioniert: Probieren Sie es online aus.

Mal sehen, ob ich später eine (wahrscheinlich viel längere, aber) effizientere Lösung finden kann.

Erläuterung:

[              # Start an infinite loop:
 ¼             #  Increase the counter variable by 1 (0 by default)
 35Ý           #  Push a list in the range [0, 35]
 ¾ã            #  Take the cartesian product of this list with itself,
               #  with chunks-sizes equal to the counter variable
 v             #  Loop `y` over each of these lists:
  t            #   Take the square-root of the (implicit) input-integer
   î           #   Ceil it
  E            #   Loop `N` in the range [1, ceil(square(input))]:
   yNβ         #    Convert list `y` to base-`N`
   Qi          #    If it's equal to the (implicit) input-integer:
     žh        #     Push string "0123456789"
       A«      #     Append the lowercase alphabet
     yè        #     Index each value in list `y` into this string
     J         #     Join the characters to a single string
     'bì      '#     Prepend a "b"
        Nì     #     Prepend the number `N`
     D         #     Duplicate it
      g        #     And pop and push the length of this string
       Ig      #     Also push the length of the input
         @i }  #     If the length of the string is >= the input-length:
           \   #      Discard the duplicated string
     q         #     Stop the program
               #     (after which the result is output implicitly;
               #      or if the string was discarded and the stack is empty, it will
               #      implicitly output the implicit input as result instead)
Kevin Cruijssen
quelle
1
Beeindruckende Antwort! Ich denke, Sie vermissen jedoch eine Regel: "Wenn die Länge jeder Repräsentationsrepräsentation XbYgrößer oder gleich der Anzahl der Ziffern von ist N, wird Nstattdessen ausgegeben ." Während Sie die ersten 10 Millionen Zahlen abgedeckt haben, vermute ich, dass eine Eingabe von 10000031so etwas zurückgeben wird 26blmoof. Die Nummer ist gültig, aber die Länge entspricht der Eingabe, sodass stattdessen die Eingabe zurückgegeben werden sollte.
Wert Tinte
@ValueInk Hoppla. Danke fürs bemerken! Sollte jetzt auf Kosten einiger Bytes behoben werden.
Kevin Cruijssen