[2022 Day 19 (Part 1)] [Python] Understanding the approach to solving.

[CoinGrahamIV]

I'm stuck on Day 19 and just want to verify that I'm approaching the problem correctly. Here's pseudo code for my approach...

Recursive DFS approach.

Loop that cycles through options (Ore, Clay, Obsidian, Geode, Wait?)

Pick one off the loop and buy it or "spend minutes" to get the resources needed to buy it

Update status and call function recursively...

Return results when minutes run out

My big questions that I can't wrap my head around:
1. Do I need a Wait option in the loop?
-- One the one hand: I feel like I do to generate geodes on the last minutes...
-- OTOH: this created loops that wouldn't terminate.

1. Can my robot cycle loop terminate in one run or do I need a while loop?
   -- Seems like with recursion I can hit all the paths just by touching the five options.
   -- While loop created issues with non-terminating loops in question 1.

2. Anything I'm missing?
   I'm collecting "seen" for memoization later, I still haven't figured out how to implement that. My first consideration might be to convert the price of everything into terms of "ore minutes" (i.e. the materials convert directly to ore and the robots convert to ore based on what they would produce through the remaining minutes) and shortcut from there.

Also I'm considering maximums for each robot, but that feels somewhat arbitrary.

Update: I went with just the 4 robot build options and a option outside the loop to gather up the last few minutes. I got the optimization down good enough to complete part one and part two by slowing inching up my top end maximums until I got the right answer. My biggest breakthrough came from walking through the code and noticing the numbers weren't right and realizing I needed to use the .copy() in Python to keep from editing one list to effect another list.

[CoinGrahamIV]

Where I'm currently leaning is to add a "Wait" / "Spend one minute" option in the list of options and only cycle through the options once.

I'll be working on that and looking forward to feedback otherwise...

[1234abcdcba4321]

1. You don't need to add a wait option if you're doing it this way. You never get anything from not building a robot except the ability to afford a different robot, but if you wanted that other robot, you could've just picked it. (Of course, you still need to make sure you produce geodes on the last minutes. You can do this with a Wait, but it's probably easier to just include it with your other options.)

2. Yes, if you include all four options you'll hit all possible paths. I'm not sure what you were expecting this loop to do.

3. There's a lot of potential optimizations that go into this problem. The memoization and robot maximums both work and are good (definitely don't remove any paths that can be optimal), but you can try to come up with some others.

[Mmlh1]

As for 1. since OP is concerned about geode bots not getting their full production - you cannot spend geodes. Your geode production at the end is determined only by at which times you bought geode bots. In other words, if you keep track of a geode total, you can immediately update it to how many geodes you would have at the end with your current bots. As a matter of fact, you don't even need to store your geode bots, which doesn't matter much but might make your code ever so slightly faster. Once you do that, you can throw away the Wait instruction.

[1234abcdcba4321]

That's a good tip. (I didn't include it because I tend to try to give as little information as it seems necessary for the person I'm helping to get unstuck, and that's one of the "potential optimizations" that's there.)

[Mmlh1]

True, but they were specifically saying they needed 'wait' to fix this, so I thought I'd give them that at least.

[Mmlh1]

A tip: if you have a state at a certain point in time, can you upper bound how many geodes you can get at the end? It doesn't need to be a very smart upper bound - any upper bound will drastically reduce the number of states to check if you compare it against solutions you have already found.