Finding a new sort o… on How big is a square? Alex on Wandrer.earth Paul Toigo on Everyone’s tiles on one… lupoeagle on Everyone’s tiles on one… Jon France on Project Thames Crossings

 Finding a new sort o… on How big is a square? Alex on Wandrer.earth Paul Toigo on Everyone’s tiles on one… lupoeagle on Everyone’s tiles on one… Jon France on Project Thames Crossings

# Number of ways to get a nine-dart finish

Off-topic post.

Just as I am gearing to watch the wonder that is the 2018 World Darts, I noticed this puzzle on 538

“In competitive darts, a player starts with 501 points and subtracts the score of each throw. He or she must finish with exactly zero points. (Also, per the rules, the final dart must land in either the bullseye or the outer, doubled segments.) What is the minimum number of throws? How many different ways are there to do it?”

The first part is very easy – the maximum with any one dart is 60 points. Therefore the maximum with eight darts is 480 points, so you can’t score 501 in eight darts or fewer. The combination T20, T20, T20, T20, T20, T20, T20, T19, D12 shows it can be done in nine darts, so this is the minimum. But how many ways are there?

We know the last dart must be a double or bullseye. Call this last value D. Then the first 8 darts must equal 501-D. As above the first 8 darts are worth at most 480 points, so 501 – D <= 480. I.e. D >= 21. Thus the possible  ninth darts are:

[Bull, D20, D19, D18, D17, D16, D15, D14, D13, D12, D11]

So for each of these last darts, we must find how the number of combinations of the first 8 darts give the right score and then add these up to get the total number of combinations.

To prune the search space, note the least possible value of the eight darts is 501-50 = 451 and the most possible value of seven darts is 7*60=420, so at the absolute least each of the first eight dart must be worth at least 451-420=31 points. There is no way to get 31 points (31 is prime) so in fact every dart must be worth 32 points. This leaves the following set of possible darts to consider for the first eight darts:

C = [T20, T19, T18, T17, Bull, T16, T15, T14, D20, T13, D19, D18, T12, D17, T11, D16]

Noting that C is descending numerical order, my recursive algorithm was as follows:

• Maintain an index into this “consideration array”, C
• Maintain a remaining target T and remaining number of darts R
• Maintain a stack starting empty
• T starts at 501-D and R starts at 8
• The next value is C[i].
• if R == 1 and T == C[i] we have found a solution and the stack consists of the darts we need (plus the ninth dart recorded separately)
• Otherwise If T- C[i] > 0 and R >= 2, then C[i] is potentially part of the solutoin for the current stack, so recurse with T -> T-C[i], R -> R-1, i staying the same, and append C[i] to the stack
• Otherwise if i < 8 and if C[i+1] * R >= target (i.e. the remaining numbers are big enough to potentially reach the target – this bit relying on the ordering of C), then recurse with T -> T, R->R, i -> i+1 and keeping the same stack.

The algorithm starts with T = 501-D, R=8, i=0 and the stack empty.

Running the algorithm, this way we get all possible solutions, not accounting for re-ordering. Naively there are 8! = 5040 different ways to re-order 8 darts, but if the same dart appears k times in the solution, then the same solution is appearing k! times in this set. In fact each solution can be ordered in  8 Choose{k_1,…k_r} ways where k_i is the number of times a particular dart appears in the solution (i.e. this is just the usual multinomial coefficient formula for counting re-arrangements).

I was taken aback by just quickly these recursive algorithm ran when implemented as a simple Python program. Here are the results:

```[T20, T20, T20, T20, T20, T20, T19, D17] , BUL (56 ways)
[T20, T20, T20, T20, T20, T20, T17, D20] , BUL (56 ways)
[T20, T20, T20, T20, T20, T19, T18, D20] , BUL (336 ways)
[T20, T20, T20, T20, T20, T17, BUL, BUL] , BUL (168 ways)
[T20, T20, T20, T20, T19, T19, T19, D20] , BUL (280 ways)
[T20, T20, T20, T20, T19, T18, BUL, BUL] , BUL (840 ways)
[T20, T20, T20, T19, T19, T19, BUL, BUL] , BUL (560 ways)
[T20, T20, T20, T20, T20, T20, T17, BUL] , D20 (56 ways)
[T20, T20, T20, T20, T20, T19, T18, BUL] , D20 (336 ways)
[T20, T20, T20, T20, T19, T19, T19, BUL] , D20 (280 ways)
[T20, T20, T20, T20, T20, T20, T20, T15] , D18 (8 ways)
[T20, T20, T20, T20, T20, T20, T19, T16] , D18 (56 ways)
[T20, T20, T20, T20, T20, T20, T18, T17] , D18 (56 ways)
[T20, T20, T20, T20, T20, T19, T19, T17] , D18 (168 ways)
[T20, T20, T20, T20, T20, T19, T18, T18] , D18 (168 ways)
[T20, T20, T20, T20, T19, T19, T19, T18] , D18 (280 ways)
[T20, T20, T20, T19, T19, T19, T19, T19] , D18 (56 ways)
[T20, T20, T20, T20, T20, T20, T19, BUL] , D17 (56 ways)
[T20, T20, T20, T20, T20, T20, T20, T17] , D15 (8 ways)
[T20, T20, T20, T20, T20, T20, T19, T18] , D15 (56 ways)
[T20, T20, T20, T20, T20, T19, T19, T19] , D15 (56 ways)
[T20, T20, T20, T20, T20, T20, T20, T19] , D12 (8 ways)```

Adding them up, there are a grand total of 3944 ways to do a nine-darter… even Phil Taylor hasn’t done all of those!