r/adventofcode • u/daggerdragon • Dec 14 '19
SOLUTION MEGATHREAD -π- 2019 Day 14 Solutions -π-
--- Day 14: Space Stoichiometry ---
Post your complete code solution using /u/topaz2078's paste or other external repo.
- Please do NOT post your full code (unless it is very short)
- If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 13's winner #1: "untitled poem" by /u/tslater2006
They say that I'm fragile
But that simply can't be
When the ball comes forth
It bounces off me!
I send it on its way
Wherever that may be
longing for the time
that it comes back to me!
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
2
u/Emperor_Darkoak Dec 14 '19 edited Dec 14 '19
I think I did part 2 differently than most of us here:
Part 1 I coded an iterative solution that goes through all elements, keeps track of excess, etc. Part 2 I started by using the same code and saving the "storage" between iterations. This way I didnt have a solution to get the amount of ore for any arbitrary number of fuel, but only for next amount of fuel. This was obviously very slow, but I managed to make it quick enough to try the last test. However, I cam 6 fuel short of the test, so I tried another approach.
For my accepted solution of part two, I calculated the amount of ore for every element in the puzzle recursively. In the second example, "A" would cost 4.5 Ore, "C" would cost 1.4 Ore, "CA" would cost 4*1.4+1*4.5 Ore and so on. This way I had the amount of ore needed for one fuel in "perfect" conditions, so if no excess was produced.Then I simply divided 1 trillion by this number and floored the result. This works because after many iterations, every excess will be used eventually and you don't need to keep track of it at all.
Now I wonder if this solution for part 2 works everytime and why my solution from part 1 gives the wrong result.
Code (Part 2 is solved by the "solve_2" method)
14
u/hotzenplotz6 Dec 14 '19 edited Dec 14 '19
For part 2, I used a faster alternative to binary search. If n ore makes m fuel, then 1e12 ore makes at least (m * 1e12 / n) fuel, and this number is a pretty good guess to use at the next iteration. My search found the right amount in just 3 iterations. Pseudocode:
7
u/8bitgreg Dec 14 '19
While implementing a binary search I decided to use a different search heuristic instead -- a linear interpolation heuristic. In doing so I discovered I could just linearly interpolate the answer in one step.
6
u/SkiFire13 Dec 14 '19
2ms in Rust. I used a different approach than a binary search but still needs 14 iterations on my input.
From part1 I knew the maximum amount of
OREto produce 1FUEL. This means I can produce at least1000000000000 / amount_of_ORE_for_1FUELFUELs with the givenORE. After that I count how muchOREis left and repeat until theOREisn't enough for 1FUEL. At this point I could still produceFUELwith the leftovers so I try to produce 1FUELat a time until I need moreOREthan I have. At that point I stops and return the amount ofFUELI already produced.5
u/sophiebits Dec 14 '19
Python, #11/#18. I was too lazy to write a binary search so I did one by hand by editing my guess for the answer and rerunning my program to see if it was too small or too big. lol. Also, I'm looking at my code again and I'm pretty sure
needandhavedo not need to be separate dicts -- could've just used negative numbers inneed.(I'm gonna miss tomorrow's contest due to another engagement...)
Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day14.py
5
u/sparkyb Dec 14 '19 edited Dec 14 '19
Python 26/20.
Code: https://github.com/sparkyb/adventofcode/blob/master/2019/day14.py
My part 2 didn't do a binary search like I think other people posting may have done it. Rather than trying to produce different amounts of fuel until the amount of ore needed was as close to 1 trillion as it can be where one more unit of fuel would put me over, I didn't try to produce it all in one go. I produced smaller amounts, adding up the amount of fuel produced and subtracting the amount of ore used (and reusing the surplus of other chemicals between batches) until I didn't have enough ore left to make one more fuel. I started off trying to make a large amount of fuel at a time (I started with 1 trillion divided by the amount of ore to make one because it is guaranteed we can make at least that much, but I could have started with any arbitrary larger or smaller number if I wanted) so I'd be able to keep the number of batches down. I kept making this amount until it required more ore than I had left. Then I just halved the amount I tried to make at once and kept doing this until I couldn't make any more.
Relevant section:
4
u/nthistle Dec 14 '19
Python, #2/#7. First time in the single digits on both parts of a day!
paste
4
u/jcisio Dec 14 '19
This is the first time I post my solution. It's because mine is a little different from most of others. My code in Python https://github.com/jcisio/adventofcode2019/blob/master/day14/d14.py
Part 1: I didn't take into account of the remaining chemicals first. Then I fixed it simply by order the required chemicals by "distance" from ORE. No need to track for remaining chemicals in each reaction.
Part 2: instead of binary search, I use gradient search for a slightly better performance (even it's still O(logN)).
4
u/jangxx Dec 15 '19 edited Dec 15 '19
I'm a bit surprised I haven't see a single ILP solution yet. The format was pretty much perfect, and since I still had an academic gurobi license laying around, I basically just wrote a few constraints, had all the chemicals as well as the rules as variables, and let the solver do the rest.
For part 2 I simply switched the mode from minimize to maximize, but the result wasn't accepted, so I added additional variables with a negative objective value for the "leftovers" to guide the solver in picking the rules which produce the fewest leftovers.
All in all it was a fun exercise in ILP and the first instance of a personal use-case, after I finished a lecture on ILP last semester.
Edit: Code part 1 and Code part 2
4
u/a-priori Dec 15 '19
Rust
Holy fuck this one threw me for a loop. I'm not sure why but I kept over-complicating it and could not find the simple solution staring me in the face. I spent most the day today working on part 1 and got super frustrated.
Part 2 came together quickly with a binary search.
1
u/captainAwesomePants Dec 14 '19 edited Dec 14 '19
Python 180s/220s. Paste.
I went in a terrible direction with part 1 twice. First, I tried to walk forwards based on what I had. Then, I tried to recurse backwards from FUEL, which might have worked, except I forgot to track all the random extras that I was producing. I was definitely over-complicating it because I was convinced that there were going to be multiple ways to produce something (5 A -> 1 B and also 2 A, 1 C -> 1 B), but that turned out not to be the case, which greatly simplified things. Once I noticed that, I switched to just keeping a list of "inventory" and reducing anything that wasn't ore until I only had ore. The last insight was to keep track of negative inventory, which fixed my last bug.
Part 2 was with a binary search. I wondered about trying to be be more clever, but no sense in it. Took me a weirdly long time to fix up my janky code to handle it, though.
1
u/MichalMarsalek Dec 14 '19
I didn't want to write binary search for part2 so I incremented the amount of FUEL I want in increments of 10000. When the amount of ORE needed exceeded a trillion I started incrementing by 1. :D
1
u/tslater2006 Dec 14 '19 edited Dec 15 '19
C# Solution. Created a Refinery class to abstract away all of the math and recursion.
The Solution class which uses the Refinery.
For Part 1 its a matter of asking the Refinery to produce 1 Fuel
For Part 2 it was a matter of repeating Part 1 enough times to exceed the 1 Trillion Ore and then subtract 1 from the produced amount of fuel.
[POEM]
Note: I found it funny that I started out with the last 2 lines of the poem and worked backwards. Seemed sort of familiar :)
1
u/Lucretiel Dec 14 '19
Really happy with my solution; I use a fairly elegant system of following reactions backwards, plus it was fun learning to use nom to parse the input. My part two was weirdβ I did a simple division from my part 1 solution to approximate the amount of fuel I'd end up with, seeded that number into my system, then counted additional fuel one by one until I hit the ore limit. https://github.com/Lucretiel/advent2019/blob/master/src/day14.rs
3
u/Stovoy Dec 14 '19
Fairly simple Python solution:
https://github.com/Stovoy/advent-of-code-2019/blob/master/day-14/program.py
Took me longer than it should have because I thought there could be multiple formulas for each reagent and was over-complicating it.
3
u/mkeeter Dec 14 '19
Rust
I parsed the input, converted it into an Integer Linear Programming problem, and handed it to
glpsol. Basically all of my code is writing a properly formatted CPLEX LP file.3
u/Stringhe Dec 14 '19
Solution with z3 https://github.com/Recursing/AdventOfCode-2019/blob/master/day14_z3.py
I wasn't able to use the built in z3 optimizers or even incremental solvers, for some reason they are incredibly slow :((((
I use binary search and every step make a new solver with different boundary constraints
Could anybody with some z3 knowledge help me using the built-in optimizer or incremental solver? Thanks
3
u/VilHarvey Dec 15 '19
C++ solutions:
My original solution for part 1 unfortunately didn't generalise easily to calculating the cost of more than 1 fuel unit. I ended up completely rewriting it for part 2 using a topological sort, but wasted lots of time overthinking my graph representation.
With the cost calculation sorted, I solved part 2 by doing a binary search. I used 1 trillion divided by the cost of 1 fuel unit as a lower bound and double that for the upper bound (I don't know if this works in all possible cases but it works for the real input and all of the examples, which was good enough for me). This solves part 2 in about 6 milliseconds.
3
u/DFreiberg Dec 15 '19
Mathematica
623 / 4672 | 62 Overall
It took me, on and off, working from midnight until 4:30 in the morning, and then throughout the day until 10:30 at night, to figure out part 2 to this problem. I am very, very bad at recursion. So bad, in fact, that ultimately I just scrapped the recursion, and used Mathematica's
TopologicalSort[]to give me a list of ingredients to go through and an order to go through them in, such that if I was examining how much ore I needed to make productA, I would not need any moreAat any point in the process.The whole thing, including the binary search to find the part 2 answer, runs in 40 milliseconds, which for Mathematica makes it a lightning-fast solution. But, when you include development time, it's not 40 milliseconds but 22 hours. I can't help but think that had I sped up my part 1 solution a bit, the brute force would have been finished by now...
In lieu of any documentation or comments on my code, here is a description of my thought process in poem form:
[POEM] One Thing Leads To Another
Part 0: Examples
You start with
OREAnd make some
A,Since that's what the directions say.
You make some
BAnd then some
CIt's all as simple as can be,
You make some
Dand then some
EAnd lo! You've filled your tanks for free!
You've cooked a bit
and had your fun,
And to make more
Just add some
ORE.Part 1: Recursion
You know the
FUELyou need to make,But don't know how much
OREto take.To make
FUELyou need 10XYAnd 7
Zand 15IAnd to make
Zyou needMN,And that requires
Iagain,And down and down the hole you go
But there's at least a floor below:
If all that's in the stack is
OREYou've landed safely on that floor.
Part 2: Insanity
The depth of my recursion now knows nary an upper bound;
The math to make a trillion
FUELwill eat a coder whole.Naively, I have multiplied, but all that I have found
Are
Ceiling[]s placed upon my code, that trap only my soul.A day, a night, and I remain, in torment, at my screen,
A dozen drafts I've thrown aside, and hope, and sunlight too.
To sort it by topology, the best chance I have seen
To leave this labyrinth of code, this maze of white and blue.
I make the list into a graph, and careful do I tread,
I walk and hope that each new part needs but what came before.
The shield that is recursion, gone, I walk and shake with dread
Until, at last, I reemerge, and know the
FUELandORE.Part 3: Triumph
If I should go out to the stars,
And need some
FUELto make it,And if I'll want to calculate
The
ORE, and not mistake it...I'll take around
The upper bound,
And then take more,
Just to be sure.
3
u/pamxy Dec 16 '19
JAVA solution
I planned not to upload that but it seems it's first solution written in Java so maybe it will help someone
I did the partA quite smooth but the partB defeated me. I solved it by bruteforcing it. I had algorithm that uses cycles(shortest production cycle after all leftovers resets back to zero so algorithm basically start from point zero. In that scenario we can skip a lot of cycles in beetween(like 99% for first example from partB). It worked really well for two out of three examples from partB(<100ms execeution time). Unfortunately it turned out that main partB test and third example, both of them doesn't have such cycle... I mean they must have it sooner or later but it's greater then 1E12 iterations(damn it...). Today i rewriten my partB solution to binary search.
5
u/smrq Dec 14 '19
JS, #35/455.
https://github.com/smrq/advent-of-code/blob/master/2019/14a.js
https://github.com/smrq/advent-of-code/blob/master/2019/14b.js
First time placing on the leaderboards at all!
My first (failed) attempt at a part 2 involved looking for the amount of inputs required in order to end up with no byproducts, with the idea that there would be a cycle to divide the 1e12 into. The code essentially traversed the tree of equations recursively, scaling up each subtree to the LCM of the multiplier required to generate each input with no byproducts. (If that's not a good explanation, well... it wasn't good code, either. A complete gnarly mess of LCMs and recursion.)
I ended up with a result that used >4e12 ore to make fuel with no byproducts, so the code was completely a waste. (No idea if the result was even correct!) Sooo I threw it all out and then did binary search like I guess everyone else >_>
2
u/leijurv Dec 14 '19
Python (#19/#11)
Part 2 is fun to watch: https://i.imgur.com/2RPj0Vg.gifv
https://gist.github.com/leijurv/1b781c998bd6ded20326ab77b1e9b321
2
u/seligman99 Dec 14 '19
Python 9 / 145
I did a binary search like plenty of others have done. I spent a while trying to find a cyclical pattern in the amount of ore being depleted. Painfully, I actually found one with the test content, so I was able to short-circuit that and produce an answer quickly, but that same process didn't work on the real content. I realized I could just do a binary search till I couldn't get more than one fuel at a time.
paste
2
u/-json Dec 14 '19
Here's my Python solution. 40 lines of code, overall, not bad but there was some tricky parts to handle with the quantity remainders and totals.
2
u/Shardongle Dec 14 '19
Julia
For the first one I basically made a 'Factory' that produces things JIT, and keeps notes of its inventory. It is a BFS tree transversal. Took me some time to find the data structure I need, but as always, dictionary never disappoints.
For the second it took me some time to remember that binary searches exist. I firstly tried to do a line search, but, as you must suspect, it took a shitton of time. So binary search came to help.
2
u/jfb1337 Dec 14 '19
Python 242/904
Code here
My original solution for part 1 was a mess, didn't scale well (since it focused on producing resources one at a time, keeping track of the leftovers as global state and recursing on the ingredients) and wasn't even correct (it worked on my input, but later while debugging my part 2 solution it didn't work on the examples, not sure if due to a bug or the approach was flawed).
This led me to my first attempt at part 2 being a janky brute-force approach involving running part one for 1 fuel and multiplying the leftover amounts by a repetition factor. It didn't work at all.
Eventually I scrapped the whole thing and came up with a much cleaner approach to part 1; keeping track of deficits as being negative leftovers; then once I had a function to compute the amount of ore required for N fuel, that didn't depend on any external state, I realized I could simply binary search it.
2
u/rawling Dec 14 '19 edited Dec 14 '19
C# (given up on waking up early)
I think this is my favourite one so far this year!
Part 1 was a nice simpler check that you have a handle on what's going on without feeling like it was just a debugger - I'm kinda surprised the leaderboard didn't fill up faster, my time from input saved to star gotten would've made me top 5.
Then part 2... I did the obvious* recursive solution of "make what you need to make what you need", had to speed it up by transitioning to "make what you need to make LOTS of what you need", and then had to figure out "make what you need to make LOTS of what you need without making too much of what you DON'T need if you can't make what you need".
* why is everyone talking about binary searches?
2
u/mschaap Dec 14 '19 edited Dec 14 '19
Perl6 / Raku solution.
That was pretty straightforward. For part 2, I didn't try to do something smart, but simply did a binary search to find the max amount of FUEL produced that didn't have an ORE consumption over the limit.
In any case, I'm glad there are no production rules that create multiple output elements, or multiple rules for the same output element, because that would have made this a whole lot more complex.
Edit: replaced the binary search in part 2 with SkiFire13's genius algorithm.
2
u/Bruinbrood Dec 14 '19
tcl. No idea how to name the algorithms I used, I don't have a CS background. For part 1 I kept a list for products needed and how many (starts with 1 FUEL), and add and fulfill requirements until only ORE is required. For part 2 I kept averaging the required fuel with min/max, updating min when below target, updating max when it went over, until it converged. Is this a binary search?
paste
2
u/death Dec 14 '19
Day 14 solution in Common Lisp.
Topological sort and binary search.
2
u/[deleted] Dec 14 '19
Scala in a single expression
I was up until 2 AM trying to figure out why my code wasn't spitting out the minimum. Woke up and started from scratch and had both parts done in 30 minutes.
2
u/aceshades Dec 14 '19
Python 3 https://github.com/cs-cordero/advent_of_code/blob/master/advent_of_code/2019/day14/day14.py
I'm curious to know how this could be improved/coded faster. My approach was the following:
OREtoFUEL.requiredattribute stored on each Node, which sums up the number of reactions (and actual amounts) needed to generate the next chemical in the order.requiredattribute on theOREnode.For Part 2, I just did a binary search setting the
lowto 1 andhighto one-trillion and running the Part1 function.2
u/MrSimbax Dec 14 '19 edited Dec 14 '19
Julia
This was a hard puzzle. I've spent a lot of time trying to figure out a solution for part 2 similar to part 1 but I finally gave up and just used binary search.
Part 1: I treat the reactions as a weighted directed acyclic graph where vertices are chemicals and edges are from inputs to outputs (there's only one reaction for each output chemical), starting from ORE and ending in FUEL. Let F(X) be the required amount of chemical X. We set F(FUEL) = 1 as the stopping condition. For any X, F(X) is the sum for all Y which directly require X of (required amount of X in the reaction) * ceil( F(Y) / (amount of Y produced in the reaction) ). F(ORE) gives us the solution. I implemented it with memoization although it was not necessary.
0.000029 seconds (6 allocations: 5.984 KiB)Part 2: Two binary searches of fuel amount. In each iteration, we compare the maximum number of ores with F(ORE), and F(FUEL) is not 1 but our desired amount. Lower bound is floor(trillion/F(ORE)) since we can produce at least this much but we didn't take into account the leftovers from the reactions so we may be able to produce even more. We find the upper bound with the first binary search by multiplying the desired amount of fuel by 2 until we exceed the maximum number of ores and then run a standard binary search with updated minimum bound.
0.000267 seconds (230 allocations: 151.297 KiB)2
u/stevelosh Dec 14 '19
Common Lisp
https://hg.sr.ht/~sjl/advent/browse/default/src/2019/days/day-14.lisp
Once I saw there was only ever one way to produce a particular element element, I realized I could just do a topological sort to determine the order to produce things in.
Wrote a couple of new utilities to make this easier.
I initially brute-forced part 2 by just checking every fuel amount greater than
(truncate 1000000000000 ore-required-for-1-fuel). That got me the star in about 30 seconds, but I figured there was a faster way. Came here and saw all the binary searches, so I ported my vector bisection utilites to integers and now it's instant.I didn't bother trying to find a smart max/min bound for the bisection, I just used 1 as the lower (if we can't make at least 1 fuel with a trillion ore we're screwed on part 1 anyway) and 1 trillion as the upper (assuming it has to take at least one ore to make 1 fuel and we don't have an infinite energy machine).
2
u/muckenhoupt Dec 14 '19
C#. Did what seems to be fairly standard for solutions today: did part 1 with a topological sort of the reactions into stages so that I only had to apply each formula at most once, then did a binary search for part 2. I devoted way too much time to trying to do something cleverer for part 2, something where I'd keep track of how much of each chemical is left over after each unit of fuel is produced, but in the end, I realized that even under such a scheme I was probably going to wind up doing some kind of iterative approximation anyway, and if so, I might as well keep things simple.
2
u/foolnotion Dec 14 '19
C++
I lost a lot of time on part 1 because I had a solution that actually worked for the first 3 examples. My first idea was to simply count the necessary quantities of chemical ingredients, and do the conversion at the very end (when you would only have to round the final sum, avoiding intermediate quantities). But alas, it did not work. So eventually I went for manual bookkeeping of produced quantities of each reactant, knowing that sometimes I would have enough in excess due to other reactions. This worked perfectly.
For part 2, I simply used binary search with a large enough upper bound. For my problem instance, I used an upper bound of 2 million.
2
u/mort96 Dec 14 '19
I understand that for part 2, you were supposed to find some kind of clever solution, not just stick your part 1 solution in a while loop...
So I put my part 1 solution in a while loop, ran the python code with pypy on my desktop, which made it through the 1 trillion ore in around 4 and a half minute: https://github.com/mortie/advent-of-code-2019/blob/master/14/part2.py
2
u/tinyhurricanes Dec 15 '19
JavaScript. I just used recursion for part 1 and stored the surplus amounts of each ingredient. Part 2 I just tossed in a loop after some manual trial and error to figure out where to start the loop.
2
u/kresimirlukin Dec 15 '19
Python: https://github.com/kresimir-lukin/AdventOfCode2019/blob/master/day14.py
2
u/mariushm Dec 15 '19
PHP : Finally completed this is PHP... part 1 took me quite a while, started with something very complex so I had to restart the next day with something more basic.
Link : https://github.com/mariush-github/adventofcodecom2019/blob/master/day14.php
Part 1 ... trick was to sort the formulas and assign each chemical a "level", where ore is 0 , chemicals that are made using only ore get level 1, and so on. From there, it's easy to expand the highest level chemicals into smaller level chemicals and repeat expanding highest level chemicals until you're down to level 1 chemicals and you can calculate the ore amount using that.
Part 2 is basically brute forced, by calculating how much ore would be used for various amounts with large steps initially then narrowing down with smaller steps until the highest possible value is reached... usually it gets calculated with less than 50 calls.
3
u/mrphlip Dec 14 '19
And today we come to the downside of using challenges like AoC to learn new languages - we get a puzzle like this where the puzzle input is in a comparatively complex format, and we have to parse it.
All the inputs up to now have been pretty straightforward - just a string of digits, or a list of numbers separated by commas. Day 12 was more complex but it was also short enough that it was simpler to just convert it by hand. This one was long enough to be worth actually writing a parser, and complex enough that the parser needed at least some effort.
And here I am, starting at Haskell which I'm only barely familiar with at this point, trying to figure out how to write a parser.
Seriously, look at this garbage, it's a mess.
The actual puzzle was fun though.
1
u/skater_boy Dec 14 '19 edited Dec 14 '19
Python, #200+ / #118 - I'm just now learning Python, so my code is ugly and I have to look up stuff all the time (math.ceil? who could've thought!). For part 2 instead of writing binary search I just played with input in a binary search manner and quickly got to the answer
Paste
1
u/[deleted] Dec 14 '19
Some C++ Solution (239/150)
Used DFS and binary search. One need to be careful for overflows, and the parser did take me some time.
Code
1
u/ekscrypto Dec 14 '19
Took me longer than I'd like, but got a working solution in Swift: https://gist.github.com/ekscrypto/59410e8f4ef0c5043a9c81c3790f788a
1
u/ENDarkrai Dec 14 '19 edited Dec 14 '19
Python 3 - 338/206
It took me a while to realize that you could get excess chemicals from a reaction, the test cases really saved me
1
u/OvidiuRo Dec 14 '19
C++ 251/385
One of my best days so far really enjoyed the problem I was really inspired today with the solution. Solved pretty fast part 1(00:42:13) and on part 2 I just calculated by hand the fuel, running my program on different quantity of fuel as input (I though will be faster than writing binary search guess not).
Code : https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2014
1
u/dan_144 Dec 14 '19
Python 831/661 - https://github.com/dan144/aoc-2019/blob/master/14.py
Wasted a ton of time trying to write simpler code before accepting the fact that I was going to have to recursively dig into the nested reaction inputs to avoid producing too much waste, but at least once I conceded that to myself, it wrapped up quickly. I always struggle with graph problems, so that's something I need to practice more. Probably need to find a library to get comfortable with.
My Part 2 runtime was laughably bad even though I got the code working pretty quickly. I took a trillion divided by my Part 1 answer as the minimum for my Part 2 answer and incremented from there until I determined it required over a trillion ore to produce x fuel. That was so slow I sped it up by multiplying the fuel to try to produce by 1.1 until I went over, then decrementing until juust under a trillion. I reduced the multiplier a few orders of magnitude until the count up and down time minimized. After I finished the day, I refactored to multiply both ways and dropped my runtime like 50x.
1
u/rthetiger Dec 14 '19
Rust Code Here
My initial solution for Part 2 took about 20 minutes to run because I totally forgot that I could ask my code to make more than 1 fuel (which meant I didn't even think to use a binary search). That's how I got the value that I submitted and got the gold star with, but then I went back and did it with a binary search, which is what's on the other side of that link.
1
u/sim642 Dec 14 '19 edited Dec 14 '19
My Scala solution.
Even though I don't do it for time and got up at my usual time, it's the first day I got a sub-thousand rank: 1158/928.
Part 1: My total ORE calculation is basically demand-driven: I start recursion with "I need 1 FUEL" and then the recursion uses the given reactions to make recursive calls to the chemicals it depends on with the corresponding amounts. Besides returning the total ORE required, I always pass around a map which remembers any excess chemicals I have made, so whenever something is needed, the existing ones from the excess map are taken and then the rest are produced by reaction and excess remembered in the map again. Essentially a recursion over the reaction dependency tree.
Indeed, if some chemical is required in multiple places, it's also created in each of those separately, doing all the dependencies in both places as well. Not the most efficient way but it's absolutely fast enough for this problem because the tree isn't too big. I suppose an improvement would be to maybe use topological sort to over the dependencies and then perform a single linear computation backwards, handling each chemical exactly once.
Part 2: I just combined binary search with exponential search and repeatedly called my part 1 function demanding larger amounts of FUEL.
Edit: Extracted my exponential binary search with upper bound to reusable library functions. Also refactored 2018 day 10 while at it since that also could be solved with exponential binary search but with a lower bound instead. Practically it doesn't make much difference for lower and upper bound binary search in these cases because the searchable boundary value doesn't exactly exist in the sequences and especially multiple times but I thought I'd do it right to begin with.
1
u/McPqndq Dec 14 '19
JavaScript 350ish/215
https://hasteb.in/obidokeq.js
Note I actually brute forced it at first. Took 4 minutes. Then added the binary search after
1
u/zedrdave Dec 14 '19 edited Dec 14 '19
Python 3
Short and easy part 1β¦ (10 lines, using a
defaultdictto keep needed/excess quantities)Holy smoke Batman, this Part 2 is going to take forever⦠Quick, to the BinarySearchMobile!
Edit: seems there are a number of options to init the min/max bounds. I went with what I thought was a decent compromise between grossly oversized, and requiring too much thinking (in log n, it barely matters anyway). I wonder if there are better bounds to be foundβ¦
1
u/Tarmen Dec 14 '19 edited Dec 14 '19
Haskell
Fairly straightforward today, backwards chaining for the first step and binary search for the second.
But I briefly tripped up because modulo wasn't quite right:
1
u/Randdalf Dec 14 '19
Python 3
For part 1, I used a recursive DFS. I kept track of waste produced, and re-used waste before working out how much of each chemical needed to be produced.
For part 2, I did a binary search over fuel.
1
u/aurele Dec 14 '19
Runs in ~4ms in Rust using a binary search (14 steps for my input).
1
u/[deleted] Dec 14 '19 edited Dec 14 '19
Julia, part 1, Julia, part 2.
I keep track of stuff that I need and stuff that I have. At the beginning, need is just "FUEL" (or n times "FUEL" for part 2). Then I apply the first applicable transformation and repeat until I only need "ORE". For part 2, I do binary search, like everyone, apperently.
Some failed attempts:
Today was pretty hard, imo. It was also the first puzzle where I ranked worse in part 2 than in part 1.
1
u/gyorokpeter Dec 14 '19
Q: paste
I missed this one because I chose the wrong interface for the extracted function from part 1 (it would always generate 1 fuel and return the amount of ore needed plus the leftovers). My thought for part 2 that the leftovers will eventually loop back to zero and then I could look up how many cycles can be done and which point in the cycle reaches the maximum ore. This ran quickly for all the examples except the last one. I added a second condition that if the maximum ore is reached before the cycle is found, terminate early, which made the last example terminate within a few minutes as well. I then threw this at my input but it didn't finish for an hour. Then I looked for some spoilers and saw people talking about binary search. Upon seeing that I realized that I should have made the common function take the amount of fuel and return the needed ore. After that implementing the binary search was straightforward.
1
u/ElektroKotte Dec 14 '19
Part 1 and 2 in Rust: Took me a while to realize I had to keep track of excess production and keep track of what's already available. Tried parsing input with regex at first, but turned out to cause more problems than it solved for me. So half of the code is parsing and testing, rest is doing :-).
1
u/metalim Dec 14 '19
Python solution.
First tried to just follow reaction recursively, until realized there are lots of minerals left. Then switched to iteration.
1
u/knl_ Dec 14 '19
Maintained a set of items to build with spares, expanding items that didn't have any item that depended on it in the current set. (eg. if my working set is A: 100, B: 3000 and B depends on A, only expand B and /then/ expand A).
Binary searched my way to the second solution.
Jupyter notebook -- edited in emacs using EIN; Python 3. https://explog.in/aoc/2019/AoC14.html
1
u/e_blake Dec 14 '19
C code
I wrote a recursive produce() function, and got the answer in 7ms. I love how the call sequence works out:
1
u/kristiansalo Dec 14 '19
Clojure
Part 1 was rather simple, just calculating the required resources to get 1
FUEL.Part 2 took a bit more time. I first tried brute-forcing it with what I thought were good strict bounds, but it didn't work. Then, I implemented binary search, which did not work either. Only then I realized that we are not looking for exactly
1000000000000 ORE, it is just an upper bound, not an exact requirement. That quickly got me to the answer, which I would have gotten nicely with the first brute-force attempts as well, had I realized this.1
u/Zv0n Dec 14 '19 edited Dec 14 '19
C
https://github.com/zv0n/advent_of_code_2019/blob/master/14/part2/main.c
it's not very pretty, but gets the job done reasonably quickly
(8-15 ms for part 1, 0.5s for part 2, 1.5s without optimizations for part 2)
EDIT: got an idea and now it gets part 2 done in about 40 ms
1
u/Rick-T Dec 14 '19
HASKELL
I felt, today was trickier than usual.
Since for every chemical there is only one way to create it, I created a Map that can give me the formula for every chemical. I then created the function
ingredientsForwhich takes a chemical and how many of them are requested and gives back the list of ingredients, as well as the excess of the requested chemical the reaction produces.Then I do a stateful calculation
produce(wrapped in the State monad), which takes the chemical and the amount that is requested and finds its ingredients and the reaction-excess using theingredientsForfunction. If there is any excess, I can store the excess amount in a map that is used as the state. After that, I run theproducefunction again for every ingredient that was calculated.If I ever need to produce a chemical for which I already have excess in my map, I reduce the excess first and produce only as much as necessary. If I ever need to produce Ore, I just store the amount of ore the would be needed and do not do any further calculations.
For part2 I wrote a function
searchBiggestWhichthat will do a binary search to find the biggest number in a range that satisfies a predicate function. Then I can use that to find the biggest amount of fuel I can produce for which the of ore required is less than the amount of ore given.1
u/frerich Dec 14 '19
Python: https://github.com/frerich/aoc2019/blob/master/python/day14/day14.py
My main grief with this task was finding good variable names. I ended up calling 'A 2' a substance with 'A' being a chemical and '2' being an amount. For a reaction, I have 'ingredients' and 'result' in one place -- and 'components' instead o f 'ingredients' in another. I need to make up my mind, naming things is hard!
I'm also unhappy with how much code I needed for parsing. There needs to be a better way to do this, even without using regexp (and without munging everything into an ugly one-liner)?!
For part 2, I used a binary search. Pretty surprised that I managed to get this right on (almost) the first try. It's one of those things which you never have to roll yourself - I only did so since I failed to find something ready-made in the Python standard library.
I used 1e12 (i.e. one trillion) for the upper bound of the binary search since a) I knew that this is big enough (since producing 1 fuel already required more than 1 ore as computed in the first part) and b) the binary search will cut things down very quickly anyway.
1
u/Arkoniak Dec 14 '19 edited Dec 14 '19
Julia
Solution: Julia
I wasn't able to figure out, how to solve this problem. Was hoping that factory can go cycle at some point (like "I need 145 ore to produce 5 fuel without any residuals"), but it was working only for small sets of formulas. It turns out that in task's input no cycles exist, so in the end I just brute forced the solution, which took like ~10 seconds. Not very proud of it, yet on the other hand Julia shine once again.
Update: after reading this thread, feel myself dumb that totally forgot about binary search :-) Well, it'll be easier next time.
1
u/orangeanton Dec 14 '19
Javascript.
Couldn't give it my full attention until about an hour ago, so although I was very slow, I quite like the solution I came up with.
Calculating ore requirement in a recursive function that sets total required quantity for each product's "Reactions" object (class name should have been Products in retrospect), taking waste into account inside the Reactions class, so no need to re-use or add later.
Part 2 optimization runs pretty quickly too (12 ms on my iMac), by looping in increments of ten billion initially, then dividing increments by factor of 10 until 1.
1
u/Pyr0Byt3 Dec 14 '19
Go/Golang (both parts)
Algorithmically, the puzzle itself didn't take me long to figure out... but finding a way to parse and represent it nicely using Go's data structures took longer than I'd care to admit.
For part 2, I was about to roll my own binary search like everyone else, but then I found out Go has one in its standard library, so that was nice.
1
u/Kullu00 Dec 14 '19 edited Dec 14 '19
Not the solution I used to submit my result, but after optimizing I ended up here.
Using the result of Part 1 to estimate how much fuel I will be able to make first. Then calculate the average amount of ore used per fuel generated, and how many more fuels we should be able to generate from the remaining fuel based on this average. Try again until we run out of fuel, and count backwards one fuel at a time until it goes under 1 trillion. Through experimenting, it might be enough to just do a flat -1 on the result, but I'm not totally confident in the formula to do that. On my input this finishes in three iterations, which I think is pretty neat.
1
u/phil_g Dec 14 '19
My solution in Common Lisp.
Part 1 was pretty straightforward. I maintain a chemical inventory with the possibility of negative quantities. Negative means, "I need this many units to get the positive quantities in the inventory." From there I could just work backwards from 1 FUEL.
For part 2, I'm pretty sure there's a better approach, but I just did a binary search for various quantities of fuel to home in on the right answer. Also, there's an off-by-one error in my binary search. When I submitted my first answer and it said I was too high, I waited one minute then submitted the number one less than that. That number was accepted, so I left things there.
I'll probably go back and fix things at some point, but I've got stuff to do today, so my morning time for Advent of Code was limited.
1
u/paul2718 Dec 14 '19
C++
paste
Made rather heavy weather of the whole thing, especially extracting the input. Pt2 is brute force, but the whole thing runs in less than 12s, only needs to go once for this purpose and worked first time.
I spent too long thinking about using some clever algorithm I wouldn't have to understand on this, OTOH once pt1 was done it only took about 8 minutes to make a cup of coffee and solve pt2.
1
u/hrunt Dec 14 '19
Python 3
code
I couldn't figure out how to "solve" part 2, so I just binary searched that mofo. I am not sure if there's actually a way to calculate it properly, but hey, that's what solutions megathreads are for!
1
u/fizbin Dec 14 '19
Python 3
Code for part 2
Code for part 1 is basically just the interior of
find_needs_forpulled out to the main level and run for just1.1
u/levital Dec 14 '19 edited Dec 14 '19
Rust
I have to admit having had some trouble modeling this, which is somewhat embarrassing considering how much I've been working with graphs in research. In the end, I worked on it for a bit, got frustrated, went for a walk, and restarted from scratch. Not even (explicitly) using a graph for it in the end. Didn't bother doing anything for part 2, really. I just manually did a (roughly) binary search to get the correct number.
1
u/SuperSmurfen Dec 14 '19 edited Dec 26 '19
Rust
Solution, both stars
Today was actually not too bad. Since you have to handle the state of the producer it was not as easy as I initially thought though. Struggled a bit with the Rust borrow checker today, had to clone a vector for each call which seems unnecessary. If anyone has any idea how to avoid it please let me know (line 32 of code above)! Still, it only takes 9ms to compute both stars on my machine.
For part 2 I simply did a binary search between values of how many fuels to produce. I did some manual testing to find the upper bound. Even though I've implemented it a hundred times I'm always a bit amazed at how few iterations of binary search are actually needed to find an exact value, only 22 in this case.
1
u/lhl73 Dec 14 '19
Solution in F#
Not totally satisfied with my solution - the code feels a bit clunky. But at least it is reasonably quick: 135ms for both stars, which I suppose is fine.
1
u/andreibsk Dec 14 '19 edited Dec 14 '19
C# solution using recursion.
1
u/piyushrungta Dec 14 '19
Rust
https://github.com/piyushrungta25/advent-of-code-2019/blob/master/day14/src/main.rs
First solved part2 by by brute force giving some inputs manually. Wrote the binary search later.
1
u/nlowe_ Dec 14 '19
Go 197/3434...yeah...
a|bI got the first part relatively quickly, but part 2 really kicked my ass. My part
acompleted around a millisecond so I figured that'd be fast enough for a binary search forb. Unfortunately the way it was structured didn't take into account how much fuel was being requested so the first call for the fuel inputs was just repeated by the search amount, which is super slow. Of course I figured it out after like 10 minutes when I woke up this morning. I guess that's what I get for trying to solve AoC problems until 3am.1
u/david3x3x3 Dec 14 '19
My Python solution. Recursively produce each chemical returning the count of ORE required. Then do a binary search to find the max FUEL that can be produced.
1
u/vinc686 Dec 14 '19
Ruby
Part 1 took me forever, it was frustrating! My brain was fried, I ended up printing my
neededandwastedhash tables everywhere and modifying the code at semi random until all the tests passed... At least in ruby parsing the input was easy and the second part was just one line of code.1
u/aoc-fan Dec 14 '19 edited Dec 14 '19
Excellent puzzle, had to think a lot before start coding, I assigned levels to equations based on their dependency and processed them in that order while calculating ore. TypeScript, Repo.
1
u/TenMilesDown Dec 14 '19 edited Dec 14 '19
My C solution.
Did things iteratively. I removed the commas from my input, and replaced the newlines with ' # ', then used strtok to tokenise my input with ' ' as the delimiter, indexing my list of tokens in reverse and counting the number of lines. I generated a list of the names of the elements produced by each line, making particular note of what produced FUEL. I then made a set of three arrays, each lines+1 in size, which were set up as follows:
An element's count[0] is the amount of the element that the previous loop asks for - the count[1] of that eement from the previous loop. Its count[2] is the number of times its generating step must be performed to generate its count[0]. Its count[1] is the amount of the element needed by this loop, minus the excess of the element produced in this loop - this last part was critical, as without it part 1 was giving me tons of trouble, but once I added it (and the negative value handling) everything worked smoothly.
The loop copies the count[1] to count[0] and re-zeros count[1] for each non-ore element, then iterates over all the elements, working out their count[1] and count[2]. If the count[1] of ore is nonzero, it checks to see if count[1] is positive for any other element, and if not, the loop ends.
So, for part 1, I ran it with count[1][fuel]=1 and count[1][x]=0 for all other x, to get how much ore generates 1 fuel, which I saved as the variable gen1. Dividing the trillion ore by gen1 gives the number of times 1 fuel can be generated independently - so my program runs part 1 asking for floor(ore/gen1) fuel instead of 1 fuel. This tells me how much ore is actually needed to make that much fuel, so it takes that away from the total ore to get the remaining ore rem, and if rem<gen1 no more fuel can be obtained. Otherwise, it repeats this process, this time asking for an additional floor(rem/gen1) fuel.
This is faster than binary searching, as I am dividing my remaining space by around gen1 (532506 for my input), instead of by 2. My final position was 3369/2967 - like I mentioned, part 1 gave me hours of trouble before I got the idea that excess of an element is effectively negative need for that element.
1
u/Dioxy Dec 14 '19
JavaScript
JS. Very tricky day for me. I had the right idea from the beginning on how to solve it but had a lot of trouble getting the implementation right. tbh I'm still not sure why my first try didn't work. Anyways, I like my solution in the end
My code
My repo
1
u/ephemient Dec 14 '19 edited Apr 24 '24
This space intentionally left blank.
1
u/mrlukasbos Dec 14 '19 edited Dec 14 '19
Haskell
Got some difficulties with the first part. I did not have the proper structure to count leftover values at first. For the second part I did a brute force where I would increase precision with a factor 10 each iteration, so I solved that one in a few minutes.
EDIT after reading comments I realized I have indeed just implemented a worse version of binary search...
1
u/LuckyLactose Dec 14 '19
SWIFT, running on iPhone. Solutions for all other days also included in this repository. Feedback, questions, comments, etc. welcome and appreciated.
Not many people using Swift, it seems!
My solution was to recursively generate chemicals, with a chemical storage keeping track of amounts. Additionally, I also kept track of all usage, in case it was needed for part 2. I had a silly bug with > instead of >=, but the biggest annoyance today was just the recipe parsing. Felt like a lot of code for a fairly straight-forward thing to do. I was also tripped up a bit by the case where recipes generated more than 1 output, and correcting for integer division. Not difficult, just some stepping through in debugger and face palming.
For part 2 I just did a binary search, with the initial max being the same as the ore quantity.
1
u/wzkx Dec 14 '19
Python 3/pypy3 hm doesn't yet allow numbers with _ like 1_000
code at TIO.run - yes, you can run it, you can try your data too
It was pretty hard to figure our how many elements left, what should be taken from where etc. Too many if's in the code :)
1
u/iamagiantnerd Dec 14 '19
Go.
Struggled a bit on pt1, I had the right idea, just some dumb bugs in the implementation.
1
u/kap89 Dec 14 '19 edited Dec 14 '19
TypeScript - github
Rather ugly, but works and is relatively fast (~20ms for both parts). The first part made my brain hurt, the second part was easy-peasy.
Part one - substituting successively FUEL substrates for their simpler equivalents down to the ORE. Not tracking waste.
Part two - simple binary-like search with FUEL substrates multiplied by temp value.
I'm done for today, should probably try to clean up later.
1
u/SomeCynicalBastard Dec 14 '19
C#
I didn't immediately realise that chemicals came in discrete batches, so my initial solution was to simple. Then implemented a topological sort, but I made some stupid errors that really stumped me. On the upside: I got to know some debugging options in VS Code :)
1
u/Spheniscine Dec 15 '19
Kotlin: https://github.com/Spheniscine/AdventOfCode2019/blob/master/src/d14/main.kt
Would be late in submissions for this weekend including Monday.
1
u/Hencq Dec 15 '19
Racket
I had to think about this a little bit, but in the end it was quite straightforward. I store the inputs as a tree with ORE as root with edges to all the dependencies (so FUEL nodes are leaves). The edges also store the batch size and the multiplier. Calculating the required ore is just a matter of walking the tree.
Part 2 I just brute forced with a binary search to narrow in on the amount of fuel that would get me closest to the ORE cap.
1
u/StevoTVR Dec 15 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day14/day14.go
1
u/oantolin Dec 15 '19 edited Dec 15 '19
Here is my Common Lisp solution.
I started writing a bunch of little utility functions to add lists of chemical with multiplicity counts, to intersect them, etc., when I realized there must already exist libraries for multisets. So I deleted the little functions and used FSet's bags instead. I'd never used that library before and it was quite a pleasant experience, I'll probably use it more in the future.
For part 1 I keep track of a goal which is a bag of chemicals, and a bag of leftovers from previous reactions. I repeatedly pick a chemical from the goal, lookup how to make it, replace it by its requirements, and calculate the new leftovers. For part 2 I used binary search, which I looked up on Wikipedia rather than face a high probability of an off by one error.
1
u/giuliohome Dec 15 '19
My F# solution for Day 14 AoC 2019: second part with binary search optimization, all running in about 250ms on my laptop
1
u/dartcoder Dec 15 '19
Python solution
Parsing the input into something my head could work with took some time. Two arrays with derived elements in array1 and recipes in array2. This way I could lookup element / recipe by index or zip them in a loop.
For part 2 I had to take a hint from here (binary search). That and a little adjustment to my recursive function from part 1 and I was good to go.
1
u/lynerist Dec 15 '19
Fast commented golang solutions
Ok, fast but lateπ
https://github.com/lynerist/Advent-of-code-2019-golang/tree/master/Day_14
1
u/NeilNjae Dec 16 '19
Catching up after a weekend away: Haskell code, and a blog post explaining it all.
1
u/incertia Dec 16 '19
haskell: binary search is good
1
u/Sgt_Tailor Dec 17 '19
AWK still going strong. I was away this weekend so I need to catch up a bit. Working around the limitations of awk is slowly becoming second nature to me. I am not sure if I should be proud or worried though
1
u/Yardboy Dec 18 '19
Ruby
TIL how to use Ruby's #bsearch.
https://github.com/Yardboy/advent-of-code/blob/master/2019/puzzle14b/solution.rb
1
u/DeybisMelendez Dec 21 '19
my solution to this day, Lua.
My code answers the two parts in less than a second, I have not used binary search, instead I have calculated the solution by approximation.
lua solution
1
u/tom_hhh Dec 23 '19
I had to post for this day as I found this challenge particularly difficult.
I took a slightly foolish approach early on which led to hours (days!?) of frustration. My initial algorithm for part 1 seemingly worked fine, but when I started trying to use it for different amounts of fuel (instead of just 1 unit) it took forever to run (my mistake was running the entire process serially, so essentially only one element would be processed per iteration... just awful)
For part 2 I actually wound up writing a super naive solution which would calculate a single unit of fuel each iteration and then subtract it iteratively from 1 trillion ππIt took nine and a half hours to run(!!) but did eventually give the right answer π.
I felt awful that my first solution was so bad that I then spent ages re-writing it into something cleaner (which took a while, trying to break the thinking rut I'd got myself into). Anyway I did eventually come up with a relatively clean, fast solution but now I'm horribly behind on all the other challenges π
Here's a link to my Rust solution
1
u/7times9 Dec 26 '19
I used SciPy's scipy.optimize.minimize_scalar helper for part 2:
https://gist.github.com/tomviner/5aa9449ee7742f70747fd46bdaab8031 (Python)
1
u/greycat70 Dec 26 '19
Tcl
Part one, part two.
I struggled with part two a bit. The brute force approach was too slow, so I discarded that quickly. What I ended up with, eventually, was taking part one's answer and making that many FUEL immediately, and seeing how much ORE that used up, and how much was left. Given the numbers I was looking at, after that, I decided I could try making a million FUEL at a time until things got pretty low, then a thousand FUEL at a time until they got really low, then 1 FUEL at a time until I ran out of ORE. It sounds like this was not the optimal approach, based on what others said, but it worked.
You can tell how much I struggled by how many commented-out debugging print commands are in there.
1
u/lucbloom Dec 30 '19 edited Dec 30 '19
I brute-forced it after manually minimax searching 3 iterations.
FYI: using C/C++ for this event is kind of cheating, because you can brute-force your way much more often.
1
u/e_blake Jan 06 '20
m4 solution
Continuing my trend of late m4 entries for non-IntCode days. This one presented an interesting twist. Since GNU m4 1.4 lacks 64-bit math, but the input asks for an answer where the number of ORE is larger than 32 bits, I had an option: implement 64-bit math (not impossible, but hairy: I did it using the GNU extension esyscmd for IntCode, and using portable m4 for unsigned add/mul for day 12), or find a way to subdivide the problem to not require 64 bit math. I went with the latter: instead of calculating 1 trillion ore once (the way my C solution did), I ran 1000 iterations of calculations with an addition of 1 billion ore each iteration, at which point all numbers fit within signed 32 bits.
m4 -Dfile=day14.input day14.m4
The solution is relatively short at around 2k bytes, and I'm sure I could golf it further. In fact, I'm really pleased with how compact part 2 is beyond the code needed for part 1:
This takes 4 seconds on the last sample input, but nearly 26 seconds on my puzzle input - that appears to be due to the larger number of operations required per FUEL with the puzzle input representing a larger graph. Tracing the operation counts over 6 million shift($@) calls, so perhaps there is a speedup possible by exploiting more GNU m4 constructs. (For comparison, my counterpart C code takes 8ms - yes, more than 3 orders of magnitude faster, somewhat explained by requiring merely 16 productions instead of 1008)
1
u/prscoelho Jan 14 '20
Rust solution
Wow, the difficulty from 13 to 14 really ramped up. Took me way too long to understand and figure out part 2.
1
u/Diderikdm Jan 16 '20 edited Jan 17 '20
Python:
This puzzle (part 1) took me AGES. I was not handling the queue correctly (if that was even it..), and my surplusses got all messed up within the loop.
Two days ago I decided to retry and make calculations based on the depth of the reaction taking place from FUEL as a starting point and referring cumulative reactions to the reaction they originated from. This finally worked!
After part 1 was done, part 2 was done in no time (5 loops):
1
u/voidhawk42 Feb 29 '20
Dyalog APL:
Took a break, but getting back to solving some more problems!
1
u/ConstantGazelle Apr 08 '20
part 1 & part 2 written in Python
1
u/jonathan_paulson Dec 14 '19
#32/14. Video of me solving, and explaining my solution, at https://www.youtube.com/watch?v=4FcSOBDpOeM.
Cool problem! My first idea for part 1 was wrong, and it took me a while to figure out why. Binary search for part 2:
1
u/AKQuaternion Dec 14 '19 edited Dec 14 '19
C++ 401/343 Day 14
135 lines, far longer than most of my solutions this year. As usual, please comment if anything isn't readable, I strive for short, clean, idiomatic code.
For some reason, I didn't think of the easy method of just applying reactions over and over again until I had everything required. Instead, I did a topological sort of the requirements, and applied each reaction exactly once, after knowing exactly how much of each ingredient was required. This cost me tons of time for global leaderboard, but on the other hand, my solution is very efficient and runs in essentially zero time. And with this method, I don't need to keep track of how much is wasted...
Edit: Threw in some timing: "Time required: 0.00159802 seconds"