Uratowany grosz to grosz

21

... policzył!

Zdasz programowi zmienną, która reprezentuje ilość pieniędzy w dolarach i / lub centach oraz tablicę wartości monet. Wyzwanie polega na wyprowadzeniu liczby możliwych kombinacji podanej tablicy wartości monet, które sumowałyby się do kwoty przekazanej do kodu. Jeśli nie jest to możliwe z nazwanymi monetami, program powinien powrócić 0.

Uwaga na temat amerykańskiej terminologii numizmatycznej:

  • Moneta 1-centowa: grosz
  • Moneta 5 centów: nikiel
  • Moneta 10 centów: grosz
  • Moneta 25 centów: kwartał (ćwierć dolara)

Przykład 1:

Program zaliczony:

12, [1, 5, 10]

(12 centów)

Wydajność:

4

Istnieją 4 możliwe sposoby łączenia nazwanych monet w celu wytworzenia 12 centów:

  1. 12 groszy
  2. 1 nikiel i 7 groszy
  3. 2 monety i 2 grosze
  4. 1 bilon i 2 grosze

Przykład 2:

Program zaliczony:

26, [1, 5, 10, 25]

(26 centów)

Wydajność:

13

Istnieje 13 możliwych sposobów łączenia nazwanych monet w celu uzyskania 26 centów:

  1. 26 groszy
  2. 21 groszy i 1 nikiel
  3. 16 groszy i 2 monety
  4. 11 groszy i 3 monety
  5. 6 groszy i 4 monety
  6. 1 grosz i 5 monet
  7. 16 groszy i 1 grosz
  8. 6 groszy i 2 dziesięciocentówki
  9. 11 groszy, 1 bilon i 1 nikiel
  10. 6 groszy, 1 bilon i 2 monety
  11. 1 grosz, 1 bilon i 3 monety
  12. 1 grosz, 2 dziesięciocentówki i 1 nikiel
  13. 1 kwartał i 1 grosz

Przykład 3:

Program zaliczony:

19, [2, 7, 12]

Wydajność:

2

Istnieją 2 możliwe sposoby łączenia monet o wartości 19 centów:

  1. 1 moneta 12 centów i 1 moneta 7 centów
  2. 1 moneta 7 centów i 6 monet 2 centów

Przykład 4:

Program zaliczony:

13, [2, 8, 25]

Wydajność:

0

Nie ma możliwości połączenia nazwanych monet w celu uzyskania 13 centów.


To było przez piaskownicę. Obowiązują standardowe luki. To jest golf golfowy, więc wygrywa odpowiedź z najmniejszą liczbą bajtów.

anonimowy 2
źródło
1
s /
counted
4
@ mbomb007 dla czterech bajtów: s/count/earn.
wizzwizz4,
5
Dla mnie i dla innych ludzi, którzy nie płacą dolarami, nie jest oczywiste, co to jest nikiel i bilon. Nie było trudno to rozgryźć, ale może mógłbyś napisać to nieco bardziej międzynarodowo?
Kritzefitz
2
@Kritzefitz. Dodałem to do pytania.
TRiG
2
@jpaugh: Chociaż monety-phile mogą się zgodzić, musiałbym się nie zgodzić. Grosz to standardowa moneta o wartości jednego centa. Pięćdziesiąt cztery centy to suma pieniędzy. Pięćdziesiąt cztery grosze to wyraźnie pięćdziesiąt cztery monety. Jest również nazywany „monetą jednocentową” lub (oficjalnie) „monetą jednocentową”. Nie mogę wymyślić żadnego formalnego otoczenia, w którym słowo „grosz” byłoby niedopuszczalne. Ci ludzie , którzy szczególnie chcą zbierać monety, nie mają problemu z nazwaniem tego „groszem”.
MichaelS,

Odpowiedzi:

12

Galaretka ( widelec ), 2 bajty

æf

To zależy od gałęzi Jelly, w której pracowałem nad wdrożeniem atomów Frobeniusa do rozwiązania atomów, więc niestety nie można wypróbować go online.

Stosowanie

$ ./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

Wyjaśnienie

æf  Input: total T, denominations D
æf  Frobenius count, determines the number of solutions
    of nonnegative X such that X dot-product D = T
mile
źródło
10
... to nawet niesprawiedliwe.
ETHproductions
... i założę się, że jest znacznie szybszy!
Jonathan Allan,
18

Haskell, 37 34 bajtów

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

Przykład użycia: 26 # [1,5,10,25]-> 13.

Proste podejście rekurencyjne: wypróbuj zarówno następny numer na liście (o ile jest on mniejszy lub równy kwocie) i pomiń go. Jeśli odjęcie liczby prowadzi do zera, weź 1inną (lub jeśli na liście brakuje elementów) weź 0. Zsumuj te 1i te 0.

Edycja: @Damien: zapisano 3 bajty, wskazując krótszy przypadek podstawowy dla rekurencji (który również można znaleźć w odpowiedzi @xnors ).

nimi
źródło
s # l @ (c: d) | s> = c = (sc) # l + s # d; s # _ = 0 ^ s
Damien
i jaki byłby wynik 1209 [1,5,10,33,48] i 6000 [1,5,10,33], więc mogę skalibrować mój kod
RosLuP
@RosLuP: 1209 # [1,5,10,33,48]-> 1314050.
nimi
@nimi ok za 1314050 Mam tutaj ten sam wynik ... Dzięki ...
RosLuP
@RosLuP: ... 537 minut później: 6000 # [1,5,10,33]-> 22086484.
nimi
15

Mathematica, 35 22 bajtów

Dziękujemy za mile za sugestie FrobeniusSolvei oszczędność 13 bajtów.

Length@*FrobeniusSolve

Zwraca wartość do nienazwanej funkcji, która przyjmuje listę monet jako pierwszy argument, a wartość docelową jako drugi. FrobeniusSolvejest skrótem do rozwiązywania równań diofantycznych formy

a1x1 + a2x2 + ... + anxn = b

dla ponad nieujemnych liczb całkowitych i daje nam wszystkie rozwiązania.xi

Martin Ender
źródło
@RosLuP Aby uruchomić tę funkcję, musisz mieć dostęp do Mathematica. Jest to również funkcja anonimowa, więc aby ją wywołać, należy umieścić ją w nawiasach lub zapisać w zmiennej. Na przykład(Length@*FrobeniusSolve)[{1, 7, 9}, 18]
mile
i jaki byłby wynik 1209 [1,5,10,33,48] i 6000 [1,5,10,33], więc mogę skalibrować mój kod
RosLuP
@RosLuP 1314050 i 22086484, odpowiednio.
Martin Ender
Ok, tutaj wynik taki sam, dzięki ...
RosLuP
16 głosów za to jest uzasadnionych tylko wtedy, gdy programista, który napisał Length @ * FrobeniusSolve, jesteś ...
RosLuP
12

Pyth, 8 bajtów

/sM{yS*E

Surowa brutalna siła, zbyt intensywna pamięć do rzeczywistych testów. Jest to O (2 mn ), gdzie n jest liczbą monet, a m jest sumą docelową. Pobiera dane wejściowe jako target\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
źródło
9

Haskell, 37 bajtów

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

Użycie kilku wielokrotności pierwszej monety hzmniejsza wymaganą sumę sdo wartości nieujemnej w postępie malejącym [s,s-h..0], którą następnie należy wykonać z pozostałymi monetami. Gdy nie pozostaną żadne monety, sprawdź, czy suma wynosi zero arytmetycznie jak 0^s.

xnor
źródło
To niesamowite, jak trafiasz dokładnie taką samą liczbę bajtów, jak @nimi, stosując inne podejście.
Kritzefitz
9

JavaScript (ES6), 51 48 bajtów

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

Akceptuje monety w dowolnej kolejności. Próbuje zarówno użyć, jak i nie użyć pierwszej monety, rekurencyjnie obliczając liczbę kombinacji w obu kierunkach. n==0oznacza pasującą kombinację, n<0oznacza, że ​​monety przekraczają ilość, podczas gdy c==undefinedoznacza, że ​​nie ma już monet. Pamiętaj, że funkcja jest bardzo wolna i jeśli masz monetę, to następująca funkcja jest szybsza (nie przekazuj monety monety w szeregu monet):

f=(n,a,[c,...b]=a)=>c?(c<=n&&f(n-c,a))+f(n,b):1
Neil
źródło
...cholera. Naprawdę fajny pomysł.
ETHprodukcje
i jaki byłby wynik 1209 [1,5,10,33,48] i 6000 [1,5,10,33], więc mogę skalibrować mój kod
RosLuP
@RosLuP Podany kod ostatecznie zwraca 1314050 dla pierwszego przykładu. Mój tłumacz nie jest w stanie obsłużyć rekurencji niezbędnej do oceny drugiego przykładu.
Neil,
@RosLuP Zmodyfikowałem funkcję, aby założyć, że istnieje dodatkowa moneta groszowa, i zwróciła 22086484 za 6000 [5,10,33].
Neil,
@Neil ok 22086484 za 6000 [1,5,10,33] ... Zamiast tego będzie 11239 tutaj za 6000 [5,10,33] (tablica, którą napisałeś)
RosLuP
7

Perl, 45 bajtów

Liczba bajtów obejmuje 44 bajty kodu i -pflagi.

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

Pobiera wartości monet w pierwszym wierszu i docelową kwotę w drugim wierszu:

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

Krótkie wyjaśnienia:

-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
źródło
6

Galaretka , 10 9 bajtów

œċЀS€€Fċ

Wypróbuj online!

W jaki sposób?

œċЀ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
źródło
2
+1 za użycie tylu symboli euro w pytaniu dotyczącym pieniędzy.
steenbergh
6

JavaScript (ES6), 59 bajtów

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

Monety są wprowadzane od najwyższej do najniższej, np f(26,[100,25,10,5,1]) . Jeśli masz grosz, usuń go i użyj zamiast tego tej o wiele szybszej wersji:

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

Wykorzystuje rekurencyjną formułę podobną do @ nimi. Pierwotnie napisałem to kilka dni temu, gdy wyzwanie wciąż znajdowało się w piaskownicy; wyglądało to tak:

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

Jedyne różnice stanowiącego wartość domyślną c(miał Ustaw wartość w oryginalnej wyzwanie) i zmiana 0w .reducefunkcji do1 (było to dwa bajty a czasy krótsze i szybsze niż bilionów c=[100,25,10,5,1]).


Oto zmodyfikowana wersja, która wyświetla wszystkie kombinacje, a nie liczbę kombinacji:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:[...x,...f(n-y,c.slice(i)).map(c=>[...c,y])],[]):[[]]
ETHprodukcje
źródło
i jaki byłby wynik 1209 [1,5,10,33,48] i 6000 [1,5,10,33], więc mogę skalibrować mój kod
RosLuP
@RosLuP Dostaję odpowiednio 1314050 (po 5 minutach) i przepełnienie stosu (po godzinie). Dzięki szybszej wersji, którą właśnie dodałem, dostaję 1314050 i 22086484 w ciągu kilku sekund.
ETHproductions
Z moim starym komputerem Pentium 2.8Gh 6 sekund dla pierwszego wyniku, dla drugich 5 minut + lub -
RosLuP
5

PHP, 327 bajtów

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

Spróbuj

Jörg Hülsermann
źródło
5

Aksjomat, 63 62 bajty

1 bajt zapisany przez @JonathanAllan

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

To podejście wykorzystuje funkcje generowania. Prawdopodobnie nie pomogło to zmniejszyć rozmiaru kodu. Myślę, że po raz pierwszy w mojej grze z Axiomem posunąłem się do zdefiniowania własnej funkcji.

Przy pierwszym wywołaniu tej funkcji daje przerażające ostrzeżenie, ale nadal daje poprawny wynik. Potem wszystko jest w porządku, dopóki lista nie jest pusta.

Christian Sievers
źródło
1
Nie wiem Axiom - czy można wcześniej usunąć przestrzeń for?
Jonathan Allan,
1
@JonathanAllan Tak, jest! Dobry instynkt golfowy, dzięki!
Christian Sievers,
5

R, 81 76 63 bajtów

Dzięki @rturnbull za grę w golfa z dala 13 bajtów!

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

Przykład (zwróć uwagę, że w c(...)ten sposób przekazujesz wektory wartości do R):

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

Wyjaśnienie:

ujest pożądaną wartością, vjest wektorem wartości monet.

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

tworzy ramkę danych z każdą możliwą kombinacją monet od 0 do k (k zależy od nominału), gdzie k jest najniższą wartością, tak że k razy wartość tej monety wynosi co najmniej u (wartość do osiągnięcia).

Zwykle używalibyśmy as.matrixdo przekształcenia tego w macierz, ale to jest wiele znaków. Zamiast tego bierzemy transpozycję transpozycji (!), Która automatycznie ją wymusza, ale zajmuje mniej znaków.

%*% vnastępnie oblicza wartość pieniężną każdego wiersza. Ostatnim krokiem jest policzenie, ile z tych wartości jest równych pożądanej wartościu .

Zauważ, że złożoność obliczeniowa i wymagania dotyczące pamięci są przerażające, ale hej, to jest golf golfowy.

JDL
źródło
1
Niezłe wykorzystanie expand.grid! I uwielbiam t(t())sztuczkę. Ponieważ twoja funkcja obejmuje tylko jeden wiersz kodu, możesz usunąć nawiasy klamrowe, oszczędzając ci 2 bajty. Możesz także przełączyć się do.call(expand.grid,lapply(u/v,seq,from=0))na tylko expand.grid(lapply(u/v,seq,f=0)), oszczędzając 11 bajtów.
rturnbull
Dzięki za te! Nigdy nie zdawałem sobie sprawy, expand.gridże wezmę listę jako wkład. Szkoda, że ":"nie działa dobrze z liczbami całkowitymi, w przeciwnym lapply(u/v,":",0)razie zaoszczędziłoby jeszcze kilka.
JDL,
do.call(x,y)jest taki sam jak x(y), więc nie chodzi o to, jakie rodzaje danych wejściowych są akceptowane. Jeśli naprawdę chcesz użyć :, przypuszczam, że możesz użyć lapply(u%/%v,`:`,0), ale to ta sama liczba bajtów.
rturnbull
1
do.call(x,y)to to samo co x(y)” --- tylko wtedy, gdy ynie jest listą, tak jak w tym przypadku. Ale zgódź się na swój drugi punkt.
JDL,
3

J, 27 bajtów

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

Stosowanie

   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

Wyjaśnienie

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
mile
źródło
J jest niesamowity, a jednocześnie tak szalony
CommaToast
2

TSQL, 105 bajtów

Te 4 typy monet pozwalają obsłużyć tylko jednego dolara. Wersja bez golfa może obsłużyć do około 4 dolarów, ale bardzo wolno - na moim pudełku zajmuje to 27 sekund. Wynik to 10045 kombinacji btw

Gra w golfa:

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=@

Nie golfowany:

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

Skrzypce

t-clausen.dk
źródło
2

repl tinylisp , 66 bajtów

(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

Rozwiązanie rekurencyjne: próbuje użyć pierwszej monety, a nie pierwszej monety, a następnie dodaje wyniki z każdej z nich. Wykładnicza złożoność czasu i brak rekurencji ogona, ale dobrze oblicza przypadki testowe.

Niegolfowany (klucz do wbudowanych: d= zdefiniuj, q= cytat, i= jeśli, l= mniej niż, s= odejmij,h = głowa, t= ogon):

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

Przykładowe użycie:

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
źródło
1

PHP, 130 bajtów

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-bajtowa funkcja rekurencyjna (i 31 bajtów wywołania), która wielokrotnie usuwa wartość bieżącej monety z celu i nazywa się nową wartością i innymi monetami. Zlicza ile razy cel osiąga dokładnie 0. Działaj jak:

 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
użytkownik59178
źródło
Jeśli zostanie wezwany z ponad 97 różnymi rodzajami monet, umrze śmiercią rekurencyjną bez zwracania czegokolwiek, ale ponieważ jest to znacznie więcej różnych rodzajów monet, musimy wesprzeć.
user59178,
1

Rakieta 275 bajtów

(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

Nie golfowany:

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

Testowanie:

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

Wydajność:

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

Następujące rozwiązanie rekurencyjne zawiera błąd:

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

Nie działa poprawnie dla:

(f 8 '[1 2 3])

Wydajność:

'((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) jest możliwe, ale nie ma go na liście rozwiązań.

rnso
źródło
Nie znam Rakiety, ale napisałem rozwiązanie w Clojure na podobny problem do tego kilka lat temu, który wykorzystałreduce
mile
„zmniejsz” nie jest częścią podstawowego języka rakiety, chociaż „fold” jest dostępny. Dodałem zmodyfikowane rozwiązanie powyżej, ponieważ wcześniejsze rozwiązanie ma pewien błąd.
rnso
Wygląda na to, że grupa entuzjastów Lisp zebrała się ... i zrobiła rakietę
Joe
1
Niektórzy entuzjaści Lisp po raz pierwszy stworzyli Scheme( groups.csail.mit.edu/mac/projects/scheme ), co ostatecznie doprowadziło do pełnego rozkwituRacket ( racket-lang.org , stackoverflow.com/questions/3345397/… )!
rnso
1

Galaretka , 15 bajtów

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

Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe.

Było to bardziej ćwiczenie polegające na napisaniu wydajnej wersji w Jelly bez użycia wbudowanych. Jest to oparte na typowym podejściu do programowania dynamicznego stosowanym do obliczania liczby sposobów wprowadzania zmian

Wyjaśnienie

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
mile
źródło
1

Właściwie 15 bajtów

Sugestie dotyczące gry w golfa mile widziane. Wypróbuj 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
źródło
0

Python, 120 bajtów

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)

Bruteforuje przez wszystkie kombinacje monet aż do wartości docelowej (nawet jeśli najmniejsza to nie 1).

Karl Napf
źródło