13
\$\begingroup\$

The J language has a very silly syntax for specifying constants. I want to focus on one cool feature in particular: the ability to write in arbitrary bases.

If you write XbY for X any number and Y any string of alphanumerics, then J will interpret Y as a base X number, where 0 through 9 have their usual meaning and a through z represent 10 through 35.

And when I say X any number, I mean any number. For the purposes of this question, I'll constrain X to be a positive integer, but in J you can use anything: negative numbers, fractions, complex numbers, whatever.

The thing that's weird is that you can only use the numbers from 0 to 35 as your base-whatever digits, because your collection of usable symbols consists only of 0-9 and a-z.

The problem

I want a program to help me golf magic numbers like 2,933,774,030,998 using this method. Well, okay, maybe not that big, I'll go easy on you. So...

Your task is to write a program or function which takes a (usually large) decimal number N between 1 and 4,294,967,295 (= 232-1) as input, and outputs/returns the shortest representation of the form XbY, where X is a positive integer, Y is a string consisting of alphanumerics (0-9 and a-z, case insensitive), and Y interpreted in base X equals N.

If the length of every representation XbY representation is greater than or equal to the number of digits of N, then output N instead. In all other ties, you may output any nonempty subset of the shortest representations.

This is code golf, so shorter is better.

Test cases

      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

If you're ever unsure about whether some representation is equal to some number, you can use any J interpreter, like the one on Try It Online. Just type in stdout 0":87brgzpt and J will spit back out 1557626714. Note that J only accepts lowercase, even though this problem is case-insensitive.

Some possibly helpful theory

  • For all N less than 10,000,000, the decimal representation is as short as any other and hence is the only acceptable output. To save anything you would need to be at least four digits shorter in the new base, and even more if the base is greater than 99.
  • It suffices to check bases up to the ceiling of the square root of N. For any larger base B, N will be at most two digits in base B, so the first time you'll get something with a valid first digit is at around BN/35. But at that size you will always be at least as large as the decimal representation, so there's no point in trying. That in mind, ceil(sqrt(largest number I'll ask you to solve this problem for)) = 65536.
  • If you have any representation in a base less than 36, then the base 36 representation will be at least as short. So you don't have to worry about accidentally short solutions in bases less than 36. For example, the representation 35bzzzzzz for 1,892,332,260 uses an unusual digit for that base, but 36bvan8x0 has the same length.
\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES6), 103 101 bytes

Takes input as a string.

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)

Test cases

NB: The number of iterations in the snippet function is limited to 600 so that the test cases complete faster. (It would take a few seconds otherwise.)

let f =

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

console.log(f("5"))
console.log(f("10000000"))
console.log(f("10000030"))
console.log(f("10000031"))
console.log(f("12345678"))
console.log(f("34307000"))
console.log(f("34307001"))
console.log(f("1557626714"))
console.log(f("1892332260"))
console.log(f("2147483647"))
console.log(f("2147483648"))
console.log(f("4294967295"))

\$\endgroup\$
  • \$\begingroup\$ If my number is too large to work with this, how would I fix it? Increasing the iterations doesn't seem to help. \$\endgroup\$ – FrownyFrog Aug 25 '18 at 14:17
  • \$\begingroup\$ @FrownyFrog Which number are you trying to process? This code is supposed to work for \$N<2^{32}\$, as per the challenge rules. \$\endgroup\$ – Arnauld Aug 25 '18 at 14:22
  • \$\begingroup\$ "Pernicious numbers" lookup, 2136894800297704. \$\endgroup\$ – FrownyFrog Aug 25 '18 at 14:23
  • \$\begingroup\$ @FrownyFrog You may be able to process it by increasing the number of iterations and using Math.floor(x/b) instead of x/b|0. (But I didn't test it.) \$\endgroup\$ – Arnauld Aug 25 '18 at 14:27
  • 1
    \$\begingroup\$ it worked! Thank you. \$\endgroup\$ – FrownyFrog Aug 25 '18 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.