{-######################################################################
# Solves problem 109 from projectEuler.net.
# Counts how many distinct ways can a player checkout with a score
# less than 100 in a game of darts.
# Copyright (C) 2010 Santiago Alessandri
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see .
#
# You can contact me at san.lt.ss@gmail.com
# Visit my wiki at http://san-ss.wikidot.com
######################################################################-}
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)