1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
module Main where
import qualified Data.Map.Strict as Map
import qualified Data.Map.Lazy as LMap
import Data.Maybe
import qualified Data.Set as Set
import Text.Parsec (runParser, sepBy1, string, many1, space, letter, string, digit)
import Input
type Comp = String
data Rule = Rule [(Int, Comp)] (Int, Comp)
deriving (Show)
parseRule :: String -> Rule
parseRule = either (error . show) id . runParser pRule () ""
where
pRule = Rule <$> (pPair `sepBy1` pComma) <*> (string " => " >> pPair)
pPair = (,) <$> (read <$> many1 digit) <*> (space >> many1 letter)
pComma = string ", "
ceilDiv :: Integral i => i -> i -> i
ceilDiv a b = (a + b - 1) `div` b
binaryMax :: Integral i => i -> i -> (i -> Bool) -> Maybe i
binaryMax low high f
| low < high = let mid = low + (high - low) `div` 2
res = f mid
in if res then binaryMax mid high f else binaryMax low (mid - 1) f
| low == high, f low = Just low
| otherwise = Nothing
main :: IO ()
main = do
rules <- map parseRule <$> getInput 14
let compounds = Set.toList $ Set.fromList [c | Rule src (_, to) <- rules, c <- to : map snd src]
supportGraph = Map.fromListWith (++)
[(srccomp, [(num, ncomp, comp)]) -- need 'num' of 'srccomp' for 'ncomp' of 'comp'
| Rule src (ncomp, comp) <- rules
, (num, srccomp) <- src]
let buildNeedOf nfuel =
let computeNeed "FUEL" = nfuel
computeNeed comp =
sum [nreqcomp * ((needOf Map.! c2) `ceilDiv` nprodc2)
| (nreqcomp, nprodc2, c2) <- fromMaybe [] (Map.lookup comp supportGraph)]
needOf = LMap.fromList [(comp, computeNeed comp) | comp <- compounds]
in needOf
print (buildNeedOf 1 Map.! "ORE")
let lim = 1000000000000
print (fromJust (binaryMax 0 lim (\m -> buildNeedOf m Map.! "ORE" <= lim)))
|
