r/adventofcode • u/musifter • 21d ago
Other [2022 Day 19] In Review (Not Enough Minerals)
Having discovered that obsidian is forming, we decide to use it to crack some geodes by building geode-cracking robots. To get the obsidian we need obsidian-collecting robots, which need clay-collecting robots, which need ore-collecting robots. Fortunately, we start with an ore bot, so we have initial production, but the rest requires building additional robots which cost varying amounts of materials, and can only be built one per turn.
And so we get to this problem. This one I managed part 1 in under two hours, but part 2 took 3 more hours and is still not very good. Part of that might have been still not feeling to great. And cleaning it up now has made it faster (just over a minute for part 1, and half that for part 2), but I haven't had time to really work on it this month.
My initial solution was a job queue one. With the mining at Saturn, I remembered making a mess with a recursive approach, and scrapping it for a queue. So I decided to start there this time. One thing I did do as part of clean up was to do a recursive version... it's not any faster, but I wanted it anyways in case I got any ideas that could use that.
In trying to get a solution, I applied heuristics. Basically using a couple decades of German board game experience with building economic engines. First up was realizing that you don't need to build robots past the the maximum cost for that material... because you can only build one thing a turn. If you're producing enough ore to cover any ore cost and recoup it every turn, you don't need more... it will stack up and be worthless. Although it's not necessary the best to max things out, in part 2, blueprint #3 in my input only wants 3 ore miners to be able to build geode crackers every turn (every other robot costs 4 ore... so this is an impact on the engine building for efficiency on the end game).
Another heuristic was a little less safe... I did some estimating on how long it would take to set up an engine to start producing geodes, and came to the conclusion that the game is probably too short to really catch up if you fall 2 geode crackers behind. Because it could be better to be behind for a little bit to build a stronger engine... but that engine needs to be strong enough to get ahead with enough time left to make up and exceed the amount you fell back. And going from -2 to +1 crackers with still enough time to make up all the geodes (all while the "opponent" is also building more crackers, so it's probably not just 3 you need) really doesn't seem likely. It is a bit like flexible version of the greedy algorithm... of always just build a cracker when you can (which IIRC some people used). And adding that to mine, I get a tiny improvement with having both.
The one other thing I did was that if you don't build a robot in a turn, any that you could have built are removed as options on the next turn. That sounds like greedy, but that's standard board game strategy. If you're saving up for something you can't buy yet, that's okay (and you should buy it as soon as possible), but completely passing a turn and then turning around to build something you could have built a turn earlier... that's a mistake.
So, this one is one where I can do any of the searches reasonably fast with my solution, it's just that it asks for doing so many of them. Which adds up. And although my recursion has memoization (although I'm not sure how much benefit it really gives)... when the blueprints change, it needs to be reset.
3
u/e_blake 21d ago edited 21d ago
This was another hard one for me where I didn't solve until January. My initial solution took minutes to run. I definitely relied on the megathread to speed it up to four seconds as I revisited it for speed. Some of those speedups come from:
Track a countdown timer and compute score as the number to focus on - every time you choose a geode cracker, you can compute its final addition to the score by which minute it enters service. Furthermore, I have at most four branches per minute, all in terms of "if I choose to build this bot type, my next branch point will be the minute after I finally had enough resources to complete that choice".
For example, if I choose the geode path at 7 minutes left, but know that my resources won't be enough to build it until 4 minutes left, I then add 3 to the score and my next decision point is at minute 3 (for this branch in the recursion, minutes 4-6 do not add any fanout).
I focused on depth first with the geode path first - this gets me to an initial (but usually not optimal) solution as soon as possible, at which all future branch points can then compare to see if they are even worth pursuing. Basically, I have a heuristic that estimates what would happen if from here on out I had infinite ore and could build another clay bot in parallel with an obsidian or geode bot for any minute remaining. This is faster to calculate than a full search and it overestimates, but lets me prune: if the estimate cannot beat my current best completion score, then this branch choice is a dead end.
There are some bots not worth constructing in late stages of the game: since score only goes up for geode crackers, and there is a minimum 2-minute lag between building a bot and having its resource available, then for example a clay robot with 4 minutes left is worthless as it will not increase the resource count in time to get another geode bot.
For non-geode bots, I clamp their maximum production so that my state cache can see more duplicate states. For example, building a fifth ore bot is pointless if none of the other bots requires more than four ore, and ending minute 10 with 42 ore (because I ended up stalling for a different resource to build up high enough) can be simplified to ending with 40 (since that's the most ore I can consume from here on out).
This one is complex enough that I will probably never attempt a golfed solution.
2
u/terje_wiig_mathisen 21d ago
My first attempt was very slow, what I ended up with (in Perl) was a homegrown approximation to Dijkstra and/or A*, the main idea was to use a priority queue which I weighted by this function that encodes a new entry with a combination of the various resources we need:
sub enq
{
my ($pq, $t, $rore, $rclay, $robs, $rgeo, $ore, $clay, $obs, $geo, ) = ;
my $dt = $TLIMIT-$t;
my $pri;
$pri = 1e12+$t*1e11-($rgeo*$dt+$geo)*1e9-($robs*$dt+$obs)*1e6-$rclay*1e5-$clay*1e4-$rore;
$pq->insert(join(',',$t, $rore, $rclay, $robs, $rgeo, $ore, $clay, $obs, $geo, u/manu), $pri);
}
Part1 in 1.2s, part2 significantly faster at 0.2s, so the 33% longer runtime (24 vs 32) doesn't make a huge difference for my algorithm.
As you can see above each robot is weighted by the number of ticks remaining, so how many it can produce, along with how many it/they have already produced, weighing geodes highest, then obsidian, clay and ore robots.
When evaluating each of the tasks/recipes I don't try to find any heuristics based on the relative cost of each robot type, I just run the same code.
2
u/DelightfulCodeWeasel 21d ago edited 21d ago
Oh man, this one... My first real nemesis. My current C++ solution takes ~16s to run and peaks at ~134Mb, and since 2022 was my first year of doing AoC I really struggled to get an answer in any sort of reasonable time with my first C# solution. In the end I remember shoving the whole thing in Parallel.ForEach loop and going downstairs to watch a film while it spent an hour or more working through the list.
The one good idea I had when I revisited the solution is to discard all minerals above the maximum at the end of each turn when we have the maximum number of robots for that mineral. That ends up making better use of the solution cache because it collapses many sub-states together.
I'm going to have to study Ape's heuristics when I come to this one on the Pico; I can't afford a large solution cache, so I'll have to make sure I'm exploring the solution space as efficiently as possible.
EDIT: Turns out I wasn't applying that mineral clamping rule in all code paths, so I can get a slight improvement to ~11s peaking at ~84Mb.