Ein gesparter Penny ist ein Penny

21

... 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:

  1. 12 Pfennige
  2. 1 Nickel und 7 Pfennige
  3. 2 Nickel und 2 Pennys
  4. 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:

  1. 26 Pfennige
  2. 21 Pfennige und 1 Nickel
  3. 16 Pfennige und 2 Nickel
  4. 11 Pennys und 3 Nickel
  5. 6 Pfennige und 4 Nickel
  6. 1 Penny und 5 Nickel
  7. 16 Pfennige und 1 Cent
  8. 6 Pfennige und 2 Groschen
  9. 11 Pennys, 1 Cent und 1 Nickel
  10. 6 Pennys, 1 Cent und 2 Nickel
  11. 1 Cent, 1 Cent und 3 Nickel
  12. 1 Penny, 2 Groschen und 1 Nickel
  13. 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. 1 12-Cent-Münze und 1 7-Cent-Münze
  2. 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.

anonymous2
quelle
1
s / gezählt / verdient
mbomb007
4
@ mbomb007 Für vier Bytes: s/count/earn.
wizzwizz4
5
Für mich und andere Leute, die nicht mit Dollars bezahlen, ist es nicht offensichtlich, was ein Nickel und ein Cent ist. Es war nicht schwer, es herauszufinden, aber vielleicht könnten Sie es ein bisschen internationaler schreiben?
Kritzefitz
2
@Kritzefitz. Ich habe das der Frage hinzugefügt.
TRiG
2
@jpaugh: Während Coin-o-Philes zustimmen könnten, müsste ich nicht zustimmen. Ein Penny ist die Standardmünze mit einem Wert von einem Cent. Vierundfünfzig Cent sind ein Geldbetrag. Vierundfünfzig Pennys sind ausdrücklich vierundfünfzig Münzen. Es wird auch "Ein-Cent-Münze" oder (offiziell) "Ein-Cent-Stück" genannt. Ich kann mir keine formale Umgebung vorstellen, in der das Wort "Penny" inakzeptabel wäre. Diese Leute , die sich speziell mit dem Sammeln von Münzen beschäftigen, haben kein Problem damit, es als "Penny" zu bezeichnen.
MichaelS

Antworten:

12

Jelly ( Gabel ), 2 Bytes

æf

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

$ ./jelly eun 'æf' '12' '[1,5,10]'
4
$ ./jelly eun 'æf' '26' '[1,5,10,25]'
13
$ ./jelly eun 'æf' '19' '[2,7,12]'
2
$ ./jelly eun 'æf' '13' '[2,8,25]'
0

Erläuterung

æf  Input: total T, denominations D
æf  Frobenius count, determines the number of solutions
    of nonnegative X such that X dot-product D = T
Meilen
quelle
10
... das ist nicht mal fair.
ETHproductions
... und ich wette, es ist viel schneller!
Jonathan Allan
18

Haskell, 37 34 Bytes

s#l@(c:d)|s>=c=(s-c)#l+s#d
s#_=0^s

Anwendungsbeispiel: 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 1else (oder wenn die Liste keine Elemente mehr enthält), nimm ein 0. Summiere diese 1s und 0s.

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

nimi
quelle
s # l @ (c: d) | s> = c = (sc) # l + s # d; s # _ = 0 ^ s
Damien
und was wäre das Ergebnis von 1209 [1,5,10,33,48] und 6000 [1,5,10,33], damit ich meinen Code kalibrieren kann
RosLuP
@ RosLuP: 1209 # [1,5,10,33,48]-> 1314050.
nimi
@nimi ok für 1314050 Ich habe das gleiche Ergebnis hier ... Danke ...
RosLuP
@RosLuP: ... 537min später: 6000 # [1,5,10,33]-> 22086484.
nimi
15

Mathematica, 35 22 Bytes

Vielen Dank an Miles FrobeniusSolve, der 13 Bytes vorgeschlagen und eingespart hat.

Length@*FrobeniusSolve

Wird zu einer unbenannten Funktion ausgewertet, bei der die Liste der Münzen als erstes Argument und der Zielwert als zweites Argument verwendet werden. FrobeniusSolveist eine Abkürzung zum Lösen von diophantinischen Gleichungen der Form

a1x1 + a2x2 + ... + anxn = b

für die über die nicht-negativen ganzen Zahlen und gibt uns alle Lösungen.xi

Martin Ender
quelle
@RosLuP Sie benötigen Zugriff auf Mathematica, um dies auszuführen. Dies ist auch eine anonyme Funktion, um sie aufzurufen, entweder in Klammern oder in einer Variablen zu speichern. Zum Beispiel(Length@*FrobeniusSolve)[{1, 7, 9}, 18]
Meilen
und was wäre das Ergebnis von 1209 [1,5,10,33,48] und 6000 [1,5,10,33], damit ich meinen Code kalibrieren kann
RosLuP
@ RosLuP 1314050 bzw. 22086484.
Martin Ender
Ok, hier das gleiche Ergebnis, danke ...
RosLuP
16 Stimmen dafür sind nur dann gerechtfertigt, wenn der Programmierer, der Length @ * FrobeniusSolve geschrieben hat, Sie sind ...
RosLuP
12

Pyth, 8 Bytes

/sM{yS*E

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 alstarget\n[c,o,i,n,s].

/sM{yS*EQQ      (implicit Q's)
      *EQ       multiply coin list by target
     S          sort
    y           powerset (all subsequences)
   {            remove duplicates
 sM             sum all results
/        Q      count correct sums
PurkkaKoodari
quelle
9

Haskell, 37 Bytes

s%(h:t)=sum$map(%t)[s,s-h..0]
s%_=0^s

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 ist 0^s.

xnor
quelle
Es ist erstaunlich, wie Sie mit einem anderen Ansatz genau dieselbe Byteanzahl wie @nimi treffen.
Kritzefitz
9

JavaScript (ES6), 51 48 Bytes

f=(n,a,[c,...b]=a)=>n?n>0&&c?f(n-c,a)+f(n,b):0:1

Akzeptiert 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==0bedeutet eine passende Kombination, n<0bedeutet, dass die Münzen die Menge überschreiten, während c==undefinedbedeutet, 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):

f=(n,a,[c,...b]=a)=>c?(c<=n&&f(n-c,a))+f(n,b):1
Neil
quelle
... Scheiße. Wirklich schöne Idee.
ETHproductions
und was wäre das Ergebnis von 1209 [1,5,10,33,48] und 6000 [1,5,10,33], damit ich meinen Code kalibrieren kann
RosLuP
@RosLuP Der angegebene Code gibt schließlich 1314050 für Ihr erstes Beispiel zurück. Mein Interpreter kann die für die Auswertung des zweiten Beispiels erforderliche Rekursion nicht verarbeiten.
Neil
@RosLuP Ich habe die Funktion dahingehend geändert, dass angenommen wird, dass eine zusätzliche Penny-Münze existiert, die 22086484 für 6000 [5,10,33] zurückgibt.
Neil
@Neil ok 22086484 für 6000 [1,5,10,33] ... Stattdessen wäre 11239 hier für 6000 [5,10,33] (das Array, das Sie geschrieben haben)
RosLuP
7

Perl, 45 Bytes

Die Bytezahl umfasst 44 Byte Code und -pFlag.

s%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{

Nimmt die Münzwerte in der ersten Zeile und den Zielbetrag in der zweiten Zeile:

$ perl -pE 's%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{' <<< "1 5 10 25
26"
13

Kurze Erklärungen:

-p                        # Set $_ to the value of the input, 
                          # and adds a print at the end of the code.
s%\S+%(1{$&})*%g,         # Converts each number n to (1{$&})* (to prepare the regex)
                          # This pattern does half the job.
(1x<>)                    # Converts the target to unary representation.
  =~                      # Match against.. (regex)
    /^ $_ $               # $_ contains the pattern we prepared with the first line.
     (?{$\++})            # Count the number of successful matches
     ^                    # Forces a fail in the regex since the begining can't be matched here.
    /x                    # Ignore white-spaces in the regex 
                          # (needed since the available coins are space-separated)
 }{                       # End the code block to avoid the input being printed (because of -p flag) 
                          # The print will still be executed, but $_ will be empty, 
                          # and only $\ will be printed (this variable is added after every print)
Dada
quelle
6

Gelee , 10 9 Bytes

œċЀS€€Fċ

Probieren Sie es online!

Wie?

œċЀS€€Fċ - Main link: coins, target
  Ѐ      - map over right argument, or for each n in [1,2,...,target]
œċ        - combinations with replacement, possible choices of each of n coins
    S€€   - sum for each for each (values of those selections)
       F  - flatten into one list
        ċ - count occurrences of right argument
Jonathan Allan
quelle
2
+1 für die Verwendung so vieler Euro-Symbole in einer Geldfrage.
Steenbergh
6

JavaScript (ES6), 59 Byte

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),0):1

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:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1

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:

f=(n,c=[100,25,10,5])=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1

Die einzigen Unterschiede sind der Standardwert von c(er hatte einen festgelegten Wert in der ursprünglichen Abfrage) und die Änderung 0der .reduceFunktion in1 (dies war zwei Bytes kürzer und millionenfach schneller als c=[100,25,10,5,1]).


Hier ist eine modifizierte Version, die alle Kombinationen anstelle der Anzahl der Kombinationen ausgibt:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:[...x,...f(n-y,c.slice(i)).map(c=>[...c,y])],[]):[[]]
ETHproductions
quelle
und was wäre das Ergebnis von 1209 [1,5,10,33,48] und 6000 [1,5,10,33], damit ich meinen Code kalibrieren kann
RosLuP
@RosLuP Ich erhalte 1314050 (nach 5 Minuten) bzw. einen Stapelüberlauf (nach einer Stunde). Mit der schnelleren Version, die ich gerade hinzugefügt habe, erhalte ich 1314050 und 22086484 innerhalb weniger Sekunden.
ETHproductions
Mit meinem alten Pentium 2.8Gh Computer 6 Sekunden für das erste Ergebnis, für die zweiten 5 Minuten + oder -
RosLuP
5

PHP, 327 Bytes

function c($f,$z=0){global$p,$d;if($z){foreach($p as$m){for($j=0;$j<=$f/$d[$z];){$n=$m;$n[$d[$z]]=$j++;$p[]=$n;}}}else for($p=[],$j=0;$j<=$f/$d[$z];$j++)$p[]=[$d[$z]=>$j];if($d[++$z])c($f,$z);}$d=$_GET[a];c($e=$_GET[b]);foreach($p as$u){$s=0;foreach($u as$k=>$v)$s+=$v*$k;if($s==$e&count($u)==count($d))$t[]=$u;}echo count($t);

Versuch es

Jörg Hülsermann
quelle
5

Axiom, 63 62 Bytes

1 Byte von @JonathanAllan gespeichert

f(n,l)==coefficient(series(reduce(*,[1/(1-x^i)for i in l])),n)

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.

Christian Sievers
quelle
1
Ich kenne Axiom nicht - ist es möglich, das Leerzeichen vorher zu entfernen for?
Jonathan Allan
1
@ JonathanAllan Ja, das ist es! Guter Golfinstinkt, danke!
Christian Sievers
5

R 81 76 63 Bytes

Vielen Dank an @rturnbull für die 13 Bytes!

function(u,v)sum(t(t(expand.grid(lapply(u/v,seq,f=0))))%*%v==u)

Beispiel (Beachten Sie, c(...)wie Sie Vektoren von Werten an R übergeben):

f(12,c(1,5,10))
[1] 4

Erläuterung:

uist der gewünschte Wert, vist der Vektor der Münzwerte.

expand.grid(lapply(u/v,seq,from=0))

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.matrixeine Matrix machen, aber das sind viele Zeichen. Stattdessen nehmen wir die Transponierte der Transponierten (!), Die sie automatisch zwingt, aber weniger Zeichen benötigt.

%*% vberechnet 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.

JDL
quelle
1
Gute Verwendung von expand.grid! Und ich liebe den t(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 schalten do.call(expand.grid,lapply(u/v,seq,from=0))für nur expand.grid(lapply(u/v,seq,f=0))11 Bytes speichern.
Rturnbull
Danke für die! Ich hätte nie gedacht, expand.griddass ich eine Liste als Eingabe nehmen würde. Es ist ein bisschen schade, dass ":"es mit Nicht-Ganzzahlen nicht gut funktioniert, sonst lapply(u/v,":",0)hätten wir ein paar mehr gespart.
JDL
do.call(x,y)ist dasselbe wie x(y), es geht also nicht darum, welche Arten von Eingaben akzeptiert werden. Wenn Sie wirklich verwenden möchten :, können Sie vermutlich verwenden lapply(u%/%v,`:`,0), aber es ist die gleiche Byteanzahl.
Rturnbull
1
" do.call(x,y)ist dasselbe wie x(y)" --- nur wenn yes keine Liste ist, was es in diesem Fall ist. Stimmen Sie jedoch Ihrem zweiten Punkt zu.
JDL
3

J, 27 Bytes

1#.[=](+/ .*~]#:,@i.)1+<.@%

Verwendung

   f =: 1#.[=](+/ .*~]#:,@i.)1+<.@%
   12 f 1 5 10
4
   26 f 1 5 10 25
13
   19 f 2 7 12
2
   13 f 2 8 25
0

Erläuterung

1#.[=](+/ .*~]#:,@i.)1+<.@%  Input: target T (LHS), denominations D (RHS)
                          %  Divide T by each in D
                       <.@   Floor each
                             These are the maximum number of each denomination
                     1+      Add 1 to each, call these B
                ,@i.         Forms the range 0 the the product of B
             ]               Get B
              #:             Convert each in the range to mixed radix B
     ]                       Get D
       +/ .*~                Dot product between D and each mixed radix number
                             These are all combinations of denominations up to T
   [                         Get T
    =                        Test if each sum is equal to T
1#.                          Convert as base 1 digits to decimal (takes the sum)
                             This is the number of times each sum was true
Meilen
quelle
J ist so toll, aber auch so verrückt
CommaToast
2

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:

DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)
;WITH c as(SELECT 0l,0s UNION ALL SELECT z,s+z FROM c,@t WHERE l<=z and s<@)SELECT SUM(1)FROM c WHERE s=@

Ungolfed:

-- input variables
DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)

-- query
;WITH c as
(
  SELECT 0l,0s
  UNION ALL
  SELECT z,s+z
  FROM c,@t
  WHERE l<=z and s<@
)
SELECT SUM(1)
FROM c
WHERE s=@
-- to allow more than 100 recursions(amounts higher than 1 dollar in this example)
OPTION(MAXRECURSION 0)

Geige

t-clausen.dk
quelle
2

tinylisp repl, 66 bytes

(d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1

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

(d combos
 (q
  ((amount coin-values)
   (i amount
    (i (l amount 0)
     0
     (i coin-values
      (s
       (combos
        (s amount (h coin-values))
        coin-values)
       (s
        0
        (combos
         amount
         (t coin-values))))
      0))
    1))))

Anwendungsbeispiel:

tl> (d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1
C
tl> (C 12 (q (1 5 10)))
4
tl> (C 26 (q (1 5 10 25)))
13
tl> (C 19 (q (2 7 12)))
2
tl> (C 13 (q (2 8 25)))
0
tl> (C 400 (q (1 5 10 25)))
Error: recursion depth exceeded. How could you forget to use tail calls?!
DLosc
quelle
1

PHP, 130 Bytes

function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));

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:

 php -r "function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));" 12 1 5 10
user59178
quelle
Wenn mit mehr als 97 verschiedenen Münzsorten gerufen wird, stirbt der Rekursionstod, ohne dass irgendetwas zurückgegeben wird. Da dies jedoch weitaus mehr verschiedene Münzsorten sind, müssen wir unterstützen, dass es in Ordnung ist.
User59178
1

Schläger 275 Bytes

(set! l(flatten(for/list((i l))(for/list((j(floor(/ s i))))i))))(define oll'())(for((i(range 1(add1(floor(/ s(apply min l)))))))
(define ol(combinations l i))(for((j ol))(set! j(sort j >))(when(and(= s(apply + j))(not(ormap(λ(x)(equal? x j))oll)))(set! oll(cons j oll)))))oll

Ungolfed:

(define(f s l)
  (set! l              ; have list contain all possible coins that can be used
        (flatten
         (for/list ((i l))
           (for/list ((j              
                       (floor
                        (/ s i))))
             i))))
  (define oll '())                    ; final list of all solutions initialized
  (for ((i (range 1  
                  (add1
                   (floor             ; for different sizes of coin-set
                    (/ s
                       (apply min l)))))))
    (define ol (combinations l i))          ; get a list of all combinations
    (for ((j ol))                           ; test each combination
      (set! j (sort j >))
      (when (and
             (= s (apply + j))              ; sum is correct
             (not(ormap                     ; solution is not already in list
                  (lambda(x)
                    (equal? x j))
                  oll)))
        (set! oll (cons j oll))             ; add found solution to final list
        )))
  (reverse oll))

Testen:

(f 4 '[1 2])
(println "-------------")
(f 12 '[1 5 10])
(println "-------------")
(f 19 '[2 7 12])
(println "-------------")
(f 8 '(1 2 3))

Ausgabe:

'((2 2) (2 1 1) (1 1 1 1))
"-------------"
'((10 1 1) (5 5 1 1) (5 1 1 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1 1 1))
"-------------"
'((12 7) (7 2 2 2 2 2 2))
"-------------"
'((3 3 2) (2 2 2 2) (3 2 2 1) (3 3 1 1) (2 2 2 1 1) (3 2 1 1 1) (2 2 1 1 1 1) (3 1 1 1 1 1) (2 1 1 1 1 1 1) (1 1 1 1 1 1 1 1))

Die folgende rekursive Lösung weist einen Fehler auf:

(define (f s l)                      ; s is sum needed; l is list of coin-types
  (set! l (sort l >))
  (define oll '())                   ; list of all solution lists
  (let loop ((l l)   
             (ol '()))               ; a solution list initialized
    (when (not (null? l))
        (set! ol (cons (first l) ol)))
    (define ols (apply + ol))        ; current sum in solution list
    (cond
      [(null? l) (remove-duplicates oll)]
      [(= ols s) (set! oll (cons ol oll))
                 (loop (rest l) '()) 
                 ]
      [(> ols s) (loop (rest l) (rest ol))
                 (loop (rest l) '())   
                 ]
      [(< ols s) (loop l ol) 
                 (loop (rest l) ol)
                 ])))

Funktioniert nicht richtig für:

(f 8 '[1 2 3])

Ausgabe:

'((1 1 1 2 3) (1 2 2 3) (1 1 1 1 1 1 1 1) (2 3 3) (1 1 1 1 1 1 2) (1 1 1 1 2 2) (1 1 2 2 2) (2 2 2 2))

(1 1 3 3) ist möglich, kommt aber nicht in die Lösungsliste.

rnso
quelle
Ich bin mit Racket nicht vertraut, aber ich habe in Clojure eine Lösung für ein ähnliches Problem wie dieses vor einigen Jahren geschrieben, bei derreduce
miles
'Reduzieren' ist nicht Teil der Basissprache von Racket, obwohl 'Falzen' verfügbar ist. Ich habe oben eine modifizierte Lösung hinzugefügt, da die frühere Lösung einen Fehler aufweist.
RNSO
Sieht aus, als hätten sich ein paar Lisp-Enthusiasten zusammengetan ... und einen Schläger gemacht
Joe,
1
Einige von Lisp-Enthusiasten haben zuerst ein Scheme( groups.csail.mit.edu/mac/projects/scheme ) erstellt, das schließlich zu einer vollständigen Umsetzung führte Racket( racket-lang.org , stackoverflow.com/questions/3345397/… )!
RNSO
1

Gelee , 15 Bytes

s+\Fṁḷ
2*BW;ç/Ṫ

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

s+\Fṁḷ  Helper link. Input: solutions S, coin C
s       Slice the solutions into non-overlapping sublists of length C
 +\     Cumulative sum
   F    Flatten
     ḷ  Left, get S
    ṁ   Mold the sums to the shape of S

2*BW;ç/Ṫ  Main link. Input: target T, denominations D
2*        Compute 2^T
  B       Convert to binary, creates a list with 1 followed by T-1 0's
          These are the number of solutions for each value from 0 to T
          starting with no coins used
   W      Wrap it inside another array
    ;     Concatenate with D
     ç/   Reduce using the helper link
       Ṫ  Tail, return the last value which is the solution
Meilen
quelle
1

Eigentlich 15 Bytes

Golfvorschläge sind willkommen. Probieren Sie es online!

╗;R`╜∙♂S╔♂Σi`Mc

Ungolfing

         Implicit input n, then the list of coins a.
╗        Save a to register 0.
;R       Duplicate n and create a range [1..n] from that duplicate.
`...`M   Map the following function over that range. Variable i.
  ╜        Push a from register 0.
  ∙        Push the i-th Cartesian power of a.
  ♂S       Sort each member of car_pow.
  ╔        Uniquify car_pow so we don't count too any duplicate coin arrangements.
  ♂Σ       Take the sum of each coin arrangement.
  i        Flatten the list.
c        Using the result of the map and the remaining n, push map.count(n).
         Implicit return.
Sherlock9
quelle
0

Python, 120 Bytes

from itertools import*
lambda t,L:[sum(map(lambda x,y:x*y,C,L))-t for C in product(range(t+1),repeat=len(L))].count(0)

Bruteforces durch alle Kombinationen von Münzen bis zum Zielwert (auch wenn der kleinste nicht 1 ist).

Karl Napf
quelle