Konwertuj liczbę na sumę cyfr

Żadna suma: potrzebujemy najkrótszej sumy
Żadnych cyfr: możesz użyć tylko cyfr liczby

Przykład
Otrzymasz dane wejściowe jako liczbę całkowitąn>0

Powiedzmy Chodźmy n=27. Musisz wyrazić 27jako sumę , używając tylko cyfr [2,7] , w możliwie najkrótszy sposób. Nie musisz używać wszystkich cyfr podanego numeru!

Tak 27=2+2+2+7+7+7. Następnie wziąć te cyfry i liczyć je : [2,2,2,7,7,7].
Ostateczna odpowiedź na n=27to pytanie to6

Jeszcze jeden przykład n=195, aby uzyskać najkrótszą sumę, musimy użyć następujących cyfr:
[5,5,5,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]i odpowiedź brzmi23

Wyzwanie

Podając liczbę całkowitą n>0, wypisz minimalną liczbę cyfr (zawartych w liczbie), które sumują się do tej liczby

Przypadki testowe

Input->Output

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

To jest golf golfowy. Najkrótsza odpowiedź w bajtach wygrywa!

Łuska , 12 bajtów

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

Bardzo szybko radzi sobie z cyframi dwucyfrowymi. Wypróbuj online!

Wyjaśnienie

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

Pyth , 12 bajtów

lef!-TsM`Q./

Wypróbuj online!

Niestety błędy pamięci na wejściach tak duże jak 58.

Wyjaśnienie

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

Mathematica, 78 bajtów

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

znajduje ostatni przypadek testowy za 5 sekund

R , 78 bajtów

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

Wypróbuj online! (wersja golfowa)

Algorytm czystej brutalnej siły, więc tak naprawdę nie rozwiązuje wszystkich przypadków testowych i myślę, że próbował przeznaczyć 40 000 GB na ostatni przypadek testowy ...

Tw R domyślnie, 1więc otrzymujemy błąd off-by-one, który naprawiamy na etapie powrotu, ale otrzymujemy również, Fktóre domyślne, 0które się opłacają.

wyjaśnienie bez golfa:

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

Wypróbuj online! (mniej golfowa wersja)

Python 2, 168 155 144 bajtów

To nie jest najkrótszy, jaki może być, ale najlepiej na początku i nie jest tak naprawdę zły, jeśli chodzi o środowisko uruchomieniowe.

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

Chodzi filter(None...o usunięcie 0 jako cyfry, co nauczyłem się, że mogę to zrobić.

Największym problemem są ramki stosu Pythona, które realistycznie nie pozwalają mi uruchamiać tego na największych wejściach. Tak więc, to nie jest prawidłowe rozwiązanie, tak naprawdę, bawiłem się ze zwiększeniem limitu rekurencji, co właśnie doprowadziło do błędów seg. Trzeba to zrobić albo za pomocą pętli i stosu, albo ze znacznie większą sprytnością, aby pracować w Pythonie.

edycja: Podziękowania dla Cairna i Chasa Browna za 13 bajtów!

Łuska , 13 bajtów

Całkiem nieefektywne

VVo=⁰ΣMṖNṘ⁰d⁰

Wypróbuj online!

JavaScript (ES6), 82 bajty

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>

Pobiera dane wejściowe jako ciąg.

Rubinowy , 70 bajtów

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

Bardzo powoli, wypróbuj wszystkie możliwe kombinacje, zwiększając rozmiar, aż dojdziemy do rozwiązania.

Dzięki Dennis za Ruby 2.4 w TIO.

Wypróbuj online!

Galaretka , 23 bajty

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

Wypróbuj online!

Jest to tak nieefektywne, że nie działa dla przypadków testowych po trzecim w TIO ze względu na limit czasu> _ <

Wszelkie wskazówki dotyczące gry w golfa są mile widziane!

Python 2 , 183 176 172 166 161 bajtów

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]

Wypróbuj online!

Dłuższy niż druga odpowiedź w języku Python, ale wykonuje wszystkie przypadki testowe łącznie plus 987654321w ciągu sekundy w TIO.

Wykorzystuje fakt, że jeśli d1<d2są cyframi, to d2-1 d1w sumie musi być co najwyżej ich liczba (ponieważ d2instancje d1można zastąpić d1instancjami d2na krótszą sumę). Tak więc, sortując cyfry w porządku rosnącym, istnieją „tylko” co najwyżej 9! = 362880możliwe sumy do rozważenia; i maksymalna głębokość rekurencji 9(niezależnie od wartości n).

Haskell , 91 bajtów

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]

Wypróbuj online! Przykładowe użycie: f 58daje 8. Szybkie dla liczb dwucyfrowych, strasznie wolne dla większych wejść.

Funkcja fkonwertuje liczbę wejściową nna listę cyfr podczas odfiltrowywania zer. Następnie ta lista i nsama są przekazywane do (#)funkcji, która zwraca listę singletonów. !!0zwraca element tej listy singletonów.

(#)używa singleton i pustych list jako typu opcji. Biorąc pod uwagę znak „ n=58i” s=[5,8], należy odjąć wszystkie cyfry sod n, a następnie zastosować rekurencyjnie (#)i sprawdzić, która cyfra spowodowała minimalną liczbę kroków, i zwrócić jeden plus to minimum jako wynik. Pierwsza część jest obliczana przez (s#).(n-)=<<s, który jest taki sam jak concat(map(s#)(map(n-)s)). Tak więc w naszym przykładzie najpierw [58-5,58-8]jest obliczana, a następnie [[5,8]#53,[5,8]#50]wyniki w [[7],[7]]lub [7,7]później concat. Wynik jest dopasowywany do wzorca, x:maby upewnić się, że lista zawiera co najmniej jeden element ( minimuminaczej kończy się niepowodzeniem), a następnie lista singletonów 1 plus minimum wyniku jest ponownie strojona. Jeślinbyło mniejsze zero lub wywołanie rekurencyjne zwróciło pustą listę, znajdujemy się w niedziałającej gałęzi wyszukiwania i zwracana jest pusta lista. Jeśli n==0oddział się powiódł i [0]jest zwracany.

Haskell , 101 bajtów

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]

Wypróbuj online! O wiele bardziej wydajne podejście, sprawdza wszystkie przypadki testowe w ciągu jednej sekundy.

Tym razem lista cyfr wejścia jest obliczana w kolejności malejącej, co pozwala (#)próbować używać największej cyfry tak często, jak to możliwe, a następnie drugiej największej, i tak, aż do znalezienia rozwiązania. Pierwsze znalezione w ten sposób rozwiązanie jest również zapewnione jako najmniejsze.