ShareMyScreen/AdventOfCode/2022/19/NotEnoughMinerals
Another tree search. How can I reduce the alternatives, and how can I cut off early?
One thing is clear: if you are planning to build, say, a clay-mining robot next, you should always build it as soon as you have the resources to do so. Thus I will model the run as a series of decisions on what to build next rather than by clock ticks. That will reduce the number of branches to prune. I will give priority to building the most valuable robots first. I start a script.
This 4-dimensional search space is way too big to visit every corner. I have to cut off unproductive searches. But how can I make a reasonable guess at what is possible 24 cycles from now?
After a couple of unproductive hours I consider a dynamic-programming solution, like I did for the integer knapsack problem, where I create a table of information representing the best solution after one cycle and incrementally update it. But I can't make it work: the state information is too big. I sleep on it.
On waking I realize that only ore production allows the diversion of its own output back to creating more of itself, producing exponential growth. The other resources grow exponentially only as multiples of ore production. I will make a continuous model of ore production and let it trickle through to the other resources. I fill up a couple of sheets of paper with calculus aimed at finding the optimal place to switch ore to other resources. When I get to the end, where I establish an upper bound on the number of geodes producible from a configuration, I realize an unpleasant fact. Production of non-ore resources isn't exponential, but it is quadratic: building 1 robot at cycle 24-n will add n of the resource. That means any conservatism in the bound is going to make for a pretty loose bound. Furthermore, the fact that only one robot per cycle can be produced is going to be very important, and my continuous model can't include that. I sleep on it again.
I wake with a fresh view. All I care about is how many geodes can be produced. The problem is that I might produce enough ore and clay early, and then spend hours enumerating all the ways of overproducing ore and clay. I need to produce a resource only if it is needed to produce more geodes. Yes, that's it. From every position I will always try to produce geodes first. If lack of a resource stops me from producing a geode (whether in the current cycle or in some later cycle), I will consider producing more of that resource in the current cycle. Otherwise I will prune the branch that would produce the resource in surplus.
MAXTIME =: 24
NB. Take a move, i. e. build a new robot
move =: {{ NB. x is (table where (<i,j){x is # of js needed to build an i) y is (prevtime);(delay);(robot to bring online);(stock of each resource as of prevtime);(numbers of robots built as of prevtime)
'time delay robno actives stocks' =. y
waitmask =. 0 0 0 1 NB. to begin with the only thing we need is geodes
delay =. (MAXTIME <. delay + time) - time
if. MAXTIME = time =. time + delay do. NB. advance clock to 1st cycle of production from added robot
NB. Time has expired. Remember how many geodes we opened
best =: best >. {: stocks + (actives * delay)
else.
if. #robno do. NB. if not first time...
NB. run the robots during the delay time, and account for resources lost to build the robot
stocks =. stocks + (actives * delay) - robno { x
NB. Bring new robot online
actives =. (>: robno { actives) robno} actives
end.
NB. At current production, how long before we can build each robot?
resdelays =. (x -"1 stocks) %"1 actives NB. # clocks we must wait, for each combination of (robot to build) and (resource needed)
totaldelay =. 1 + 0 >. >. >./"1 resdelays NB. total delay until production from each robot, including the 1 for building the robot
NB. Attempt to build each robot, provided that some later robot (including in recursion) is waiting on the robot's resource
for_r. 3 2 1 0 do. NB. Build geodes first
if. r { waitmask do. waitmask =. waitmask +. (0. < r { resdelays) +. x move time;(r { totaldelay);r;actives;stocks end.
end.
end.
NB. Return the mask of limiting resources, cumulative from this & lower levels
waitmask
}}
runsim =: {{ best [ y move 0 ; 0 ; '' ; 1 0 0 0 ; 0 0 0 0 [ best =: 0 }}"2
Now that I know the format I want for the blueprint, I can read it in. I put the example data on the clipboard and remove the excess linefeeds.
line =: {{ NB. Fill in the resource-requirement table for one blueprint
tbl =. 4 4 $ 00
tbl =. (0 ". ' ' taketo 'ore robot costs ' takeafter y) (<0 0)} tbl
tbl =. (0 ". ' ' taketo 'clay robot costs ' takeafter y) (<1 0)} tbl
tbl =. (0 ". ' ' taketo 'obsidian robot costs ' takeafter y) (<2 0)} tbl
tbl =. (0 ". ' ' taketo 'and ' takeafter 'obsidian robot costs ' takeafter y) (<2 1)} tbl
tbl =. (0 ". ' ' taketo 'geode robot costs ' takeafter y) (<3 0)} tbl
tbl =. (0 ". ' ' taketo 'and ' takeafter 'geode robot costs ' takeafter y) (<3 2)} tbl
tbl
}}
]tbl =. (line;.1~ 'Blueprint'&E.) LF ,~ wd 'clippaste'
4 0 0 0
2 0 0 0
3 14 0 0
2 0 7 0
2 0 0 0
3 0 0 0
3 8 0 0
3 0 12 0
I run the simulation on the example input. After fixing one bug (I had (1. < r { resdelays) instead of (0. < r { resdelays) as in the corrected version above), it works:
runsim tbl 9 12 +/ (runsim * #\) tbl 33
(#/) gives me a giggle every time I get to use it. Work out what it does and you'll see why.
Part 2 doesn't require any change except the running time.
MAXTIME =: 32
*/ runsim 3 {. tbl
5301
After 30 seconds I start wondering what I could do to make it faster, but it completes in under 2 minutes.
Revision
A few days later I am still thinking what I could do to make the program run faster. I realize that I could have pruned the tree better toward the end of the run.
- on the last minute n there is no need to build anything
- in minute n-1 and n-2 there is no need to build anything except geode
- in minute n-3 and n-4 there is no need to build clay
- in minute n-3, if a geode can be built there is no need to try anything else
- in minute n-5, if a geode can be built there is no need to try clay, or ore except when a later geode blocks on ore
I'm not sure about minute n-4, but I think that it's never wrong to build a geode if you can. It would be worth figuring out just when it would be right not to build geode.
I expect that these changes would be equivalent to shortening MAXTIME by about 2, which would be a noticeable factor in run time.