... gezählt!
Sie übergeben Ihrem Programm eine Variable, die eine Geldmenge in Dollar und / oder Cent und eine Reihe von Münzwerten darstellt. Ihre Herausforderung besteht darin, die Anzahl der möglichen Kombinationen der angegebenen Reihe von Münzwerten auszugeben, die sich zu dem Betrag addieren, der an den Code übergeben wird. Wenn es mit den genannten Münzen nicht möglich ist, sollte das Programm zurückkehren 0
.
Anmerkung zur amerikanischen numismatischen Terminologie:
- 1-Cent-Münze: Penny
- 5-Cent-Münze: Nickel
- 10-Cent-Münze: Cent
- 25-Cent-Münze: Viertel (Vierteldollar)
Beispiel 1:
Programm ist bestanden:
12, [1, 5, 10]
(12 Cent)
Ausgabe:
4
Es gibt 4 Möglichkeiten, die genannten Münzen zu 12 Cent zu kombinieren:
- 12 Pfennige
- 1 Nickel und 7 Pfennige
- 2 Nickel und 2 Pennys
- 1 Cent und 2 Cent
Beispiel 2:
Programm ist bestanden:
26, [1, 5, 10, 25]
(26 Cent)
Ausgabe:
13
Es gibt 13 Möglichkeiten, die genannten Münzen zu 26 Cent zu kombinieren:
- 26 Pfennige
- 21 Pfennige und 1 Nickel
- 16 Pfennige und 2 Nickel
- 11 Pennys und 3 Nickel
- 6 Pfennige und 4 Nickel
- 1 Penny und 5 Nickel
- 16 Pfennige und 1 Cent
- 6 Pfennige und 2 Groschen
- 11 Pennys, 1 Cent und 1 Nickel
- 6 Pennys, 1 Cent und 2 Nickel
- 1 Cent, 1 Cent und 3 Nickel
- 1 Penny, 2 Groschen und 1 Nickel
- 1 Viertel und 1 Penny
Beispiel 3:
Programm ist bestanden:
19, [2, 7, 12]
Ausgabe:
2
Es gibt zwei Möglichkeiten, die genannten Münzen zu 19 Cent zu kombinieren:
- 1 12-Cent-Münze und 1 7-Cent-Münze
- 1 7-Cent-Münze und 6 2-Cent-Münzen
Beispiel 4:
Programm ist bestanden:
13, [2, 8, 25]
Ausgabe:
0
Es gibt keine Möglichkeit, die genannten Münzen zu 13 Cent zu kombinieren.
Dies wurde durch die Sandbox. Es gelten Standardlücken. Dies ist Codegolf, daher gewinnt die Antwort mit den wenigsten Bytes.
quelle
s/count/earn
.Antworten:
Jelly ( Gabel ), 2 Bytes
Dies beruht auf a Zweig von Jelly, in dem ich an der Implementierung von Frobenius-Lösungsatomen gearbeitet habe. Leider können Sie es nicht online ausprobieren.
Verwendung
Erläuterung
quelle
Haskell,
3734 BytesAnwendungsbeispiel:
26 # [1,5,10,25]
->13
.Einfacher rekursiver Ansatz: Versuchen Sie es mit der nächsten Zahl in der Liste (solange sie kleiner oder gleich der Menge ist) und überspringen Sie sie. Wenn das Subtrahieren der Zahl zu einem Betrag von Null führt, nimm ein
1
else (oder wenn die Liste keine Elemente mehr enthält), nimm ein0
. Summiere diese1
s und0
s.Edit: @Damien: 3 Bytes gespart, indem auf einen kürzeren Basisfall für die Rekursion verwiesen wird (der auch in @xnors answer zu finden ist ).
quelle
1209 # [1,5,10,33,48]
->1314050
.6000 # [1,5,10,33]
->22086484
.Mathematica,
3522 BytesVielen Dank an Miles
FrobeniusSolve
, der 13 Bytes vorgeschlagen und eingespart hat.Wird zu einer unbenannten Funktion ausgewertet, bei der die Liste der Münzen als erstes Argument und der Zielwert als zweites Argument verwendet werden.
FrobeniusSolve
ist eine Abkürzung zum Lösen von diophantinischen Gleichungen der Formfür die über die nicht-negativen ganzen Zahlen und gibt uns alle Lösungen.
xi
quelle
(Length@*FrobeniusSolve)[{1, 7, 9}, 18]
Pyth, 8 Bytes
Rohe Brute Force, zu speicherintensiv für tatsächliche Tests. Das ist O (2 mn ), wobei n die Anzahl der Münzen und m die Zielsumme ist. Übernimmt die Eingabe als
target\n[c,o,i,n,s]
.quelle
Haskell, 37 Bytes
Wenn Sie ein Vielfaches der ersten Münze verwenden
h
, wird die erforderliche Summe verringerts
im abnehmenden Verlauf auf einen nicht negativen Wert verringert[s,s-h..0]
, der dann mit den verbleibenden Münzen vorgenommen werden muss. Wenn keine Münzen mehr vorhanden sind, überprüfen Sie, ob die Summe rechnerisch Null ist0^s
.quelle
JavaScript (ES6),
5148 BytesAkzeptiert Münzen in beliebiger Reihenfolge. Es wird versucht, die erste Münze zu verwenden und nicht, wobei die Anzahl der Kombinationen in beide Richtungen rekursiv berechnet wird.
n==0
bedeutet eine passende Kombination,n<0
bedeutet, dass die Münzen die Menge überschreiten, währendc==undefined
bedeutet, dass keine Münzen mehr übrig sind. Beachten Sie, dass die Funktion sehr langsam ist. Wenn Sie eine Penny-Münze haben, ist die folgende Funktion schneller (geben Sie die Penny-Münze nicht in die Reihe der Münzen ein):quelle
Perl, 45 Bytes
Die Bytezahl umfasst 44 Byte Code und
-p
Flag.Nimmt die Münzwerte in der ersten Zeile und den Zielbetrag in der zweiten Zeile:
Kurze Erklärungen:
quelle
Gelee ,
109 BytesProbieren Sie es online!
Wie?
quelle
JavaScript (ES6), 59 Byte
Münzen werden vom höchsten zum niedrigsten eingegeben, z
f(26,[100,25,10,5,1])
. Wenn Sie einen Penny haben, entfernen Sie ihn und verwenden Sie stattdessen diese viel schnellere Version:Dies verwendet eine rekursive Formel, ähnlich wie bei @ nimi. Ich habe das ursprünglich vor ein paar Tagen geschrieben, als sich die Herausforderung noch im Sandkasten befand. es sah so aus:
Die einzigen Unterschiede sind der Standardwert von
c
(er hatte einen festgelegten Wert in der ursprünglichen Abfrage) und die Änderung0
der.reduce
Funktion in1
(dies war zwei Bytes kürzer und millionenfach schneller alsc=[100,25,10,5,1]
).Hier ist eine modifizierte Version, die alle Kombinationen anstelle der Anzahl der Kombinationen ausgibt:
quelle
PHP, 327 Bytes
Versuch es
quelle
Axiom,
6362 Bytes1 Byte von @JonathanAllan gespeichert
Dieser Ansatz verwendet Generierungsfunktionen. Wahrscheinlich hat das nicht dazu beigetragen, die Codegröße zu verringern. Ich denke, dies ist das erste Mal, dass ich bei Axiom meine eigene Funktion definiert habe.
Wenn die Funktion zum ersten Mal aufgerufen wird, gibt sie eine entsetzliche Warnung aus, liefert jedoch immer noch das richtige Ergebnis. Danach ist alles in Ordnung, solange die Liste nicht leer ist.
quelle
for
?R
817663 BytesVielen Dank an @rturnbull für die 13 Bytes!
Beispiel (Beachten Sie,
c(...)
wie Sie Vektoren von Werten an R übergeben):Erläuterung:
u
ist der gewünschte Wert,v
ist der Vektor der Münzwerte.Erstellt einen Datenrahmen mit jeder möglichen Kombination von 0 bis k Münzen (k hängt vom Nennwert ab), wobei k der niedrigste Wert ist, sodass das k-fache des Werts dieser Münze mindestens u ist (der zu erreichende Wert).
Normalerweise würden wir daraus
as.matrix
eine Matrix machen, aber das sind viele Zeichen. Stattdessen nehmen wir die Transponierte der Transponierten (!), Die sie automatisch zwingt, aber weniger Zeichen benötigt.%*% v
berechnet dann den Geldwert jeder Zeile. Der letzte Schritt besteht darin, zu zählen, wie viele dieser Werte dem gewünschten Wert entsprechenu
.Beachten Sie, dass die Komplexität der Berechnungen und die Anforderungen an den Arbeitsspeicher schrecklich sind, aber es ist Code Golf.
quelle
expand.grid
! Und ich liebe dent(t())
Trick. Da Ihre Funktion nur eine einzige Codezeile enthält, können Sie die geschweiften Klammern entfernen und so 2 Byte sparen. Außerdem können Sie schaltendo.call(expand.grid,lapply(u/v,seq,from=0))
für nurexpand.grid(lapply(u/v,seq,f=0))
11 Bytes speichern.expand.grid
dass ich eine Liste als Eingabe nehmen würde. Es ist ein bisschen schade, dass":"
es mit Nicht-Ganzzahlen nicht gut funktioniert, sonstlapply(u/v,":",0)
hätten wir ein paar mehr gespart.do.call(x,y)
ist dasselbe wiex(y)
, es geht also nicht darum, welche Arten von Eingaben akzeptiert werden. Wenn Sie wirklich verwenden möchten:
, können Sie vermutlich verwendenlapply(u%/%v,`:`,0)
, aber es ist die gleiche Byteanzahl.do.call(x,y)
ist dasselbe wiex(y)
" --- nur wenny
es keine Liste ist, was es in diesem Fall ist. Stimmen Sie jedoch Ihrem zweiten Punkt zu.J, 27 Bytes
Verwendung
Erläuterung
quelle
TSQL, 105 Bytes
Dies kann mit diesen 4 Münztypen nur bis zu einem Dollar bewältigen. Die ungolfed Version kann bis zu 4 Dollar verarbeiten, aber sehr langsam - auf meiner Box dauert dies 27 Sekunden. Ergebnis sind übrigens 10045 Kombinationen
Golf gespielt:
Ungolfed:
Geige
quelle
tinylisp repl, 66 bytes
Rekursive Lösung: Versuchen Sie, die erste Münze und nicht die erste Münze zu verwenden, und addieren Sie dann die Ergebnisse der einzelnen Münzen. Exponentielle Zeitkomplexität und keine Schwanzrekursion, aber die Testfälle werden einwandfrei berechnet.
Ungolfed (Schlüssel zu Builtins:
d
= Define,q
= Quote ,i
= If,l
= Less -than,s
= Subtract,h
= Head,t
= Tail):Anwendungsbeispiel:
quelle
PHP, 130 Bytes
99 Byte rekursive Funktion (und 31 Byte Aufruf), die wiederholt den Wert der aktuellen Münze vom Ziel entfernt und sich mit dem neuen Wert und den anderen Münzen aufruft. Zählt, wie oft das Ziel genau 0 erreicht. Laufen Sie wie folgt:
quelle
Schläger 275 Bytes
Ungolfed:
Testen:
Ausgabe:
Die folgende rekursive Lösung weist einen Fehler auf:
Funktioniert nicht richtig für:
Ausgabe:
(1 1 3 3) ist möglich, kommt aber nicht in die Lösungsliste.
quelle
reduce
Scheme
( groups.csail.mit.edu/mac/projects/scheme ) erstellt, das schließlich zu einer vollständigen Umsetzung führteRacket
( racket-lang.org , stackoverflow.com/questions/3345397/… )!Gelee , 15 Bytes
Probieren Sie es online! oder Überprüfen Sie alle Testfälle.
Dies war eher eine Übung, um eine effiziente Version in Jelly zu schreiben, ohne eingebaute Funktionen zu verwenden. Dies basiert auf dem typischen Ansatz der dynamischen Programmierung, mit dem die Anzahl der Änderungsmöglichkeiten berechnet wird
Erläuterung
quelle
Eigentlich 15 Bytes
Golfvorschläge sind willkommen. Probieren Sie es online!
Ungolfing
quelle
Python, 120 Bytes
Bruteforces durch alle Kombinationen von Münzen bis zum Zielwert (auch wenn der kleinste nicht 1 ist).
quelle