Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Searches all combinations of "6 in 49" for the smallest payout given lottery tickets.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.