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 XbY
für eine X
beliebige Nummer schreiben undY
beliebige alphanumerische Zeichenfolge , interpretiert J Y
als Basiszahl X
, wobei 0
through 9
die übliche Bedeutung hat und a
through z
10 bis 35 darstellt.
Und wenn ich X
irgendeine Zahl sage , meine ich irgendeine Zahl. Für die Zwecke dieser Frage beschränke ich mich X
darauf, 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
N
zwischen 1 und 4.294.967.295 (= 2 32 -1) als Eingabe verwendet und die kürzeste Darstellung des Formulars ausgibt / zurückgibtXbY
, wobeiX
es sich um eine positive GanzzahlY
handelt Eine Zeichenfolge, die aus alphanumerischen Zeichen (0-9 und az, ohne Berücksichtigung der Groß- und Kleinschreibung) besteht undY
inX
Basisgleichungen interpretiert wirdN
.Wenn die Länge jeder Repräsentationsrepräsentation
XbY
größer oder gleich der Anzahl der Stellen von istN
, wirdN
stattdessen 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":87brgzpt
und 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 sindN
höchstens zwei Stellen in der Basis B enthalten , sodass das erste Mal, dass Sie etwas mit einer gültigen ersten Stelle erhalten, bei etwa B ≈N
/ 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
35bzzzzzz
für 1.892.332.260 verwendet beispielsweise eine ungewöhnliche Ziffer für diese Basis,36bvan8x0
hat jedoch dieselbe Länge.
quelle
Antworten:
JavaScript (ES6),
103 bis101 ByteÜbernimmt die Eingabe als Zeichenfolge.
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.)
Code-Snippet anzeigen
quelle
Math.floor(x/b)
anstelle vonx/b|0
. (Aber ich habe es nicht getestet.)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
digits
Built-In aufruft, um die Ziffern abzurufen, aber da dies mit der am wenigsten signifikanten Ziffer beginnt, müssen wirreverse
sie 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?Probieren Sie es online!
Probieren Sie es online mit sqrt aus, damit alles pünktlich fertig wird
quelle
05AB1E , 37 Bytes
Sollte theoretisch funktionieren, aber für alle nicht-trivialen Testfälle auch mal raus≥ 4 ..
10000000
. Das kartesische Produktã
ist extrem langsam fürOhne 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:
quelle
XbY
größer oder gleich der Anzahl der Ziffern von istN
, wirdN
stattdessen ausgegeben ." Während Sie die ersten 10 Millionen Zahlen abgedeckt haben, vermute ich, dass eine Eingabe von10000031
so etwas zurückgeben wird26blmoof
. Die Nummer ist gültig, aber die Länge entspricht der Eingabe, sodass stattdessen die Eingabe zurückgegeben werden sollte.