La mejor base es 10 ... ¡Hagámoslo!

40

Entrada:

Un entero positivo n que consta de dígitos en el rango 0-9 .

Reto:

Si d es el dígito más alto en el entero, suponga que la base del número es d + 1 . Por ejemplo, si el número entero es 1256 , supondrá que está en base-7 , si es 10110 , supondrá que es base-2 (binario), y si es 159, entonces es decimal.

Ahora, haga lo siguiente hasta que: 1: alcance un entero de base 10 o 2: alcance un entero de un solo dígito.

  1. Convierta el número entero de base- (d + 1) a base-10
  2. Encuentre la base de este nuevo entero (nuevamente, base- (d + 1) donde d es el dígito más alto en el nuevo número)
  3. Ve al paso 1 .

Ejemplos:

Suponga que la entrada es n = 413574 . El dígito más alto d = 7 , entonces esto es base-8 (octal). Convierta esto a decimal y obtenga 137084 . El dígito más alto d = 8 , entonces esto es base-9 . Convierta esto a decimal y obtenga 83911 . El dígito más alto es 9 , entonces este es un número decimal y nos detenemos. La salida será 83911 .

Suponga que la entrada es n = 13552 . El dígito más alto es d = 5 , por lo que es base-6 . Convierta esto a decimal y obtenga 2156 . El dígito más alto d = 6 , entonces esto es base-7 . Convierte esto a decimal y obtén 776 . El dígito más alto es d = 7 , por lo que es base-8 . Convierta esto a decimal y obtenga 510 . El dígito más alto es d = 5, por lo que es base-6 . Convierta esto a decimal y obtenga 186 . El dígito más alto es 8 , por lo que es base-9 . Convierte esto a decimal y obtén 159. El dígito más alto es 9 , entonces este es un número decimal y nos detenemos. El resultado será 159 .

Suponga que la entrada es n = 17 . Esto nos dará 15 , luego 11 , luego 3 , que mostraremos ya que es un solo dígito.


Casos de prueba:

5
5

17
3

999
999

87654321  (base-9 -> 42374116 in decimal -> base-7 -> 90419978 in decimal) 
9041998

41253  (5505 -> 1265 -> 488 -> 404 -> 104 -> 29)
29

Notas:

  • Reglas estándar sobre E / S, lagunas, etc. Puede tomar la entrada como una cadena
  • Se alientan las explicaciones.
  • Puede usar comandos de conversión de base incorporados
    • Las soluciones que no utilizan las funciones integradas de conversión de bases del lenguaje (si existen) son bienvenidas, incluso si terminan siendo mucho más largas que el enfoque obvio que usa funciones incorporadas.

Aparentemente, esto es OEIS A091047 .

Stewie Griffin
fuente
2
Aparentemente amo las matrices , así que pensé en hacer un desafío de conversión de base .
Stewie Griffin
34
"La mejor base es 10" ... ¿En qué base está escrito "10"?
Olivier Grégoire
55
@ OlivierGrégoire Eso es lo inteligente ... ¡Cualquiera sea la base con la que terminemos, seguirá siendo una declaración válida!
Stewie Griffin
@StewieGriffin ¿Pero cómo lo lees? "10" tiene un nombre diferente en cada base.
user11153
10
Bueno, eso depende de la base ... o como diría Meghan "todo se trata de esa base, 'Sobre esa base, no hay problema" ;-)
Stewie Griffin

Respuestas:

20

Mathematica, 56 bytes

#//.x_/;(b=Max[d=IntegerDigits@x]+1)<11:>d~FromDigits~b&

Pruébalo en línea! (Usando matemáticas).

Pensé en comprobar cómo se ve la secuencia:

ingrese la descripción de la imagen aquí

Y aquí hay una gráfica del número de pasos necesarios para encontrar el resultado:

ingrese la descripción de la imagen aquí

(Haga clic para versiones más grandes. Consulte el historial de revisiones para gráficos solo hasta n = 1000 ).

Parece una mezcla muy interesante de estructura a gran escala y caos a gran escala. Me pregunto qué pasa con las brechas más amplias alrededor de 30,000 y 60,000.

Martin Ender
fuente
44
@StewieGriffin debe estar en el lado izquierdo. Las brechas pequeñas están ahí, porque los números que conducen a un múltiplo de una potencia de 10 contienen a 9, por lo que ya están en la base 10. Pero para 30k y 60k parece que los números con un 8 o incluso 7 (tendrían que check) en lugar de ese 9 siempre se convierte en base 10 después de como máximo un paso.
Martin Ender
@StewieGriffin Para ser precisos, todos los números en el rango [28051, 28888] son ​​base 9 y se traducen a números de la forma 19xxx, lo que duplica bastante esa brecha.
cmaster
Ah, lo tengo ... :) Para que conste: sabía por qué había huecos en el lado izquierdo de las potencias de los 10 ... Solo los huecos de doble tamaño eran extraños (por qué 30/60, y no 20 / 40/50). Ahora veo sin embargo que los números en el rango 28xxx -> 19xxx, pero 38xxx -> 26xxx, no 29xxx.
Stewie Griffin
10

Java 8, 172 166 163 152 151 140 138 116 114 99 bytes

s->{for(Integer b=0;b<10&s.length()>1;s=""+b.valueOf(s,b=s.chars().max().getAsInt()-47));return s;}

Toma la entrada como a String.

-64 bytes gracias a @ OlivierGrégoire . Y aquí pensé que mi 172 inicial no era tan malo ...;)

Pruébalo aquí

Explicación:

s->{                    // Method with String as parameter and return-type
  for(Integer b=0;b<10  //  Loop as long as the largest digit + 1 is not 10
      &s.length()>1;    //  and as long as `s` contains more than 1 digit
    s=""+               //   Replace `s` with the String representation of:
         b.valueOf(s,   //    `s` as a Base-`b` integer
          b=s.chars().max().getAsInt()-47)
                        //     where `b` is the largest digit in the String + 1
  );                    //  End of loop
  return s;             //  Return result-String
}                       // End of method
Kevin Cruijssen
fuente
1
¿Prometes mantener la calma? : p Ok ... vamos a ir: s->{for(Integer b=0;b<10&s.length()>1;)s=""+b.valueOf(s,b=s.chars().max().getAsInt()-47);return s;}. También eliminé la mayoría de mis comentarios, ya que ahora son totalmente irrelevantes ( bes la base, tu a; y ses el número en el que estamos trabajando).
Olivier Grégoire
1
Intenté recursificar esto para eliminar algunos bytes con: Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:c(""+b.valueOf(s,b));(88), pero soy nuevo en el código de golf. Este es un fragmento, ¿verdad? ¿Hay alguna manera de declarar esto como un método sin necesidad de agregar public String c(String s)?
Lord Farquaad
1
@LordFarquaad No necesita el public, pero me temo que tendrá que usarlo String c(String s){}para llamadas recursivas, incluso en Java 8. Cuando cree un lambda usando java.util.function.Function<String, String> c=s->{Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:c‌.apply​(""+b.valueOf(s,b));}o usando una interfaz interface N{String c(String s);}N n = s->{Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:n.c‌​(""+b.valueOf(s,b));};, le dará una " autorreferencia en el inicializador error "en ambos casos. Pero muy buen enfoque, no obstante!
Kevin Cruijssen
Ah, supongo que lo descarté unos pocos bytes entonces. ¡Pero gracias por la ayuda! Voy a tener esto en cuenta para seguir adelante.
Lord Farquaad
8

Pyth, 9 bytes

ui`GhseS`

Banco de pruebas

Explicación:

ui`GhseS`
ui`GhseS`GQ    Implicit variable introduction
u         Q    Repeatedly apply the following function until the value repeats,
               starting with Q, the input.
        `G     Convert the working value to a string.
      eS       Take its maximum.
     s         Convert to an integer.
    h          Add one.
 i`G           Convert the working value to that base
isaacg
fuente
Es un poco extraño cómo usaste una lambda de dos variables que terminó usando una variable ... y no arrojó errores. Oh, las dos variables son Qy Q, lo entiendo.
Erik the Outgolfer
@EriktheOutgolfer No exactamente. usin su tercera entrada se aplica hasta la repetición, mientras que con una tercera entrada se aplica un número fijo de veces. ulambda tiene Gy H, pero no necesita usar H.
isaacg
En realidad, la sustitución Gcon Hhabría tenido el mismo resultado ... por cierto variables implícita es G?
Erik the Outgolfer
@EriktheOutgolfer La variable implícita es Gsí. Hcuenta desde 0 con cada iteración, por lo que es completamente diferente. No estoy realmente seguro de lo que estás hablando. Aquí hay un programa de ejemplo para mostrarle lo que está sucediendo: pyth.herokuapp.com/…
isaacg
6

JavaScript (ES6), 63 57 54 53 bytes

f=a=>a>9&(b=Math.max(...a+""))<9?f(parseInt(a,b+1)):a

Guardado 8 bytes gracias a Shaggy y Dom Hastings

f=a=>a>9&(b=Math.max(...a+""))<9?f(parseInt(a,b+1)):a;

console.log(f("413574"))

Tom
fuente
Gáname a eso. Creo que podría guardar algunos bytes +a>9||b<9e invertir el ternario.
Shaggy
1
@Shaggy edit: soy tonto
Tom
1
¡No seas tan duro contigo mismo, Tom! ¡No eres tonto, pero definitivamente no eres tan inteligente como @Shaggy!
Stewie Griffin
1
Alternativa para 55 bytesf=n=>n>9&&(k=Math.max(...n+"")+1)<10?f(parseInt(n,k)):n
Dom Hastings
@DomHastings ¡Gracias por las mejoras! :)
Tom
5

Python 3 , 91 78 76 75 73 bytes

@Emigna recortó 5 bytes. @FelipeNardiBatista guardó 1 byte. @ RomanGräf guardó 2 bytes

i=input()
while'9'>max(i)and~-len(i):i=str(int(i,int(max(i))+1))
print(i)

Pruébalo en línea!


Explicación

i=input()                                  - takes input and assigns it to a variable i
while '9'>max(i)and~-len(i):               - repeatedly checks if the number is still base-9 or lower and has a length greater than 1
    i=str(...)                             - assigns i to the string representation of ...
          int(i,int(max(i))+1)             - converts the current number to the real base 10 and loops back again
print(i)                                   - prints the mutated i
Sr. Xcoder
fuente
5

05AB1E , 10 5 bytes

5 bytes guardados gracias a Magic Octopus Urn

F§Z>ö

A medida que esto se ralentiza muy rápidamente para grandes entradas, dejo la versión anterior mucho más rápida aquí para probar. El algoritmo es el mismo, solo difiere el número de iteraciones.

[©Z>öD®Q#§

Pruébalo en línea!

Explicación

[             # start a loop
 ©            # store a copy of the current value in the register
  Z>          # get the maximum (digit) and increment
    ö         # convert the current value to base-10 from this base
     D        # duplicate
      ®Q#     # break loop if the new value is the same as the stored value
         §    # convert to string (to prevent Z from taking the maximum int on the stack)
Emigna
fuente
Además, ¿no puedes usarlo тFZ>ö§? ¿Ver como el número de iteraciones ( como se ve aquí ) parece estabilizarse? Si desea ser técnico, la velocidad a la que aumentan las iteraciones es probablemente logarítmica ... Por lo tanto, podría usar algo como: DFZ>ö§y afirmar que no se ejecutará en gran medida n. O tal vez incluso: T.n>FZ>ö§para calcular directamente el número de iteraciones como log_10(n).
Magic Octopus Urn
@MagicOctopusUrn: Sí, ahora que lo mencionas, ya que la secuencia definitivamente parece más lenta que lineal, F§Z>ödebería ser el truco.
Emigna
Creo que puedes eliminar el §.
Erik the Outgolfer
@EriktheOutgolfer: Desafortunadamente no. Si eliminamos el §, Ztomará el número más alto en la pila en lugar del dígito más alto en el número en la parte superior de la pila.
Emigna
@Emigna ¿Eh?
Erik the Outgolfer
3

APL (Dyalog) , 20 16 bytes

Toma y devuelve una cadena.

((⍕⊢⊥⍨1+⌈/)⍎¨)⍣≡

(... )⍣≡ aplique la siguiente función hasta que dos términos consecutivos sean idénticos:

⍎¨ ejecuta cada carácter (convierte la cadena en una lista de números)

(...)  Aplica la siguiente función tácita a eso:

  ⌈/ encuentra el máximo del argumento

  1+ Agrega uno

  ⊢⊥⍨ evaluar el argumento en esa base

   formato (stringify, en preparación para otra aplicación de la función externa)

Pruébalo en línea!

Adán
fuente
3

Mathematica, 52 bytes

FromDigits[s=IntegerDigits@#,Max@s+1]&~FixedPoint~#&

Función pura que toma un entero no negativo como entrada y devuelve un entero no negativo. Utiliza la misma mecánica central FromDigits[s=IntegerDigits@#,Max@s+1]que la respuesta de Jenny_mathy , pero explota FixedPointpara hacer la iteración.

Greg Martin
fuente
3

Perl 6 , 49 bytes

{($_,{.Str.parse-base(1+.comb.max)}...*==*).tail}

Pruébalo

Expandido:

{
  (

    $_,                 # seed the sequence with the input

    {
      .Str
      .parse-base(      # parse in base:
        1 + .comb.max   # largest digit + 1
      )
    }

    ...                 # keep generating values until

    * == *              # two of them match (should only be in base 10)

  ).tail                # get the last value from the sequence
}
Brad Gilbert b2gills
fuente
2

Pip , 17 bytes

Wa>9>YMXaaFB:1+ya

Toma entrada como argumento de línea de comando. Pruébalo en línea!

Explicación

Esto fue divertido: tuve que sacar los operadores de comparación de encadenamiento.

Queremos hacer un ciclo hasta que el número sea un solo dígito O contenga un 9. De manera equivalente, queremos hacer un ciclo mientras el número tenga varios dígitos Y no contenga un 9. De manera equivalente, haga un ciclo mientras el número sea mayor que 9 Y el dígito máximo sea menos de 9: a>9>MXa.

Wa>9>YMXaaFB:1+ya
                   a is 1st cmdline arg (implicit)
     YMXa          Yank a's maximum digit into the y variable
Wa>9>              While a is greater than 9 and 9 is greater than a's max digit:
         aFB:1+y    Convert a from base 1+y to decimal and assign back to a
                a  At the end of the program, print a
DLosc
fuente
2

Pitón 2 , 60 59 56 53 bytes

Guardado 4 bytes gracias a Felipe Nardi Batista
Guardado 3 bytes gracias a ovs

f=lambda x,y=0:x*(x==y)or f(`int(x,int(max(x))+1)`,x)

Pruébalo en línea!

Usando una lambda recursiva, comparando el resultado de la conversión de base con la iteración anterior.

Emigna
fuente
¿Por qué no utilizar x==y and x or ...como xnunca será 0(base 1). o incluso(x==y)*x or ...
Felipe Nardi Batista
@FelipeNardiBatista: ¡Gracias! Intenté x and x==y or ...lo que no funcionó, pero no soy muy competente con estos trucos, así que no me di cuenta de que podía revertirlo :)
Emigna
@ovs: Tienes razón. ¡Gracias!
Emigna
@FelipeNardiBatista "Entrada: Un entero positivo n que consta de dígitos en el rango 0-9". 0 sigue siendo una entrada válida, y ahora el código la rechaza.
Mástil
@Mast: Afortunadamente para nosotros, 0 no es un entero positivo, por lo que no se dará como entrada.
Emigna
2

C #, 257 244 243 244 233 222 bytes

using System.Linq;z=m=>{int b=int.Parse(m.OrderBy(s=>int.Parse(s+"")).Last()+""),n=0,p=0;if(b<9&m.Length>1){for(int i=m.Length-1;i>=0;i--)n+=int.Parse(m[i]+"")*(int)System.Math.Pow(b+1,p++);return z(n+"");}else return m;};

Bueno, C # siempre toma muchos bytes, pero esto es simplemente ridículo. Ninguno de los incorporados puede manejar una base arbitraria, así que tuve que calcular la conversión yo mismo. Sin golf:

using System.Linq;
z = m => {
int b = int.Parse(m.OrderBy(s => int.Parse(s + "")).Last()+""), n = 0, p = 0; //Get the max digit in the string
if (b < 9 & m.Length > 1) //if conditions not satisfied, process and recurse
{
    for (int i = m.Length - 1; i >= 0; i--)
        n += int.Parse(m[i] + "") * (int)System.Math.Pow(b+1, p++); //convert each base-b+1 representation to base-10
    return z(n + ""); //recurse
}
else return m; };
Ceshion
fuente
1

Mathematica, 92 bytes

f[x_]:=FromDigits[s=IntegerDigits@x,d=Max@s+1];(z=f@#;While[d!=10&&Length@s>1,h=f@z;z=h];z)&
J42161217
fuente
1

Javascript (ES6) con función de flecha 0, 74 bytes

function f(a){a>9&&b=Math.max(...a)<9&&f(parseInt(a,b+1));alert(a)}f('11')
usuario71507
fuente
3
Bienvenido a PPCG! :) Esta es probablemente una muy buena respuesta, pero no puedo decirlo sin una explicación. Yo (y probablemente otros) nunca voté las respuestas que no contienen explicaciones.
Stewie Griffin
1
¿Por qué llamas f('11')después de la función? A menos que me falte algo que solo parece ser un uso que en realidad no forma parte del envío. Si es así, debe sacarlo de la sección de código y ponerlo en su explicación (cuando agrega uno) y actualizar su recuento de bytes a 67.
PunPun1000
1

K4 , 19 bytes

Solución:

{(1+|/x)/:x:10\:x}/

Ejemplos:

q)\
  {(1+|/x)/:x:10\:x}/413574
83911
  {(1+|/x)/:x:10\:x}/13552
159
  {(1+|/x)/:x:10\:x}/17
3
  {(1+|/x)/:x:10\:x}/41253
29    

Explicación:

Use /:incorporado para convertir la base.

{(1+|/x)/:x:10\:x}/ / the solution
{                }/ / converge lambda, repeat until same result returned
            10\:x   / convert input x to base 10 (.:'$x would do the same)
          x:        / store in variable x
 (     )/:          / convert to base given by the result of the brackets
    |/x             / max (|) over (/) input, ie return largest
  1+                / add 1 to this
callejero
fuente
1

Kotlin , 97 bytes

fun String.f():String=if(length==1||contains("9"))this else "${toInt(map{it-'0'}.max()!!+1)}".f()

Embellecido

fun String.f(): String = if (length == 1 || contains("9")) this else "${toInt(map { it - '0' }.max()!! + 1)}".f()

Prueba

fun String.f():String=if(length==1||contains("9"))this else "${toInt(map{it-'0'}.max()!!+1)}".f()
val tests = listOf(
        5 to 5,
        17 to 3,
        999 to 999,
        87654321 to 9041998,
        41253 to 29
)

fun main(args: Array<String>) {
    tests.forEach { (input, output) ->
        val answer = input.toString().f()
        if (answer != output.toString()) {
            throw AssertionError()
        }
    }
}

TIO

TryItOnline

jrtapsell
fuente
0

C, 159 157 bytes

#include <stdlib.h>
char b[99];i=0;m=-1;c(n){do{m=-1;sprintf(b,"%d",n);i=0;while(b[i]){m=max(b[i]-48,m);i++;}n=strtol(b,0,++m);}while(b[1]&&m<10);return n;}
Govind Parmar
fuente
0

Scala , 119 bytes

if(x.max==57|x.length==1)x else{val l=x.length-1
f((0 to l).map(k=>(((x(k)-48)*math.pow(x.max-47,l-k))) toInt).sum+"")}

Pruébalo en línea!

Scala , 119 bytes

if(x.max==57|x.length==1)x else f((0 to x.length-1).map(k=>(((x(k)-48)*math.pow(x.max-47,x.length-1-k))) toInt).sum+"")

Pruébalo en línea!

Ambos métodos funcionan de la misma manera, pero en el primero pongo x.length-1una variable y en el segundo no.

V. Courtois
fuente