| Bytes | Lang | Time | Link |
|---|---|---|---|
| 112 | Python 3.8 prerelease | 250904T195201Z | V_R |
| 083 | JavaScript ES6 | 250819T094002Z | Arnauld |
| 010 | 05AB1E | 250819T082203Z | Kevin Cr |
| 013 | Jelly | 250820T114129Z | Jonathan |
| 083 | Wolfram Language Mathematica | 250820T024216Z | Greg Mar |
| 256 | Python3 | 250819T152255Z | Ajax1234 |
| 045 | Charcoal | 250819T091020Z | Neil |
| 011 | Nekomata | 250819T033049Z | alephalp |
| 013 | Vyxal | 250819T004348Z | lyxal |
Python 3.8 (pre-release), 112 bytes
Like many others I've written horribly slow code, but I've put some test cases on TIO that run in a few seconds. With this approach, it's actually shorter to return all the possible solutions rather than just one of them.
from itertools import*
def f(l,b):g=lambda r:map(sum,product(l,repeat=r));return[a for a in g(b)if b*100in g(a)]
Explanation
Uses the Cartesian product function from itertools. First loop through every possible sum a of b-many values from l. Then save every a for which b*100 is a possible sum of a-many values from l.
I had to use a function f(l,b) rather than a lambda expression with a big list comprehension: lambda l,b:[...] because Python doesn't let you define the helper function g using the walrus operator inside of a list comprehension (even though you can use it in a regular for loop).
JavaScript (ES6), 83 bytes
Expects (L)(B) and returns the first solution found.
L=>B=>(g=(v,n,[q,...b]=L)=>q*v>0?g(v,n,b)||g(v-q,-~n):v?n*g(!~~v*n):n==B)(100*B+.5)
Commented
The recursive function \$g\$ is called a first time to find a list of \$n\$ coins that sum to \$100B\$ (with no constraint on \$n\$) and a second time to find a list of \$B\$ coins that sum to \$n\$. We add \$0.5\$ to the target sum in the first pass to distinguish it from the second.
L => // outer function taking the list L[]
B => ( // inner function taking B
g = ( // g = recursive function taking:
v, // v = target value
n, // n = counter
[ q, // q = next value from L[]
...b ] = L // b[] = remaining values in L[]
) => //
q * v > 0 ? // if q is defined and v is positive:
g(v, n, b) || // 1st recursive call with q ignored,
// using b[] for the next values
g(v - q, -~n) // 2nd recursive call with q subtracted
// from v and n incremented, restarting
// from L[]
: // else (end of pass):
v ? // if v is not 0:
n * // multiply by n the result of ...
g(!~~v * n) // ... a recursive call with either
// n if v is 0.5 (successful 1st pass)
// or 0 otherwise (which will return 0)
: // else (target reached on 2nd pass):
n == B // test whether n is equal to B
)(100 * B + .5) // initial call with 100*B+0.5 as the target
05AB1E, 10 bytes
ãOʒãOт/¹Qà
Inputs in the order \$B,list\$. Output isn't sorted and contains possibly duplicated values.
(Don't) try it online. (Will time out for every test case..)
Replacing the à with .Δ, allows it to at least output for the example test case to verify it works: Try it online. (All other test cases will still time out..)
Explanation:
ã # Cartesian product, to get all (implicit) first input B-sized lists
# using values of the (implicit) second input-list
O # Sum each inner B-sized list
ʒ # Filter this list of A's by:
ã # Cartesian product again, to get all A-sized lists using values
# of the (implicit) second input-list
O # Sum each inner A-sized list again
т/ # Divide each by 100
¹Q # Check if it equals the first input-integer
à # Check if any is truthy within this list for size A
# (after which the filtered list is output implicitly as result)
Jelly, 13 bytes
ṗ§Q³ṗ§÷ȷ2iʋɗƇ
A full program that accepts the list of denominations and the initial coin count \$B\$ and prints a list of all valid coin counts \$A\$ (to only print one, add Ḣ for 1 byte).
Don't try it online!, but this is a touch faster (using combinations-with replacement in place of Cartesian powers).
How?
ṗ§Q³ṗ§÷ȷ2iʋɗƇ - Main Link: L, B
ṗ - {L} Cartesian power {B} -> all B-coin collections
§ - sums
Q - deduplicate -> possible B-coin sums
Ƈ - keep those for which:
ɗ - last three links as a dyad - f(CoinSum, B):
³ - program's first argument -> L
ṗ - Cartesian power {CoinSum} -> all CoinSum-coin collections
ʋ - last four links as a dyad - f(CoinSum-coinCollections, B):
§ - sums -> possible CoinSum-coin sums
÷ - divide all of {those} by...
ȷ2 - ...10^2 = 100
i - first 1-index of {B} in that or 0
- implicit print
Wolfram Language (Mathematica), 83 bytes
e=Exponent[#,x,List]&;L_~f~B_:=SelectFirst[e@(p=Tr[x^L]^#&)@B,MemberQ[e@p@#,100B]&]
Try all test cases online! Defines a named function f that takes the list L as the first argument and the number B as the second argument.
I was motivated by trying to find code that finished quickly, and the approach uses generating functions. Using the third test case as an example: the exponents of the polynomial \$(x^2+x^5+x^{10})^3 = x^6 + 3 x^9 + 3 x^{12} + 3 x^{14} + x^{15} + 6 x^{17} + 3 x^{20} + 3 x^{22} + 3 x^{25} + x^{30}\$, namely 6,9,12,14,15,17,20,22,25,30, are the values that can be made with 3 coins from the list {2,5,10}. (The coefficients record how many ways this can be done, but we're ignoring that here.) We then want to look at the polynomials \$(x^2+x^5+x^{10})^6\$, \$(x^2+x^5+x^{10})^9\$, \$(x^2+x^5+x^{10})^{12}\$, … in turn to see if the exponent 300 ever appears.
In the code, e is a helper function that produces the list of exponents of a polynomial in x, while p is a helper function that computes polynomials of the form \$(x^2+x^5+x^{10})^3\$ where the exponents of x are from L and the power at the end is the argument of p. Then e@p@B is the list of possible candidates for \$A\$, which we need to examine by seeing whether 100B is one of the exponents of e@p@# where # is the candidate. SelectFirst finds and returns the first successful candidate, both abiding by the spec and also making the code terminate much faster.
Python3, 256 bytes
def C(l,b,a):
q=[(l,[])]
for l,L in q:
if len(L)==b:
if a==-1 or sum(L)==a:yield L
continue
if l:q+=[(l[1:],K)for i in range(b-len(L)+1)if sum(K:=L+[l[0]]*i)<=a or a==-1]
def f(l,b):
for L in C(l,b,-1):
for _ in C(l,O:=sum(L),100*b):return O
Charcoal, 45 bytes
FEXLθηΣEη§θ÷ιXLθλ¿¬ⅈ¿№EXLθιΣEι§θ÷κXLθμ×¹⁰⁰ηIι
Try it online! Link is to verbose version of code. Stupidly slow, so only finishes for the last two test cases on TIO. Explanation:
FEXLθηΣEη§θ÷ιXLθλ
Get all sums of lists of B elements of L.
¿¬ⅈ
Stop once an answer is found.
¿№EXLθιΣEι§θ÷κXLθμ×¹⁰⁰η
Get all sums of lists of A elements of L, and see if any of them contain 100B.
Iι
If so then output A.
49 bytes for a much faster version which can solve all of the test cases on ATO:
⊞υE⊕×¹⁰⁰η¬ιF⌊υ«≔⌊υζ⊞υEζ⊙θ∧÷λμ§ζ⁻λμ»I⌕A×Eυ§ι±¹§υη¹
Attempt This Online! Link is to verbose version of code. Explanation: Uses @alephalpha's polynomial trick to calculate which potential sums are possible and intersects the sums for B elements with the sums for A elements that sum to 100B.
⊞υE⊕×¹⁰⁰η¬ι
Start with the sums for 0 elements. We're only interested in sums that go up to 100B.
F⌊υ«≔⌊υζ⊞υEζ⊙θ∧÷λμ§ζ⁻λμ»
Calculate 100B more sets of sums, using saturation so that the values are either 0 or 1. (Interpolating Minimum(u) would reduce the byte count by a further 4 but makes the code too slow for the last test case to finish on ATO.)
I⌕A×Eυ§ι±¹§υη¹
Output those sums of B that can have sums of 100B. These are the 1 entries in the vectorised product of the Bth row and 100Bth column.
Nekomata, 11 bytes
$ŧ∑ᵖ{ŧ∑'d/=
Extremely slow. Time out for almost every test case.
$ŧ∑ᵖ{ŧ∑'d/= Input: L, B
$ŧ Find a B-tuple of elements of L
∑ Sum
ᵖ{ Check that the sum A satisfies:
ŧ Find an A-tuple of elements of L
∑ Sum
'd/ Divide by 100
= Check that it is equal to B
By default, Nekomata will find all possible solutions, possibly with duplicates. You can use the -1 flag to find only the first solution. Even with this flag, it still times out for all test cases except the last two.
Nekomata, 16 bytes
ŧ∑ũ§Ħvřʳ×§'d*@Z¿
Longer but faster. At least it can find some (not all) solutions in a reasonable time for all test cases.
If you have a list of positive integers \$L = [a_1, a_2, \ldots, a_n]\$, and you want to check if there is a \$k\$-tuple of elements of \$L\$ that sums to \$m\$, a fast way to do this is to take the \$k\$-th power of the polynomial \$x^{a_1} + x^{a_2} + \cdots + x^{a_n}\$, and check if the coefficient of \$x^m\$ is nonzero.
ŧ∑ũ§Ħvřʳ×§'d*@Z¿ Input: B, L
ŧ Find a B-tuple of elements of L
∑ Sum
ũ Uniquify the possible results
(This is not necessary, but it speeds up the search)
Let's say the sum is A
§Ħ Make a histogram of the elements of L
e.g., [2,5,10] -> [0,0,1,0,0,1,0,0,0,0,1]
vř Replicate the histogram A times
ʳ× Fold by convolution
§'d* Multiply B by 100
@ Take the n-th element of the result of the convolution
Z Check that it is nonzero
¿ If so, return A
The last two test cases will time out if you are trying to find all solutions. You can add the flag -l 10 to find at most 10 solutions.
Vyxal, 13 bytes
↔Ṡ'¹↔Ṡ⁰₁*=a;h
Will time out online for every test case, so you'll have to read the explanation to verify correctness. Takes L then B.
Explained
↔Ṡ'¹↔Ṡ⁰₁*=a;h
↔ # Generate all B-sized combinations of L with replacement
Ṡ # Summate each combination - this gives candidates for values of A
' ; # Keep A's where the result of the following is truthy:
¹↔ # Generate all A-sized combinations of L with replacement (this is why it'll time out for everything)
Ṡ # Summate each of those combinations
⁰₁*= # Check whether each sum equals 100 * B
a # And return whether any do
h # Output the first valid A
💎
Created with the help of Luminespire.