Simplificação de números

15

Como, você não consegue se lembrar do número de telefone de 6 ou 7 dígitos que apareceu na tela da TV por um segundo ?! Usando a técnica especial descrita abaixo, você se transformará em uma agenda telefônica ambulante!

Obviamente, o número 402é mais fácil de lembrar do que o número 110010010e o número337377 é mais fácil de lembrar que o número 957472. Isso significa que o número memorizado, por um lado, deve conter o menor número possível de dígitos e, por outro lado, é desejável que o número contenha o maior número possível de números repetidos.

Como critério para a dificuldade de lembrar, tomamos a soma do número de dígitos em número e o número de dígitos diferentes em número. Um número memorizado pode ser escrito em outro sistema numérico, talvez seja mais fácil lembrar. Por exemplo, o número 65535na notação hexadecimal se parece comFFFF .

Tarefa

Você precisa escrever um programa para selecionar a base do sistema numérico para minimizar o critério de complexidade. A base do sistema numérico deve ser selecionada no intervalo de 2 a 36, ​​depois os números0-9 e as letras em inglês A-Zpossam ser usados ​​para representar o número.

Entrada

A entrada contém um número inteiro decimal de 1 a 999999999.

Resultado

A saída deve conter a base do sistema numérico (de 2 a 36), minimizando o critério de complexidade da memorização e o número no sistema numérico selecionado, separados por um espaço. Se várias bases fornecerem o mesmo valor para o critério, escolha a menor dentre elas.

Notas

  • As letras devem estar em maiúsculas ( A-Z).

Casos de teste

Saída de Entrada

1              2 1

2              3 2

65535       16 FFFF

123          12 A3

code-golf number base-conversion Ver Nick diz Restabelecer Monica
fonte
16
Grande desafio, mas precisa de mais casos de teste.
Grimmy
7
Além disso, o formato de saída é um pouco rígido demais, você pode permitir, por exemplo, uma matriz de dois elementos, a base e a string, ou permitir em ordem inversa ou separados por outro caractere. Além disso, suponho que você adicione a soma dos dígitos ao número de dígitos, mas convém esclarecer isso.
Erik the Outgolfer
8
Posso usar em a-zvez de A-Z?
214 Neil
5
Podemos apenas usar os números correspondentes em vez de A-Z?
flawr
8
@VerNick Na próxima vez em que você escrever um desafio semelhante, sugiro permitir ambos os pedidos, pois eles são apenas uma complicação desnecessária que são desencorajados: veja, por exemplo, aqui .
flawr

Respostas:

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'

Experimente online!

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

Experimente online!

Python 3.8 (pré-lançamento) , 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

Experimente online!

c converte um número base 10 em qualquer base (2-36) e a primeira função (anônima) encontra o menor resultado.

TFeld
fonte
5

05AB1E , 16 14 bytes

-1 byte graças a Kevin Cruijssen

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

Experimente online!

Ou adicione R) »no final para se ajustar exatamente ao formato de saída especificado, mas a maioria das outras respostas não incomodou.

Explicação:

₆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)
Grimmy
fonte
1
-1 byte usando em ₆L©B®øvez de₆LεBy‚}
Kevin Cruijssen 12/08/19
1
@KevinCruijssen Thanks! Outro -1 usando ā, parece que você sempre esquece esse.
Grimmy
Lol, eu de fato não .. eu me lembrava com este desafio hoje cedo, não que ajudaram de alguma forma, haha xD
Kevin Cruijssen
@ recursivo você parece não ter lido a resposta. Vinculo uma versão que cumpre os requisitos estritos de saída e explico por que não a fiz a versão principal.
Grimmy
@Grimy culpado conforme cobrado. Desculpe incomodá-lo.
recursivo
5

Perl 6 , 55 54 bytes

-1 byte graças a Jo King.

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

Experimente online!

Nwellnhof
fonte
Droga, eu não vi isso e tem praticamente a mesma resposta exata , exceto com @$_em vez de .[*]para menos um byte
Jo rei
4

JavaScript (ES6),  87 85  101 bytes

Edit: +16 bytes inúteis para obedecer ao formato de saída estrito

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)

Experimente online!

Arnauld
fonte
Ah, eu perdi essa parte
TFeld
4

Japt v2.0a0 -gS, 24 23 bytes

Não é bonito, mas faz o trabalho. +2 bytes para o requisito completamente desnecessário de que a saída seja maiúscula.

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

Tente

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
Shaggy
fonte
Sim, funciona bem, mas as letras devem estar em maiúsculas.
Ver Nick diz Restabelecer Monica
1
@VerNick, por quê? Isso não acrescenta absolutamente nada ao desafio.
Shaggy
... Acho que a próxima coisa será "separada por um espaço". Parece que o formato de saída foi muito rigoroso nesse desafio e, a partir dos comentários, parece que ele não será alterado.
Jonathan Allan
@ JonathanAllan, felizmente eu posso "consertar" aquele com uma mudança de flag.
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);

Experimente online!

Uma pena os +12 bytes no PHP para maiúsculas na saída ... mas ... de qualquer maneira.

640KB
fonte
3

Zsh , 85 bytes

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

Para esse número de instruções dentro do loop for, o uso ...&&...&&...é menor 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)

Experimente online!

Aqui está uma solução de 81 bytes que imprime no formulário [base]#[num]:

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

Experimente online!

GammaFunction
fonte
3

J , 67 bytes

(];'0123456789ABCDEF'{~b)[:(2+]i.<./)](#+#@~.)@(b=:#.inv~)"+2+i.@35

Experimente online!

Galen Ivanov
fonte
2

Carvão , 38 bytes

Ｎθ≔ＥＥ³⁴↨θ⁺²ιＬ⁺ιΦι⁼λ⌕ικη≔⁺²⌕η⌊ηηＩη ↥⍘θη

Experimente online! Link é a versão detalhada do código. Explicação:

Ｎθ

Insira o número inteiro.

≔ＥＥ³⁴↨θ⁺²ι

Converta-o da base 2 para a base 36 ...

Ｌ⁺ιΦι⁼λ⌕ικη

... deduplicar, concatenar e levar o comprimento.

≔⁺²⌕η⌊ηη

Pegue o índice da complexidade mínima e adicione 2 para obter a base.

Ｉη ↥⍘θη

Imprima a base e o número inteiro convertido nessa base em maiúsculas.

Neil
fonte
2

Stax , 19 bytes

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

Execute e depure

Nenhum algoritmo sofisticado, apenas força bruta direta. Cerca de um terço do programa discute o formato das regras de saída precisas.

Programa de bônus: Saída para [1..1000]

recursivo
fonte
2

Gelatina , 25 bytes

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

Experimente online!

Um link monádico usando um número inteiro como argumento e retornando uma sequência Jelly no formato desejado. Se uma lista de dois itens tiver uma saída aceitável (conforme a maioria dos desafios), poderá economizar 2 bytes. Se a base 1 fosse aceitável para a aresta de 1 como entrada, poderia salvar mais 2 bytes.

Nick Kennedy
fonte
2

Braquilog , 44 bytes

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

Experimente online!

Isso doeu um pouco para escrever.

String não relacionada
fonte
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)):''}

Experimente online!

Kjetil S.
fonte
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''

Experimente online!

Chas Brown
fonte
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

Experimente online!

Xcali
fonte
1

Wolfram Language (Mathematica) , 109 111 bytes

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

+2: fixo. Obrigado pela captura @Roman

OrderingBy foi introduzido no Mathematica 12.0, que o TIO parece não ter atualizado ainda.

attinat
fonte
"Se várias bases dão o mesmo valor para o critério, escolha a menor dentre elas.": OrderingByNão está de acordo com este requisito.
Roman
Talvez algo com MinimalBy, assim ?
Roman
@ Roman não é? Tanto quanto eu posso dizer, ele preserva a ordem relativa de dois índices que têm o mesmo valor ..
attinat
2
Com o argumento 123, sua solução é impressa em 36 3Fvez da necessária 12 A3. De OrderingBy[123~IntegerDigits~Range@36, Tr[1^#] + Tr[1^Union@#] &]como recebo a resposta {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}, a suposição usual de não reordenar entradas equivalentes parece ser ignorada aqui. Meu $Versioné "12.0.0 para Mac OS X x86 (64 bits) (7 de abril de 2019)".
Roman
Ah, você está certo. Meu mal por não perceber isso.
attinat 14/08/19
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,_);}

Experimente online!

n // entrada

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

, j // complexidade atual

, p = 99 // melhor complexidade

, r // resultado = iterador

, m // cópia temporária de n

, x; // m% i

char * g // string atual ptr

, * _ // melhor str ptr

, b [74] [37]; // buffer

/ * [37 + 37] = [cadeias obtidas + teste para caracteres usados] * /

t (n) {

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

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

   ++i){//for every base

for (j = 0, m = n; m; m / = i, // extrai o 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 byte em relação ao caractere

// e se foram 0 incrementos j de 2: 1 para o novo caractere usado e 1 para contagem de dígitos

// else incr apenas dígitos contam + move o ponteiro

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

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

}

printf ("% i,% s", r, _); // saída

}

AZTECCO
fonte
1
163 bytes podem ser chamados mais de uma vez.
ceilingcat
1

Japt v2.0a0, 31 bytes

2o37 ñ@sX Ê+UsX â ÊÃÎ
+S+NÎsU u

Tente

Modalidade de ignorância
fonte