... 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:
- 12 groszy
- 1 nikiel i 7 groszy
- 2 monety i 2 grosze
- 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:
- 26 groszy
- 21 groszy i 1 nikiel
- 16 groszy i 2 monety
- 11 groszy i 3 monety
- 6 groszy i 4 monety
- 1 grosz i 5 monet
- 16 groszy i 1 grosz
- 6 groszy i 2 dziesięciocentówki
- 11 groszy, 1 bilon i 1 nikiel
- 6 groszy, 1 bilon i 2 monety
- 1 grosz, 1 bilon i 3 monety
- 1 grosz, 2 dziesięciocentówki i 1 nikiel
- 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 moneta 12 centów i 1 moneta 7 centów
- 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.
źródło
s/count/earn
.Odpowiedzi:
Galaretka ( widelec ), 2 bajty
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
Wyjaśnienie
źródło
Haskell,
3734 bajtówPrzykł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ź
1
inną (lub jeśli na liście brakuje elementów) weź0
. Zsumuj te1
i te0
.Edycja: @Damien: zapisano 3 bajty, wskazując krótszy przypadek podstawowy dla rekurencji (który również można znaleźć w odpowiedzi @xnors ).
źródło
1209 # [1,5,10,33,48]
->1314050
.6000 # [1,5,10,33]
->22086484
.Mathematica,
3522 bajtówDziękujemy za mile za sugestie
FrobeniusSolve
i oszczędność 13 bajtów.Zwraca wartość do nienazwanej funkcji, która przyjmuje listę monet jako pierwszy argument, a wartość docelową jako drugi.
FrobeniusSolve
jest skrótem do rozwiązywania równań diofantycznych formydla ponad nieujemnych liczb całkowitych i daje nam wszystkie rozwiązania.
xi
źródło
(Length@*FrobeniusSolve)[{1, 7, 9}, 18]
Pyth, 8 bajtów
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]
.źródło
Haskell, 37 bajtów
Użycie kilku wielokrotności pierwszej monety
h
zmniejsza wymaganą sumęs
do 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 jak0^s
.źródło
JavaScript (ES6),
5148 bajtówAkceptuje 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==0
oznacza pasującą kombinację,n<0
oznacza, że monety przekraczają ilość, podczas gdyc==undefined
oznacza, ż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):źródło
Perl, 45 bajtów
Liczba bajtów obejmuje 44 bajty kodu i
-p
flagi.Pobiera wartości monet w pierwszym wierszu i docelową kwotę w drugim wierszu:
Krótkie wyjaśnienia:
źródło
Galaretka ,
109 bajtówWypróbuj online!
W jaki sposób?
źródło
JavaScript (ES6), 59 bajtów
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: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:
Jedyne różnice stanowiącego wartość domyślną
c
(miał Ustaw wartość w oryginalnej wyzwanie) i zmiana0
w.reduce
funkcji do1
(było to dwa bajty a czasy krótsze i szybsze niż bilionówc=[100,25,10,5,1]
).Oto zmodyfikowana wersja, która wyświetla wszystkie kombinacje, a nie liczbę kombinacji:
źródło
PHP, 327 bajtów
Spróbuj
źródło
Aksjomat,
6362 bajty1 bajt zapisany przez @JonathanAllan
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.
źródło
for
?R,
817663 bajtówDzięki @rturnbull za grę w golfa z dala 13 bajtów!
Przykład (zwróć uwagę, że w
c(...)
ten sposób przekazujesz wektory wartości do R):Wyjaśnienie:
u
jest pożądaną wartością,v
jest wektorem wartości monet.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.matrix
do 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.%*% v
nastę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.
źródło
expand.grid
! I uwielbiamt(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 tylkoexpand.grid(lapply(u/v,seq,f=0))
, oszczędzając 11 bajtów.expand.grid
że wezmę listę jako wkład. Szkoda, że":"
nie działa dobrze z liczbami całkowitymi, w przeciwnymlapply(u/v,":",0)
razie zaoszczędziłoby jeszcze kilka.do.call(x,y)
jest taki sam jakx(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.do.call(x,y)
to to samo cox(y)
” --- tylko wtedy, gdyy
nie jest listą, tak jak w tym przypadku. Ale zgódź się na swój drugi punkt.J, 27 bajtów
Stosowanie
Wyjaśnienie
źródło
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:
Nie golfowany:
Skrzypce
źródło
repl tinylisp , 66 bajtów
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):Przykładowe użycie:
źródło
PHP, 130 bajtów
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:
źródło
Rakieta 275 bajtów
Nie golfowany:
Testowanie:
Wydajność:
Następujące rozwiązanie rekurencyjne zawiera błąd:
Nie działa poprawnie dla:
Wydajność:
(1 1 3 3) jest możliwe, ale nie ma go na liście rozwiązań.
źródło
reduce
Scheme
( groups.csail.mit.edu/mac/projects/scheme ), co ostatecznie doprowadziło do pełnego rozkwituRacket
( racket-lang.org , stackoverflow.com/questions/3345397/… )!Galaretka , 15 bajtów
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
źródło
Właściwie 15 bajtów
Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!
Ungolfing
źródło
Python, 120 bajtów
Bruteforuje przez wszystkie kombinacje monet aż do wartości docelowej (nawet jeśli najmniejsza to nie 1).
źródło