posted 2 years ago
Hmm, been very busy with day 19 of AoC 2022, and what a nightmare of an exercise this is.
At first reading I thought of applying some linear optimization tricks, but I did not manage to get some working formulas. And besides, I could not find any free software that could solve such a thing.
Then I decided to go for brute force, DFS search, since I was afraid that BFS would tend to very long queues. But with DFS, there are several strategies that you can apply. Whatever strategy I tried, I did get 9 for the example blueprint 1, but I got only 11 for example blueprint 2.
Today I tried the strategy of: given a minute, buy as much geode-robots as possible, and if there is some 'cash' left, buy as much obsidian-robots, et cetera, and enter the next minute with this new situation. I also dfs'ed doing nothing in that same scenario. To my big surprise I got 13 as the optimal result for example blueprint 2! Yes, a bug of course, but here is my version of the scheme that was given in the example.
every line starts with an m, giving the minute at hand. Read for minute the situation at the end of the previous minute, so for minute 1 we see the initial state, with just one ore-robot and nothing else. Then in the next minute (m: 2) we see that we did nothing, just letting that robot collect one ore, and that situation is seen on the line with m: 2, so in fact it is the end-situation for the first minute as given in the example.
Have a look at m: 14. If we compare the 4 numbers on the right (giving the number of robots) and compare that to these numbers in the line above, we see that we built an ore-robot and an obsidian-robot. That costs 2 + 3 ores and 8 clays. If we look at the previous line, we ended with 5 ores and 8 clays, so these become 0 and 0. Then we had 5 ore-robots and 6 clay-robots, so the minute ends with 5 ores and 6 clays, and with 6 ore-robots, 6 clay-robots and 2 obsidian-robots.
I checked the whole list, but I did not find any mistakes. As you see, I ended with 13 geodes, where the example claims that 12 is the optimal number.
And I know it is a monk-labour (monnikenwerk), but can anyone spot whats wrong with my scheme?
**************************************************************************************************
Piets result day 19 AOC 2022 example blueprint 2
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
**************************************************************************************************
m: 1, c: INIT, or: 0, cl: 0, ob: 0, ge: 0, orR: 1, clR: 0, obR: 0, geR: 0
m: 2, c: DID_NOTHING, or: 1, cl: 0, ob: 0, ge: 0, orR: 1, clR: 0, obR: 0, geR: 0
m: 3, c: DID_NOTHING, or: 2, cl: 0, ob: 0, ge: 0, orR: 1, clR: 0, obR: 0, geR: 0
m: 4, c: BUILT_ORE, or: 1, cl: 0, ob: 0, ge: 0, orR: 2, clR: 0, obR: 0, geR: 0
m: 5, c: DID_NOTHING, or: 3, cl: 0, ob: 0, ge: 0, orR: 2, clR: 0, obR: 0, geR: 0
m: 6, c: BUILT_CLAY, or: 2, cl: 0, ob: 0, ge: 0, orR: 2, clR: 1, obR: 0, geR: 0
m: 7, c: BUILT_ORE, or: 2, cl: 1, ob: 0, ge: 0, orR: 3, clR: 1, obR: 0, geR: 0
m: 8, c: BUILT_ORE, or: 3, cl: 2, ob: 0, ge: 0, orR: 4, clR: 1, obR: 0, geR: 0
m: 9, c: BUILT_CLAY, or: 4, cl: 3, ob: 0, ge: 0, orR: 4, clR: 2, obR: 0, geR: 0
m: 10, c: BUILT_CLAY, or: 5, cl: 5, ob: 0, ge: 0, orR: 4, clR: 3, obR: 0, geR: 0
m: 11, c: BUILT_CLAY, or: 4, cl: 8, ob: 0, ge: 0, orR: 5, clR: 4, obR: 0, geR: 0
m: 12, c: BUILT_OBSIDIAN, or: 6, cl: 4, ob: 0, ge: 0, orR: 5, clR: 4, obR: 1, geR: 0
m: 13, c: BUILT_CLAY, or: 5, cl: 8, ob: 1, ge: 0, orR: 5, clR: 6, obR: 1, geR: 0
m: 14, c: BUILT_OBSIDIAN, or: 5, cl: 6, ob: 2, ge: 0, orR: 6, clR: 6, obR: 2, geR: 0
m: 15, c: BUILT_CLAY, or: 6, cl: 12, ob: 4, ge: 0, orR: 7, clR: 7, obR: 2, geR: 0
m: 16, c: BUILT_OBSIDIAN, or: 7, cl: 11, ob: 6, ge: 0, orR: 7, clR: 8, obR: 3, geR: 0
m: 17, c: BUILT_OBSIDIAN, or: 8, cl: 11, ob: 9, ge: 0, orR: 7, clR: 9, obR: 4, geR: 0
m: 18, c: BUILT_OBSIDIAN, or: 7, cl: 12, ob: 13, ge: 0, orR: 8, clR: 10, obR: 5, geR: 0
m: 19, c: BUILT_GEODE, or: 9, cl: 14, ob: 6, ge: 0, orR: 8, clR: 10, obR: 6, geR: 1
m: 20, c: BUILT_OBSIDIAN, or: 8, cl: 16, ob: 12, ge: 1, orR: 8, clR: 12, obR: 7, geR: 1
m: 21, c: BUILT_GEODE, or: 8, cl: 20, ob: 7, ge: 2, orR: 9, clR: 12, obR: 8, geR: 2
m: 22, c: BUILT_OBSIDIAN, or: 9, cl: 16, ob: 15, ge: 4, orR: 10, clR: 12, obR: 10, geR: 2
m: 23, c: BUILT_GEODE, or: 10, cl: 12, ob: 13, ge: 6, orR: 10, clR: 12, obR: 12, geR: 3
m: 24, c: BUILT_GEODE, or: 11, cl: 16, ob: 13, ge: 9, orR: 10, clR: 13, obR: 13, geR: 4
m: 25, c: BUILT_GEODE, or: 10, cl: 13, ob: 14, ge: 13, orR: 11, clR: 13, obR: 15, geR: 5
A: 13
There are three kinds of actuaries: those who can count, and those who can't.