Язык J имеет очень глупый синтаксис для определения констант . Я хочу сосредоточиться на одной интересной особенности в частности: способность писать произвольно.

Если вы пишете XbYдля Xлюбого числа и Yлюбой строки буквенно-цифровых символов, то J будет интерпретироваться Yкак базовое Xчисло, где 0сквозные 9имеют свое обычное значение, а aсквозные zобозначают от 10 до 35.

И когда я говорю Xлюбое число, я имею в виду любое число. Для целей этого вопроса я ограничусь Xположительным целым числом, но в J вы можете использовать что угодно: отрицательные числа, дроби, комплексные числа, что угодно.

Странно то, что вы можете использовать только цифры от 0 до 35 в качестве своей базовой цифры, независимо от того, какие цифры вы используете, потому что ваша коллекция используемых символов состоит только из 0-9 и az.

Проблема

Я хочу, чтобы программа помогла мне использовать магические числа в гольф, такие как 2 933 774 030 998, используя этот метод. Ну, ладно, может быть, не так уж и много, я с тобой справлюсь. Так...

Ваша задача - написать программу или функцию, которая принимает (обычно большое) десятичное число Nот 1 до 4 294 967 295 (= 2 ³² -1) в качестве входных данных и выводит / возвращает самое короткое представление формы XbY, где Xположительное целое число Yравно строка, состоящая из буквенно-цифровых символов (0-9 и az, без учета регистра) и Yинтерпретируемая в базовых Xравных N.

Если длина каждого представления XbYпредставления больше или равна количеству цифр N, то Nвместо этого выведите . Во всех других связях вы можете вывести любое непустое подмножество кратчайших представлений.

Это код гольф, поэтому чем короче, тем лучше.

Контрольные примеры

      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

Если вы когда-либо не уверены, равно ли какое-либо представление некоторому числу, вы можете использовать любой J-интерпретатор, например, такой, как в Try It Online . Просто введите stdout 0":87brgzptи J выплюнет обратно 1557626714. Обратите внимание, что J принимает только строчные буквы, даже если эта проблема не чувствительна к регистру.

Некоторая, возможно, полезная теория

• Для всех Nменее 10 000 000 десятичное представление такое же короткое, как и любое другое, и, следовательно, является единственным приемлемым выходным значением. Чтобы сохранить что-либо, вам нужно быть как минимум на четыре цифры короче в новой базе, и даже больше, если база больше 99.
• Достаточно проверить основания до потолка квадратного корня N. Для любого большего основания B , Nбудет не более два цифр в базовой B , поэтому в первый раз , вы получите что - то с действительной первой цифрой около B ≈ N/ 35. Но при таком размере вы всегда будете не меньше десятичного представления, так что нет смысла пытаться. Помните, что ceil (sqrt (наибольшее число, для которого я попрошу вас решить эту проблему)) = 65536.
• Если у вас есть какое-либо представление в базе менее 36, то представление в базе 36 будет по меньшей мере таким же коротким. Таким образом, вам не нужно беспокоиться о случайно коротких решениях в базах менее 36. Например, представление 35bzzzzzzдля 1 892 322 260 использует необычную цифру для этой базы, но 36bvan8x0имеет ту же длину.

JavaScript (ES6), 103 101 байт

Принимает ввод в виде строки.

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)

Контрольные примеры

NB. Количество итераций в функции сниппета ограничено 600, чтобы тесты выполнялись быстрее. (В противном случае это займет несколько секунд.)

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"))

Рубин , 118 байт

Это было связано с другим вопросом, и я заметил, что здесь не так много ответов, поэтому я решил дать ему шанс.

Пройдите по всем базам вплоть до ввода, чтобы построить все действительные конструкции числа J. Это пропускает 1-8, хотя, потому что никоим образом они не будут короче, чем представление 10. Это довольно наивное решение, учитывая все обстоятельства, так как оно вызывает digitsвстроенную функцию для получения цифр, но, поскольку она начинается с наименее значащей цифры, сначала мы должны reverseполучить фактическое число, поэтому его можно улучшить.

Это медленно. Так оооочень невероятно медленно. Тайм-аут на 34307000, например. Мы могли бы пойти с квадратным корнем или даже выбором Арно, 7e4чтобы сэкономить время, но это стоит дополнительных байтов, так зачем беспокоиться?

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

Попробуйте онлайн!

Попробуйте онлайн с sqrt, чтобы все закончилось вовремя

05AB1E , 37 байт

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

10000000ã$\geq4$

Без окончательного оператора if DgIg@i\}он все еще может быть проверен на более низкие значения, чтобы убедиться, что он действительно работает: попробуйте его онлайн.

Посмотрим, смогу ли я придумать (возможно, гораздо дольше, но) более эффективное решение позже.

Объяснение:

[              # 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)