Simplificacion de numeros

16

¿Cómo, no puedes recordar el número de teléfono de 6 o 7 dígitos que apareció en la pantalla del televisor por un segundo? ¡Usando la técnica especial que se describe a continuación, se convertirá en una guía telefónica ambulante!

Obviamente, el número 402es más fácil de recordar que el número 110010010, y el número 337377es más fácil de recordar que el número 957472. Esto significa que el número memorizado, por un lado, debe contener la menor cantidad de dígitos posible y, por otro lado, es deseable que el número contenga tantos números repetidos como sea posible.

Como criterio para la dificultad de recordar, tomamos la suma del número de dígitos en número y el número de dígitos diferentes en número. Un número memorizado puede escribirse en otro sistema de números, quizás entonces sea más fácil de recordar. Por ejemplo, se 65535ve el número en la notación hexadecimal FFFF.

Tarea

Debe escribir un programa para seleccionar la base del sistema de números para minimizar el criterio de complejidad. La base del sistema de números debe seleccionarse en el rango de 2 a 36, ​​luego los números 0-9y las letras en inglés A-Zse pueden usar para representar el número.

Entrada

La entrada contiene un entero decimal del 1 al 999999999.

Salida

La salida debe contener la base del sistema numérico (de 2 a 36), minimizando el criterio de complejidad de memorización y el número en el sistema numérico seleccionado, separados por un espacio. Si varias bases dan el mismo valor para el criterio, elija la más pequeña entre ellas.

Notas

  • Las letras deben ser mayúsculas ( A-Z).

Casos de prueba

De entrada y salida

1              2 1

2              3 2

65535       16 FFFF

123          12 A3

Ver Nick dice reinstalar a Mónica
fuente
16
Gran desafío, pero necesita más casos de prueba.
Grimmy
77
Además, el formato de salida es demasiado estricto, es posible que desee permitir, por ejemplo, una matriz de dos elementos, la base y la cadena, o permitirlos en orden inverso o separados por otro carácter. Además, supongo que agrega la suma de los dígitos al número de dígitos, pero es posible que desee aclarar eso.
Erik the Outgolfer
8
¿Puedo usar en a-zlugar de A-Z?
Neil
55
¿Podemos usar los números correspondientes en lugar de A-Z?
flawr
8
@VerNick La próxima vez que escriba un desafío similar, sugeriría permitir ambas solicitudes, ya que son solo una complicación innecesaria que se desaconseja: consulte, por ejemplo, aquí .
flawr

Respuestas:

6

Perl 6 , 55 54 bytes

-1 byte gracias a Jo King.

{~map({$^b,.base($b)},2..36).min:{@$_+.Set}o*[1].comb}

Pruébalo en línea!

nwellnhof
fuente
1
Puede reemplazar @$_con @_y todavía funciona.
SirBogman hace
2
@SirBogman Esto simplemente funciona con los muy pocos casos de prueba.
nwellnhof hace
Eso tiene sentido. No se sentía del todo bien.
SirBogman hace
5

Python 2 , 150 149 127 144 bytes

lambda n:min((len(c(n,b))+len(set(c(n,b))),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n/b,b,chr(n%b+48+7*(n%b>9))+s)or s or'0'

Pruébalo en línea!


Python 3 , 136 bytes

lambda n:min((len((*c(n,b),*{*c(n,b)})),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

Pruébalo en línea!


Python 3.8 (prelanzamiento) , 131 bytes

lambda n:min((len((*(x:=c(n,b)),*{*x})),b,x)for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

Pruébalo en línea!


c convierte un número base 10 en cualquier base (2-36), y la primera función (anónima) encuentra el resultado más pequeño.

TFeld
fuente
5

05AB1E , 16 14 bytes

-1 byte gracias a Kevin Cruijssen

₆LBāøΣнDÙìg}1è

Pruébalo en línea!

O agregue R) »al final para ajustarse exactamente al formato de salida especificado, pero la mayoría de las otras respuestas no molestaron.

Explicación:

₆L          # range 1..36
  B         # convert the input to each of those bases
   āø       # enumerate (pair each element with its 1-based index)
Σ     }     # sort by
     g      # length
 н          # of the first element
    ì       # concatenated to
  DÙ        # itself, uniquified
1è          # take the second entry (first will always be base 1)
Mugriento
fuente
1
-1 byte usando en ₆L©B®ølugar de₆LεBy‚}
Kevin Cruijssen
1
@KevinCruijssen ¡Gracias! Otro -1 al usar ā, parece que siempre te olvidas de ese.
Grimmy el
Lol, de hecho lo hago ... Lo recordé con este desafío el día de hoy, no es que haya ayudado de ninguna manera, jaja xD
Kevin Cruijssen
@recursivo, parece que no has leído la respuesta. Enlace una versión que cumpla con los estrictos requisitos de salida y explique por qué no hice que sea la versión principal.
Grimmy
@ Grimy culpable de los cargos. Perdón por molestarte.
recursivo el
4

JavaScript (ES6),  87  85101 bytes

Editar: +16 bytes inútiles para cumplir con el formato de salida estricto

n=>(g=m=>--b>2?g(m<(v=new Set(s=n.toString(b)).size+s.length)?m:(o=b+' '+s.toUpperCase(),v)):o)(b=37)

Pruébalo en línea!

Arnauld
fuente
Ah, me perdí esa parte
TFeld
4

Japt v2.0a0 -gS, 24 23 bytes

No es bonito, pero hace el trabajo. +2 bytes para el requisito completamente innecesario de que la salida sea mayúscula.

37o2@sX u ¸iXÃñÈÌiXÌâ)l

Intentalo

37o2@sX u ¸iXÃñÈÌiXÌâ)l     :Implicit input of integer
37o2                        :Range [2,37)
    @                       :Map each X
     sX                     :  Convert the input to a base-X string
        u                   :  Uppercase
          ¸                 :  Split on spaces (there are none, so this returns a singleton array)
           iX               :  Prepend X
             Ã              :End map
              ñ             :Sort by
               È            :Pass each X through the following function
                Ì           :  Last element of X
                 i          :  Prepend
                  XÌâ       :    Last element of X, deduplicated
                     )      :  End prepend
                      l     :  Length
                            :Implicit output of the first sub-array, joined with spaces
Lanudo
fuente
Sí, funciona bien, pero las letras deben ser mayúsculas.
Ver Nick dice reinstalar a Mónica el
1
@VerNick, ¿por qué? Eso no agrega absolutamente nada al desafío.
Shaggy
... Supongo que lo siguiente será "separados por un espacio". Parece que el formato de salida se ha hecho muy estricto en este desafío, y de los comentarios no parece que vaya a cambiar.
Jonathan Allan
@JonathanAllan, por suerte puedo "arreglarlo" con un cambio de bandera.
Shaggy
3

PHP ,124 119 bytes

for($i=36;$b=strtoupper(base_convert($argn,10,--$i));$o[strlen($b.count_chars($b,3))]="$i $b");krsort($o);echo end($o);

Pruébalo en línea!

Una pena sobre los +12 bytes en PHP para poner en mayúscula la salida ... pero ... de todos modos.

640 KB
fuente
3

Zsh , 85 bytes

for b ({36..2})x=$[[#$b]$1]&&x=${x#*\#}&&a[$#x+${#${(us::)x}}]=$b\ $x
a=($a)
<<<$a[1]

Para este número de declaraciones dentro del ciclo for, el uso ...&&...&&...es más corto que {...;...;...;}.

for b ({36..2})                   # order decreasing: smaller bases overwrite larger ones
    x=$[[#$b]$1] && \             # set x to [base]#[num] 
    x=${x#*\#} && \               # strip leading [base]#
    a[$#x+${#${(us::)x}}]=$b\ $x  # use score as index to store "[base] [number]"
#            ${(us::) }           # (s::)plit into characters, take (u)nique
a=($a)                            # remove empty elements from array
<<<$a[1]                          # print out the first element (smallest score)

Pruébalo en línea!

Aquí hay una solución de 81 bytes que se imprime en el formulario [base]#[num]:

for b ({36..2})x=$[[#$b]$1]&&y=${x#*\#}&&a[$#y+${#${(us::)y}}]=$x
a=($a)
<<<$a[1]

Pruébalo en línea!

Función Gamma
fuente
2

Carbón , 38 bytes

Nθ≔EE³⁴↨θ⁺²ιL⁺ιΦι⁼λ⌕ικη≔⁺²⌕η⌊ηηIη ↥⍘θη

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

Nθ

Ingrese el entero.

≔EE³⁴↨θ⁺²ι

Conviértalo de la base 2 a la base 36 ...

L⁺ιΦι⁼λ⌕ικη

... deduplica, concatena y toma la longitud.

≔⁺²⌕η⌊ηη

Tome el índice de la complejidad mínima y agregue 2 para obtener la base.

Iη ↥⍘θη

Imprima la base y el entero convertido a esa base en mayúsculas.

Neil
fuente
2

Stax , 19 bytes

Ç╛;ⁿY3█↕(╖S♪*ò▌?½╦l

Ejecutar y depurarlo

Sin algoritmo sofisticado, solo fuerza bruta directa. Alrededor de un tercio del programa está discutiendo el formato de las reglas de salida precisas.

Programa de bonificación: Salida para [1..1000]

recursivo
fuente
2

Jalea , 25 bytes

bⱮ36µQL+LN)Mḟ1Ḣ,ị‘ịØBʋ¥⁸K

Pruébalo en línea!

Un enlace monádico que toma un número entero como argumento y devuelve una cadena Jelly del formato deseado. Si una lista de dos elementos fuera una salida aceptable (según la mayoría de los desafíos), podría ahorrar 2 bytes. Si la base 1 fuera aceptable para el caso límite de 1 como entrada, podría guardar otros 2 bytes.

Nick Kennedy
fuente
2

Brachylog , 44 bytes

∧Y≜∧36≥Xℕ₂≜&ḃ↙X Zd,Zl≡Y∧XwṢwZ{-₁₀;Ạụᵗ∋₍|}ᵐwᵐ

Pruébalo en línea!

Esto duele un poco para escribir.

Cadena no relacionada
fuente
1

Perl 5 , 161 bytes

sub f{$X=99;for$b(2..36){$_=c($_[0],$b);$x=uniq(/./g)+y///c;($X,$B,$C)=($x,$b,$_)if$x<$X}$B,$C}
sub c{my($n,$b)=@_;$n?c(int$n/$b,$b).chr(48+$n%$b+7*($n%$b>9)):''}

Pruébalo en línea!

Kjetil S.
fuente
1

Python 2 , 140 135 bytes

lambda n:min([(b,g(n,b))for b in range(2,36)],key=lambda(b,s):len(s)+len(set(s)))
g=lambda n,b:n and g(n/b,b)+chr(n%b+48+7*(n%b>9))or''

Pruébalo en línea!

Chas Brown
fuente
1

Perl 5 -Minteger -MList::Util=uniq,first -ap , 123 112 bytes

$"=$,;map{@r=();$t="@F";do{unshift@r,(0..9,A..Z)[$t%$_]}while$t/=$_;$a[@r+uniq@r]||="$_ @r"}2..36;$_=first{$_}@a

Pruébalo en línea!

Xcali
fuente
1

Wolfram Language (Mathematica) , 109 111 bytes

Print[a=OrderingBy[#~IntegerDigits~Range@36,Tr[1^#]+Tr[1^Union@#]&,1][[1]]," ",ToUpperCase[#~IntegerString~a]]&

+2: fijo. Gracias por la captura @Roman

OrderingBy se introdujo en Mathematica 12.0, que TIO no parece haberse actualizado todavía.

attinat
fuente
"Si varias bases dan el mismo valor para el criterio, elija la más pequeña entre ellas": OrderingByno cumple con este requisito.
Romano
Tal vez algo con MinimalBy, como esto ?
Romano
@Roman no? Por lo que puedo decir, conserva el orden relativo de dos índices que tienen el mismo valor ...
attinat
2
Con el argumento 123, su solución se imprime en 36 3Flugar de la requerida 12 A3. De OrderingBy[123~IntegerDigits~Range@36, Tr[1^#] + Tr[1^Union@#] &]donde obtengo la respuesta {36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 6, 5, 11, 10, 9, 8, 7, 4, 3, 2, 1}, entonces la suposición habitual de no reordenar entradas equivalentes parece ignorarse aquí. Mi $Versiones "12.0.0 para Mac OS X x86 (64 bits) (7 de abril de 2019)".
Romano
Ah, tienes razon. Mi mal por no notar eso.
attinat
1

C (clang) , 165 bytes

n,i=2,j,p=99,r,m,x;char*g,*_,b[74][37];t(n){for(;g=b[i],i<37;r=j<p?_=g,p=j,i:r,++i)for(j=0,m=n;m;m/=i,*--g=x+=x>9?87:48)j+=b[i+36][x=m%i]++?1:2;printf("%i,%s",r,_);}

Pruébalo en línea!

n // entrada

, i = 2 // iterador de base 2 a 36

, j // complejidad actual

, p = 99 // mejor complejidad

, r // resultado = iterador

, m // copia temporal de n

, x; // m% i

char * g // ptr de cadena actual

, * _ // mejor str ptr

, b [74] [37]; // tampón

/ * [37 + 37] = [cadenas obtenidas + prueba de caracteres usados] * /

Tennesse){

para (; g = b [i], // mover ptr

   i<37 ; 
   r=j<p?_=g,p=j,i:r, // save best solution

   ++i){//for every base

para (j = 0, m = n; m; m / = i, // extraer dígito

   *--g=x+=x>9?87:48)
   // move ptr backward for printf use and transform to ascii value

j + = b [i + 36] [x = m% i] ++? 1: 2; // incrementa el byte relativo al caracter

// y si fuera 0 incrementa j por 2: 1 para el nuevo carácter utilizado y 1 para el recuento de dígitos

// de lo contrario, solo incr. los dígitos cuentan + mover el puntero

// printf ("% s -", ​​g); // prueba

// printf ("r% ip% ij% i \ n", r, p, j); // prueba

}

printf ("% i,% s", r, _); // salida

}

AZTECCO
fuente
1
Se pueden llamar 163 bytes más de una vez.
ceilingcat