Self-summed numbers

Question

Convert a number to a sum of digits

Not any sum: we need the shortest sum
Not any digits: you can use only digits of the number

Example
You will be given as input an integer n>0

Let's say n=27. You have to express 27 as a sum, using only the digits [2,7], in the shortest way possible. You don't have to use all the digits of the given number!

So 27=2+2+2+7+7+7. We then take those digits and count them: [2,2,2,7,7,7].
Final answer for n=27 is 6

One more example for n=195 in order to get the shortest sum we have to use the following digits:
[5,5,5,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9] and the answer is 23

The challenge

Given an integer n>0, output the minimum number of digits (contained in the number) that sum up to this number

Test Cases

Input->Output

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

This is code-golf.Shortest answer in bytes wins!

Answer 1

Husk, 12 bytes

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

Handles two-digit numbers pretty fast. Try it online!

Explanation

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

Answer 2

Python 2, 168 155 144 bytes

It isn't the shortest it could be, but it's best-first and not real bad, runtime wise.

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)) 

The filter(None... is to remove 0 as a digit, which I learned I could do while making this.

The biggest problem is python stack frames, which realistically don't allow me to run this on the largest inputs. So, it is not a valid solution, really, I played around with increasing the recursion limit which just led to seg-faults. This has to either be done with a loop and a stack or with a lot more cleverness to work in python.

edit: Thanks to caird and Chas Brown for 13 bytes!

Answer 3

Pyth, 12 bytes

lef!-TsM`Q./

Try it online!

Unfortunately it memory errors on inputs as large as 58.

Explanation

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

Answer 4

Mathematica, 78 bytes

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

finds last test case in 5 sec

Answer 5

R, 78 bytes

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

Try it online! (golfed version)

Pure brute force algorithm, so it doesn't actually solve all the test cases, and I think it tried to allocate 40,000 GB for the last test case...

T in R defaults to 1 so we get an off-by-one error which we correct at the return step, but we also get F which defaults to 0 which pays off.

ungolfed explanation:

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

Try it online! (less golfy version)

Answer 6

Husk, 13 bytes

Pretty inefficient

VVo=⁰ΣMṖNṘ⁰d⁰

Try it online!

Answer 7

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>

Takes input as a string.

Answer 8

Ruby, 70 bytes

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

Very slow, try all the possible combinations increasing the size until we get to a solution.

Thanks Dennis for Ruby 2.4 on TIO.

Try it online!

Answer 9

Jelly, 23 bytes

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

Try it online!

This is so inefficient, that it does not run for the test cases after the third one on TIO due to a time limit >_<

Any golfing tips are welcome!

Answer 10

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]

Try it online! Example usage: f 58 yields 8. Quick for two-digit numbers, horrendously slow for larger inputs.

The function f converts the input number n into a list of digits while filtering out zeros. Then this list and n itself are handed to the (#) function, which returns a singleton list. !!0 returns the element of this singleton list.

(#) uses singleton and empty lists as option type. Given an input of n=58 and s=[5,8], the idea is to subtract all digits in s from n, then recursively apply (#) and check which digit resulted in the minimum number of steps and return one plus this minimum as result. The first part is computed by (s#).(n-)=<<s, which is the same as concat(map(s#)(map(n-)s)). So in our example first [58-5,58-8] is computed, followed by [[5,8]#53,[5,8]#50] which results in [[7],[7]] or [7,7] after concat. The result is matched on the pattern x:m to make sure the list has at least one element (minimum fails otherwise), then the singleton list of 1 plus the minimum of the result is retuned. If n was smaller zero or the recursive call returned an empty list, we are in a failing branch of the search and an empty list is returned. If n==0 the branch was succeeding and [0] is returned.

---

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]

Try it online! A way more efficient approach, checks all test cases in under one second.

This time, the list of digits of the input is computed to be in descending order, which allows (#) to try to use the largest digit as often as possible, then the second largest, and so until a solution is found. The first solution found this way is also guaranteed to be the smallest one.

Answer 11

Python 2, 183 176 172 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]

Try it online!

Longer than the other Python answer, but performs all test cases combined plus 987654321 in under a second on TIO.

Takes advantage of the fact that if d1<d2 are digits, then there need be at most d2-1 d1's in the sum (since d2 instances of d1 can be replaced with d1 instances of d2 for a shorter sum). Thus, sorting the digits in ascending order, there are "only" at most 9! = 362880 possible sums to consider; and a maximum recursion depth of 9 (regardless of the value of n).