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
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Ah, a variant on the knapsack problem. Related XKCD \$\endgroup\$
    – Value Ink
    Apr 12 '20 at 6:17

22 Answers 22

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!

\$\endgroup\$
1
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!

\$\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.
\$\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!

\$\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)
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 23 bytes

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

Try it online!

recursive

\$\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!

\$\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=¹Σ).

\$\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!

\$\endgroup\$
3
  • \$\begingroup\$ nice port! 41 bytes \$\endgroup\$
    – ZaMoC
    Apr 11 '20 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\$
    – DanTheMan
    Apr 11 '20 at 22:01
  • \$\begingroup\$ 39 bytes \$\endgroup\$
    – att
    Nov 20 '20 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!

\$\endgroup\$
1
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!

\$\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\$ Apr 12 '20 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\$
    – Noodle9
    Apr 12 '20 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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think you can get around the 'boolean issue' by using 1<<n instead of n==0?1:0. \$\endgroup\$ Apr 12 '20 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...

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

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 21 20 bytes

⊞υ¹Fθ⊞υ↨Φυ№η⁻⊕ιλ¹I⊟υ

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

Fθ⊞υ

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.

I⊟υ

Print the result for n.

\$\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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 7 bytes with your first approach: L€ãO˜¹¢ \$\endgroup\$
    – ovs
    Nov 19 '20 at 12:59
  • \$\begingroup\$ @ovs Oh, that's indeed a lot better. Thanks! \$\endgroup\$ Nov 19 '20 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!

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

\$\endgroup\$
2
  • \$\begingroup\$ 55 bytes? \$\endgroup\$
    – Giuseppe
    Nov 19 '20 at 19:00
  • \$\begingroup\$ @Giuseppe - Yes! Thanks! \$\endgroup\$ Nov 19 '20 at 20:00
0
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

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

Try it online!

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

\$\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!

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.