Le langage J a une syntaxe très idiote pour spécifier des constantes . Je veux me concentrer sur une fonctionnalité intéressante en particulier: la possibilité d'écrire dans des bases arbitraires.
Si vous écrivez XbY
pour X
n'importe quel nombre et Y
n'importe quelle chaîne alphanumérique, alors J interprétera Y
comme un X
nombre de base , où 0
through 9
a leur signification habituelle et a
through z
représente 10 à 35.
Et quand je dis X
n'importe quel nombre, je veux dire n'importe quel nombre. Aux fins de cette question, je vais contraindre X
à être un entier positif, mais en J, vous pouvez utiliser n'importe quoi: nombres négatifs, fractions, nombres complexes, peu importe.
Ce qui est bizarre, c'est que vous ne pouvez utiliser que les chiffres de 0 à 35 comme chiffres de base, car votre collection de symboles utilisables se compose uniquement de 0-9 et az.
Le problème
Je veux un programme pour m'aider avec des nombres magiques de golf comme 2,933,774,030,998 en utilisant cette méthode. Bon, d'accord, peut-être pas si gros que ça, je vais aller doucement avec toi. Donc...
Votre tâche consiste à écrire un programme ou une fonction qui prend un nombre décimal (généralement grand)
N
entre 1 et 4 294 967 295 (= 2 32 -1) en entrée, et génère / renvoie la représentation la plus courte du formulaireXbY
, oùX
est un entier positif,Y
est une chaîne composée de caractères alphanumériques (0-9 et az, insensible à la casse) etY
interprétée en baseX
égaleN
.Si la longueur de chaque représentation de
XbY
représentation est supérieure ou égale au nombre de chiffres deN
, sortez à laN
place. Dans tous les autres liens, vous pouvez générer n'importe quel sous-ensemble non vide des représentations les plus courtes.
C'est le golf de code, donc plus court est mieux.
Cas de test
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
Si vous n'êtes jamais sûr de savoir si une représentation est égale à un certain nombre, vous pouvez utiliser n'importe quel interpréteur J, comme celui de Try It Online . Tapez simplement stdout 0":87brgzpt
et J crachera 1557626714
. Notez que J accepte uniquement les minuscules, même si ce problème n'est pas sensible à la casse.
Une théorie peut-être utile
- Pour tous les
N
moins de 10 000 000, la représentation décimale est aussi courte que les autres et est donc la seule sortie acceptable. Pour enregistrer quoi que ce soit, vous devez être au moins quatre chiffres plus court dans la nouvelle base, et encore plus si la base est supérieure à 99. - Il suffit de vérifier les bases jusqu'au plafond de la racine carrée de
N
. Pour toute base B plus grande , il yN
aura au plus deux chiffres dans la base B , donc la première fois que vous obtiendrez quelque chose avec un premier chiffre valide se situe autour de B ≈N
/ 35. Mais à cette taille, vous serez toujours au moins aussi grand que la représentation décimale, il est donc inutile d'essayer. Cela à l'esprit, ceil (sqrt (le plus grand nombre pour lequel je vous demanderai de résoudre ce problème)) = 65536. - Si vous avez une représentation dans une base inférieure à 36, la représentation de la base 36 sera au moins aussi courte. Vous n'avez donc pas à vous soucier de solutions accidentellement courtes dans des bases inférieures à 36. Par exemple, la représentation
35bzzzzzz
de 1 892 332 260 utilise un chiffre inhabituel pour cette base, mais36bvan8x0
a la même longueur.
la source
Réponses:
JavaScript (ES6),
103101 octetsPrend l'entrée sous forme de chaîne.
Cas de test
NB: Le nombre d'itérations dans la fonction d'extrait est limité à 600 afin que les cas de test se terminent plus rapidement. (Sinon, cela prendrait quelques secondes.)
Afficher l'extrait de code
la source
Math.floor(x/b)
au lieu dex/b|0
. (Mais je ne l'ai pas testé.)Rubis , 118 octets
C'était lié dans une autre question et j'ai remarqué qu'il n'y a pas beaucoup de réponses ici, alors j'ai décidé de tenter le coup.
Parcourez toutes les bases jusqu'à et y compris l'entrée pour construire toutes les constructions de nombres J valides. Cependant, il saute de 1 à 8, car il ne sera en aucun cas plus court que la représentation de base 10. C'est une solution assez naïve, tout bien considéré, car il appelle le
digits
code intégré pour obtenir les chiffres, mais comme cela commence par le chiffre le moins significatif, nous devons d'abordreverse
obtenir le numéro réel, il pourrait donc être amélioré.C'est lent. Donc, soooooo incroyablement lent. TIO expire par exemple sur 34307000. Nous pourrions choisir la racine carrée ou même le choix d'Arnauld de
7e4
gagner du temps, mais cela coûte des octets supplémentaires, alors pourquoi s'embêter?Essayez-le en ligne!
Essayez-le en ligne avec sqrt pour que tout se termine à temps
la source
05AB1E , 37 octets
10000000
ã
Sans l'instruction if finale,
DgIg@i\}
il peut toujours être testé pour des valeurs inférieures, pour vérifier qu'il fonctionne réellement: Essayez-le en ligne.Je verrai si je peux trouver une solution (probablement beaucoup plus longue mais) plus efficace plus tard.
Explication:
la source
XbY
représentation est supérieure ou égale au nombre de chiffres deN
, alors sortez à laN
place." Bien que vous ayez couvert les 10 premiers millions de numéros, je soupçonne qu'une entrée de10000031
donnera quelque chose comme26blmoof
. Le nombre est valide, mais la longueur est la même que l'entrée, il devrait donc renvoyer l'entrée à la place.