Ok it's the weekend so I had some fun in Haskell. The input data has a more complex structure today so I whipped out my trusty parser combinator toolkit. But I've got this far with very few external libraries so let's write our own!
dataParseResultinputvalue=Okvalueinput|ErrStringinputderiving(Eq,Show)instanceFunctor(ParseResultinput)wherefmapf(Okvaluerest)=Ok(fvalue)restfmapf(Errexpectedactual)=ErrexpectedactualnewtypeParserinputvalue=Parser(input->ParseResultinputvalue)instanceFunctor(Parserinput)wherefmapf(Parserp)=Parser(\input->fmapf(pinput))instanceApplicative(Parserinput)wherepurex=Parser(\input->Okxinput)(Parserp)<*>(Parserq)=Parser$\input->casepinputofOkrrest->fmapr(qrest)Errea->Erreaparse::Parserinputvalue->input->ParseResultinputvalueparse(Parserp)input=pinputparseWith::(Char->Bool)->(String->a)->String->ParserStringaparseWithmatchconvertexpected=Parser$\input->letmatching=takeWhilematchinputrest=dropWhilematchinputinifnullmatchingthenErrexpectedinputelseOk(convertmatching)restliteral::String->ParserString()literals=Parser$\input->casestripPrefixsinputofNothing->Err("'"++s++"'")input(Justrest)->Ok()restinteger::ParserStringIntinteger=parseWithisDigitread"an integer"chemical::ParserStringStringchemical=parseWithisAsciiUpperid"a chemical symbol"whitespace::ParserString()whitespace=Parser$\input->Ok()(dropWhileisSpaceinput)before::Parserix->Parseria->Parseriax`before`p=fmapsnd$pure(,)<*>x<*>pfollowedBy::Parseria->Parserix->Parseriap`followedBy`x=fmapfst$pure(,)<*>p<*>xsepBy::Parseria->Parseris->Parseri[a]sepBy(Parserp)(Parserq)=ParsersepBy'wheresepBy'input=casepinputofErr__->Ok[]inputOkvrest->caseqrestofErr__->Ok[v]restOk_rest'->fmap(\vs->v:vs)(sepBy'rest')
That was fun, and lets me write really simple code for parsing the input data:
Ok on to the problem. We've had topological sort problems before in AoC so I recognised the general form of the problem pretty quickly. If you sort the chemicals by dependency then you can walk that list in order knowing when you reach a chemical you've already dealt with everything that has a demand on it.
Then the quantity needed is found by walking the topologically sorted list of chemicals and building a map of the amount of each needed. For each chemical look up the inputs and add the appropriately scaled amount to each input's requirements.
At first I thought part 2 was going to reverse the search order so we started from ORE but I quickly realised the search space explodes once you can use an input for multiple outputs. It turned out much simpler - starting with an estimate of the quantity of ORE divided by the ORE needed for 1 FUEL, it's just a binary search to find the maximum amount of FUEL we can make.
Ok it's the weekend so I had some fun in Haskell. The input data has a more complex structure today so I whipped out my trusty parser combinator toolkit. But I've got this far with very few external libraries so let's write our own!
That was fun, and lets me write really simple code for parsing the input data:
Ok on to the problem. We've had topological sort problems before in AoC so I recognised the general form of the problem pretty quickly. If you sort the chemicals by dependency then you can walk that list in order knowing when you reach a chemical you've already dealt with everything that has a demand on it.
The next bit was tricky. First I reorganised the reaction data into a map from chemical name to its requirements and quantity produced:
Then the quantity needed is found by walking the topologically sorted list of chemicals and building a map of the amount of each needed. For each chemical look up the inputs and add the appropriately scaled amount to each input's requirements.
The final answer is waiting the in the map at the end
At first I thought part 2 was going to reverse the search order so we started from ORE but I quickly realised the search space explodes once you can use an input for multiple outputs. It turned out much simpler - starting with an estimate of the quantity of ORE divided by the ORE needed for 1 FUEL, it's just a binary search to find the maximum amount of FUEL we can make.
Full source with unit tests.