Feel free to send your feedback or ask some help here!
Pas si vite ? Bande de vilains pervers qui n’aiment pas être dynamités !
What was the winning strategy? Backtracking?
why the final score is compute based on the example tests?
When putting the challenge in the “single player” section, I think you should clarify in the instructions that the nodes are destroyed on the round that follows the explosion, and not on the same round. Or was it written and I missed that part? (Anyway, good bye, 100%… T_T)
EDIT: I read the statement again, and fair enough, it is accurate. Problem is, in the visualizer, the bombs appear to explode one round early. Well, no big deal, better luck next time I guess. 
EDIT2: I would like to add that it is very nice to have the report 15 minutes after the challenge instead of the next morning. That’s less time worrying where I went wrong. 
1 Like
That was cool ! I liked having only the big exercise to focus on, but with lots of levels of difficulty
3 Likes
How do you think, Monther Carlo method is good for this challenge?
No, I don’t think Monte Carlo is appropriate here. I used a greedy solution that failed on the test designed to foil greedy solutions. I tried using a feasibility checker that recursively projected future moves but it failed because it was too slow when there were many bombs and so I had to disable that and settle for a 94% score. I think a quicker feasibility checker that just made sure there were enough bombs to cover the remaining detectors would have worked because I notice that none of the tests bothered to require you to use the rule that bombs could trigger other bombs.
Couldn’t find a better way than performing divide and conquer. Takes about some CPU time, but ensures you don’t miss any possibility.
Got trouble doing that in C, since the time limit is 1 second, and the code is executed in valgrind.
Do you mean, that in each turn you put the bomb which destroys as much nodes as possible?
Yes. That also means checking that a bomb isn’t being placed where another bomb already is and isn’t counting detectors that another bomb that has already been placed but hasn’t gone off yet will destroy. But that won’t always work since it is possible to make a move that blows up the most detectors but leaves you in an unwinnable position. For that case you need to not make that move and make a move that will destroy fewer detectors while leaving you a feasible position.
Thanks, I thought about this first, but I had not time to do it, because my friend call me to football match 
How did you use D&C? thanks
basically it’s a recursive function which explores for a specific turn of the game all possible bomb locations, as well as the wait case. Then for each location and the wait case it calls itself to explore all possibilities for the next turn, and so on until you have placed all bombs. Whenever you find a solution where there are no remaining nodes on the map, then you are done, and can either wait or place the bomb at the location leading to that solution.
But this sounds to me a backtracking solution, it’s not not D&C, where is the Divide approach?
I can’t run this puzzle in “Solo” mode. The IDE opens, it sends the default solution and I land on the results page with a score of 0%. When I press “Retry” it does the same again.
I don’t have this problem on other puzzles. Am I the only one?
The last test case was one where one centrally planted bomb would wipe out most of the targets, but the remaining targets were too scattered to take out with the few bombs you had left. I ran out of time on this one, but I came up with a scheme to use:
To deal with the last test case, we need to plan ahead.
   For each position on the grid, scan for spy nodes.
       If we find any at all, make a copy of the map and mark the blast radius.
   If we have enough to deploy at all locations, go ahead on.
   Otherwise we have a problem.
   Now we combine (bombs) number of blast maps to find one that will eliminate all
   nodes.
   We OR (bomb) number of blast locations together, then
       compare with original to see if any nodes are left. This requires exhaustive
       combinations of all the premutations of blast maps.
   When we have our list, then we need to schedule our bombs.
   We can do this by simply restricting our normal scan to locations from our list.
   Each time a bomb is placed it is stricken from our list.
Since there is only 15 minutes left, I doubt I will be able to complete it in time.
   I’ve done enough of these problems I should have planned ahead better, but where’s
   the fun in that? Much more to fun to just try and bull your way through. I mean,
   I’m not getting paid, and planning ahead is lot like work.
1 Like
Well at each step the problem is divided into as many subproblems as there are interesting bomb locations (and the no bomb case).
I might be incorrect, but to me backtracking and D&C are very similar.
For the last one, I was copying the board to calculate the first turn “aftermath” of the naive bomb placement : 4 nodes left + 3 bombs left + the best possible position would only destroy only one bomb.
Which is trivially impossible to complete. Bascially a very obvious trap detector, which should do the job.
This passed the final test, but unfortunately I didn’t have time to adjust it to fix a few execution errors this thing was causing elsewhere in my code.
1 Like
it’s definitely not D&C, your solutions is brute force or backtracking if you some discard non-viable solutions. The approach is pretty slow due to constraints.