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.
1 Like
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…)
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 
Good luck.
2 Likes
Really cool game !!
It’s amazing to see how this game is easy to solve for any human, but finally so hard to solve with a coded AI. At first, I thought this puzzle would be solved in an evening… I took me 5 half days 
Thanks for this really interesting challenge 
PS : I used recursivity, simulation, brute force, and several conditions to avoid all the traps
2 Likes
And 10 days later, the episode 2 is now solved !! I’m proud 
It was really hard, but very interesting and so fun !! Thanks for this great challenge 
I am in a hurry to see the solutions of the other players.
3 Likes
Finally managed to solve 100% (in C) using backtracking approach without any hacks for specific tests. In case anyone is interested, here’s how my algorithm works:
-
It waits first 3 moves and determines all nodes’ directions (where they are moving). I figured that first three positions unambiguously define all node movements, assuming no nodes are overlapping on the first move.
-
After it determined nodes’ directions, it starts backtracking search and outputs the sequence of moves. During next moves it doesn’t think and just outputs next move in the sequence it calculated on the 3rd move.
-
Backtracking works like this (in short): generate all possible moves (including WAIT) for the current state, try the first move, save it in the sequence, update state, repeat. If wrong state occurs (for example, there are still nodes, but no bombs left, or reaches maximum rounds), it goes back, restores previous state and tries next move.
-
The most tricky part to implement is the move order during move generation, because it has the biggest influence on the performance. If it just generates all possible moves and tries them in random order, the algorithm will timeout even on the 1st test. So, it should try “better” moves first, best case scenario: all the correct moves are first, and no backtracking occurs.
-
So, during move generation, it copies the current state, updates it three times and uses it to see which nodes will explode. For each empty cell (where no nodes, no walls, no bombs), it tries to explode the bomb there and counts how many nodes are exploded in the future. It also counts how many moving nodes are exploded. If no nodes are exploded, then this bomb placement is discarded.
-
Then it sorts bomb placements in the following order: first those which explode the most moving nodes, and if this amount is the same, it puts first those which explode the most nodes (including non-moving ones). The WAIT action is tried the last.
-
It iterates from the first action to the last (excluding WAIT) and marks the nodes which are exploded by the action. Then, when it gets to those actions which explode only one node, it discards them if previous “better” actions already explode this node (these actions are redundant).
-
The simulation was relatively easy to implement but is still tricky. The interesting part is when one bomb’s explosion causes another bomb to explode immediately. First I thought that it is very hard to implement since there can be “bomb chains” (i.e. the bomb explodes, causes another to explode, it explodes the third and so on). But, since the bomb timer is 3 moves maximum, the biggest chain would include only 3 bombs. It allows me to implement this part in very simple way: when the bomb is placed, its timer is set to 3 moves. Then all bombs in the explosion range (including the newly placed one) set their timer to the minimum timer value amongst them. So, when one bomb explodes and causes this newly placed one to explode, it should explode all bombs in its range and thus they all should explode at the same time, hence they have their timer value set to the minimum value amongst them. And during the simulation when one bomb explodes, I only need to check which nodes it explode and I don’t need to check which bombs it causes to explode.
Initially, I only sorted bomb placements only by the amount of nodes exploded (including non-moving nodes) and the last “Vandalism” test timed out. Interestingly, some test was randomly passed and timed out later without changing any code. I guess my algorithm there was on the border of 100 ms. I tried limiting the number of generated moves for each position to 5 best ones (plus WAIT action) - all tests were consistently passed, but the last still timed out.
Found here on the forum the idea that for the last test, the map should be divided into smaller regions (using flood fill) and each solved separately. Way too complicated I thought and the solution didn’t seem universal (what if the last test had random “holes” in the walls of smaller regions?). Another idea was to somehow calculate the minimum number of bombs required to explode remaining nodes, and if the number of bombs left is smaller than calculated number - then to backtrack (so it backtracks way earlier, otherwise in hopeless positions it waits, explodes remaining bombs in every possible order, backtracks, waits a turn more, explodes again in every possible order, waits two turns more and so on - so many pointless cycles). But I haven’t managed to come up with the algorithm to calculate this number.
Then I came up with the idea to sort bomb placements by amount of exploded moving nodes. In the last test the first moves was to explode those four non-moving nodes (maximum number of exploded nodes), but this is wrong. And when it prioritized exploding moving nodes, the last test was finally passed. I don’t consider this move prioritization a hack for the last test to pass, since targeting moving nodes should be a good strategy in all cases - it is easier to explode non-moving nodes in conjunction with some moving node and one should not waste the bomb only on non-moving nodes while there are still moving nodes.