Project Euler Problem 109

# Statement

In a game of darts:

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

# Solution

The solution is straight-forward, for each value:

1. Check if you can checkout with a double.
2. With all values of dart throws possibles less than the value, see if you can checkout with a double.
3. For all two-throw combinations where the first is lower or equal the second throw check if the remainder can be checked-out with a double.

The python code for this:

```limit = 100

doubles = set(2 * x for x in range(1, 21))
casual = sorted([x for x in range(1,21)] + [2 * x for x in range(1, 21)] + [3 * x for x in range(1, 21)] +  + )

if __name__ == '__main__':
result = 0
for score in range(2, limit):
if score in doubles:
result += 1
for first in casual:
if first >= score:
break
result += (score - first) in doubles and 1 or 0
first = 0
while first < len(casual) and casual[first] * 2 < score:
remain = score - casual[first]
second = first
while second < len(casual) and casual[second] < remain:
result += (remain - casual[second]) in doubles and 1 or 0
second += 1
first += 1
print("The result is:", result)
```

The Haskell code for this is:

``````import Data.List

limit = 99

doubles = [2 * i | i <- [1..20]] ++ 
ordinary = sort ([1..20] ++ doubles ++ [3 * i | i <- [1..20]] ++ )

solve n sum | n == 1 = sum
| n > 1 = solve (n - 1) (sum + n_res)
where
one_dart = if n `elem` doubles then 1 else 0
two_dart = length (filter (\x -> x `elem` doubles) (map (n -) (filter (< n) ordinary)))
three_dart = length (filter (\x -> x `elem` doubles) remains)
where
remains = map (n - ) pair_sums
pair_sums = [(ordinary !! x) + (ordinary !! y) | x <- [0..ord_size], y <- [0..ord_size], x <= y]
where
ord_size = (length ordinary) - 1
n_res = one_dart + two_dart + three_dart

main = print (solve limit 0)```
```