Problem 109: Darts

Project Euler Problem 109 Solution

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

Problem Summary In this darts setting, a checkout may use one, two, or three darts, but the final dart must land in a double. The goal is to count how many distinct checkouts produce a total score strictly below $100$. The important word is distinct . Different landing regions are counted separately even when they have the same numerical value. For example, $S6$, $D3$, and $T2$ all score $6$, but they are different darts and therefore different non-final choices. The solution must count regions, not just totals. Mathematical Approach Let $A$ be the set of all legal non-final darts and $F$ the set of legal finishing darts. Then $$A=\{S1,\dots,S20,D1,\dots,D20,T1,\dots,T20,S25,D25\},\qquad |A|=62,$$ and $$F=\{D1,\dots,D20,D25\},\qquad |F|=21.$$ If $v(x)$ denotes the score of region $x$, the problem becomes a finite counting problem on these two sets. The correct state space: a multiset of preliminary darts Only the final dart keeps its position in the ordering. The first two darts may be swapped without creating a new checkout, so the preliminary part is best modeled as a multiset of size $0$, $1$, or $2$ drawn from $A$. Size $0$ corresponds to a one-dart checkout, size $1$ to a two-dart checkout, and size $2$ to a three-dart checkout. This viewpoint also explains why misses are absent from the implementations....

Detailed mathematical approach

Problem Summary

A dartboard is split into twenty equal sections numbered $1$ to $20$. A dart scores the number of its section, doubled in the red and green outer ring and trebled in the middle ring; a dart outside the outer ring scores zero. At the centre, the outer bull is worth $25$ points and the inner bull, which is a double, is worth $50$. A player throws three darts per turn, starting from a score such as $301$ or $501$ that must be brought down to exactly zero. Under the "doubles out" rule the final dart must land in a double, the inner bull included, and any other dart that would leave one or less makes that set of three darts "bust". Finishing on the current score is called a checkout; the highest one is $170$, $\mathtt{T20\ T20\ D25}$, where $\mathtt S$, $\mathtt D$ and $\mathtt T$ stand for single, double and treble and $\mathtt{D25}$ is the inner bull. Misses are not counted, so $\mathtt{D3}$, $\mathtt{0\ D3}$ and $\mathtt{0\ 0\ D3}$ are the same checkout; $\mathtt{S1\ T1\ D1}$ and $\mathtt{T1\ S1\ D1}$ are also the same; but $\mathtt{D1\ D2}$ and $\mathtt{D2\ D1}$ are different, because they finish on different doubles. There are exactly $11$ checkouts on a score of $6$ and $42336$ checkouts in total, and we must find the number of distinct checkouts with a score less than $100$. ^[1]

The whole solution in one sentence: a checkout is just a final double together with an unordered choice of at most two earlier scoring regions, repetitions allowed, so there are only $42336$ checkouts in all, and we list them and count those whose darts add up to less than $100$.

Mathematical Approach

We first turn the rules into an exact description of a checkout and count all checkouts with one formula. Then we count the checkouts below a limit in three ways: by simulating the throws, with the loops of the programs, and with generating functions.

1. Sixty-two regions

A dart that does not miss lands in one of $62$ scoring regions of the standard board: ^[2] the singles $\mathtt{S1},\dots,\mathtt{S20}$, worth $1$ to $20$; the doubles $\mathtt{D1},\dots,\mathtt{D20}$, worth $2,4,\dots,40$; the trebles $\mathtt{T1},\dots,\mathtt{T20}$, worth $3,6,\dots,60$; the outer bull, written $\mathtt{S25}$, worth $25$; and the inner bull $\mathtt{D25}$, worth $50$. There is no treble bull. The treble ring splits the single area of each number in two, but both parts carry the same label, such as $\mathtt{S5}$, and count as one region, as the statement's count confirms: $82$ separate areas would give $22$ checkouts on $6$, not $11$. A checkout ends in one of the $21$ doubles $\mathtt{D1},\dots,\mathtt{D20}$ and $\mathtt{D25}$. We write $v(a)$ for the score of a region $a$.

Different regions can share a score: $6$ is the score of $\mathtt{S6}$, $\mathtt{D3}$ and $\mathtt{T2}$. The $62$ regions take $43$ different scores: $27$ scores belong to one region, $13$ to two regions, such as $2$ to $\mathtt{S2}$ and $\mathtt{D1}$, and $6$, $12$ and $18$ to three regions each; indeed $27+2\cdot13+3\cdot3=62$.

2. The eleven checkouts on $6$

Let us find the eleven checkouts on $6$ of the statement by hand, writing the darts thrown before the last one in braces, because their order does not matter. The final double is $\mathtt{D1}$, $\mathtt{D2}$ or $\mathtt{D3}$, so the earlier darts must make up $4$, $2$ or $0$ points.

$\mathtt{D3}$: no earlier dart, $1$ checkout.
$\mathtt{D2}$: one dart $\mathtt{S2}$ or $\mathtt{D1}$, or the two darts $\{\mathtt{S1},\mathtt{S1}\}$, $3$ checkouts.
$\mathtt{D1}$: one dart $\mathtt{S4}$ or $\mathtt{D2}$; two darts worth $1$ and $3$, that is $\{\mathtt{S1},\mathtt{S3}\}$ or $\{\mathtt{S1},\mathtt{T1}\}$; or two darts worth $2$, taken from $\mathtt{S2}$ and $\mathtt{D1}$, that is $\{\mathtt{S2},\mathtt{S2}\}$, $\{\mathtt{S2},\mathtt{D1}\}$ or $\{\mathtt{D1},\mathtt{D1}\}$. This gives $2+2+3=7$ checkouts.

Altogether $1+3+7=11$, exactly the list of the statement. The last group shows that regions count, not scores, and that order does not: $\mathtt{S3}$ and $\mathtt{T1}$ are different regions, so $\{\mathtt{S1},\mathtt{S3}\}$ and $\{\mathtt{S1},\mathtt{T1}\}$ are different checkouts, while $\{\mathtt{S2},\mathtt{D1}\}$ and $\{\mathtt{D1},\mathtt{S2}\}$ are the same, so two darts worth $2$ can be chosen in three ways, not four.

3. What a checkout really is

In general, by the rules of the statement, misses are left out, the darts before the last one may be swapped, and the last dart keeps its special place. So a checkout is described exactly by its final double $d$ and the darts thrown before it, with the misses removed and their order forgotten. These earlier darts may repeat a region, as in $\mathtt{D1\ D1\ D1}$, so they form a multiset: a collection in which order does not matter but an element may occur more than once. ^[3] We write a checkout as a pair: $\mathtt{S1\ T1\ D1}$ is $(\{\mathtt{S1},\mathtt{T1}\},\mathtt{D1})$, and $\mathtt{D3}$ is $(\emptyset,\mathtt{D3})$ with the empty multiset $\emptyset$. A checkout with one, two or three darts has a multiset $M$ of size $0$, $1$ or $2$, and its score is $v(M)+v(d)$, where $v(M)$ is the sum of the scores in $M$.

4. The bust rule never gets in the way

Could the bust rule forbid some of these pairs? An earlier dart must not leave $1$ or less. But after each earlier dart, the darts still to come, the final double among them, must score exactly what is left, so at least $v(d)\ge2$ is left; and the final double brings the total to exactly $0$, as the rule demands. So every pair $(M,d)$, with $M$ a multiset of at most two regions and $d$ one of the $21$ doubles, is a legal checkout of the score $v(M)+v(d)$, and by Section 3 different pairs are different checkouts. We write $c(s)$ for the number of checkouts on exactly $s$ and $C(L)$ for the number of checkouts on a score below $L$; the question asks for $C(100)$.

5. All checkouts at once

Without the score limit there is a short formula. Treat a miss as a sixty-third symbol $\mathtt 0$ worth nothing, and fill the multiset of earlier darts up with misses to exactly two elements: $\{\mathtt{S1}\}$ becomes $\{\mathtt{S1},\mathtt 0\}$, and $\emptyset$ becomes $\{\mathtt 0,\mathtt 0\}$. Removing the misses undoes this, so the multisets of at most two regions correspond one to one to the multisets of exactly two of the $63$ symbols. The number of multisets of size $k$ taken from $n$ symbols is the multiset coefficient $\binom{n+k-1}{k}$. ^[3] For $k=2$ this is easy to see: a multiset of two symbols repeats one symbol, in $n$ ways, or uses two different ones, in $\binom n2$ ways, and $n+\binom n2=\binom{n+1}{2}$. With $n=63$ and $21$ final doubles there are

$$21\cdot\binom{64}{2}=21\cdot2016=42336$$

checkouts, the total of the statement: $21$ with one dart, $62\cdot21=1302$ with two and $1953\cdot21=41013$ with three, where $1953=62+\binom{62}{2}$ counts the pairs of a region with itself and the pairs of two different regions.

6. First method: simulating the throws

The most direct count follows the statement throw by throw. Each of the first two darts is a miss or one of the $62$ regions, and the third is one of the $21$ doubles, so there are $63\cdot63\cdot21=83349$ ordered throws. For each we form a canonical key: we drop the misses, sort the names of the remaining earlier darts and attach the final double. For example, $(\mathtt{T1},\mathtt{S1},\mathtt{D1})$ and $(\mathtt{S1},\mathtt{T1},\mathtt{D1})$ get the same key $(\{\mathtt{S1},\mathtt{T1}\},\mathtt{D1})$. By Section 3 two throws are the same checkout exactly when their keys agree, so the checkouts are the distinct keys; a set of all keys indeed ends up with $42336$ elements, and the keys with a total below $L$ give $C(L)$. The method needs no bust test, by Section 4, and otherwise only the definitions of Section 3, so it is a good independent check of the faster methods.

7. Second method: three loops over the regions

Number the regions $a_1,\dots,a_{62}$ in any fixed order, write $v_i=v(a_i)$, and let $[Q]$ be $1$ when the condition $Q$ holds and $0$ otherwise. By Section 4,

$$\begin{aligned}&C(L)=\sum_{d}\,[v(d)\lt L]\\&\quad+\sum_{i}\sum_{d}\,[v_i+v(d)\lt L]\\&\quad+\sum_{i\le j}\sum_{d}\,[v_i+v_j+v(d)\lt L],\end{aligned}$$

where $d$ runs over the $21$ doubles and $i$ and $j$ over $1,\dots,62$. The three lines count the checkouts with one, two and three darts. The condition $i\le j$ makes the first two darts unordered: a multiset of two different regions appears once, with the smaller index first, and a repeated region once, with $i=j$; ordered pairs would count $\{\mathtt{S1},\mathtt{T1}\}$ twice but $\{\mathtt{D1},\mathtt{D1}\}$ once. The three sums have $21+1302+41013=42336$ terms, one for each checkout. The three programs evaluate exactly this formula.

8. Third method: generating functions

A third method counts the checkouts of every score at once. Let $r(w)$ be the number of regions worth $w$, and store these numbers in one polynomial, the generating function of the regions: ^[4]

$$\begin{aligned}A(x)&=\sum_{a}x^{v(a)}=\sum_{w}r(w)\,x^w\\&=x+2x^2+2x^3+2x^4\\&\quad+x^5+3x^6+\dots\end{aligned}$$

The coefficient of $x^w$, the number in front of it, counts the regions worth $w$, for example three for $6$. To read off a count we never need a value of $x$: its exponents carry the scores and its coefficients the counts. The point is that multiplication adds scores, because $x^m\cdot x^n=x^{m+n}$: multiplying out $A(x)\cdot A(x)$ gives one term $x^{v(a)+v(b)}$ for every ordered pair of regions $(a,b)$, so the coefficient of $x^t$ in $A(x)^2$ counts the ordered pairs with total $t$. ^[4] The doubles have the generating function $F(x)=x^2+x^4+\dots+x^{40}+x^{50}$, so the two-dart checkouts are counted by $A(x)\,F(x)$.

9. Counting each unordered pair once

The three-dart checkouts need unordered pairs. In $A(x)^2$ the pair $\{\mathtt{S1},\mathtt{T1}\}$ appears twice, as $(\mathtt{S1},\mathtt{T1})$ and $(\mathtt{T1},\mathtt{S1})$, but $\{\mathtt{D1},\mathtt{D1}\}$ only once, so halving $A(x)^2$ would count the repeated pairs only half. A repeated pair $\{a,a\}$ is worth $2v(a)$, so the repeated pairs are counted by $A(x^2)=\sum_w r(w)\,x^{2w}$. Adding it gives every unordered pair exactly two copies, so

$$\frac{A(x)^2+A(x^2)}{2}$$

counts every multiset of two regions once, by its total. For example, the coefficient of $x^4$ is $r(1)r(3)+r(2)r(2)+r(3)r(1)$${}=8$ in $A(x)^2$ and $r(2)=2$ in $A(x^2)$, and half of $8+2$ is $5$: the pairs $\{\mathtt{S1},\mathtt{S3}\}$, $\{\mathtt{S1},\mathtt{T1}\}$, $\{\mathtt{S2},\mathtt{S2}\}$, $\{\mathtt{S2},\mathtt{D1}\}$ and $\{\mathtt{D1},\mathtt{D1}\}$ of Section 2.

This is the simplest case of Burnside's lemma: the number of essentially different objects, where objects that a symmetry turns into each other count as one, is the average over the symmetries of the number of objects that each symmetry leaves unchanged. ^[5] Here doing nothing leaves all ordered pairs unchanged, counted by $A(x)^2$, and swapping the two darts leaves only the pairs $(a,a)$, counted by $A(x^2)$. Since a swap keeps the total, the lemma applies to the pairs of each total $t$ separately, which gives the coefficients of the formula above. With the empty multiset, counted by $1$, the multisets of one earlier dart, counted by $A(x)$, and a final double, the checkouts are counted by

$$P(x)=1+A(x)+\frac{A(x)^2+A(x^2)}{2},$$

$$K(x)=F(x)\,P(x).$$

At $x=1$ every power of $x$ becomes $1$, so a polynomial turns into the sum of its coefficients: $P(1)=1+62+(3844+62)/2$${}=2016$ and $K(1)=21\cdot2016=42336$, as in Section 5. With the miss as a term $x^0=1$, that is with $B(x)=1+A(x)$, the polynomial $P(x)$ equals $\bigl(B(x)^2+B(x^2)\bigr)/2$, because $B(x)^2+B(x^2)$ is $2+2A(x)+A(x)^2+A(x^2)$. The coefficient $c(s)$ of $x^s$ in $K(x)$ counts the checkouts on $s$, and $C(L)=c(0)+\dots+c(L-1)$ is the coefficient of $x^{L-1}$ in $K(x)/(1-x)$, because multiplying by $1/(1-x)=1+x+x^2+\dots$ turns a sequence into its partial sums. ^[4]

10. Worked example: the first coefficients

Let $p(t)$ be the coefficient of $x^t$ in $P(x)$, the number of multisets of at most two regions with total $t$. For $t=4$ there are the one-dart multisets $\{\mathtt{S4}\}$ and $\{\mathtt{D2}\}$ and the $5$ pairs above, so $p(4)=7$. For $t=0,1,\dots,10$ the values are $1, 1, 3, 4, 7, 7,$ $11, 10, 14, 14, 17$. Multiplying by $F(x)$ shifts $P(x)$ by the score of each double, so $c(s)$ is the sum of $p\bigl(s-v(d)\bigr)$ over the doubles $d$ worth at most $s$; for example $c(6)=p(4)+p(2)+p(0)$${}=7+3+1=11$, the three groups of Section 2. For $s=2,3,\dots,12$ the counts are $1, 1, 4, 5, 11, 12,$ $22, 22, 36, 36, 53$, and their partial sums give $C(3)=1$, $C(4)=2$, $C(5)=6$, $C(6)=11$, $C(7)=22$ and $C(8)=34$.

The checkouts below $6$ are $\mathtt{D1}$; $\mathtt{S1\ D1}$; $\mathtt{D2}$, $\mathtt{S2\ D1}$, $\mathtt{D1\ D1}$, $\mathtt{S1\ S1\ D1}$; and $\mathtt{S3\ D1}$, $\mathtt{T1\ D1}$, $\mathtt{S1\ D2}$, $\mathtt{S1\ S2\ D1}$, $\mathtt{S1\ D1\ D1}$, that is $1+1+4+5=11$. It is a coincidence that there are exactly as many checkouts on $6$: one step further, $C(7)=22$ but $c(7)=12$. This coincidence matters for the check in the C++ program.

11. The top of the board

No checkout scores more than $60+60+50=170$, and $\mathtt{T20\ T20\ D25}$ is the only checkout on $170$, so $C(L)=42336$ for every $L\ge171$. The scores from $159$ to $170$ can be settled by hand. A final double other than $\mathtt{D25}$ allows at most $60+60+40=160$. With $\mathtt{D25}$, a score $s\ge159$ needs two earlier darts worth $s-50\ge109$ together, so each of them is worth at least $109-60=49$. Only five region scores are that large, $50$, $51$, $54$, $57$ and $60$, and the totals of two of them that reach $109$ are just $110$, $111$, $114$, $117$ and $120$. So in this range $\mathtt{D25}$ finishes exactly $160$, $161$, $164$, $167$ and $170$; $167$, for example, has only one checkout, $\mathtt{T19\ T20\ D25}$, while $169$ would need $119=60+59$, and no region is worth $59$. Without $\mathtt{D25}$ only $159$ and $160$ come into question, and for $159$ the double $\mathtt{D20}$ leaves the same impossible $119$, while a smaller double leaves more than the $120$ that two darts can score. Hence $159$, $162$, $163$, $165$, $166$, $168$ and $169$ have no checkout. Every score from $2$ to $158$ has at least one, as the coefficients of $K(x)$ show, so the $42336$ checkouts are spread over $157+5=162$ scores.

12. Pitfalls

Each rule of Section 3 matters, and each mistake already shows for the score $6$, whose $11$ checkouts the statement lists:

ordered first darts count $\{\mathtt{S1},\mathtt{S3}\}$, $\{\mathtt{S1},\mathtt{T1}\}$ and $\{\mathtt{S2},\mathtt{D1}\}$ twice: $14$ checkouts on $6$, and $82047$ in total instead of $42336$;
counting scores instead of regions merges $\mathtt{S3}$ with $\mathtt{T1}$, $\mathtt{S2}$ with $\mathtt{D1}$ and $\mathtt{S4}$ with $\mathtt{D2}$: $6$ checkouts on $6$, and $20790$ in total;
counting misses makes $\mathtt{D3}$, $\mathtt{0\ D3}$ and $\mathtt{0\ 0\ D3}$ three checkouts: $17$ on $6$, and $43680$ in total.

Finally, "less than $100$" excludes $100$ itself: for the limit $6$, including the score $6$ would give $C(7)=22$ instead of $C(6)=11$.

13. More darts

The padding of Section 5 works for any number of darts. If a checkout may use up to $k$ darts, the earlier darts form a multiset of exactly $k-1$ of the $63$ symbols, and there are

$$21\binom{61+k}{k-1}$$

checkouts: $21$, $1323$, $42336$ and $917280$ for $k=1,2,3,4$. On a board with $R$ regions and $D$ doubles the three-dart count is $D\binom{R+2}{2}$.

For $k=4$ the counts by score follow from Burnside's lemma as in Section 9, now with the six orders of three padded earlier darts. Keeping the order leaves every ordered triple unchanged, counted by $B(x)^3$; each of the three swaps of two darts leaves the triples in which those two darts are equal, counted by $B(x)B(x^2)$; and each of the two rotations, which move every dart one place on, leaves only three equal darts, counted by $B(x^3)$. The average over the six orders,

$$\begin{aligned}P_3(x)={}&\frac{1}{6}\bigl(B(x)^3+3B(x)B(x^2)\\&\qquad+2B(x^3)\bigr),\end{aligned}$$

counts the multisets of three padded darts by their total, and at $x=1$ the product $F(x)\,P_3(x)$ gives $21\binom{65}{3}=917280$, the count above. Pólya's enumeration theorem writes this average as the cycle index $(t_1^3+3t_1t_2+2t_3)/6$ of the six orders, with $B(x^k)$ in place of $t_k$: each order contributes one factor $t_k$ for every cycle of $k$ darts that it moves round, a dart kept in place being a cycle of length $1$. ^[6]

How the Code Works

The C++ program ^[7] starts in main, which reads the options into an Options record with parse_arguments. The limit is $100$ unless --limit=N gives another one, read by parse_int_after_prefix as a nonempty string of decimal digits, and --skip-checkpoints turns off the check. Any other argument, or a limit below $2$, ends the program with exit code $1$. The digits are not range-checked, so a limit too large for an int overflows, which C++ leaves undefined.

The counting is done by solve(limit). It calls all_nonfinal_throws, which builds the $62$ regions of Section 1 as Throw records of a label such as T20 and a score, the single, double and treble of every number from $1$ to $20$ followed by S25 and D25, and final_doubles, which builds the $21$ doubles; only the scores are used. Then it evaluates the formula of Section 7 in three passes: the doubles below the limit, every region in front of every double, and every pair of indices $i\le j$ of the region list, with an inner loop that starts at the current index $i$, in front of every double. Each candidate below the limit adds $1$ to an int counter.

Before the real count, run_checkpoints checks that solve(6) returns $11$, and otherwise the program stops with exit code $2$; then main prints solve for the chosen limit. The eleven checkouts of the statement are those on exactly $6$, while solve(6) counts those on the scores $2$ to $5$. By the coincidence of Section 10 both numbers are $11$, so the check passes, but it tests a different list from the statement's, which is counted by solve(7) minus solve(6).

The Python program does the same inside one function solve, with the singles, $\mathtt{S25}$ included, the doubles, $\mathtt{D25}$ included, and the trebles joined into all_throws, a list of label and score pairs, and with the fixed limit $100$. The Java program does everything in main: it builds singles, doubles and trebles as arrays of one-element int arrays, copies their $62$ scores into the array all and runs the same loops. It stores no labels, but equal scores stay at different indices, so $\mathtt{S2}$ and $\mathtt{D1}$ are two entries worth $2$: the loops count regions, not scores, and avoid the second pitfall of Section 12. Neither program has options or a check, and their different region order does not matter, since $i\le j$ lists every multiset once in any fixed order. The counter is an int in C++, which has 32 bits on all common platforms, a 32-bit int in Java and an integer of unlimited size in Python; since no score sum exceeds $170$ and no count exceeds $42336$, all three compute the counts exactly.

Complexity and Verification

The programs test all $42336$ candidates, one for every checkout, even when the limit lets only a few of them count; each test takes at most two additions and one comparison, and the C++ program does all this once more for its check. For $R$ regions and $D$ doubles there are $D\bigl(1+R+R(R+1)/2\bigr)$ tests, which grows like $DR^2$, and the memory, a few short lists of regions and doubles (two in C++, four in Python and Java), is proportional to $R+D$. In tests on a desktop computer each program finished within a few hundredths of a second, mostly start-up time. The generating functions depend on the range of scores, not on the number of checkouts: squaring $B(x)$, which has $44$ terms, takes $1936$ multiplications, and multiplying $P(x)$, which has $112$ nonzero coefficients, by $F(x)$ takes $2352$ more, after which every $C(L)$ is a partial sum.

The only check in the published code is the C++ check with the limit $6$. For this article the three methods were programmed separately; they agree on $C(L)$ for every limit from $0$ to $200$ and confirm every number above, among them the scores without a checkout and the counts of Section 12. A test of all $42336$ checkouts confirms that no earlier dart leaves less than $2$, and a brute force over all multisets of two and of three padded darts confirms the polynomials of Sections 9 and 13. The three published programs print the same number, equal to the number of canonical keys with a total below $100$, and the C++ option --limit gives $0, 1, 2, 6, 11, 22, 34$ for the limits $2,\dots,8$ and $42336$ for the limits $171$ and $1000$; in particular solve(7) minus solve(6) is the $11$ of the statement.

Footnotes and References

The references below supply the background facts used above. The description of a checkout as a multiset and a final double, the counts and the polynomial $K(x)$ are derived explicitly in this article.

Project Euler 109 — Darts. The official statement describes the board and the doubles-out rule with its bust condition, lists the eleven checkouts on a score of 6, explains when two checkouts count as the same, states that there are 42336 checkouts in total, and asks for the number of distinct checkouts with a score less than 100.
Wikipedia — Darts. The standard board has 20 numbered sections scoring 1 to 20, with double and treble rings, an outer bull worth 25 and an inner bull worth 50 that counts as a double; a game of 301 or 501 must end on exactly zero with a final dart in a double or the bullseye, and the highest finish with three darts is 170 (T20, T20, inner bull).
Wikipedia — Multiset. A multiset allows several instances of each element, and the order of its elements does not matter; the number of multisets of cardinality k with elements from a set of cardinality n is the multiset coefficient, which equals the binomial coefficient n + k − 1 choose k.
Wikipedia — Generating function. A generating function represents a sequence as the coefficients of a formal power series; multiplying ordinary generating functions gives the convolution of the sequences, and multiplying by 1/(1 − x) gives the partial sums.
Wikipedia — Burnside's lemma. The number of orbits of a group acting on a set equals the average number of points fixed by the elements of the group.
Wikipedia — Pólya enumeration theorem. Substituting f(t^k) for t_k in the cycle index, the average over the group of products with one t_k for each cycle of length k, gives the generating function of the colourings up to symmetry; the simplified form follows from Burnside's lemma, and for the three children of a node of a rooted ternary tree the page uses the cycle index (t₁³ + 3t₁t₂ + 2t₃)/6 of S₃.
C++ — Euler109.cpp. The linked immutable C++ revision contains all_nonfinal_throws, final_doubles, solve, run_checkpoints and the options --limit and --skip-checkpoints. It is the implementation record for this article.

Problem 109 source code

C++

#include <iostream>
#include <string>
#include <vector>

namespace {

struct Options {
    int limit = 100;
    bool run_checkpoints = true;
};

struct Throw {
    std::string label;
    int score = 0;
};

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, "--limit=", options.limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.limit >= 2;
}

std::vector<Throw> all_nonfinal_throws() {
    std::vector<Throw> out;
    out.reserve(62);

    for (int n = 1; n <= 20; ++n) {
        out.push_back({"S" + std::to_string(n), n});
        out.push_back({"D" + std::to_string(n), 2 * n});
        out.push_back({"T" + std::to_string(n), 3 * n});
    }

    out.push_back({"S25", 25});
    out.push_back({"D25", 50});
    return out;
}

std::vector<Throw> final_doubles() {
    std::vector<Throw> out;
    out.reserve(21);

    for (int n = 1; n <= 20; ++n) {
        out.push_back({"D" + std::to_string(n), 2 * n});
    }
    out.push_back({"D25", 50});
    return out;
}

int solve(const int limit) {
    const std::vector<Throw> first_throws = all_nonfinal_throws();
    const std::vector<Throw> doubles = final_doubles();

    int count = 0;

    for (const Throw& d : doubles) {
        if (d.score < limit) {
            ++count;
        }
    }

    for (const Throw& a : first_throws) {
        for (const Throw& d : doubles) {
            if (a.score + d.score < limit) {
                ++count;
            }
        }
    }

    for (std::size_t i = 0; i < first_throws.size(); ++i) {
        for (std::size_t j = i; j < first_throws.size(); ++j) {
            const int first_two = first_throws[i].score + first_throws[j].score;
            for (const Throw& d : doubles) {
                if (first_two + d.score < limit) {
                    ++count;
                }
            }
        }
    }

    return count;
}

bool run_checkpoints() {
    if (solve(6) != 11) {
        std::cerr << "Checkpoint failed for limit=6" << '\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.limit) << '\n';
    return 0;
}

Python

# Problem 109: Darts
# How many distinct ways can a player check out with a score less than 100?

def solve():
    singles = [(f"S{i}", i) for i in range(1, 21)] + [("S25", 25)]
    doubles = [(f"D{i}", 2*i) for i in range(1, 21)] + [("D25", 50)]
    trebles = [(f"T{i}", 3*i) for i in range(1, 21)]
    
    all_throws = singles + doubles + trebles
    limit = 100
    count = 0
    
    # Checkout with just a double
    for _, d in doubles:
        if d < limit:
            count += 1
    
    # One throw + double
    for _, a in all_throws:
        for _, d in doubles:
            if a + d < limit:
                count += 1
    
    # Two throws + double (unordered first two)
    for i in range(len(all_throws)):
        for j in range(i, len(all_throws)):
            for _, d in doubles:
                if all_throws[i][1] + all_throws[j][1] + d < limit:
                    count += 1
    
    print(count)

solve()

Java

public class Euler109 {
    public static void main(String[] args) {
        int[][] singles = new int[21][1];
        for (int i = 1; i <= 20; i++)
            singles[i - 1] = new int[] { i };
        singles[20] = new int[] { 25 };
        int[][] doubles = new int[21][1];
        for (int i = 1; i <= 20; i++)
            doubles[i - 1] = new int[] { 2 * i };
        doubles[20] = new int[] { 50 };
        int[][] trebles = new int[20][1];
        for (int i = 1; i <= 20; i++)
            trebles[i - 1] = new int[] { 3 * i };
        int[] all = new int[62];
        int idx = 0;
        for (int[] s : singles)
            all[idx++] = s[0];
        for (int[] d : doubles)
            all[idx++] = d[0];
        for (int[] t : trebles)
            all[idx++] = t[0];
        int limit = 100, count = 0;
        for (int[] d : doubles)
            if (d[0] < limit)
                count++;
        for (int a : all)
            for (int[] d : doubles)
                if (a + d[0] < limit)
                    count++;
        for (int i = 0; i < all.length; i++)
            for (int j = i; j < all.length; j++)
                for (int[] d : doubles)
                    if (all[i] + all[j] + d[0] < limit)
                        count++;
        System.out.println(count);
    }
}