Números auto-somados

12

Converter um número em uma soma de dígitos

Nenhuma soma: precisamos da soma mais curta
Não há dígitos: você pode usar apenas dígitos do número

Exemplo
Você receberá como entrada um número inteiron>0

Vamos dizer n=27. Você deve expressar 27como uma soma , usando apenas os dígitos [2,7] , da maneira mais curta possível. Você não precisa usar todos os dígitos do número especificado!

Então 27=2+2+2+7+7+7. Em seguida, tome esses dígitos e contá-los : [2,2,2,7,7,7].
A resposta final para n=27é6

Mais um exemplo para n=195obter a soma mais curta , temos que usar os seguintes dígitos:
[5,5,5,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]e a resposta é23

O desafio

Dado um número inteiro n>0, imprima o número mínimo de dígitos (contidos no número) que somam esse número

Casos de teste

Input->Output

1->1  
2->1  
10->10  
58->8  
874->110  
1259->142  
12347->1765  
123456->20576  
3456789->384088  

Este é o . A resposta mais curta em bytes vence!


fonte
Existem números que não podem somar sozinhos / serão inseridos?
Stephen
1
@ Stephen Todos eles podem!
7
@Stephen Porque cada número pode ser expresso como d_0 + 10 * d_1 + 100 * d_2, etc ...
geokavel
Podemos pegar a entrada como string, char-array ou número inteiro?
Kevin Cruijssen
1
@KevinCruijssen String is ok. char-array ou número inteiro não são.

Respostas:

4

Casca , 12 bytes

Lḟo=⁰ΣṁΠḣ∞d⁰

Lida com números de dois dígitos bem rápido. Experimente online!

Explicação

Lḟo=⁰ΣṁΠḣ∞d⁰  Input is n, say n = 13.
          d⁰  Digits of n: [1,3]
         ∞    Repeat infinitely: [[1,3],[1,3],[1,3],[1,3]...
        ḣ     Prefixes: [[],[[1,3]],[[1,3],[1,3]],[[1,3],[1,3],[1,3]],...
      ṁ       Map and concatenate
       Π      Cartesian product: [[],[1],[3],[1,1],[3,1],[1,3],[3,3],[1,1,1],[3,1,1],...
 ḟo           Find the first element
     Σ        whose sum
   =⁰         equals n: [3,3,3,3,1]
L             Return its length: 5
Zgarb
fonte
2

Pitão , 12 bytes

lef!-TsM`Q./

Experimente online!

Infelizmente, erros de memória em entradas tão grandes quanto 58.

Explicação

lef!-TsM`Q./
          ./    All lists of integers that sum to [the input]
  f             Filter for:
    -TsM`Q           Remove all occurrences of the digits in the input
   !                 Check if falsey (i.e. an empty list)
le              Length of the last occurrence, which is the shortest because all the
                filtered partitions share the same digit pool
notjagan
fonte
você se importaria de adicionar uma explicação?
Jonah
@Jonah Explicação adicionada.
precisa saber é o seguinte
1
Obrigado. Interessante que Pyth tem um primitivo que essencialmente resolve o problema em./
Jonah
Alternativa de 12 bytes: lef<.{TjQ;./(filtro - subconjunto adequado - de dígitos de entrada)
Mr. Xcoder
2

Mathematica, 78 bytes

(t=1;While[(s=IntegerPartitions[x=#,t,IntegerDigits@x])=={},t++];Tr[1^#&@@s])&  

encontra o último caso de teste em 5 segundos

J42161217
fonte
Um pouco mais curto:Length@IntegerPartitions[#, All, Sort@DeleteCases[0]@IntegerDigits@#, 1][[1]] &
Kuba
2

R , 78 bytes

function(n){while(all(F-n)){F=outer(F,n%/%10^(0:nchar(n))%%10,"+")
T=T+1}
T-1}

Experimente online! (versão para golfe)

Algoritmo de força bruta pura, para que ele não resolva todos os casos de teste, e acho que ele tentou alocar 40.000 GB para o último caso de teste ...

Tem R é padronizado para 1obter um erro de um por um que corrigimos na etapa de retorno, mas também obtemos Fquais padrões para os 0quais compensa.

explicação ungolfed:

function(n){
 d <- n%/%10^(0:nchar(n))%%10   # digit list with a 0 appended at end
 d <- unique(d[d>0])            # filter zeros (not technically necessary)
                                # and get unique digits
 x <- 0                         # storage for sums
 i <- 0                         # counter for number of sums done
 while(!any(x==n)){             # until we find a combination
  x <- outer(x,d,"+")           # take all sums of x and d, store as x
  i <- i + 1}                   # increment counter
i}                              # return counter

Experimente online! (versão menos golfe)

Giuseppe
fonte
2

Python 2, 168 155 144 bytes

Não é o mais curto possível, mas é o melhor primeiro e não é muito ruim, em termos de tempo de execução.

n=input()
g=sorted(set(n)-{0})[::-1]
def h(k):
 if k<0:return
 if`k`in g:return 1
 for d in g:
  f=h(k-int(d))
  if f:return 1+f
print h(int(n)) 

O filter(None...é remover 0 como um dígito, o que eu aprendi que poderia fazer enquanto fazia isso.

O maior problema são os quadros de pilha python, que realisticamente não me permitem executar isso nas maiores entradas. Então, não é uma solução válida, na verdade, eu brinquei com o aumento do limite de recursão, o que levou a seg-falhas. Isso precisa ser feito com um loop e uma pilha ou com muito mais inteligência para trabalhar em python.

edit: Obrigado a caird e Chas Brown por 13 bytes!

Backerupper
fonte
Você pode usar inpute exigir que a entrada esteja entre aspas.
caird coinheringaahing
2
É perfeitamente aceitável falhar devido a limitações físicas, desde que seja bem-sucedido na teoria, o que ocorre.
Jonathan Allan
Salve 9 bytes substituindo filter(None,sorted(map(int,set(n)))[::-1])por sorted(set(map(int,n))-{0})[::-1](embora Noneseja interessante saber sobre isso).
quer
@ChasBrown Na maioria dos casos, você pode usar filter(len,...)para listas e seqüências de caracteres e filter(abs,...)para números inteiros e flutuantes.
ovs 31/08/19
0

Casca , 13 bytes

Bastante ineficiente

VVo=⁰ΣMṖNṘ⁰d⁰

Experimente online!

H.PWiz
fonte
0

JavaScript (ES6), 82 bytes

f=(n,l=0,a=n,[c,...b]=a)=>n?1/c?Math.min(!+c|+c>n?1/0:f(n-c,l+1,a),f(n,l,b)):1/0:l
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Recebe a entrada como uma sequência.

Neil
fonte
Você pode explicar por que está usando 1/0?
Zachary
1
@ Zacharý Quero a soma mais curta, ou seja, o número mínimo de dígitos. As tentativas que levam a uma solução inválida não devem contar; portanto, para excluí-las, elas pontuam Infinito, o que não afeta o mínimo.
315 Neil
Ah, não percebi que é recursivo.
Zachary
@ Zacharý O f=começo é uma grande pista, já que você não precisa dela para lambdas não-recursivas.
315 Neil
0

Ruby , 70 bytes

->n{w,s=n.digits,0;s+=1while !w.product(*[w]*s).find{|x|x.sum==n};s+1}

Muito devagar, tente todas as combinações possíveis, aumentando o tamanho até chegarmos a uma solução.

Obrigado Dennis pelo Ruby 2.4 no TIO.

Experimente online!

GB
fonte
0

Gelatina , 23 bytes

D;0ṗµḟ€0
ÇS€=µT
Çị1ĿL€Ṃ

Experimente online!

Isso é tão ineficiente que não é executado nos casos de teste após o terceiro no TIO devido a um limite de tempo> _ <

Quaisquer dicas de golfe são bem-vindas!

Zacharý
fonte
0

Python 2 , 183 176 172 166 166 161 bytes

def f(n,D=0,p=0,b=0):
	D=D or set(map(int,`n`))-{0}
	d=min(D);c=0;D=D-{d}
	q=[p+n/d,b][n%d>0]
	while c<min(D or{0}):q=b=f(n-c*d,D,p+c,b);c+=1
	return[q,b][q>b>0]

Experimente online!

Mais longo que a outra resposta Python, mas executa todos os casos de teste combinados mais 987654321em menos de um segundo no TIO.

Aproveita o fato de que, se houver d1<d2dígitos, é necessário que haja no máximo d2-1 d1na soma (uma vez que d2instâncias de d1podem ser substituídas por d1instâncias de d2uma soma menor). Assim, classificando os dígitos em ordem crescente, existem "apenas", no máximo, 9! = 362880somas possíveis a serem consideradas; e uma profundidade máxima de recursão de 9(independentemente do valor de n).

Chas Brown
fonte
0

Haskell , 91 bytes

f n=[read[c]|c<-show n,c>'0']#n!!0
s#n|n>0,x:m<-(s#).(n-)=<<s=[1+minimum(x:m)]|1<3=[0|n==0]

Experimente online! Exemplo de uso: f 58rendimentos 8. Rápido para números de dois dígitos, terrivelmente lento para entradas maiores.

A função fconverte o número de entrada nem uma lista de dígitos enquanto filtra zeros. Em seguida, essa lista e nela mesma são entregues à (#)função, que retorna uma lista única. !!0retorna o elemento dessa lista de singleton.

(#)usa listas singleton e vazias como tipo de opção. Dada uma entrada de n=58e s=[5,8], a idéia é subtrair todos os dígitos sde n, aplicar recursivamente (#)e verificar qual dígito resultou no número mínimo de etapas e retornar um mais esse mínimo como resultado. A primeira parte é calculada por (s#).(n-)=<<s, que é igual a concat(map(s#)(map(n-)s)). Portanto, em nosso exemplo, primeiro [58-5,58-8]é calculado, seguido pelo [[5,8]#53,[5,8]#50]resultado [[7],[7]]ou [7,7]depois concat. O resultado é correspondido no padrão x:mpara garantir que a lista tenha pelo menos um elemento ( minimumfalhará de outra forma); em seguida, a lista de singleton de 1 mais o mínimo do resultado será reajustada. E senera menor que zero ou a chamada recursiva retornou uma lista vazia, estamos em um ramo com falha da pesquisa e uma lista vazia é retornada. Se n==0a ramificação foi bem-sucedida e [0]é retornada.


Haskell , 101 bytes

f n=[d|d<-[9,8..1],show d!!0`elem`show n]#n!!0
s@(d:r)#n|n>=d,[x]<-s#(n-d)=[x+1]|1<3=r#n
s#n=[0|n==0]

Experimente online! Uma abordagem muito mais eficiente, verifica todos os casos de teste em menos de um segundo.

Desta vez, a lista de dígitos da entrada é calculada em ordem decrescente, o que permite (#)tentar usar o maior dígito sempre que possível, depois o segundo maior e assim até que uma solução seja encontrada. A primeira solução encontrada dessa maneira também é garantida como a menor.

Laikoni
fonte