projects
/
advent-of-code-19.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
b66feb5
)
Day 14 done.
author
Neil Smith
<neil.git@njae.me.uk>
Mon, 16 Dec 2019 15:43:10 +0000
(15:43 +0000)
committer
Neil Smith
<neil.git@njae.me.uk>
Mon, 16 Dec 2019 15:43:10 +0000
(15:43 +0000)
advent14/src/advent14.hs
patch
|
blob
|
history
diff --git
a/advent14/src/advent14.hs
b/advent14/src/advent14.hs
index c8a14566859529426c3014953b63d630e3aa70a9..1fafe9bce157c425d898d3099832e89265e4ed1d 100644
(file)
--- a/
advent14/src/advent14.hs
+++ b/
advent14/src/advent14.hs
@@
-10,8
+10,6
@@
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L
import qualified Control.Applicative as CA
import qualified Text.Megaparsec.Char.Lexer as L
import qualified Control.Applicative as CA
-
-import Data.Ratio
import Data.List
import qualified Data.Map.Strict as M
import Data.Map.Strict ((!))
import Data.List
import qualified Data.Map.Strict as M
import Data.Map.Strict ((!))
@@
-28,45
+26,51
@@
type Requirement = M.Map String Int
main :: IO ()
main = do
text <- TIO.readFile "data/advent14.txt"
main :: IO ()
main = do
text <- TIO.readFile "data/advent14.txt"
- let rules = successfulParse text
- let ruleBase = mkRuleBase rules
+ -- let rules = successfulParse text
+ -- let ruleBase = mkRuleBase rules
+ let ruleBase = successfulParse text
-- print rules
-- print ruleBase
print $ part1 ruleBase
print $ part2 ruleBase
-- print rules
-- print ruleBase
print $ part1 ruleBase
print $ part2 ruleBase
+oreLimit :: Int
oreLimit = 10^12
oreLimit = 10^12
+mkRuleBase :: [Rule] -> RuleBase
mkRuleBase = foldl' addRule M.empty
where addRule base rule = M.insert (_chemical $ _rhs rule) rule base
mkRuleBase = foldl' addRule M.empty
where addRule base rule = M.insert (_chemical $ _rhs rule) rule base
+
-- part1 rules = required!"ORE"
-- where required0 = M.singleton "FUEL" 1
-- part1 rules = required!"ORE"
-- where required0 = M.singleton "FUEL" 1
--- required = produce rules required
0
+-- required = produce rules required
part1 rules = oreForFuel rules 1
part1 rules = oreForFuel rules 1
-part2 rules = searchFuel rules
1
upper
+part2 rules = searchFuel rules
(upper `div` 2)
upper
where upper = findUpper rules (oreLimit `div` base)
base = oreForFuel rules 1
where upper = findUpper rules (oreLimit `div` base)
base = oreForFuel rules 1
-
+oreForFuel :: RuleBase -> Int -> Int
oreForFuel rules n = required!"ORE"
where required0 = M.singleton "FUEL" n
required = produce rules required0
oreForFuel rules n = required!"ORE"
where required0 = M.singleton "FUEL" n
required = produce rules required0
-findUpper _ n | trace ("Upper " ++ show n) False = undefined
+findUpper :: RuleBase -> Int -> Int
+-- findUpper _ n | trace ("Upper " ++ show n) False = undefined
findUpper rules n = if ore > oreLimit
then n
else findUpper rules (n * 2)
where ore = oreForFuel rules n
findUpper rules n = if ore > oreLimit
then n
else findUpper rules (n * 2)
where ore = oreForFuel rules n
-searchFuel _ lower upper | trace ("Search " ++ show lower ++ " - " ++ show upper) False = undefined
+searchFuel :: RuleBase -> Int -> Int -> Int
+-- searchFuel _ lower upper | trace ("Search " ++ show lower ++ " - " ++ show upper) False = undefined
searchFuel rules lower upper
| upper == lower = upper
| otherwise = if ore > oreLimit
searchFuel rules lower upper
| upper == lower = upper
| otherwise = if ore > oreLimit
- then searchFuel rules lower
mid
+ then searchFuel rules lower
(mid - 1)
else searchFuel rules mid upper
else searchFuel rules mid upper
- where mid = (upper + lower) `div` 2
+ where mid = (upper + lower
+ 1
) `div` 2
ore = oreForFuel rules mid
ore = oreForFuel rules mid
@@
-77,20
+81,22
@@
produce rules required
where outstanding = M.filter (> 0) $ nonOre required
(chem, qty) = M.findMin outstanding
rule = rules!chem
where outstanding = M.filter (> 0) $ nonOre required
(chem, qty) = M.findMin outstanding
rule = rules!chem
- qty' = qty - (_quantity $ _rhs rule)
+ productQty = _quantity $ _rhs rule
+ applications = max 1 (qty `div` productQty)
+ qty' = qty - (applications * productQty)
required' = M.insert chem qty' required
required' = M.insert chem qty' required
- required'' = S.foldl
addRequrirement required' (_lhs rule)
+ required'' = S.foldl
(addRequrirement applications) required' (_lhs rule)
nonOre :: Requirement -> Requirement
nonOre = M.filterWithKey (\c _ -> c /= "ORE")
nonOre :: Requirement -> Requirement
nonOre = M.filterWithKey (\c _ -> c /= "ORE")
-addRequrirement :: Requirement -> Reagent -> Requirement
-addRequrirement requirements reagent = M.insert chem qty' requirements
+addRequrirement ::
Int ->
Requirement -> Reagent -> Requirement
+addRequrirement
n
requirements reagent = M.insert chem qty' requirements
where chem = _chemical reagent
qty = M.findWithDefault 0 chem requirements
where chem = _chemical reagent
qty = M.findWithDefault 0 chem requirements
- qty' = qty + (_quantity reagent)
+ qty' = qty + (
n *
_quantity reagent)
-- Parse the input file
-- Parse the input file
@@
-108,8
+114,7
@@
arrowP = symb "=>"
commaP = symb ","
identifierP = some alphaNumChar <* sc
commaP = symb ","
identifierP = some alphaNumChar <* sc
-
-rulesP = many ruleP
+rulesP = mkRuleBase <$> many ruleP
ruleP = Rule <$> reagentsP <* arrowP <*> reagentP
ruleP = Rule <$> reagentsP <* arrowP <*> reagentP
@@
-117,8
+122,8
@@
reagentP = Reagent <$> integer <*> identifierP
reagentsP = S.fromList <$> reagentP `sepBy` commaP
-- successfulParse :: Text -> [Vec]
reagentsP = S.fromList <$> reagentP `sepBy` commaP
-- successfulParse :: Text -> [Vec]
-successfulParse :: Text ->
[Rule]
+successfulParse :: Text ->
RuleBase
successfulParse input =
case parse rulesP "input" input of
successfulParse input =
case parse rulesP "input" input of
- Left _err ->
[]
-- TIO.putStr $ T.pack $ parseErrorPretty err
+ Left _err ->
M.empty
-- TIO.putStr $ T.pack $ parseErrorPretty err
Right rules -> rules
Right rules -> rules