13
\$\begingroup\$

Inspired by this glove-themed 538 Riddler Express Puzzle.

Task

You are given a positive integer n, and a list A = [a_1, a_2, ..., a_k] of k distinct positive integers.

Then a restricted composition is an ordered list P = [p_1, p_2, ..., p_m] where each p_i is a (not necessarily distinct) member of A, and p_1 + p_2 + ... + p_m = n.

So, if n = 10, and A = [2,3,4] then an example of a restricted composition would be P = [3,4,3]. Another example would be P = [2,3,3,2]. A third example would be P = [3,3,4]. But there's no restricted composition that starts [3,3,3,...], because 10-(3+3+3) = 1, which is not in A.

We want the total number of different restricted compositions given the inputs, as an integer.

Inputs

A positive integer n and a list A of distinct positive integers. All reasonable input formats allowed.

Output

The number of distinct restricted compositions.

Terms and Conditions

This is ; and thus we seek the shortest submissions in bytes satisfying the constraints. Any use of the usual loopholes voids this contract.

Test Cases

(5, [2, 3, 4]) => 2 (10, [2, 3, 4]) => 17 (15, [3, 5, 7]) => 8
Improve this question
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Ah, a variant on the knapsack problem. Related XKCD \$\endgroup\$ Commented Apr 12, 2020 at 6:17

22 Answers 22

Reset to default
7
\$\begingroup\$

Python 2, 50 49 bytes

-1 byte thanks to @Jonathan Allan

f=lambda n,A:n>=0and(n<1)+sum(f(n-x,A)for x in A)

Try it online!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ A little bit of a switcharoo can save a byte \$\endgroup\$ Commented Apr 12, 2020 at 17:57
5
\$\begingroup\$

JavaScript (ES6),  48  40 bytes

Takes input as (a)(n).

a=>g=n=>n>0?a.map(x=>t+=g(n-x),t=0)|t:!n

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

J, 24 17 bytes

1#.[=1#.[:>@,{\@#

Try it online!

Recursive version was too verbose in J, so I went brute force.

Take the integers in the right arg as a boxed list and the target number n in the left arg.

  • {\@# - We create a series of cartesian products of the list with itself, starting with 1 (the list unchanged) and up to n (the list crossed with itself n times).
  • [:>@, We flatten all of those, open them, and sum them.
  • [= Check which sums equal n. This returns a boolean list.
  • 1#. Sum it.
Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

APL (Dyalog), 18 bytes

Accepts n as the right argument and A as the left argument.

{⍵>0:+/⍺∘∇¨⍵-⍺⋄⍵=0}

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly,  6  5 bytes

ṗⱮẎ§ċ

Try it online! (Very inefficient.)

How?

Builds all lists of lengths \$1\$ to \$n\$ made from the integers in \$A\$ and then counts how many sum to \$n\$.

ṗⱮẎ§ċ - Link: list of positive integers, A; positive integer, n Ɱ - map across x in (implicit range [1..n]) applying: ṗ - Cartesian power -> all length x lists made from values in A Ẏ - tighten (to a list of lists) § - sum each list ċ - count occurrences of (n)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 23 bytes

{$[x>0;+/(x-y)o\:y;~x]}

Try it online!

recursive

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Io, 57 bytes

Port of the Python answer.

f :=method(n,A,if(n>0,A map(x,f(n-x,A))sum,if(n==0,1,0)))

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Husk, 10 8 bytes

#o=¹ΣuṖ*

Try it online!

This is so ridiculously inefficient that it struggles on TIO to even run any of the given test cases: link is to a super-easy test case of n=2, a=[1,2,3] (for which output is 4).

Repeats and concatenates (*) the input list n times, and then generates all possible subsets (uṖ - this is the slow step!). Then counts the number (#) of subsets for which the total equals n (o=¹Σ).

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 56 49 46 43 41 bytes

2 bytes golfed thanks to J42161217

n_~f~a_=If[n<1,1+Sign@n,Tr[f[n-#,a]&/@a]]

Try it online!

Initial solution:

Length[Join@@Permutations/@IntegerPartitions[#,∞,#2]]&

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ nice port! 41 bytes \$\endgroup\$ Commented Apr 11, 2020 at 21:46
  • \$\begingroup\$ @J42161217 Thanks! That's a clever use of infix notation btw, I wouldn't have thought of using it for function definition \$\endgroup\$ Commented Apr 11, 2020 at 22:01
  • \$\begingroup\$ 39 bytes \$\endgroup\$ Commented Nov 20, 2020 at 1:23
1
\$\begingroup\$

C (gcc), 89 bytes

Port of the Python answer.

Edit: Outgolfed by Noodle9 :/

int n;f(int x,int*a){if(x<=0)return!x;int y=0,i=0;while(i++<n)y+=f(x-a[i-1],a);return y;}

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 72 bytes \$\endgroup\$ Commented Apr 12, 2020 at 23:47
1
\$\begingroup\$

C (gcc), 65 63 bytes

Saved 2 bytes thanks to my pronoun is monicareinstate!!! 

f(n,a,l,s,i)int*a;{for(s=i=!n;i<l&n>0;)s+=f(n-a[i++],a,l);n=s;}

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ You can remove i++ by moving the ++ to f(n-a[i],...). I do not know the algorithm nor the problem itself, but if I replace s=!n,i=0 with i=s=!n, I get the same answers for the test cases. \$\endgroup\$ Commented Apr 12, 2020 at 7:02
  • \$\begingroup\$ @mypronounismonicareinstate Just moved the ++ but thanks for the i init! If !n isn't 0 the for loop isn't going to run and i isn't used. Nice one :-) \$\endgroup\$ Commented Apr 12, 2020 at 7:07
1
\$\begingroup\$

Ruby, 40 36 bytes

Python answer port but Ruby strict typing means I can't coerce booleans into integers.

-4 bytes from dingledooper.

f=->n,a{n>0?a.sum{|e|f[n-e,a]}:1<<n}

Try it online!

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think you can get around the 'boolean issue' by using 1<<n instead of n==0?1:0. \$\endgroup\$ Commented Apr 12, 2020 at 7:13
1
\$\begingroup\$

Perl, 52 bytes

$r.=1x$_."|"}{(1x$^I)=~/^($r@){1,$^I}$(?{$\++})(*F)/

Usage

printf "2\n3\n4" | perl -p -i10 glovebox.pl

Explanation

Attempts to turn the problem into a string matching one, then uses regex backtracking to do the hard work! In the example given above it ends up constructing a regex match similar to 1111111111 =~ /^(1{2}|1{3}|1{4}){1,10}$(?{$count++})(*F)/

This will cause the regex engine to attempt each combination of the regex, using (?{$count++}) to increase $count each time the engine matches the input and reaches that point in the pattern, but forcing a fail (*F) before the match returns to cause the engine to backtrack and start again with the next combination. $count ends up being the answer.

Slightly different approach, was hoping it'd end up a bit shorter though...

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 37 bytes

n!a|n<0=0|n<1=1|n>0=sum$(!a).(n-)<$>a

Try it online!

Quick port of the Python answer, call as n ! a.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 21 20 bytes

⊞υ¹Ｆθ⊞υ↨Φυ№η⁻⊕ιλ¹Ｉ⊟υ

Try it online! Link is to verbose version of code. Edit: Saved 1 byte by using base conversion from 1 instead of summing a potentially empty list. Explanation:

⊞υ¹

Start our result list with the number of solutions for n=0 which is always 1 (the empty list).

Ｆθ⊞υ

Loop n times, so that we calculate the results for 1..n, appending them to the result list.

↨Φυ№η⁻⊕ιλ¹

Sum those results so far that contribute to the next total. For example, if A is [2, 3, 4], then to calculate the result for n=10, we already know the results for n=0..9, but we only add the results for n=6, n=7 and n=8. The sum is calculated by converting from base 1 in case the list is empty.

Ｉ⊟υ

Print the result for n.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 11 7 bytes

L€ãO˜¹¢

-4 bytes thanks to @ovs.

Very slow approach!

Try it online or verify the first two test cases at once (third one times out..).

Explanation:

L # Push a list in the range [1, first (implicit) input-integer] € # Map over each integer in this list ã # Take the cartesian product of the second (implicit) input-list that many times O # Sum each inner-most list ˜ # Flatten the list of lists ¹¢ # And count how many times the first input occurs in this list # (after which the result is output implicitly)

05AB1E, 12 bytes

ÅœʒåP}€œ€`Ùg

Here a faster (but now way longer) approach using the Ŝ builtin.

Try it online or verify all test cases.

Explanation:

Åœ # Get all lists of positive integer that sum to the (implicit) input-integer ʒ # Filter this list of lists by: å # Check for each value whether it's in the second (implicit) input-list P # And check if this is truthy for all of them }€œ # After the filter: get the permutations of each remaining list €` # Flatten one level down Ù # Uniquify the list of lists g # Pop and push the length for the amount of remaining lists # (after which the result is output implicitly)
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 7 bytes with your first approach: L€ãO˜¹¢ \$\endgroup\$ Commented Nov 19, 2020 at 12:59
  • \$\begingroup\$ @ovs Oh, that's indeed a lot better. Thanks! \$\endgroup\$ Commented Nov 19, 2020 at 13:21
1
\$\begingroup\$

Julia 1.0, 35 bytes

port of this Python answer

f(n,A)=n>=0&&+(n<1,f.(n.-A,[A])...)

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

R, 59 55 bytes

Edit: -4 bytes thanks to Giuseppe

g=function(t,l,u=t-l)sum(!u,unlist(sapply(u[u>0],g,l)))

Try it online!

Recursively removes each element from the glove box, and calls itself with the new total if there's anything left.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 55 bytes? \$\endgroup\$ Commented Nov 19, 2020 at 19:00
  • \$\begingroup\$ @Giuseppe - Yes! Thanks! \$\endgroup\$ Commented Nov 19, 2020 at 20:00
0
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

Tr[Length/@Permutations/@IntegerPartitions[#,All,#2]]&

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Red, 81 80 bytes

f: func[x y][case[x = 0[1]x < 0[0]on[sum collect[foreach a y[keep f x - a y]]]]]

Try it online!

The same recursive approach almost everyone is using, much longer though.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Racket, 74 64 bytes

(λ(x y)(if(< x 1)(+(sgn x)1)(apply +(map(λ(a)(f(- x a)y))y))))

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

Tr[Multinomial@@@FrobeniusSolve@##]&

Try it online!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.