Project Euler 109: How many distinct ways can a player checkout in the game of darts with a score of less than 100?

Unlike most of the problems I have encountered recently, Problem 109 of Project Euler has proven to be pretty easy. The problem reads

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 scores. 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:


D3

 

 
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 sameas 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?

Already in the problem description we know that there are app. 42000 different combinations to check out in, so if we can find a way to iterate them all then we should be able to brute force the problem.

Generating all the possible scores is pretty easy. It is possible to score 1-20 and then times 2 and times 3. That is a total of 60 combinations plus the two bulls eye. The number of times we can score a double is also pretty easy, there is a total of 21 possibilities.

So now we just need to loop over all the “miss, miss, double”, the “miss, score, double” and half the “score, score, double”. This can be done with the following (not nicely optimized) code.

int limit = 100;
int result = 0;

List scores = new List();

//build all possible single dart scores
for (int i = 1; i <= 20; i++) {
    scores.Add(i);
    scores.Add(2 * i);
    scores.Add(3 * i);
}
scores.Add(25);
scores.Add(50);

//make all the possible doubles
List doubles = new List();
for (int i = 1; i <= 20; i++) {
    doubles.Add(2 * i);
}
doubles.Add(25 * 2);

//Count all miss, miss, double
foreach (int third in doubles) {
    if (third < limit)
        result++;
}

 //count all miss, hit, double
for (int i = 0; i < scores.Count; i++) {
    foreach (int third in doubles) {

        if (scores[i] + third < limit)
            result++;
    }
}

//count all hit, hit, double
for(int i = 0; i < scores.Count; i++){
    for(int j = i; j< scores.Count; j++){
        foreach (int third in doubles) {
            if (scores[i] + scores[j] + third < limit)
                result++;
        }
    }
}

I told you it wasn’t nice, but it works for all that matters here. I get the result

There are 38182 ways to checkout

which runs in

Solution took 0,2997 ms

so I think that is really fast enough for it to be accepted.

 

Wrapping up

A short post for an easy problem. The source code is available here.

Posted by Kristian

5 comments

Bjarki Ágúst

The code is acting weird again, and you forgot to upload the complete source code.

But as for the problem itself, I created a function ways which counted, with dynamic programming, the number of ways to get a score [latex]n[/latex] in [latex]k[/latex] throws. Then I looped from [latex]n = 1[/latex] up to [latex]n = 99[/latex], and to enforce the “must end in a double” rule I simply summed up [latex]\textrm{ways}(n – 2i, 2)[/latex] for all possible [latex]i[/latex].

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <fstream>
using namespace std;

#define all(o) (o).begin(), (o).end()
#define allr(o) (o).rbegin(), (o).rend()
#define INF 2147483647
typedef long long ll;
typedef pair<int, int> ii;
template <class T> int size(T x) { return x.size(); }

struct state
{
	int n, i, k;
	state(int n_, int i_, int k_)
	{
		n = n_;
		i = i_;
		k = k_;
	}
};

bool operator <(const state& a, const state& b)
{
	if (a.n != b.n) return a.n < b.n;
	if (a.i != b.i) return a.i < b.i;
	if (a.k != b.k) return a.k < b.k;
	return false;
}

vector<int> vals;
int valcnt;
map<state, int> mem;

int ways(state s)
{
	if (s.n == 0)
		return 1;

	if (s.k < 1 || s.i >= valcnt || vals[s.i] > s.n)
		return 0;

	map<state, int>::const_iterator it = mem.find(s);
	if (it != mem.end()) return it->second;

	return mem[s] = ways(state(s.n - vals[s.i], s.i, s.k - 1)) + ways(state(s.n, s.i + 1, s.k));
}

int main()
{
	vals.push_back(25);
	vals.push_back(50);

	for (int i = 1; i <= 20; i++)
	{
		vals.push_back(i);
		vals.push_back(2 * i);
		vals.push_back(3 * i);
	}

	sort(all(vals));
	valcnt = size(vals);

	int total = 0;
	for (int n = 1; n < 100; n++)
	{
		int cnt = 0,
			mx = min(20, n / 2);
		for (int i = 1; i <= mx; i++)
		{
			cnt += ways(state(n - 2 * i, 0, 2));
		}

		cnt += ways(state(n - 2 * 25, 0, 2));
		total += cnt;
	}

	printf("%d\n", total);
	return 0;
}

The code runs in a couple of ms.

Sorry for that, it should be corrected now.

Nice solution using dynamic programming. Since the problem is as small as it is, I doubt you will see much of a difference in execution time, but for larger problems it should be faster.

[…] Mathblog has a good write up on the brute force approach to solving this problem. […]

Jean-Marie Hachey

Quote:
“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).”
https://projecteuler.net/problem=109

There are exactly 42335 (not 42336) distinct ways to checkout on the maximum possible score of 170.

Table
Score Checkout t (ms)
(distinct ways)

160 42328 0,56
161 42330 0,5
162 42332 0,48
163 42332 0,47
164 42332 0,49
165 42332 0,48
166 42334 0,5
167 42334 0,52
168 42335 0,68
169 42335 0,52
170 42335 0,48
171 42336 0,49

Calculations done with Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem109.cs

Fabio Christmann

@Jean Marie Hachey

Your calculations are wrong, you calculated the number of checkouts less than, instead of less or equal to.

You can see that if you check your values for 168 – 170. Theres no possible way to checkout 168 and 169, hence for scores less or equal to 169/168 you should get the same result (and you do). But for 170, there is a way (T20 T20 BE), so there should be one more way compared to 169.
Your code is fine for the problem itself as it asked for ways less than 100, but for calculating ALL checkout combinations you need to go less/equal to 170 or less than 171.
Just take a look at the beginning of your table. For a score of 2, you probably have 0 as the result – even if there is a way to checkout (D1).

Leave a Reply