23
\$\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 B ≈ N/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.
Improve this question
\$\endgroup\$
1
  • \$\begingroup\$ Lol, 1557626714 = 420blaze ^_^ \$\endgroup\$ Commented Aug 26, 2019 at 1:35

3 Answers 3

Reset to default
9
\$\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"))

Improve this answer
\$\endgroup\$
5
  • \$\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\$ Commented Aug 25, 2018 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\$ Commented Aug 25, 2018 at 14:22
  • \$\begingroup\$ "Pernicious numbers" lookup, 2136894800297704. \$\endgroup\$ Commented Aug 25, 2018 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\$ Commented Aug 25, 2018 at 14:27
  • 1
    \$\begingroup\$ it worked! Thank you. \$\endgroup\$ Commented Aug 25, 2018 at 14:30
3
\$\begingroup\$

Ruby, 118 bytes

This was linked in another question and I noticed there aren't many answers here, so I decided to give it a shot.

Walk through all bases up to and including the input to construct all valid J number constructions. It skips 1-8 though, because there's no way those will be shorter than the base-10 representation anyways. It's a pretty naive solution, all things considered, since it calls the digits builtin to get the digits, but since that starts with the least significant digit first we have to reverse it to get the actual number, so it could possibly be improved.

It's slow. So, soooooo incredibly slow. TIO times out on 34307000, for example. We could go with the square root or even Arnauld's choice of 7e4 to save time, but that costs extra bytes, so why bother?

->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}

Try it online!

Try it online w/ sqrt so everything finishes on time

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 37 bytes

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

Should work in theory, but times out for all non-trivial test cases, even 10000000. The cartesian product builtin ã is extremely slow for \$\geq4\$..

Without the final if-statement DgIg@i\} it can still be tested for lower values, to verify that it does in fact work: Try it online.

Will see if I can come up with a (probably much longer but) more efficient solution later on.

Explanation:

[ # 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)
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Impressive answer! I think you're missing a rule, though: "If the length of every representation XbY representation is greater than or equal to the number of digits of N, then output N instead." While you do have the first 10 million numbers covered, I suspect that an input of 10000031 will give back something like 26blmoof. The number is valid, but the length is the same as the input, so it should be returning the input instead. \$\endgroup\$ Commented Jun 21, 2019 at 18:38
  • \$\begingroup\$ @ValueInk Ah oops. Thanks for noticing! Should be fixed now at the cost of a few bytes. \$\endgroup\$ Commented Jun 21, 2019 at 19:18

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.