Searches all combinations of "6 in 49" for the smallest payout given lottery tickets.

lottery-maximization.hs

import Control.Applicative ((<$>))
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import Data.Function (on)
import Data.List (foldl', minimumBy, tails)
import Data.Maybe (fromMaybe)
import Data.Text (lines, splitOn, pack, unpack)
import Data.Text.IO (readFile)
import Prelude hiding (lines, readFile)
import System.Environment (getArgs)

main :: IO ()
main = do
  input:_ <- getArgs
  tickets <- map (map (read . unpack) . splitOn (pack ",")) . lines <$> readFile input
  let trie = foldl' (file [0,0,0,50,0,4500,272000]) empty tickets
      c = cheapest trie (combinations 6 [1..49])
  putStrLn $ show c ++ ": " ++ show (payout trie c)

data Trie = Trie !Int !(IntMap Trie)
          deriving (Show, Eq, Ord)

empty :: Trie
empty = Trie 0 IntMap.empty

file :: [Int] -> Trie -> [Int] -> Trie
file (c:cs) (Trie n children) = Trie (n+c) . foldl' (update cs) children . init . tails
  where
    update :: [Int] -> IntMap Trie -> [Int] -> IntMap Trie
    update costs children (x:xs) = IntMap.insert x (file costs (fromMaybe empty (IntMap.lookup x children)) xs) children

payout :: Trie -> [Int] -> Int
payout (Trie n children) = foldl' (\k (x:xs) -> k + maybe 0 (flip payout xs) (IntMap.lookup x children)) n . init . tails

cheapest :: Trie -> [[Int]] -> [Int]
cheapest trie xs = fst . minimumBy (compare `on` snd) $ zip xs (map (payout trie) xs)

combinations :: Eq a => Int -> [a] -> [[a]]
combinations k list = if k == 0 then [[]] else case list of
  []   -> []
  x:xs -> map (x:) (combinations (k-1) xs) ++ combinations k xs