Wandle eine Zahl in eine Summe von Ziffern um
Keine Summe: Wir brauchen die kürzeste Summe.
Keine Ziffern: Sie können nur Ziffern der Zahl verwenden
Beispiel
Als Eingabe erhalten Sie eine ganze Zahln>0
Sagen wir mal n=27
. Sie müssen zum Ausdruck bringen 27
als Summe , indem nur die Ziffern [2,7]
, in dem kürzesten Weg möglich. Sie müssen nicht alle Ziffern der angegebenen Nummer verwenden!
Also 27=2+2+2+7+7+7
. Wir haben dann nehmen diese Ziffern und zählen sie : [2,2,2,7,7,7]
.
Endgültige Antwort für n=27
ist6
Ein weiteres Beispiel n=195
, um die kürzeste Summe zu erhalten, müssen wir die folgenden Ziffern verwenden:
[5,5,5,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
und die Antwort lautet23
Die Herausforderung
Geben Sie bei einer Ganzzahl n>0
die Mindestanzahl von Ziffern (in der Zahl enthalten) aus, die sich zu dieser Zahl summieren
Testfälle
Input->Output
1->1
2->1
10->10
58->8
874->110
1259->142
12347->1765
123456->20576
3456789->384088
Dies ist Code-Golf. Die kürzeste Antwort in Bytes gewinnt!
Antworten:
Schale , 12 Bytes
Verarbeitet zweistellige Zahlen ziemlich schnell. Probieren Sie es online!
Erläuterung
quelle
Pyth , 12 Bytes
Probieren Sie es online!
Leider ist es Speicherfehler bei Eingaben so groß wie
58
.Erläuterung
quelle
./
lef<.{TjQ;./
(Filter - richtige Teilmenge - der Ziffern des Eingangs)Mathematica, 78 Bytes
findet letzten Testfall in 5 sek
quelle
Length@IntegerPartitions[#, All, Sort@DeleteCases[0]@IntegerDigits@#, 1][[1]] &
R , 78 Bytes
Probieren Sie es online! (Golfversion)
Ein reiner Brute-Force-Algorithmus, der nicht alle Testfälle löst. Ich denke, er hat versucht, 40.000 GB für den letzten Testfall zuzuweisen ...
T
in R ist der Standardwert1
so , dass wir einen Fehler "off by one" erhalten, den wir im Rückgabeschritt korrigieren, aber wir erhalten auch,F
welcher Standardwert sich für0
wen auszahlt.ungolfed Erklärung:
Probieren Sie es online! (weniger Golfversion)
quelle
Python 2,
168155144 BytesEs ist nicht die kürzeste, die es sein könnte, aber es ist die beste und nicht wirklich schlechte, was die Laufzeit angeht.
Dasfilter(None...
ist, 0 als Ziffer zu entfernen, was ich gelernt habe, als ich das gemacht habe.Das größte Problem sind Python-Stack-Frames, die es mir realistisch gesehen nicht erlauben, diese auf den größten Eingaben auszuführen. Es ist also keine gültige Lösung. Ich habe versucht, das Rekursionslimit zu erhöhen, was zu Seg-Fehlern führte. Dies muss entweder mit einer Schleife und einem Stapel oder mit viel mehr Cleverness geschehen, um in Python zu arbeiten.
edit: Danke an Caird und Chas Brown für 13 Bytes!
quelle
input
die Eingabe verwenden und von Anführungszeichen umgeben lassen.filter(None,sorted(map(int,set(n)))[::-1])
mitsorted(set(map(int,n))-{0})[::-1]
(obwohl dieNone
Sache ist ziemlich schön zu wissen , über).filter(len,...)
für Listen und Zeichenfolgen sowiefilter(abs,...)
für Ganzzahlen und Gleitkommazahlen verwenden.Schale , 13 Bytes
Ziemlich ineffizient
Probieren Sie es online!
quelle
JavaScript (ES6), 82 Byte
Nimmt die Eingabe als String.
quelle
1/0
?f=
am Anfang ist ein großer Hinweis, da man es für nichtrekursive Lambdas nicht braucht.Ruby , 70 Bytes
Probieren Sie sehr langsam alle möglichen Kombinationen aus, um die Größe zu erhöhen, bis wir zu einer Lösung kommen.
Danke Dennis für Ruby 2.4 auf TIO.
Probieren Sie es online!
quelle
Jelly , 23 Bytes
Probieren Sie es online!
Dies ist so ineffizient, dass es für die Testfälle nach dem dritten auf TIO aufgrund eines Zeitlimits> _ <nicht ausgeführt wird
Alle Golftipps sind willkommen!
quelle
Python 2 ,
183176172166161 BytesProbieren Sie es online!
Länger als die andere Python-Antwort, führt jedoch alle Testfälle zusammen und
987654321
in weniger als einer Sekunde auf TIO aus.Nutzt die Tatsache aus, dass, wenn
d1<d2
es sich um Ziffern handelt, höchstens Ziffernd2-1
d1
in der Summe vorhanden sein müssen (dad2
Instanzen vond1
durchd1
Instanzen vond2
für eine kürzere Summe ersetzt werden können). Wenn Sie also die Ziffern in aufsteigender Reihenfolge sortieren, gibt es "nur" die9! = 362880
höchstmöglichen Beträge, die berücksichtigt werden müssen. und eine maximale Rekursionstiefe von9
(unabhängig vom Wert vonn
).quelle
Haskell , 91 Bytes
Probieren Sie es online! Anwendungsbeispiel:
f 58
Erträge8
. Schnell für zweistellige Zahlen, horrend langsam für größere Eingaben.Die Funktion
f
wandelt die eingegebene Nummern
in eine Liste von Ziffern um, während Nullen herausgefiltert werden. Dann werden diese Liste und sichn
selbst an die(#)
Funktion übergeben, die eine Singleton-Liste zurückgibt.!!0
Gibt das Element dieser Singleton-Liste zurück.(#)
Verwendet Singleton- und leere Listen als Optionstyp. Bei einer Eingabe vonn=58
unds=[5,8]
sollen alle Zifferns
von subtrahiertn
, dann rekursiv(#)
angewendet und geprüft werden, welche Ziffer zur Mindestanzahl von Schritten geführt hat, und als Ergebnis eins plus dieses Minimum zurückgegeben werden. Der erste Teil wird mit berechnet. Dies(s#).(n-)=<<s
ist das Gleiche wieconcat(map(s#)(map(n-)s))
. In unserem Beispiel wird also zuerst[58-5,58-8]
berechnet, gefolgt von dem,[[5,8]#53,[5,8]#50]
was in[[7],[7]]
oder[7,7]
nachher resultiertconcat
. Das Ergebnis wird mit dem Muster abgeglichenx:m
, um sicherzustellen, dass die Liste mindestens ein Element enthält (minimum
andernfalls schlägt dies fehl). Anschließend wird die Singleton-Liste von 1 plus dem Minimum des Ergebnisses erneut abgestimmt. Wennn
War die Null kleiner oder gab der rekursive Aufruf eine leere Liste zurück, befinden wir uns in einem fehlerhaften Zweig der Suche und es wird eine leere Liste zurückgegeben. Wennn==0
die Verzweigung erfolgreich war und[0]
zurückgegeben wird.Haskell , 101 Bytes
Probieren Sie es online! Bei einem effizienteren Ansatz werden alle Testfälle in weniger als einer Sekunde überprüft.
Dieses Mal wird die Liste der Ziffern der Eingabe in absteigender Reihenfolge berechnet
(#)
, sodass versucht werden kann, so oft wie möglich die größte und dann die zweitgrößte Ziffer zu verwenden, bis eine Lösung gefunden wird. Die erste auf diese Weise gefundene Lösung ist garantiert auch die kleinste.quelle