ShareMyScreen/AdventOfCode/2022/19/NotEnoughMineralsJP
This day had me stumped for a long time, and in the end, I "borrowed" the key part (the wait mask) from Henry's solution after all my ideas failed. One of the more crazy ideas I had was casting it as a constraint linear program, but this attempt failed because of numerical accuracy issues with floating point numbers (which simply did not finish either when using extended integers). I did learn that J does have two scripts for getting one jump-started on linear optimisation using the Simplex method (simplex.ijs and simplexnr.ijs in ~addons/math/misc/).
Entire solution
i19=: freads '19.txt'
NB. Part 1: +/ quality level= ID*max # geodes in 24 min
NB. parse input to id, ore, clay, obsidian(ore+clay), geode (ore+obs)
par=:".@(#~ e.&' 0123456789');._2
NB. Encode cost blueprint to matrix
encbp =: {{ (}. y) (0 0;1 0;2 0;2 1;3 0;3 2)}4 4$0 }} NB. check.
NB. recursive robot production
NB. x: blueprint matrix robots x resources
NB. y: time left, robots, resources (order: ore, clay, obsidian, geodes)
rec =: {{
'tl rob res'=. y
mask =. 0 0 0 1 NB. Keeps which robot we try to make
if. BEST <: ({:res)+(tl*{:rob)+(-:*<:)tl do. NB. stock+prod current+prod very optimistic future.
NB. find delays before we can build robots. _ where impossible without first building other bot.
resdel =. rob %~"1 x-"1 res NB. delay before resources are higher than cost
maxdel =. >: 0 >. >. >./"1 resdel NB. maximum delay per robot type
for_c. i._4 do. NB. for each robot type in mask, from last
if. c { mask do. NB. if mask value is true, try making robot.
if. 0>:newtl=. tl - step=.c{maxdel do. NB. time left <: 0 for this branch:
BEST =: BEST >. res (+tl&*)&{: rob NB. update largest amount of geodes created
mask =. mask +. (0 < c{resdel) NB. add current robot to mask to return
else.
NB. Recurse: update mask as above, OR mask of next step, pass new tl, new rob, new res
mask =. mask +. (0 < c{resdel) +. x rec newtl;(rob+c=i.4);(c{x)-~res+rob*step
end.
end.
end.
end.
mask NB. return mask
}}
run =: {{ NB. x: number of turns to run; y: parsed input
BEST =: 0 NB. set counters
(encbp y) rec x;1 0 0 0;0 0 0 0 NB. call recursion on initial inputs
BEST NB. return best score found
}}"1
part1=: ([: +/ {."1 * 24&run)@par
part2=: [: */ [: 32&run 3 {. par
(part1;part2)i19
Data and Parsing
So, today's problem is an optimization problem, trying to find the maximum number of robots of each type that can be produced given the costs (which is our input), given as follows (though each blueprint on a single line):
Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian. Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.
I write this little parsing verb, that, for each line, converts to numbers the characters that are either numbers or spaces:
par=:".@(#~ e.&' 0123456789');._2
As par cares only about numbers and spaces, the testcases can be concisely written as:
tst=: '1 4 2 3 14 2 7',LF,'2 2 3 3 8 3 12',LF
From the story given, it is clear the dependency pattern is the same for each blueprint, e.g. a geode robot will always require ore and obsidian. This is used in the solution as well.
Solution
For part 1, the solution should find, for each blue print, how many geodes can be produced at most, and give the sum of the products of the blueprint number with the produced geodes. Each robot takes 1 turn to build and harvests 1 unit per turn, and costs resources to build as given in the input, which are consumed when building starts. Each simulations starts with a single ore robot, and runs for 24 turns.
For ease of use, the blueprints, are once parsed, converted to a matrix with one row for each robot, and one column for each resource cost for that robot:
encbp"1 par tst
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
Now, I write a recursive verb that takes as x the cost matrix and as y the time left and counts of robots and resource. It's goal is to make the best robot it can, keeping which robots it is trying to make in a mask, and which makes time steps based on how long it takes to produce at least all resources required for the type of robot it is producing. It returns the mask of robots it is trying to build, in order to avoid building robots that are not needed anymore in the future (again, borrowed this juicy part from Henry).
rec =: {{
'tl rob res'=. y
mask =. 0 0 0 1 NB. Keeps which robot we try to make
REC=:REC+1
if. BEST > ({:res) + (tl*{:rob)+(-:*<:) tl do.NB. stock+prod current+prod very optimistic future.
GAVEUP=:GAVEUP+1 NB. give up.
else.
NB. find delays before we can build robots. _ where impossible without first building other bot.
resdel =. rob %~"1 x-"1 res NB. delay before resources are higher than cost
maxdel =. >: 0 >. >. >./"1 resdel NB. maximum delay per robot type
for_c. i._4 do. NB. for each robot type in mask, from last
if. c { mask do. NB. if mask value is true, try making robot.
if. 0>:newtl=. tl - step=.c{maxdel do. NB. time left <: 0 for this branch:
BEST =: BEST >. res (+tl&*)&{: rob NB. update largest amount of geodes created
mask =. mask +. (0 < c{resdel) NB. add current robot to mask to return
else.
NB. Recurse: update mask as above, OR mask of next step, pass new tl, new rob, new res
mask =. mask +. (0 < c{resdel) +. x rec newtl;(rob+c=i.4);(c{x)-~res+rob*step
end.
end.
end.
end.
mask NB. return mask
}}
At each level, it first checks whether for this branch there is any hope to beat the current BEST score, that is, if the sum of the current amount of geodes + the production of the current robots and a new geode cracking robot if one were to be made at every turn (which is the most optimistic scenario possible). Note that (-:*<:) is the Gauss summation of 0, 1, 2 ... being the production of the geode robots created (hypothetically) at times where the time left is 0, 1, 2 ...
For instance, if there are currently 3 robots, and the time left is 5 steps, the current robots would produce 15 geodes, the one created next 4 geodes, then 3, then 2, then 1; or in total 10 geodes could possibly still be produced (not looking at resources required).
If there's no hope of beating BEST, it gives up. REC and GAVEUP record how many times rec is called, and how many times it cuts off the current branch, being almost 27% on average for my input, which I found quite remarkable. Without this optimisation, the combination of the solutions for parts 1 and 2 takes about 10 times longer (try setting the first if. condition to 0).
If there is still hope, it calculates the delay, for each robot recipe and resource, that one should wait to have enough resources for building the robot in case. The maximum delay is the maximum resource delay rounded up to entire turns, per robot. This max delay is used as step size, so we don't simulate every single time step.
The for loop tries to make robots in order of preference: geode > obsidian > clay > ore (As the dependencies of the robots remain the same for each blueprint). Of course, initially, the geode robot building will fail, as it would take an infinity of steps to produce enough obsidian. After failing, the mask is updated to include robots for producing the resources that are required to build our geode robot. Then it continues to the second option, now included in the mask to make an obsidian robot, again failing, for lack of clay (added to the mask) then a clay robot is tried, which will work. At this point, the rec calls itself with the new time, the new amounts of robots, and the new resource stocks after the step, in order to update the mask, and see whether in the future, any robot will be waiting for others not yet in the mask, and still to be checked at the current level.
A simple run verb sets up the BEST score, and counters for my little optimisation and calls rec with the cost matrix and initial values:
run =: {{i NB. x: number of turns to run; y: parsed input
BEST =: GAVEUP =: REC=: 0 NB. set counters
(encbp y) rec x;1 0 0 0;0 0 0 0 NB. call recursion on initial inputs
BEST NB. return best score found
}}"1
So, run runs the simulation for each row of the parsed input, so for the 2 parts, we get the requested scores as follows:
part1=: ([: +/ {."1 * 24&run)@par
part2=: [: */ [: 32&run 3 {. par
Take away
- Recursion has more to it than simply repeatedly calling a function. Here, the mask is made by "future" runs of the function so that the current one knows what branches to try.
- Even the simplest, most optimistic branch cutting can lead to enormous benefits.
- In Day 16, I used time left for a similar optimisation, rather than actual time. Also for this problem it was a good choice.