How do you search for the bomb places? Do you consider all possible places of bombs that will affect at least a surveillant node in the next move? If you do, the number of possible moves will increase crazily fast. Try a bit greedy, and you’ll see the performance is improved.
My brain doesn’t feel the same after solving part 2…
In the first few rounds I wait and analyze node movements until all nodes’ move directions become known for sure. After this, I can simulate node movements for any rounds in the future. I run a DFS on these simulations (with a fixed depth limit that is more than the bomb timer by several rounds), thus searching for the most node kills (counted after a fixed number of simulation rounds, allowing bombs time to explode.)
In the search tree I limit the branching only to the best 3 (a fixed number) possibilities. ‘Best’ meaning how much direct kills that bomb can make (I pre-check this without doing the full simulation). So this is the ‘greedy’ part of the algorithm in place.
The problem with being such greedy is that in IDE TEST 10, my search puts happily a bomb at (4,4) and at (11,7) because of the direct 4 kills. But that means 2 bombs wasted as each neighbouring sections must use up a bomb for a single kill, so in the end 2 nodes remain. For similar reason, I also fail TEST 08 (1 node remaining alive).
If I raise the horizon by considering more than the 3 best bomb placements, or by going more rounds in the simulations, then timeout kicks in.
Wow… Your method is very similar to me.
In the last test, you should try to divide the map into smaller regions, and focus on solving the subproblems one by one, to be able to increase the number of rounds. There are probably many ways to do this, but I stick with a simple flood fill algorithm because it’s relatable to me. By doing this, I could predict ahead 8 moves.
I didn’t consider any 3 best bomb placements like you did, instead I try to find the best bomb, then search for the surrounding if there are any bomb that could affect this result. Removing duplicates or inefficient ones (bombs destroying the same 2 nodes, destroying 2 nodes but there’s a better bomb that destroy 3 nodes including the last 2,…) (trust me there are a lot) and you’ll find improvement
I almost finished the puzzle, but I have a bug I need to share: The only testcase I’m not able to solve is Foresee the future better with two bombs:
BUT in the test Foresee the future (same with three bombs), I solved it… using only 2 bombs:
This shouldn’t be too hard to solve, but I had to share it
What’s your code for handling the bomb limits?