Who says we can't play god? Well, a god is probably better at combinatorics than I am.
Day 14 - The Problem
Bad news, folks. We're running out of fuel. The good news is that we're right next to a big source of ORE.
Part 1 has us trying to assemble fuel with our amazing elemental recombinator.
Part 2: will be described when I get there.
Ongoing Meta
Dev.to List of Leaderboards
-
120635-5c140b9a
- provided by Linda Thompson
If you were part of Ryan Palo's leaderboard last year, you're still a member of that!
If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)
I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.
There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.
Neat Statistics
I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?
Languages Seen On Day 12
Under construction
Top comments (4)
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.
Finally something not involving grid points. Took wrong path and wasted lot of time
Swift solution here.
Oooh another nice problem :)
First of all, parsing. Fairly simple, you just have to create a map. Note that there's only one reaction to produce a specific chemical.
But the produced amount may vary, so we have to track that information. For some silly reason, I used a JavaScript
Symbol
to store that in the map 😅. I basically never usedSymbol
s in my job, but here I am practicing with them:The basic idea here is, of course, that you have to start with the reaction needed for FUEL (there's only one) and create a shopping list of the chemicals you need (and how many of them). But while doing so, you also have to keep track of the chemicals you end up not using for the current reaction, because they may come in handy for the next reactions.
I'm wrapping everything in a function so it can be used in the second part:
For the second part, we have to remind that after producing 1 FUEL, we still have some useful chemicals left. So, should we produce one FUEL at a time, always keeping track of the reserves? I had a better idea, and it involves estimations. Turns out it reaches the correct answer pretty fast (right at the second iteration for me!):
Text, input and solution at my repo 👋
After much stewing and drawing diagrams, I realized it was an acyclic directed graph. It's always a graph! Part 2 took a little bit of pragmatic, targeted brute forcing because I was sleepy.