[Vox Codei Redux] Predict bomb movement

Puzzles
#1

Good morning everyone,

Today I’m stuck on a problem. The Vox Codei Redux puzzle is giving me a headache…

I created a code to be able to place bombs where it’s the more useful. But I’m stuck on the bomb movement prediction. How could I predict what the map will be in … 3 turns?

I could compare the actual map with the last one to know what the movement will be, but when they are too many bombs, the movement of each bomb won’t be predictable because of crossings…

What did you do?

Thanks,

#2

My code guess the mouvements of each moving nodes. When they are too many moving nodes, my code can’t guess all the mouvements from the first turn. So it just wait until it can guess for all moving nodes. Sometimes it take 4 or 5 turns to guess everything and then i plant the bombs. Here an example : https://www.codingame.com/replay/solo/64688953

As you can see, my code do nothing the 5 first turns because it can’t know for sure how the nodes move. But when it knows every move of every nodes, it plant the bombs.

#3

Thank you for your answer! That’s what I was asking to myself. Well, may I ask you a last question? Are you planning which bomb you’ll plant on each turn when you know every move of every nodes? I mean, do you calculate if you’ll win at the turn you are able to know every move of every nodes? (I’m afraid to have a too big delay on calculating each possibility)

#4

I have a heuristic solution. I know i have X bombs, and there is Y nodes to destroy. So each turn, i look how the game will be in 3 turns. Each cells on the map will have a score, the score is the amount of nodes i’ll destroy by planting a bomb here now. Then i keep the highest cell and plant a bomb on it.

But i have some exception

  • I check for the next 20 turns. If the cell will have a better score in the next 20 turns, i don’t plant a bomb on it now.
  • Very specific case for the last level. If a bomb will put the game in a “dead state” (i can’t destroy the remainings nodes with the bombs i got), i don’t plant it
#5

Thank you for all the precision. The code I imaginated was way more complex than that. Now let’s code! :slight_smile: