TheAlgorithms-Python
89 строк · 3.0 Кб
1"""
2In the game of darts a player throws three darts at a target board which is
3split into twenty equal sized sections numbered one to twenty.
4
5The score of a dart is determined by the number of the region that the dart
6lands in. A dart landing outside the red/green outer ring scores zero. The black
7and cream regions inside this ring represent single scores. However, the red/green
8outer ring and middle ring score double and treble scores respectively.
9
10At the centre of the board are two concentric circles called the bull region, or
11bulls-eye. The outer bull is worth 25 points and the inner bull is a double,
12worth 50 points.
13
14There are many variations of rules but in the most popular game the players will
15begin with a score 301 or 501 and the first player to reduce their running total
16to zero is a winner. However, it is normal to play a "doubles out" system, which
17means that the player must land a double (including the double bulls-eye at the
18centre of the board) on their final dart to win; any other dart that would reduce
19their running total to one or lower means the score for that set of three darts
20is "bust".
21
22When a player is able to finish on their current score it is called a "checkout"
23and the highest checkout is 170: T20 T20 D25 (two treble 20s and double bull).
24
25There are exactly eleven distinct ways to checkout on a score of 6:
26
27D3
28D1 D2
29S2 D2
30D2 D1
31S4 D1
32S1 S1 D2
33S1 T1 D1
34S1 S3 D1
35D1 D1 D1
36D1 S2 D1
37S2 S2 D1
38
39Note that D1 D2 is considered different to D2 D1 as they finish on different
40doubles. However, the combination S1 T1 D1 is considered the same as T1 S1 D1.
41
42In addition we shall not include misses in considering combinations; for example,
43D3 is the same as 0 D3 and 0 0 D3.
44
45Incredibly there are 42336 distinct ways of checking out in total.
46
47How many distinct ways can a player checkout with a score less than 100?
48
49Solution:
50We first construct a list of the possible dart values, separated by type.
51We then iterate through the doubles, followed by the possible 2 following throws.
52If the total of these three darts is less than the given limit, we increment
53the counter.
54"""
55
56from itertools import combinations_with_replacement57
58
59def solution(limit: int = 100) -> int:60"""61Count the number of distinct ways a player can checkout with a score
62less than limit.
63>>> solution(171)
6442336
65>>> solution(50)
6612577
67"""
68singles: list[int] = [*list(range(1, 21)), 25]69doubles: list[int] = [2 * x for x in range(1, 21)] + [50]70triples: list[int] = [3 * x for x in range(1, 21)]71all_values: list[int] = singles + doubles + triples + [0]72
73num_checkouts: int = 074double: int75throw1: int76throw2: int77checkout_total: int78
79for double in doubles:80for throw1, throw2 in combinations_with_replacement(all_values, 2):81checkout_total = double + throw1 + throw282if checkout_total < limit:83num_checkouts += 184
85return num_checkouts86
87
88if __name__ == "__main__":89print(f"{solution() = }")90