What is your pruning strategy?
#AoC 2022 | Day 19 | Solutions & Spoilers
simple cypress
blissful lily
- if a proposed purchase would lead to more robots than needed to build things in a single turn, don't buy it
- if there's a useful pre-requisite that can purchased while waiting for an advanced machine without delaying the advanced purchase, don't buy it
- if magically the state started buying geodebots one a turn for the rest of the sim and still didn't outproduce the current best, don't add any new states to the frontier
simple cypress
1 and 3 sound ok, but I'm not sure about 2. What's the reasoning?
blissful lily
like, at the present I can build an obsidian robot in 1 turn or a geode robot in 4 turns, I could add both futures to the frontier, but the geode robot future is skipping out on possibly building an obsidian robot while it's waiting for 4 turns, so it's just always behind the other path. So avoid excess branching and just explore the future where I build the obsidian robot
i think my implementation of 2 is probably where the mistakes are happening
molten kernel
do you make sure you have enough ore such that building the obsidian bot doesn't slow down the geode bot making?
random rose
i think my implementation of 2 is probably where the mistakes are happening
i think the whole reasoning for 2 is flawed since you just won't know down the line how that affects purchase timings, just because you don't slow down the next purchase you still might slow down the one after that or possibly even further
blissful lily
i think the whole reasoning for 2 is flawed since you just won't know down the l...
the only shared resource between obsidian and geode is ore, and usually you're waiting on lots of obsidian, so if in the time to make the obsidian for a geodebot, you also generated enough ore for an obsidian bot, not buying it is wasting a turn you could build
random rose
But you might not be able to build a clay robot the turn after because you decided that branch is worse, having 4 ore and 3 obsidian robots may be better than having 0 ore and 4 obsidian robots. It's really the whole reason you can't just easily precalculate the best path without branching.
The problem is about timings so you just won't know how each combination of robots to ores will perform
Or at least if you had the method to actually calculate the best path with math you wouldn't be doing BFS/DFS in the first place.
In the same way you couldn't say for sure that (1, 2, 1, 1) < (1, 2, 1, 2) for the robots you couldn't say (1, 2, 1, 2) < (1, 2, 2, 2) either
kindred python