Generator functions

This gives the context for why this challenge came to life. Feel free to ignore.

Generator functions are a nice way of encoding the solution to a problem of combinatorics. You just write some polynomials, multiply them and then your solution is the coefficient of one of the terms.

For example, how many bouquets of 10 flowers can you make if you want to use 3 or more dandelions, really want to use an even number of lilies and cannot afford more than 5 roses? Easy, just find the coefficient of x^10 in

$$(x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10})\times(1 + x^2 + x^4 + x^6 + x^8 + x^{10})\times(1 + x + x^2 + x^3 + x^4 + x^5)$$


Compute a specific coefficient from a product of polynomials.


If k = 3 and the product given is "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" then we have

$$(1 + 3x + 5x^2)(5 + 3x + 2x^2) = (5 + 3x + 2x^2) + (15x + 9x^2 + 6x^3) + (25x^2 + 15x^3 + 10x^4) = 5 + 18x + 36x^2 + 21x^3 + 10x^4$$

And because k = 3 we get 21.


You receive an integer k and several polynomials. k is always a non-negative integer, and so are the coefficients and the exponents in the input polynomials.

k may be larger than the combined degree of all the input polynomials.

The input polynomials can be in any sensible format. A few suggestions come to mind:

  • A string, like "(1 + 3x + 5x^2)(5 + 3x + 2x^2)"
  • A list of strings, like ["1 + 3x + 5x^2", "5 + 3x + 2x^2"]
  • A list of lists of coefficients where index encodes exponent, like [[1, 3, 5], [5, 3, 2]]
  • A list of lists of (coefficient, exponent) pairs, like [[(1, 0), (3, 1), (5, 2)], [(5, 0), (3, 1), (2, 2)]]

An input format must be sensible AND completely unambiguous over the input space.

Test cases

0, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 5
1, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 18
2, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 36
3, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 21
4, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 10
5, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 0
6, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 8
7, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
8, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 32
9, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
17, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
18, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 160
19, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
20, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 384
  • \$\begingroup\$ Do we need to handle cases where k is greater then the combined degrees of the input polynomials? \$\endgroup\$
    – Chas Brown
    Commented Feb 2, 2020 at 0:49
  • \$\begingroup\$ @ChasBrown the 6th test case shows you do, yes. \$\endgroup\$
    – RGS
    Commented Feb 2, 2020 at 0:50
  • \$\begingroup\$ Is [5, 3, 1] (reversed version of [1, 3, 5]) for 5x^2+3x+1 allowed? Some languages would prefer this format. \$\endgroup\$
    – tsh
    Commented Feb 2, 2020 at 3:38
  • 2
    \$\begingroup\$ @RSG I think the reason is that k has a definite meaning (degree of coefficient), it’s not just an index \$\endgroup\$
    – Luis Mendo
    Commented Feb 2, 2020 at 13:28
  • 2
    \$\begingroup\$ @RGS I just want to thank you for teaching me a new way to solve combinatorics problems today \$\endgroup\$
    – Wboy
    Commented Feb 3, 2020 at 5:35

18 Answers 18


J, 21 19 18 bytes

{ ::0[:+//.@(*/)/>

Try it online!

-1 byte thanks to FrownyFrog

J has a nice geometric idiom for multiplying polynomials, which we represent as lists of coefficients, with explicit zeroes where needed:


Let's see how this works using the example:

1 3 5 +//.@(*/) 5 3 2

First it creates a multiplication table */:

 5  3  2
15  9  6
25 15 10

And @: then it computes the sums along each diagonal +//. using the Oblique /. adverb:


This works because moving down a diagonal is equivalent to decrementing the power of one x while incrementing the power of another, meaning that the numbers along a diagonal represent all the components of some a factor x^n for some n.

The rest of the solution is just mechanics for the problem as stated:

{ ::0[: <polynomial idiom> />

Since we can have an arbitrary number of polynomials, we represent them as a list of boxes (each box containing one polynomial) and take that as the right arg. The left arg is the index we want.

Now { ::0 ... is a dyadic hook asking for the index specified by the left arg, after transforming the right arg by everything in .... And, if you can't find the index, return 0 ::0.

Finally [: <polynomial idiom> /> says to first unbox > the right arg lists, filling any missing coefficients with 0. Then reduce / that list using the polynomial multiplication idiom.

  • \$\begingroup\$ @ works without the colon. \$\endgroup\$
    – FrownyFrog
    Commented Feb 7, 2020 at 1:52
  • \$\begingroup\$ Nice, thank you sir \$\endgroup\$
    – Jonah
    Commented Feb 7, 2020 at 1:58

MATL, 18 15 bytes


Input is a cell array of numerical vectors with the polynomial coefficients, followed by an integer (k).

Try it online! Or verify all test cases.


Polynomial multiplication is convolution of their coefficients. And

convolution is the key to success

Y:     % Implicit input: cell array of numeric vectors. Unbox into its constituents
iWB    % Input k. 2 raised to that. Convert to binary. Gives [1 0...0] with k zeros
1G     % Push first input (cell array of numeric vectors) again
"      % For each. This runs n iterations, where n is the number of polynomials
  Y+   %   Convolution
]      % End
       % The first convolution uses one of the polynomials in the input and the
       % [1 0...0] vector. This doesn't alter the actual coefficients, but adds k 
       % zeros. Thus the final product polynomial will contain k zeros after the
       % highest-degree nonzero coefficient. This ensures that k doesn't exceed
       % the number of existing coefficients
2G     % Push second input (k) again
Q      % Add 1
)      % Index. This retrieves the k-th degree coefficient. Implicit display
  • 1
    \$\begingroup\$ "convolution is the key to success" - thanks, you saved me 10 of my 17 bytes!! \$\endgroup\$ Commented Feb 2, 2020 at 13:37
  • \$\begingroup\$ @Jonathan Quote is from flawr :-) \$\endgroup\$
    – Luis Mendo
    Commented Feb 2, 2020 at 14:45
  • \$\begingroup\$ Sure, but your post is what saved me bytes. \$\endgroup\$ Commented Feb 2, 2020 at 14:46
  • \$\begingroup\$ Polynomial multiplication is convolution of their coefficients Which general mathematical definition of convolution are we using here? \$\endgroup\$
    – Jonah
    Commented Feb 2, 2020 at 19:53
  • \$\begingroup\$ I'm using this definition (is there any other definition for discrete convolution?) \$\endgroup\$
    – Luis Mendo
    Commented Feb 2, 2020 at 22:59

Haskell, 42 bytes


Try it online!

An infix function taking a number n and a lists of lists of coefficients with lowest exponents first.

Here's the key recursive idea. Instead of actually multiplying out the polynomials to get one big polynomial, we only just try to extract the coefficient. Algorithmically, this isn't faster than multiplying out coefficient, but in terms of brevity, it saves us from needing to product lists for the intermediate or final product.

When multiply \$p(x)\cdot q(x)\$, we can split up \$p(x)\$ into its constant and remaining terms as \$p(x)=p_0(x) +x \cdot p_{\mathrm{rest}}(x)\$. Then, the coefficient of \$x^n\$ in \$p(x)\cdot q(x)\$ can be written as:

$$ \begin{align} [p(x)\cdot q(x)]_n &= [(p_0 +x \cdot p_{\mathrm{rest}}(x)) \cdot q(x)]_n \\ &= [p_0 \cdot q(x)]_n + [x \cdot p_{\mathrm{rest}}(x) \cdot q(x)]_n \\ &= p_0 \cdot q(x)_n + [p_{\mathrm{rest}}(x) \cdot q(x)]_{n-1} \\ \end{align} $$

We can continue expanding this out recursively until we get \$p=0\$, where the remaining result is zero. If \$q(x)\$ is itself expressed as a product of polynomials, we continue to extract coefficients from there. The base case is that the empty product is \$1\$, so its \$x^0\$ coefficient is \$1\$ and the rest are zero.

  • \$\begingroup\$ Just to be sure, you are defining % as an infix function, right? Also, I liked your recursive approach. \$\endgroup\$
    – RGS
    Commented Feb 2, 2020 at 9:58
  • 1
    \$\begingroup\$ @RGS Yes, exactly. \$\endgroup\$
    – xnor
    Commented Feb 2, 2020 at 10:02

Mathematica, 20 bytes

A nice benchmark for other answers:


Takes the symbolic expressions as input.

You can try it online!


Python, 67 bytes

f=lambda n,p,*q:p>[]and(f(n,*q)if q else n==0)*p[0]+f(n-1,p[1:],*q)

Try it online!

Takes input like f(3,[1,2,3],[4,5,6]), with the polynomials as separate arguments. The idea for the recursion if the same as in my Haskell answer. But, since Python doesn't have as nice pattern matching, we need to check for empty lists explicitly.


Jelly,  22 17  7 bytes

-10 bytes by realising I'd implemented convolution - go upvote Luis Mendo's MATL answer too, as that was what made me realise this.


A dyadic link accepting a list of coefficient lists on the left and the exponent on the right.

Try it online! Or see the test suite.


æc/ṫ‘}Ḣ - Link: list of lists, Ps; integer, E
  /     - reduce (Ps) by:
æc      -   convolution
     }  - use right argument (E) for:
    ‘   -   increment -> E+1
   ṫ    - tail from (1-indexed) index (E+1)
      Ḣ - head (if given an empty list yields 0)

The 17 (without the convolution atom) was:

  • 1
    \$\begingroup\$ Isn't there an elegant way to gracefully return 0 when the exponent is too high? :/ \$\endgroup\$
    – RGS
    Commented Feb 2, 2020 at 9:57
  • 2
    \$\begingroup\$ @RGS I've found a much more elegant way to combine the indexing and the maximal exponent issue (tail from index exponent+1 then take the head, since head for an empty list yields zero) \$\endgroup\$ Commented Feb 2, 2020 at 13:17
  • 1
    \$\begingroup\$ this answer is 3x shorter! Well golfed :D \$\endgroup\$
    – RGS
    Commented Feb 2, 2020 at 14:09

Husk, 18 16 bytes


First Husk answer. This took so much longer to complete than I thought it would. I'm glad there is a tutorial with good explanation of how the input-order and super-numbers work, otherwise I had to give up. I never programmed in Haskell, and maybe I'm just too used to the left-to-right stack-based 05AB1E, but Husk isn't exactly straight-forward due to its strong-typed nature and right-to-left execution (including input-arguments) imho..
But, it works, which is what counts in the end. :)

First input-argument is a list of lists of coefficients where index encodes exponent, like the third input example in the challenge description. Second argument is the coefficient integer \$k\$.

Try it online.


             ²    # Use the first argument,
     G(     )     # and left-reduce it by:
          Ṫ       #  Apply double-vectorized:
           *      #   Multiply
                  #  (This basically results in the multiplication table of the lists)
         ∂        #  Take the diagonals of this multiplication table
       m          #  Map over these diagonal-lists:
        Σ         #   And sum each together
    →             # Only leave the last list after the reduce-by
              ∞0  # Push an infinite list of 0s: [0,0,0,...]
   +              # Merge the two lists together
  ⁰               # Push the second argument `k`
 →                # Increase it by 1 (since Husk uses 1-based indexing instead of 0-based)
!                 # And use it to index into the list we created
                  # (after which the result is output implicitly)
  • \$\begingroup\$ Great work on this! \$\endgroup\$
    – RGS
    Commented Feb 4, 2020 at 15:31
  • 1
    \$\begingroup\$ @RGS I'm glad I got it's working in the end. I kept getting the Could not infer valid type for program error almost every step of the way, haha. I should have read that tutorial more thoroughly sooner though, bit my own fault. At first I tried to use implicit inputs, which works with a single argument. Took me a while to realize only the even superscript digits ⁰²⁴⁶⁸ are used to get arguments (odd ones are used to push an argument twice), and also in reversed order.. So with my two argument program, ² is the first argument and the second. Ah well.. \$\endgroup\$ Commented Feb 4, 2020 at 15:44
  • \$\begingroup\$ if you didn't know husk, why did you go for it? \$\endgroup\$
    – RGS
    Commented Feb 4, 2020 at 16:01
  • 1
    \$\begingroup\$ @RGS To try something new. :) And I remember Husk had a 1-byte diagonals builtin, so I figured it would be pretty short using a rather similar approach as the J answer. \$\endgroup\$ Commented Feb 4, 2020 at 16:15

Python 2, 139 131 bytes

lambda k,L:sum(reduce(lambda a,(i,c):a*c[i],zip(p,L),1)for p in product(*map(range,map(len,L)))if sum(p)==k)
from itertools import*

Try it online!

Takes as inputs k and then polynomials as a list of lists of coefficents [c0, c1, c2, ...]. Forms all tuples of indexes into the polynomials that sum to the desired coefficent; and then sums up the products of the corresponding coefficients.


JavaScript (Node.js), 55 bytes


Try it online!

The first argument is k. The second argument is "a list of lists of coefficients where index encodes exponent", like [[1, 3, 5], [5, 3, 2]].

  • \$\begingroup\$ 51 \$\endgroup\$
    – l4m2
    Commented Aug 8, 2023 at 8:59

Jelly, 19 15 bytes


Try it online!

A dyadic link taking k as the left argument and the list of polynomials as a list of lists of coefficients as the right argument. Returns an integer. If k could be 1-indexed, ‘} could be deleted for 13 bytes.

Adapted to use @JonathanAllan’s revised method for dealing with larger k; be sure to upvote his (still shorter) answer too!


R, 68 bytes


Try it online!

Convolution is the key to success here, too, since it's a port of Luis' answer.

Takes input as a list() of vectors c() of coefficients in decreasing order, because R's convolve documentation says:

Note that the usual definition of convolution of two sequences x and y is given by convolve(x, rev(y), type = "o").

  • \$\begingroup\$ Thanks for your R submission! Waiting for your R submission in the mirror challenge about division! \$\endgroup\$
    – RGS
    Commented Feb 25, 2020 at 20:45

Pari/GP, 29 bytes


Try it online!

  • \$\begingroup\$ Good job on this one! +1 \$\endgroup\$
    – RGS
    Commented Feb 26, 2020 at 7:55

Sledgehammer, 6 bytes


Only works in the interactive app (that requires excessive amounts of tinkering to get it to actually decompress the Braille code itself, but it's possible), because of a bug where the console app doesn't call postprocess and ends up replacing all occurrences of #, #1, #2, ## by s1, s2, s3, ss1.

Accepts input as, for example, {"(1 + 2x1^2 + 4x1^4)(2x1^2 + 4x1^4 + 8x1^8)(4x1^4 + 8x1^8 + 16x1^16)", 20} - x1 is the variable the first undefined variable used gets replaced with.

Obtained from the Mathematica code Coefficient[ToExpression@#, z, #2] (where ToExpression is eval and Coefficient simply gets the right coefficient, and z gets replaced by x1 as part of the compression).


05AB1E, 32 24 23 bytes


Definitely not the right language to use for this challenge (no builtins for convolution, polynomials, getting all diagonals of a matrix, etc.).. But with some -rather long- workarounds, it still works (although is too slow for the last test cases).

Input as a list of list of coefficients where index encodes exponent, as well as the integer \$k\$ as second input.

Inspired by @Jonah's J answer.
-8 bytes by porting two approaches I've used in my Husk answer.

Try it online or verify some more test cases (outputs all coefficients without the indexing part).


Å»        # Left reduce the (implicit) input-list of lists of integers by:
          #  1) Calculate the multiplication table of the current two lists:
  δ       #   Apply double-vectorized:
   *      #    Multiply
          #  2) Take the sums of each diagonal:
  ε       #   Map each inner list to:
   ā      #    Push a list in the range [1,list-length] (without popping the list itself)
    _     #    Convert each to 0, so we'll have a list of 0s of the same length
     «    #    Append this list of 0s to the current list
      NF  #    Loop the 0-based map-index amount of times:
        Á #     And rotate the current list that many times towards the right
  }}      #   End the loop and map
    ø     #   Zip/transpose; swapping rows/columns
          #   (We now have a list of all diagonals)
     O    #   And take the sum of each inner list
}θ        # After the reduce-by is done, pop and push the final resulting list
  ∞_«     # Append an infinite amount of trailing 0s
     Iè   # And then use the second input to (0-based) index into this list
          # (after which the result is output implicitly)
  • \$\begingroup\$ Good job nonetheless :D \$\endgroup\$
    – RGS
    Commented Feb 4, 2020 at 15:31

Itr, 9 bytes


Input: nonempty list of polynomials (given as coefficient vectors) followed by index of coefficient that should be computed

Does not work if input list is empty

online interpreter


#          ; read the list of polynomials
 R     «   ; reduce with
  C*µS     ; polynomial multiplication
  C*       ; go through the diagonals of the Cartesian product, multiplying the two elements in the pairs
    µS     ; sum up the diagonals
        #@ ; get the specified coefficient 
           ; implicit output

Itr, 10 bytes

Also works for empty input list


Input: list of polynomials (given as coefficient vectors) followed by index of coefficient that should be computed


1           ; push 1
 #          ; read the list of polynomials
  M     «   ; for polynomial in the list
   C*µS     ; multiply that polynomial with the top stack value
         #@ ; get the specified coefficient 
            ; implicit output

Itr, 8 bytes (only works for 2 inputs)


Input: two list of coefficients for the polynomials followed by the index of the coefficents

online interpreter


##       ; read the two coefficient lists for standard input
  C*µS   ; multiply them as polynomials
  C*     ; go through the diagonals of the Cartesian product, multiplying the two elements in the pairs
    µS   ; sum up the diagonals
      #@ ; get int specified coefficient
         ; implicit output
  • 3
    \$\begingroup\$ The input may contain more than two polynomials. \$\endgroup\$
    – Bubbler
    Commented Aug 8, 2023 at 6:24

K (ngn/k), 39 bytes


Try it online!


Charcoal, 52 bytes


Try it online! Link is to verbose version of code. Takes input using the last suggestion but with the exponent first, then the coefficient. Explanation:


Initialise a variable to the polynomial 1.


Loop over the input polynomials.


Accumulate terms in a temporary variable.


Loop over the Cartesian product of both sets of terms.


Multiply the coefficients and add the exponents.


Move the resulting terms back to the original variable. (Charcoal doesn't have any flattening operators, and this is the golfiest way of flattening manually.)


Filter for the terms with the desired exponent and sum the coefficients, unless there weren't any, in which case the result is 0.


Brachylog, 16 bytes


Try it online!

Takes input as a list of lists of [coefficient, exponent] pairs, paired with k. Could be trivially modified to accept index-as-exponent coefficient lists by replacing with i, which is in fact what I did originally before I made an error writing out the test cases and switched for my own convenience.

⟨       ⟩           Call the first element of the input L and the last element k.
         ᶠ          Find every
 ∋                  selection of a [coefficient, exponent] pair
  ᵐ                 from each polynomial in L
   {   }            such that k is
      +             the sum of
    tᵐ              the exponents.
          hᵐ²       Extract the coefficients from each selection,
             ×ᵐ     multiply the coefficients extracted from each selection,
               +    and output the sum of the products.

{⟨∋ᵐ{tᵐ+}⟩hᵐ×}ᶠ+ is an equally valid solution at the same length, but I'm not sure I remember ever superscripting before this, so I'm just going with the version that does that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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