Using Recursive CTEs to compute darts combinations

Jorginho — Tue, 08 Jan 2008 15:43:00 GMT

In my first blog post I will explain Common Table Expressions (CTEs) in T-SQL queries and the powerful feature of recursive CTEs, i.e., CTEs that reference themselves. The game of darts provides a great example to illustrate these concepts.

When two players play a game (leg) of darts, the purpose is to go from 501 to 0 in as few darts as possible, where the last dart has to be a double score (in the outer ring of the dartboard). The bull's eye (center of the dartboard) is also considered a double, so with 1 dart a player can only finish on 2, 4, 6, ..., 40 and 50 (bull). A turn of a player consists of throwing 3 darts and since 60 (triple-20) is the highest score on the board the highest possible 3-dart finish is 170 (triple-20, triple-20, bull). Accidentally, the lowest number of darts with which a leg of 501 can be finished is 9 and this so-called 9-darter is the ultimate achievement for a dart player.

The purpose of this post is to calculate the best possible or optimal finishes for a given score and the number of possible combinations for every finish. By optimal I mean with as few darts as possible, i.e., if it's possible to finish a score with 2 darts then we are not interested in other finishes of the same score with 3 or more darts.

First I will create a table Throw with all possible scores with 1 dart:

IF EXISTS (SELECT * FROM INFORMATION_SCHEMA.TABLES WHERE TABLE_NAME = 'Throw')

DROP TABLE Throw

CREATE TABLE Throw (

ThrowID INT IDENTITY PRIMARY KEY,

ThrowName VARCHAR(15),

Value INT,

Factor INT,

Score INT

)

Value is the number on the dartboard, Factor is 1 (single), 2 (double) or 3 (triple) and Score is the resulting score (Value times Factor). ThrowName is a short-hand description of the score, e.g. T20 for triple-20.

To populate the table I will use a CTE for a table containing the numbers from 1 to 20. CTEs can be seen as temporary tables that only exist within the scope of the current query. They are very useful in cases where an auxiliary table is referenced multiple times in the same query. A CTE can be defined using WITH <Name of CTE> AS <Query statement>, followed by a query in which the CTE can be referenced just like a regular table. In this case I use the CTE Numbers three times to compute the single, the double and the triple scores:

WITH Numbers AS

(

SELECT a.Number + 5*(b.Number-1) AS Number

FROM ((SELECT 1 AS Number UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5) a

CROSS JOIN (SELECT 1 AS Number UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) b)

)

INSERT Throw

SELECT 'S' + CONVERT(VARCHAR, Number), Number, 1, Number

FROM Numbers

WHERE Number <= 20

UNION

SELECT 'D' + CONVERT(VARCHAR, Number), Number, 2, 2*Number

FROM Numbers

WHERE Number <= 20

UNION

SELECT 'T' + CONVERT(VARCHAR, Number), Number, 3, 3*Number

FROM Numbers

WHERE Number <= 20

UNION

SELECT 'SBULL', 25, 1, 25

UNION

SELECT 'BULL', 25, 2, 50

ORDER BY 3,4

Note that the Numbers table is constructed via a cross join of a table with 5 numbers and a table with 4 numbers, which is a bit more efficient than simply enumerating 20 numbers. The last 2 select statements add the single-bull and the bull throws for a total of 62 possible throws.

Now the stage is set to compute 2-dart and 3-dart finishes. By joining the Throw table to itself all possible 2-dart finishes can be computed:

SELECT t1.ThrowName + '-' + t2.ThrowName AS 'Combination',

t1.Score + t2.Score AS Score

FROM Throw t1

CROSS JOIN Throw t2

WHERE t2.Factor = 2

ORDER BY Score DESC, t1.Score DESC

The filter Factor = 2 expresses the fact that the last dart has to be a double. To compute all possible 3-dart finishes simply add an extra join:

SELECT t1.ThrowName + '-' + t2.ThrowName + '-' + t3.ThrowName AS 'Combination',

t1.Score + t2.Score + t3.Score AS Score

FROM Throw t1

CROSS JOIN Throw t2

CROSS JOIN Throw t3

WHERE t3.Factor = 2

AND t2.Score <= t1.Score

ORDER BY Score DESC, t1.Score DESC, t2.Score DESC

The filter t2.Score <= t1.Score is added to remove identical combinations from the resultset because T20-T19-BULL is effectively the same combination as T19-T20-BULL. The query yields a total of 41475 records, so there are no less than 41475 possible combinations for a 3-dart finish. By grouping on Score it can be found that 62 can be finished in most different ways with 3 darts, namely in 721 ways! However, this includes all finishes with more darts then necessary (in fact, none of these 721 finishes is optimal since 62 can be finished with 2 darts).

Obviously, the number of combinations with n darts can be found by joining the Throw table to itself n-1 times. But what if we don't want to fix to the number of throws on beforehand but instead want to determine the minimum number of darts needed to finish a given score and the optimal combinations? The solution to this problem is a recursive CTE!

Let's provide the query does the trick and then discuss how it works. Here it is:

WITH Score AS

(

SELECT 1 AS NumberOfThrows,

Factor,

Score,

Score AS LastScore,

CONVERT(VARCHAR(255), ThrowName) AS Combination

FROM Throw

UNION ALL

SELECT s.NumberOfThrows + 1,

s.Factor + t.Factor,

s.Score + t.Score,

t.Score,

CONVERT(VARCHAR(255), s.Combination + '-' + t.ThrowName)

FROM Score s

CROSS JOIN Throw t

WHERE s.NumberOfThrows <= 1

AND s.Factor + t.Factor >= 3*s.NumberOfThrows

AND t.Score <= s.LastScore

Finish AS

(

SELECT s.Score + t.Score AS Score,

s.NumberOfThrows + 1 AS NumberOfThrows,

CONVERT(VARCHAR(255), s.Combination + '-' + t.ThrowName) AS Combination

FROM Score s

CROSS JOIN Throw t

WHERE t.Factor = 2

)

SELECT Score, NumberOfThrows, Combination

FROM Finish f

WHERE NumberOfThrows = (SELECT MIN(NumberOfThrows) FROM Finish WHERE Score = f.Score)

ORDER BY Score DESC

To be continued...

Jorginho on T-SQL & Business Intelligence

Using Recursive CTEs to compute darts combinations