Detailed mathematical approach

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. A shorter checkout is already represented by choosing fewer preliminary darts, so explicit misses would duplicate cases rather than create new ones.

Translate the rules into one counting formula

Write \(A=\{a_1,\dots,a_{62}\}\). For a score limit \(L\), every valid checkout is counted exactly once by

$C(L)=\sum_{d\in F}\mathbf{1}\bigl(v(d)\lt L\bigr)+\sum_{i=1}^{62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(d)\lt L\bigr)+\sum_{1\le i\le j\le 62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(a_j)+v(d)\lt L\bigr).$

Here \(\mathbf{1}(\cdot)\) is the indicator function: it contributes \(1\) when the inequality is true and \(0\) otherwise. The condition \(i\le j\) is exactly the mathematical statement that the first two darts are unordered, while repetition such as \(\{D1,D1\}\) is still allowed.

What the score cap filters out

Before imposing the bound \(L=100\), the total number of formal checkout patterns is easy to compute. There are \(21\) one-dart finishes, \(62\cdot 21\) two-dart finishes, and

$\binom{62+1}{2}\cdot 21=\binom{63}{2}\cdot 21$

three-dart finishes, because the first two darts form a two-element multiset chosen from \(62\) region types. Therefore the unrestricted search space has

$21+62\cdot 21+\binom{63}{2}\cdot 21=42336$

distinct formal checkouts. The actual Project Euler task is simply the subset of these patterns whose total score is below \(100\).

Worked Example: why the limit \(6\) gives \(11\)

A good sanity check is \(L=6\). Only \(D1\) and \(D2\) can be finishing doubles, because \(D3=6\) already fails the strict inequality.

If the checkout ends on \(D1\), the preliminary darts must total less than \(4\). That gives one empty preliminary multiset, five one-dart choices \((S1,S2,D1,S3,T1)\), and three two-dart multisets \(\{S1,S1\}\), \(\{S1,S2\}\), and \(\{S1,D1\}\). So finishes ending on \(D1\) contribute \(1+5+3=9\) checkouts.

If the checkout ends on \(D2\), the preliminary darts must total less than \(2\). The only possibilities are the empty multiset and the single dart \(S1\), so finishes ending on \(D2\) contribute \(2\) more checkouts. Hence

$C(6)=9+2=11.$

This example also shows why region identity matters: \(S3\) and \(T1\) both score \(3\), but they remain distinct checkouts when followed by \(D1\).

How the Code Works

The C++, Python, and Java implementations first construct the two lists dictated by the mathematics: the \(62\) legal non-final regions and the \(21\) legal finishing doubles. Each entry stores both a label and its numerical score, so later checks are simple additions and comparisons.

They then perform three passes that match the three terms in the formula. The first counts one-dart finishes. The second pairs every non-final region with every finishing double. The third enumerates two preliminary darts as an unordered pair by starting the second loop at the current position of the first, which keeps repetitions while avoiding double-counting from swapped order.

Every candidate pattern is accepted exactly when its total is strictly less than the limit. The C++ implementation exposes that limit as a parameter and verifies the smaller case \(L=6\); the Python and Java implementations evaluate the same enumeration directly for \(L=100\).

Complexity Analysis

The candidate space is tiny. There are \(21\) one-dart cases, \(62\cdot 21=1302\) two-dart cases, and \(\binom{63}{2}\cdot 21=41013\) three-dart cases, for a total of \(42336\) candidates before filtering. That is why direct enumeration is not merely acceptable here; it is the natural exact method.

In generalized notation the runtime is \(O(|F|\cdot |A|^2)\), dominated by the unordered two-preliminary-dart sweep. Memory usage is \(O(|A|+|F|)\) for the two region lists, which is constant for the fixed dartboard in the problem.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=109
2. Darts: Wikipedia - Darts
3. Dartboard: Wikipedia - Dartboard
4. 501 and double-out play: Wikipedia - 501 (darts)
5. Multisets and combinations with repetition: Wikipedia - Multiset