Euler Problem 109

Euler Problem 109 asks:

In the game of darts a player throws three darts at a target board which is split into twenty equal sized sections numbered one to twenty.

The score of a dart is determined by the number of the region that the dart lands in. A dart landing outside the red/green outer ring scores zero. The black and cream regions inside this ring represent single Darts. However, the red/green outer ring and middle ring score double and treble scores respectively.

At the centre of the board are two concentric circles called the bull region, or bulls-eye. The outer bull is worth 25 points and the inner bull is a double, worth 50 points.

There are many variations of rules but in the most popular game the players will begin with a score 301 or 501 and the first player to reduce their running total to zero is a winner. However, it is normal to play a “doubles out” system, which means that the player must land a double (including the double bulls-eye at the centre of the board) on their final dart to win; any other dart that would reduce their running total to one or lower means the score for that set of three darts is “bust”.

When a player is able to finish on their current score it is called a “checkout” and the highest checkout is 170: T20 T20 D25 (two treble 20s and double bull).

There are exactly eleven distinct ways to checkout on a score of 6:

D1 D2
S2 D2
D2 D1
S4 D1
S1 S1 D2
S1 T1 D1
S1 S3 D1
D1 D1 D1
D1 S2 D1
S2 S2 D1

Note that D1 D2 is considered different to D2 D1 as they finish on different doubles. However, the combination S1 T1 D1 is considered the same as T1 S1 D1.

In addition we shall not include misses in considering combinations; for example, D3 is the same as 0 D3 and 0 0 D3.

Incredibly there are 42336 distinct ways of checking out in total.

How many distinct ways can a player checkout with a score less than 100?

If you’ve never “done darts,” this is the hard way to learn the rules. I did darts often in a Scot pub (I was “pretty good for a Yank”–damning with faint praise) so I had a good understanding of the game. A dart board has 20 spokes, worth from 1 to 20 points, an inner hub worth 50 points (the bull’s eye), an outer hub worth 25 points, a midway ring worth triple the spoke score, and an outer rim worth double the spoke score. Very good players countdown from 501, but the pub matches started down from 301. To win, your last dart had to land in the double ring and take you exactly to zero. Too high a value, or a reduction to one, and your turn was wasted.

A good picture of a dart board and the 3-dart “double-outs” is here.

The one tricky thing about this problem was the requirement that “S1 T1 D1 is considered the same as T1 S1 D1.” I couldn’t figure out how to handle that until I decided to not let it happen at all. This is why the middle loop of the 3-dart solutions starts at the same counter as the outer loop.

Here is the code that does the counting. It runs in a blink:

Sub Problem_109()
Dim DartScore(1 To 62) As Long, i As Long
   Dim Dart_1 As Long
   Dim Dart_2 As Long
   Dim Dart_Last As Long
   Dim Answer As Long, T As Single
   Dim SetScore As Long
   T = Timer
   For i = 1 To 20
      DartScore(i) = i   ‘ Singles
     DartScore(i + 21) = i * 2   ‘ Doubles
     DartScore(i + 42) = i * 3   ‘ Trebels
  Next i
   DartScore(21) = 25   ‘ Single Bull
  DartScore(42) = 50   ‘ Double Bull

   ‘One-dart set
  Answer = 21   ’21 ways to double out with one dart

   ‘Two-dart set
  For Dart_1 = 1 To 62   ‘ 1st Dart – All possible scores
     For Dart_Last = 22 To 42   ‘ 2nd Dart – doubles out
        SetScore = DartScore(Dart_1) + DartScore(Dart_Last)
         If SetScore < 100 Then
            Answer = Answer + 1   ‘ Doubled out
            Exit For
         End If
      Next Dart_Last
   Next Dart_1
   ‘Three-dart set
  For Dart_1 = 1 To 62   ‘ 1st Dart – All possible scores
     For Dart_2 = Dart_1 To 62   ‘ 2nd Dart – All possible scores
        For Dart_Last = 22 To 42   ‘ Last Dart – Doubles out
           SetScore = DartScore(Dart_1) + DartScore(Dart_2) + DartScore(Dart_Last)
            If SetScore < 100 Then
               Answer = Answer + 1   ‘ Doubled out
               Exit For
            End If
         Next Dart_Last
      Next Dart_2
   Next Dart_1
   Debug.Print Answer; ”  Time:”; Timer – T
End Sub

The reason you “go bust” on one is because you can’t double out from there. The usual angle bracket substitutions are in the above.


Posted in Uncategorized

4 thoughts on “Euler Problem 109

  1. It figures you would go with this problem next. I remember not caring for it much. I used a collection to store the dart throws to make sure there weren’t any duplicates – not very efficient. I like your way much better. One thing I did (and this probably won’t make much difference in your code at all) is to throw the last dart first. In other words, the first dart was always a double. This guarantees a double and may also allow you to jump out of the loop earlier. Well done, sir.


  2. Hi Josh –


    I’d agree, probably won’t make a difference. Since doubles are an ordered sort, as soon as one double fails by summing >= 100, leave the loop, for all the remaining ones, being higher, will fail too.

    I sort the problems in ascending difficulty, and I’m on the upper part of page 3. These are solved by ~1200 to 1500 members, and they are really challenging me. Problem 109 was the first in a while that I had an insight to. I give full credit to those days in Dunoon, Scotland. ;-)


  3. If my last throw is a Double bulls eye what 2 possible combination’s could I use to win with my first 2 darts?

Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.