El lenguaje J tiene una sintaxis muy tonta para especificar constantes . Quiero centrarme en una característica interesante en particular: la capacidad de escribir en bases arbitrarias.
Si se escribe XbY
para X
cualquier número y Y
cualquier cadena de caracteres alfanuméricos, entonces J interpretará Y
como base X
el número, donde 0
a través 9
tienen su significado habitual ya
a través z
representan 10 a 35.
Y cuando digo X
cualquier número, me refiero a cualquier número. Para los propósitos de esta pregunta, me limitaré X
a ser un número entero positivo, pero en J puedes usar cualquier cosa: números negativos, fracciones, números complejos, lo que sea.
Lo extraño es que solo puede usar los números del 0 al 35 como su base, independientemente de los dígitos, porque su colección de símbolos utilizables consta solo de 0-9 y az.
El problema
Quiero un programa que me ayude a usar números mágicos de golf como 2,933,774,030,998 usando este método. Bueno, está bien, tal vez no sea tan grande, seré fácil contigo. Entonces...
Su tarea es escribir un programa o función que tome un número decimal (generalmente grande)
N
entre 1 y 4,294,967,295 (= 2 32 -1) como entrada, y salidas / devuelve la representación más corta de la formaXbY
, dondeX
es un entero positivo,Y
es una cadena que consiste en alfanuméricos (0-9 y az, sin distinción entre mayúsculas y minúsculas), eY
interpretada en basesX
igualesN
.Si la longitud de cada representación de
XbY
representación es mayor o igual que el número de dígitos deN
, entonces se genera la salidaN
. En todos los demás vínculos, puede generar cualquier subconjunto no vacío de las representaciones más cortas.
Este es el código de golf, así que más corto es mejor.
Casos de prueba
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 alguna vez no está seguro de si alguna representación es igual a algún número, puede usar cualquier intérprete de J, como el de Try It Online . Simplemente escriba stdout 0":87brgzpt
y J volverá a escupir 1557626714
. Tenga en cuenta que J solo acepta minúsculas, aunque este problema no distingue entre mayúsculas y minúsculas.
Alguna teoría posiblemente útil
- Para todos
N
menos de 10,000,000, la representación decimal es tan corta como cualquier otra y, por lo tanto, es la única salida aceptable. Para guardar cualquier cosa, deberá tener al menos cuatro dígitos menos en la nueva base, y aún más si la base es mayor que 99. - Es suficiente verificar las bases hasta el techo de la raíz cuadrada de
N
. Para cualquier base B más grande ,N
tendrá como máximo dos dígitos en la base B , por lo que la primera vez que obtenga algo con un primer dígito válido será alrededor de B ≈N
/ 35. Pero en ese tamaño siempre será al menos tan grande como la representación decimal, por lo que no tiene sentido intentarlo. Eso en mente, ceil (sqrt (número más grande para el que le pediré que resuelva este problema)) = 65536. - Si tiene alguna representación en una base inferior a 36, la representación de la base 36 será al menos tan corta. Por lo tanto, no tiene que preocuparse por soluciones accidentalmente cortas en bases de menos de 36. Por ejemplo, la representación
35bzzzzzz
de 1,892,332,260 usa un dígito inusual para esa base, pero36bvan8x0
tiene la misma longitud.
fuente
Respuestas:
JavaScript (ES6),
103bytesToma la entrada como una cadena.
Casos de prueba
NB: el número de iteraciones en la función de fragmento está limitado a 600 para que los casos de prueba se completen más rápido. (De lo contrario, tomaría unos segundos).
Mostrar fragmento de código
fuente
Math.floor(x/b)
lugar dex/b|0
. (Pero no lo probé.)Ruby , 118 bytes
Esto estaba vinculado en otra pregunta y noté que no hay muchas respuestas aquí, así que decidí darle una oportunidad.
Recorre todas las bases hasta e incluyendo la entrada para construir todas las construcciones válidas de números J. Sin embargo, omite 1-8, porque no hay forma de que sean más cortas que la representación de base 10 de todos modos. Es una solución bastante ingenua, considerando todo, ya que llama a la
digits
generador para obtener los dígitos, pero dado que eso comienza con el dígito menos significativo primero, tenemosreverse
que obtener el número real, por lo que posiblemente podría mejorarse.Es lento. Entonces, muuuy increíblemente lento. TIO agota el tiempo de espera en 34307000, por ejemplo. Nos podíamos ir con la raíz cuadrada o incluso la elección de Arnauld de
7e4
ahorrar tiempo, pero bytes que los costos adicionales, así que ¿por qué molestarse?Pruébalo en línea!
Pruébelo en línea con sqrt para que todo termine a tiempo
fuente
05AB1E , 37 bytes
Debería funcionar en teoría, pero el tiempo de espera para todos los casos de prueba no triviales, incluso≥ 4 ..
10000000
. El producto cartesiano incorporadoã
es extremadamente lento paraSin la declaración final if
DgIg@i\}
, aún puede probarse para valores más bajos, para verificar que realmente funciona: Pruébelo en línea.Veré si puedo encontrar una solución (probablemente mucho más larga pero) más eficiente más adelante.
Explicación:
fuente
XbY
representación es mayor o igual que el número de dígitos deN
, entonces, en suN
lugar , genera ". Si bien tiene los primeros 10 millones de números cubiertos, sospecho que una entrada de10000031
devolverá algo como26blmoof
. El número es válido, pero la longitud es la misma que la entrada, por lo que debería devolver la entrada.