A forum to this puzzle: https://www.codingame.com/ide/puzzle/vox-codei-episode-2
I beat this with some little scheme to catch how nodes were moving and a greedy algorithm. Both my movement catching scheme and the greedy algorithm broke down on the last test but I patched them up with some hacks. I tried to bruteforce this in a more proper way but couldnt so had to resort to hacks in the end. Would be interested to hear about other peopleās solutionsā.
I also had to resort to some hacks for the last test.
There are two problems with the last test:
- Some moves would destroy more nodes in the short term, but force you to use more bombs in the long run (placing bombs between cross shaped static nodes)
- Some moves could destroy more nodes if you are able to plan 15 turns ahead. (half cross shaped static nodes + 1 moving node in the bottom)
I think itās doable if you split the terrain between smaller areas surrounded by indestructible blocks, and try to plan ahead deeper for these zones.
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,
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 : Coding Games and Programming Challenges to Code Better
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.
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)
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
1 Like
Thank you for all the precision. The code I imaginated was way more complex than that. Now letās code! 
Salut Ć tous,
Il y a une erreur dans lāĆ©noncĆ© au niveau des contraintes sur les variables :
Il est Ć©crit 3 < rounds < 20 alors que la valeur limite dans les tests semble ĆŖtre <100
Je nāai pas encore fini le puzzle, mais je reviendrai poster ici quand Ƨa sera faitā¦
Hi,
Here i got 90%. I managed to clean my code before begin to think about that last test. Like in the last difficult Vox Codei puzzle, i think the good way is eliminate max kill option if future win is impossible due to lack of bombs. But iāll take some days to think about that because maybe there is a scheme to detect those situationsā¦ Iāll come back when finished.
This puzzle is very interesting 
So, i tried a simple trickā¦ and did 100%. Perhaps some tests are missing to disable this possibilityā¦
Solved it using backtracking.
I started by discerning nodesā movements, then built a parameter space. Then I reduced it to a manageable size by discarding points that I deem strictly worse than others. Then used backtracking to find the first valid solution that covers all nodes within available amount of bombs.
The trick is, of course, to reduce set of candidate solutions to a size solvable in 100ms.
2 Likes
The relatively clean way that I have found to handle this,
is to use the moving range of the node as a priority sorting weight.
In this episode nodes are now moving! How to get nodes direction on start?
Thanks.
Observe the positions over several turns.
It is save to assume that
- at the beginning all blocks are visible (no two blocks at the same location)
- there is a unique way of moving (#@@# could be #āā# (swapping places) or #ā¦# (both stationary), this case wonāt occur)
- you have enough turns to fully analyze the moment before placing the first bomb
Ok thanks eulerscheZahl.
Some test cases are hard to analyse (like #08: āindestructible nodes, 4 bombsā where they all start in a same diagonal ans leave in different directions)
Done. 2 episodes 100%
I managed to solve the task in the third turn (100 ms time frame) for episode 2 and in the first turn for episode 1.
For episode 1 first I mark best cells for placing bombs (which will destroy more than 2 surveillance nodes) and then using DFS to try different combinations of those cells.
For episode 2 first I gather the movement data from the first two turns, then generate the surveillance nodes movement directions, after that I mark the best cells to place bombs, using the directions data and simulating all rounds and then try different combinations of those cells using DFS.
Most important things I made, were to sort the candidate cells based on the destroyed nodes if a bomb is placed there and if a bomb destroys much nodes, use it immediately.
I got here after trying about 4 different strategies in time span of several weeks.
My combination algorithm is not good itās rather problem specific, and generates many duplicate combinations, but at the end it worked nicely.
Cheers
I am stuck at 80% with Vox Codei - Episode 2 puzzle. I have a working simulator and a DFS-style search on the game state tree, but:
- If I limit search depth to 4 steps ahead, then IDE tests 08 and 10 fails (use up too much bombs in sub-optimal solution)
- If I try to search deeper, even more tests fail due to timeout.
I am not sure how to proceed:
- Do I miss some important search tree pruning idea?
- Or shall I simply try to make my code faster? (Itās currently not speed-optimized, using arrays of objects, more bytes than essential for game state representation, and written in PHPā¦)