1 {-# LANGUAGE OverloadedStrings #-}
3 import Data.List (inits, sortBy, foldl')
4 import Data.Function (on)
6 import Data.Text (Text)
7 import qualified Data.Text.IO as TIO
9 import Data.Void (Void)
11 import Text.Megaparsec
12 import Text.Megaparsec.Char
13 import qualified Text.Megaparsec.Char.Lexer as L
14 import qualified Control.Applicative as CA
16 import qualified Data.HashMap.Strict as M
17 import Data.HashMap.Strict ((!))
22 data Bag = Bag { bagWeight :: Weight, bagValue :: Value} deriving (Show, Eq)
23 data TableEntry = TableEntry {value :: Value, backpointer :: (Int, Weight)} deriving (Show, Eq)
24 type DPTable = M.HashMap (Int, Weight) TableEntry
28 bagsT <- TIO.readFile "data/09-bags.txt"
29 let bags = successfulParse bagsT
32 print $ part1 limit bags
33 print $ part2 limit bags
35 part1 :: Weight -> [Bag] -> Int
36 part1 limit bags = length $ last $ takeWhile (willFit limit) $ inits sortedBags
37 where sortedBags = sortBy (compare `on` bagWeight) bags
38 willFit limit' bags' = (sum $ map bagWeight bags') < limit'
40 part2 :: Weight -> [Bag] -> Value
41 part2 limit bags = value $ table!(length bags, limit)
42 where initialTable = M.fromList [((0, w), TableEntry {value = 0, backpointer = (0, w)}) | w <- [0..limit]]
43 table = foldl' includeBag initialTable
44 [ (thisBag, bagNumber, allowedWeight)
45 | (thisBag, bagNumber) <- zip bags [1..]
46 , allowedWeight <- [0..limit]
50 includeBag :: DPTable -> (Bag, Int, Weight) -> DPTable
51 includeBag table (bag, bagNumber, weight) =
52 if bagWeight bag > weight
53 then M.insert here withoutBag table
54 else if value withBagEntry + bagValue bag > value withoutBagEntry
55 then M.insert here withBag table
56 else M.insert here withoutBag table
57 where here = (bagNumber, weight)
58 withoutBagKey = (bagNumber - 1, weight)
59 withBagKey = (bagNumber - 1, weight - bagWeight bag)
60 withoutBagEntry = table!withoutBagKey
61 withBagEntry = table!withBagKey
62 withoutBag = TableEntry {value = value withoutBagEntry, backpointer = withoutBagKey}
63 withBag = TableEntry {value = value withBagEntry + bagValue bag, backpointer = withBagKey}
66 -- Parse the input file
68 type Parser = Parsec Void Text
70 -- don't treat newlines as automatically-consumed whitespace
72 sc = L.space (skipSome (char ' ')) CA.empty CA.empty
75 integer = lexeme L.decimal
78 bagsFileP = bagP `sepBy` newline
80 bagP = bagify <$> integer <*> integer
81 where bagify w v = Bag { bagWeight = w , bagValue = v}
83 successfulParse :: Text -> [Bag]
84 successfulParse input =
85 case parse bagsFileP "input" input of
86 Left _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err