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

18 Answers 18

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

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\$
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\$
  • \$\begingroup\$ nice port! 41 bytes \$\endgroup\$ – J42161217 Apr 11 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 at 22:01
1
\$\begingroup\$

Charcoal, 21 bytes

⊞υ¹Fθ⊞υΣEυ∧№η⁻⊕ιλκI⊟υ

Try it online! Link is to verbose version of code. 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.

ΣEυ∧№η⁻⊕ιλκ

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 zeroing out the unwanted results to avoid edge cases in Charcoal.

I⊟υ

Print the result for n.

| improve this answer | |
\$\endgroup\$
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\$
  • \$\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\$ – my pronoun is monicareinstate Apr 12 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 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\$
  • 2
    \$\begingroup\$ I think you can get around the 'boolean issue' by using 1<<n instead of n==0?1:0. \$\endgroup\$ – dingledooper Apr 12 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\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\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\$
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\$

05AB1E, 11 bytes

¯sƒINã«}O¹¢

Very slow approach!

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

Explanation:

¯        # Push an empty list []
 sƒ      # Loop `N` in the range [1, first input-integer]:
   I     #  Push the second input-list
    Nã   #  Take the cartesian product of this list `N` times
      «  #  Merge it to the earlier list
  }O     # After the loop: sum all inner 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

A faster approach using the Ŝ builtin, but unfortunately 1 byte longer.

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

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.