Problem 240: Top Dice

Project Euler Problem 240 Solution

EulerSolve provides an optimized solution for Project Euler Problem 240, Top Dice, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Project Euler 240 asks for the number of ordered outcomes obtained by rolling 20 twelve-sided dice such that, after sorting the 20 results in descending order, the 10 largest values add up to 70. If the sorted roll is $x_1 \ge x_2 \ge \cdots \ge x_{20}$, the condition is $$x_1+x_2+\cdots+x_{10}=70.$$ The dice are distinguishable before sorting, so two rolls with the same multiset of face values still count as different outcomes when those values are assigned to different dice. Any correct method therefore has to count raw rolls, not just sorted patterns. Mathematical Approach The implementations solve the problem by scanning face values from 12 down to 1. At each step they decide how many remaining dice show the current face, keep track of how many positions of the top ten have already been forced by larger faces, and accumulate the partial top-ten sum. Face Multiplicities Encode the Sorted Roll Let $c_v$ be the number of dice showing face $v$, for $1 \le v \le 12$. Then $$\sum_{v=1}^{12} c_v = 20.$$ Once the counts $c_{12},c_{11},\dots,c_1$ are known, the sorted roll is determined: first come all 12s, then all 11s, and so on. The only subtlety is that not every die contributes to the top-ten sum....

Detailed mathematical approach

Problem Summary

Twenty dice, each with twelve faces numbered $1$ to $12$, are rolled. A roll is the ordered list $D_1,D_2,\dots,D_{20}$ of the faces shown, so two rolls that differ only in the order of their faces count separately. The top ten of a roll are its ten largest values, where a repeated value counts as often as it occurs, and we must count the rolls whose top ten sum to $70$. The statement gives a smaller case: five six-sided dice can be rolled in $1111$ ways so that the top three sum to $15$. Among its examples, $4,3,6,3,5$ has the top three $6,5,4$, while $3,3,3,6,6$ and $6,6,3,3,3$ both have the top three $6,6,3$ and count as two different rolls. ^[1]

The whole solution in one sentence: we go through the faces from $12$ down to $1$, choose how many of the still free dice show each face, count the ways to pick them with a binomial coefficient, and keep only how many dice are free, how many of the ten top places are taken and their sum.

Mathematical Approach

We write $n$ for the number of dice, $F$ for the number of faces, $K$ for the number of top values and $S$ for their required sum. The task is the case $(n,F,K,S)=(20,12,10,70)$, and the checkpoint of the statement is $(5,6,3,15)$.

1. Rolls and their top part

Sorting the faces of a roll from the largest to the smallest gives $x_1\ge x_2\ge\dots\ge x_n$, and the problem asks about $T_K=x_1+\dots+x_K$, the sum of the $K$ largest order statistics of the roll. ^[2] Checking all $12^{20}\approx3.8\cdot10^{21}$ rolls one by one is out of the question.

2. The checkpoint by hand

For five six-sided dice the top three are faces from $1$ to $6$ with sum $15$, and only three non-increasing triples qualify: $(6,5,4)$, $(6,6,3)$ and $(5,5,5)$. We count the rolls of each kind, using that $k$ dice can show faces of at most $u$, at least one of them $u$, in $u^k-(u-1)^k$ ways: all ways with faces up to $u$, minus those without any $u$.

$(6,5,4)$: the roll has exactly one $6$ and one $5$, since a second $6$ or $5$ would push the $4$ out of the top three, and its other three dice show at most $4$, at least one of them a $4$. There are $5$ choices for the die with the $6$, then $4$ for the $5$, and $4^3-3^3=37$ for the rest: $5\cdot4\cdot37=740$ rolls.
$(6,6,3)$: exactly two $6$s, no $5$ or $4$, and the other three dice show at most $3$, at least one of them a $3$: $\binom52\cdot(3^3-2^3)$${}=10\cdot19=190$ rolls.
$(5,5,5)$: no $6$ and at least three $5$s, the other dice showing $1$ to $4$: $\binom53\cdot4^2+\binom54\cdot4+1$${}=160+20+1=181$ rolls, for exactly three, four and five $5$s.

Together $740+190+181=1111$, the value of the statement. Three ideas carry over to the real problem: only how many dice show each face decides the top sum; which dice show it is a choice counted by binomial coefficients; and the faces are best handled from the largest down, because the largest faces fill the top places first.

3. Face counts decide the top sum

Let $c_v$ be the number of dice that show the face $v$, so that $c_1+\dots+c_F=n$. The sorted roll consists of $c_F$ copies of $F$, then $c_{F-1}$ copies of $F-1$, and so on, so $T_K$ depends only on the face counts. Going down from $v=F$, we define numbers $t_v$ and $m_v$ by $m_F=0$ and

$$\begin{aligned}t_v&=\min(c_v,\,K-m_v),\\m_{v-1}&=m_v+t_v.\end{aligned}$$

Claim. $m_v$ is the number of top places taken by the faces larger than $v$, $t_v$ is the number of copies of $v$ among the top $K$ values, and therefore $T_K=\sum_{v}v\,t_v$.

Proof. Let $P_v=c_F+\dots+c_{v+1}$ be the number of dice larger than $v$. They fill the first $P_v$ sorted places and so take $\min(K,P_v)$ top places; we prove $m_v=\min(K,P_v)$ along the way, and for $v=F$ both sides are $0$. The copies of $v$ occupy the sorted places $P_v+1,\dots,P_v+c_v$, and $\min\bigl(c_v,\max(0,K-P_v)\bigr)$ of these places are among the first $K$. Since $m_v=\min(K,P_v)$, we have $\max(0,K-P_v)=K-m_v$, so this number is $t_v$. Moreover $m_v+t_v=\min(K,P_v+c_v)$, which is $\min(K,P_{v-1})$ and continues the induction. $\square$

For the roll $3,3,3,6,6$ and $K=3$ we have $c_6=2$ and $c_3=3$, so $t_6=2$, $t_5=t_4=0$, $t_3=\min(3,1)=1$ and $T_3=12+3=15$. Once $m_v=K$, every smaller face gets $t=0$: its dice belong to the bottom part, and their values no longer affect the sum.

4. Counting the rolls with given face counts

Many rolls have the same face counts. To count them, choose the $c_F$ dice that show $F$ among all $n$ dice, then the $c_{F-1}$ dice that show $F-1$ among the $n-c_F$ others, and so on. A set of $c$ dice can be chosen from $r$ dice in $\binom rc$ ways, ^[3] and in the product the factorials $(n-c_F)!$, $(n-c_F-c_{F-1})!$, $\dots$ cancel, which leaves the multinomial coefficient ^[4]

$$\begin{aligned}&\binom{n}{c_F}\binom{n-c_F}{c_{F-1}}\cdots\binom{c_1}{c_1}\\&\quad=\frac{n!}{c_1!\,c_2!\cdots c_F!}.\end{aligned}$$

For $c_6=2$ and $c_3=3$ this gives $\binom52\binom33=10=5!/(2!\,3!)$ rolls, among them $3,3,3,6,6$ and $6,6,3,3,3$. Every roll has exactly one list of face counts, so the number of rolls with $T_K=S$ is the sum of these coefficients over all lists $(c_1,\dots,c_F)$ whose top sum, computed as in Section 3, equals $S$.

5. What a partial count must remember

Suppose the dice showing the faces $F,F-1,\dots,v+1$ have been chosen as in Section 4. To continue, only three numbers matter:

$r$, the number of dice that are still free, because the next factor is $\binom r{c_v}$;
$m$, the number of top places already taken, because the rule $t_v=\min(c_v,K-m)$ of Section 3 needs nothing else;
$s$, the sum of the taken top places, because it has to end at exactly $S$.

Two partial choices with the same three numbers can be completed in the same ways, with the same factors, so they can be merged into one entry. For $s\le S$, let $D_v(r,m,s)$ be the number of ways to choose the sets of dice that show $F,\dots,v+1$ so that $r$ dice are left free and $m$ top places are taken, with sum $s$. At the start $D_F(n,0,0)=1$, and every other entry of $D_F$ is $0$. Computing each table from the previous one in this way is dynamic programming. ^[5]

6. One face at a time

To go from $D_v$ to $D_{v-1}$, every state $(r,m,s)$ chooses how many of its free dice show the face $v$, some $c$ with $0\le c\le r$. These dice can be picked in $\binom rc$ ways, and $a=\min(c,K-m)$ of them enter the top, so the state moves to

$$(r,m,s)\ \longrightarrow\ (r-c,\ m+a,\ s+a\,v),$$

and $\binom rc\,D_v(r,m,s)$ is added to that entry of $D_{v-1}$. A move with $s+av\gt S$ is dropped: $s$ never decreases, so such a state can never end at $S$. After face $1$ the answer is read from the state in which no die is free and all top places are taken:

$$D_0(0,K,S).$$

7. Why every roll is counted exactly once

Claim. For $n\ge K$, $D_0(0,K,S)$ is the number of rolls with $T_K=S$.

Proof. A roll is the same thing as a list of disjoint sets $A_F,\dots,A_1$ that together contain all $n$ dice, $A_v$ being the set of dice that show $v$. Call $A_F,\dots,A_{v+1}$ a partial roll, with the state $(r,m,s)$: $r$ dice lie outside these sets, and $m$ and $s$ are the values of Section 3 for the faces above $v$, which depend only on the sizes of the sets. By induction over the faces, $D_v(r,m,s)$ is the number of partial rolls with state $(r,m,s)$, for every $s\le S$. For $v=F$ the only partial roll is the empty list, with state $(n,0,0)$. Each partial roll $A_F,\dots,A_v$ comes from exactly one partial roll $A_F,\dots,A_{v+1}$, whose sum is at most its own. If that one has state $(r,m,s)$, then by Section 3 the $\binom rc$ choices of $A_v$ with $c$ elements all lead to the state $(r-c,m+a,s+av)$, exactly the moves of Section 6, and a sum above $S$ stays above $S$ in every extension, so dropping it loses nothing. After face $1$, the partial rolls with $r=0$ are the complete rolls, with $m=\min(K,n)=K$ and $s=T_K$. $\square$

The entries with $r\gt0$ after face $1$ belong to partial rolls in which some dice never received a face; they are computed but never used.

8. A complete small example

Take $n=3$ dice with $F=3$ faces and ask for the top two to sum to $5$. By hand, the top two must be $3$ and $2$ and the third die shows $2$ or $1$: the faces $3,2,2$ can be arranged in $3$ ways and $3,2,1$ in $3!=6$ ways, so the answer is $9$. Writing an entry as state: count, we list every nonzero state after faces $3$ and $2$, and then follow the moves into the final state:

Start: $(3,0,0)\colon1$.
Face $3$: $c=0$ keeps $(3,0,0)\colon1$, and $c=1$ gives $(2,1,3)\colon\binom31=3$. With $c=2$ or $c=3$ two $3$s enter the top, with sum $6\gt5$, so these moves are dropped.
Face $2$: from $(3,0,0)\colon1$, the choices $c=0,1,2,3$ give $(3,0,0)\colon1$, $(2,1,2)\colon3$, $(1,2,4)\colon3$ and $(0,2,4)\colon1$; for $c=3$ only two of the three $2$s enter the top. From $(2,1,3)\colon3$, the choices $c=0,1,2$ give $(2,1,3)\colon3$, $(1,2,5)\colon3\cdot2=6$ and $(0,2,5)\colon3\cdot1=3$; for $c=2$ only one of the two $2$s enters the top.
Face $1$: the state $(0,2,5)$ keeps its $3$ with $c=0$ and receives $6\cdot\binom11=6$ from $(1,2,5)$, whose last free die shows $1$ and stays out of the top. So $D_0(0,2,5)=9$.

The other final entries with $r=0$, $D_0(0,2,s)=1,3,7$ for $s=2,3,4$, count the rolls with these top sums; with the $7$ dropped rolls whose top two are $3,3$ they make up all $27=3^3$ rolls.

9. Other ways to group the rolls

A list of face counts of Section 4 writes $20$ as a sum of $12$ parts $c_{12},\dots,c_1\ge0$, that is, a row of $20$ stars cut into $12$ groups by $11$ bars; by stars and bars there are $\binom{31}{11}=84\,672\,315$ lists, ^[6] more than $2000$ times as many as the moves that the tables try. Section 2 grouped the rolls more coarsely, by their sorted top $K$. In the real problem there are $9160$ such lists, the partitions of $70$ into ten parts of size at most $12$. Let the smallest value $\mu$ of a list occur $j$ times in it, let $k_v$ be the number of times a larger value $v$ occurs, and let $\Pi$ be the product of the factorials $k_v!$. The other $b=n-K$ dice show at most $\mu$. If exactly $i$ of them show $\mu$, the roll has $j+i$ copies of $\mu$, which form one group, $k_v$ copies of each larger $v$, and $b-i$ dice below $\mu$. By Section 4 the dice can be split into these groups in $n!/\bigl(\Pi\,(j+i)!\,(b-i)!\bigr)$ ways, and each of the last $b-i$ dice shows one of the $\mu-1$ smaller faces. The cases $i=0,\dots,b$ are disjoint, so the list belongs to

$$\sum_{i=0}^{b}\frac{n!\,(\mu-1)^{b-i}}{\Pi\,(j+i)!\,(b-i)!}$$

rolls, with $0^0=1$ when $\mu=1$. For the triple $(6,5,4)$ of Section 2, with $\mu=4$, $j=1$, $\Pi=1$ and $b=2$, the three terms are $540+180+20=740$.

How the Code Works

The C++ program ^[7] keeps the parameters, by default $n=20$, $F=12$, $K=10$ and $S=70$, in the struct Options. parse_arguments accepts --num-dice=, --max-points=, --top-count=, --top-sum= and --skip-checkpoints, and the program stops with exit code $1$ on an unknown argument or unless $n\ge1$, $F\ge1$, $1\le K\le n$ and $K\le S\le KF$. Neither the conversion of the digits to int in parse_int_after_prefix nor the product $KF$ is checked for overflow, so huge values are not reliably rejected. Unless they are switched off, run_checkpoints requires solve(5, 6, 3, 15) to return $1111$ and solve(7, 4, 3, 10) to agree with brute_small(7, 4, 3, 10), which sorts each of the $4^7=16384$ rolls and adds up its top three; both give $3962$. A failed checkpoint gives exit code $2$.

build_binom(n) fills Pascal's triangle up to row $n$ with the rule $\binom ij=\binom{i-1}{j-1}+\binom{i-1}j$, ^[3] and solve stores a table $D_v$ as the nested vector dp[rem][filled][sum], where rem, filled and sum are $r$, $m$ and $s$, and sets dp[num_dice][0][0] = 1 as in Section 5. For face from $F$ down to $1$ it allocates a zeroed table next, skips the entries of dp that are $0$, and for every count $c$ from $0$ to rem computes add_top, which is $a=\min(c,K-m)$, and new_sum. A move with new_sum above $S$ is dropped; otherwise ways * comb is added to next[rem - count][filled + add_top][new_sum]. Then dp.swap(next) makes the new table current, and after face $1$ the function returns dp[0][top_count][top_sum], the entry $D_0(0,K,S)$ of Section 7. Python's build_binom and Java's buildBinom build the same triangle, and their solve functions run the same loops over nested lists and long[][][] arrays. Python's solve takes the four parameters, with the real values as defaults, and returns the count as a string; Java fixes them inside solve; neither has options or checkpoints.

Since $12^{20}$ exceeds $2^{64}\approx1.8\cdot10^{19}$, the sizes of the numbers need a check. C++ counts in std::uint64_t, Java in long, and Python in integers of unlimited precision. An exact computation of all tables shows that every entry of $D_{12},\dots,D_1$ is below $2^{61}$ and every product ways * comb is below $2^{63}$. Only in the last table $D_0$ do $14$ entries reach $2^{63}$, three of them even $2^{64}$, all with $r\ge1$, the unused states of Section 7. There the sums wrap around: unsigned C++ arithmetic is defined modulo $2^{64}$, and Java's long addition keeps the low-order bits of the true sum. ^[8] These entries are never read, and the entry that is read, a sum of nonnegative products, stays below $2^{63}$, so all three programs print the exact count. With other parameters given through the C++ options, such as $22$ dice whose top eleven sum to $80$, the count itself can exceed $2^{64}$, and the C++ program then prints it modulo $2^{64}$ without a warning.

Complexity and Verification

Each table has $(n+1)(K+1)(S+1)$ entries, and for each of the $F$ faces every state tries at most $n+1$ values of $c$. Counting each arithmetic operation as one step, the running time is therefore $O(F\,n^2KS)$, which includes the $O(n^2)$ steps for Pascal's triangle, and the memory, the $(n+1)^2$ binomial coefficients and two tables at a time, is $O(n^2+nKS)$. For the real problem a table has $21\cdot11\cdot71=16401$ entries, but few of them are ever nonzero: $6$ after face $12$, since six $12$s already sum to $72$, and $1096$ after face $1$. Over the twelve faces the loops meet $3589$ nonzero states and try $39309$ values of $c$, of which $32351$ pass the test against $S$, so all three programs finish in a fraction of a second.

The C++ program checks itself with its two checkpoints. The following checks were made for this article and are not part of the published solutions. A brute force over all rolls agrees with the tables in all $1651$ cases with $n\le10$, $F\le6$, $F^n\le60000$, $K\le n$ and every possible $S$, among them the examples of Sections 2 and 8. The grouping of Section 9 agrees with the tables in all $2772$ cases with $n\le8$ and $F\le7$, and in the real problem. Rerunning the tables modulo $2^{64}$, as the C++ program computes them, gives the same final entry as exact arithmetic, and the three programs print the same number.

Footnotes and References

The references below supply the background facts used above; the rule for the top places, the tables and their proof, the small examples and the operation counts are derived in this article.

Project Euler 240 — Top Dice. The official statement: five 6-sided dice can be rolled in 1111 ways so that the top three sum to 15, with four examples, among them 3,3,3,6,6 and 6,6,3,3,3; the task asks in how many ways twenty 12-sided dice can be rolled so that the top ten sum to 70.
Wikipedia — Order statistic. The k-th order statistic of a sample is its k-th smallest value; the order statistics X(1), …, X(n) are obtained by sorting the sample in increasing order, so the top K values of a roll are X(n − K + 1), …, X(n).
Wikipedia — Binomial coefficient. C(n, k) is the number of ways to choose a subset of k elements from a set of n elements. The recursive formula C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for 1 ≤ k < n, with C(n, 0) = C(n, n) = 1, builds Pascal's triangle with additions only.
Wikipedia — Multinomial theorem, multinomial coefficients. The coefficient n!/(k₁! k₂! ⋯ kₘ!) counts the ways to put n distinct objects into m distinct bins with kᵢ objects in bin i, and it equals the product C(n, k₁) C(n − k₁, k₂) ⋯ of binomial coefficients.
Wikipedia — Dynamic programming. It simplifies a complicated problem by breaking it down into simpler sub-problems; the bottom-up approach solves the smaller ones first, usually in a table, and builds the larger solutions from them.
Wikipedia — Stars and bars (combinatorics). By Theorem two, the number of k-tuples of non-negative integers with sum n, that is, of multisets of size n taken from k kinds, is C(n + k − 1, k − 1); here n = 20 and k = 12.
C++ — Euler240.cpp. The linked immutable revision contains parse_arguments, build_binom, solve, brute_small and run_checkpoints. It is the implementation record for this article.
cppreference — Arithmetic operators: unsigned integer arithmetic is always performed modulo 2ⁿ, where n is the number of bits of the type. The Java Language Specification, §15.18.2: if an integer addition overflows, the result is the low-order bits of the mathematical sum in a sufficiently large two's-complement format. Python — numeric types: integers have unlimited precision.

Problem 240 source code

C++

#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>

namespace {

using u64 = std::uint64_t;

struct Options {
    int num_dice = 20;
    int max_points = 12;
    int top_count = 10;
    int top_sum = 70;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--num-dice=", options.num_dice) ||
            parse_int_after_prefix(arg, "--max-points=", options.max_points) ||
            parse_int_after_prefix(arg, "--top-count=", options.top_count) ||
            parse_int_after_prefix(arg, "--top-sum=", options.top_sum)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.num_dice >= 1 && options.max_points >= 1 &&
           options.top_count >= 1 && options.top_count <= options.num_dice &&
           options.top_sum >= options.top_count && options.top_sum <= options.top_count * options.max_points;
}

std::vector<std::vector<u64>> build_binom(const int n) {
    std::vector<std::vector<u64>> c(static_cast<std::size_t>(n + 1),
                                    std::vector<u64>(static_cast<std::size_t>(n + 1), 0));
    for (int i = 0; i <= n; ++i) {
        c[static_cast<std::size_t>(i)][0] = 1;
        c[static_cast<std::size_t>(i)][static_cast<std::size_t>(i)] = 1;
        for (int j = 1; j < i; ++j) {
            c[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)] =
                c[static_cast<std::size_t>(i - 1)][static_cast<std::size_t>(j - 1)] +
                c[static_cast<std::size_t>(i - 1)][static_cast<std::size_t>(j)];
        }
    }
    return c;
}

u64 solve(const int num_dice, const int max_points, const int top_count, const int top_sum) {
    const auto choose = build_binom(num_dice);

    std::vector<std::vector<std::vector<u64>>> dp(
        static_cast<std::size_t>(num_dice + 1),
        std::vector<std::vector<u64>>(
            static_cast<std::size_t>(top_count + 1),
            std::vector<u64>(static_cast<std::size_t>(top_sum + 1), 0)));
    dp[static_cast<std::size_t>(num_dice)][0][0] = 1;

    for (int face = max_points; face >= 1; --face) {
        std::vector<std::vector<std::vector<u64>>> next(
            static_cast<std::size_t>(num_dice + 1),
            std::vector<std::vector<u64>>(
                static_cast<std::size_t>(top_count + 1),
                std::vector<u64>(static_cast<std::size_t>(top_sum + 1), 0)));

        for (int rem = 0; rem <= num_dice; ++rem) {
            for (int filled = 0; filled <= top_count; ++filled) {
                for (int sum = 0; sum <= top_sum; ++sum) {
                    const u64 ways = dp[static_cast<std::size_t>(rem)][static_cast<std::size_t>(filled)][static_cast<std::size_t>(sum)];
                    if (ways == 0) {
                        continue;
                    }

                    for (int count = 0; count <= rem; ++count) {
                        const int add_top = std::min(count, top_count - filled);
                        const int new_filled = filled + add_top;
                        const int new_sum = sum + add_top * face;
                        if (new_sum > top_sum) {
                            continue;
                        }

                        const u64 comb = choose[static_cast<std::size_t>(rem)][static_cast<std::size_t>(count)];
                        next[static_cast<std::size_t>(rem - count)][static_cast<std::size_t>(new_filled)][static_cast<std::size_t>(new_sum)] +=
                            ways * comb;
                    }
                }
            }
        }

        dp.swap(next);
    }

    return dp[0][static_cast<std::size_t>(top_count)][static_cast<std::size_t>(top_sum)];
}

u64 brute_small(const int num_dice, const int max_points, const int top_count, const int top_sum) {
    std::vector<int> rolls(static_cast<std::size_t>(num_dice), 1);
    u64 count = 0;

    while (true) {
        std::vector<int> sorted = rolls;
        std::sort(sorted.begin(), sorted.end(), std::greater<int>());
        int sum = 0;
        for (int i = 0; i < top_count; ++i) {
            sum += sorted[static_cast<std::size_t>(i)];
        }
        if (sum == top_sum) {
            ++count;
        }

        int pos = 0;
        while (pos < num_dice && rolls[static_cast<std::size_t>(pos)] == max_points) {
            rolls[static_cast<std::size_t>(pos)] = 1;
            ++pos;
        }
        if (pos == num_dice) {
            break;
        }
        ++rolls[static_cast<std::size_t>(pos)];
    }

    return count;
}

bool run_checkpoints() {
    if (solve(5, 6, 3, 15) != 1111ULL) {
        std::cerr << "Checkpoint failed for stated sample (5,6,3,15)" << '\n';
        return false;
    }
    if (solve(7, 4, 3, 10) != brute_small(7, 4, 3, 10)) {
        std::cerr << "Checkpoint failed for brute cross-check (7,4,3,10)" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.num_dice, options.max_points, options.top_count, options.top_sum) << '\n';
    return 0;
}

Python

def build_binom(n):
    c = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        c[i][0] = 1
        c[i][i] = 1
        for j in range(1, i):
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
    return c

def solve(num_dice=20, max_points=12, top_count=10, top_sum=70):
    choose = build_binom(num_dice)
    
    dp = [[[0] * (top_sum + 1) for _ in range(top_count + 1)] for _ in range(num_dice + 1)]
    dp[num_dice][0][0] = 1
    
    for face in range(max_points, 0, -1):
        next_dp = [[[0] * (top_sum + 1) for _ in range(top_count + 1)] for _ in range(num_dice + 1)]
        
        for rem in range(num_dice + 1):
            for filled in range(top_count + 1):
                for current_sum in range(top_sum + 1):
                    ways = dp[rem][filled][current_sum]
                    if ways == 0:
                        continue
                        
                    for count in range(rem + 1):
                        add_top = min(count, top_count - filled)
                        new_filled = filled + add_top
                        new_sum = current_sum + add_top * face
                        
                        if new_sum > top_sum:
                            continue
                            
                        comb = choose[rem][count]
                        next_dp[rem - count][new_filled][new_sum] += ways * comb
                        
        dp = next_dp
        
    return str(dp[0][top_count][top_sum])

if __name__ == '__main__':
    print(solve())

Java

public class Euler240 {
    static long[][] buildBinom(int n) {
        long[][] c = new long[n + 1][n + 1];
        for (int i = 0; i <= n; ++i) {
            c[i][0] = 1;
            c[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            }
        }
        return c;
    }

    public static String solve() {
        int numDice = 20;
        int maxPoints = 12;
        int topCount = 10;
        int topSum = 70;

        long[][] choose = buildBinom(numDice);
        long[][][] dp = new long[numDice + 1][topCount + 1][topSum + 1];
        dp[numDice][0][0] = 1;

        for (int face = maxPoints; face >= 1; --face) {
            long[][][] nextDp = new long[numDice + 1][topCount + 1][topSum + 1];

            for (int rem = 0; rem <= numDice; ++rem) {
                for (int filled = 0; filled <= topCount; ++filled) {
                    for (int sum = 0; sum <= topSum; ++sum) {
                        long ways = dp[rem][filled][sum];
                        if (ways == 0)
                            continue;

                        for (int count = 0; count <= rem; ++count) {
                            int addTop = Math.min(count, topCount - filled);
                            int newFilled = filled + addTop;
                            int newSum = sum + addTop * face;

                            if (newSum > topSum)
                                continue;

                            long comb = choose[rem][count];
                            nextDp[rem - count][newFilled][newSum] += ways * comb;
                        }
                    }
                }
            }
            dp = nextDp;
        }

        return String.valueOf(dp[0][topCount][topSum]);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}