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:
- Check if you can checkout with a double.
- With all values of dart throws possibles less than the value, see if you can checkout with a double.
- 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)) doubles.add(50) 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)] + [25] + [50]) 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]] ++ [50]
ordinary = sort ([1..20] ++ doubles ++ [3 * i | i <- [1..20]] ++ [25])
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)
The Python and Haskell files are available for download: problem109.py and problem109.hs.
