My solution was way simpler than I would have thought; it ended up something like ‘get as close as you can and only swing if you can kill them all or have no escape’. It didn’t require pathfinding or prediction, though the edge case of having them all in a line with Thor required a tiebreaker.
Fun puzzle.
Cela vient-il du Timeout ou d’une laveur retournée fausse? Dans le dernier cas, sur combien de bits l’entier de ta solution est-il codé?
That one had me sweat a little 
I ended up with a rather simple solution : try to get to the furthest giant, taking detours if the direct route is unsafe, and strike when cornered or everyone is in range. No pathfinding, no hardcoding for the last test, just good old geometry to test the 8 directions in the most sensible order.
Man, you saved my life! 
I hated this problem so much for lacking any definitive solution, and instead requiring us to find some kind of heuristic.
Your heuristic worked like a charm, I didn’t even implement any tiebreaker. But I used a magic number, though, to determine if I need to “swing”.
I ended up with a rather simple solution, close to yours. Instead of ‘swing if you can kill them all or have no escape’, I chose rather ‘strike if you can kill enough of them or have no escape’.
‘enough of them’ being the average of giants killed per strikes left.
I can confirm that trying to predict their moves is really tricky, I never had it 100% and the game does not even respect its own rules : for instance, try ‘E’ 11 times and ‘SE’ 8 times in the last testcase and at turn 18 you’ll see two giants at (16, 10)… 
When submitting I get 100% even with the last test case ever red.
Can’t figure out exactly how the giants move, but an approximation seems good enough to solve anything but the last test case.
I see a lot here about hueristics and bruteforce search algos, has anyone tried Genetic Algorithm for this or is predicting the giants too hard?
Hi Akadine,
I tryed with a Python AG, it give me about 80/90%.
I definitly miss calculation power for Horde, so first Hammer Strike are nearly random.
Other levels are OK.
My giant calculation is not perfect, I don’t handle when the area is already occupied by a giant.
I will port my AG to C++ and see if it help to be 100% even with Horde level.
BigUP
OK, I did it, 100% on Thor2 with a C++ AG.
I have to back port my code from C++ to Python,
100% with Python AG should be possible.
BigUP
Hi guys!
Thank you for the tip to apply minmax algorithm. W/o that I don’t know how I could have solved it. I used 10 as max depth. 8 was enough for all test except ‘Horde, 4 strikes’. There’s no need to precisely predict the giants’ move. It’s enough to know that they always want to catch Thor. The main thing is that Thor steps first, and the giants move in his direction. Centroid was another key word in my solution. Thor always wants to be there and wait as long as there’s no escape and he has no other choice than STRIKE. It was a very challenging test. I loved it.
My heuristic: move toward the centroid or the first safe direction close to that until trapped or all giants are in range.
By being trapped I mean the situation when waiting or moving in any direction leads to death.
To anyone who’s having trouble, Here’s what I did:
This idea extends CyberLemonades’s idea.
For step 3, another approach that sheds light is to modify the centroid, if the bounding box of the crowd looks too stretched out.
Thank’s CyberLemonade, i did this:
,It was enough to validate all tests
Solved it, I tried 3 different strategies:
All 3 involved the center of the bounding box formed by the giants.
Also I assumed a safe cell is if it doesn’t have giants around it.
WAIT is used only if Thor is on the BB center and his cell is safe.
If all left giants are in the range of Thor or “giantsInThorRange > giantsInPlay / leftStrikes”, STRIKE. If not move towards the BB center, if the move is not on safe cell, move on the first adjacent safe cell, found by clockwise iterating neighbors.
If all left giants are in the range of Thor or if Thor cannot move, STRIKE. If not, move towards the BB center, if the move is not on safe cell, move on the first adjacent safe cell, found by clockwise iterating neighbors.
If all left giants are in the range of Thor or if Thor cannot move, STRIKE. If not, move towards the BB center, if the move is not on safe cell, move on the adjacent safe cell, which has most giants in potential Thor’s range (if Thor would strike if he’s there).
All strategies passed all test cases, but only number 3 managed to pass the last validation test. I had problem viewing the validation tests animation, so I couldn’t find what’s wrong with the first two strategies.
Cheers
Thanks to you, I managed to solve the last 2 cases. Thank you !
Thanks for your suggesstion that I have passed all the tests 
I cannot believe that just by knowing the right kind of evaluation of 9 spaces around Thor in one move, it cleared all the giants. XD
Thanks for sharing!
Yes, the animation is awful. The crowd is covering the controlled unit plus we have absolutely NO WAY to send a debug message (unlike many other puzzles).
This all still blocks me from validation, while I pass 100% test cases with no idea what’s wrong during validation.
Btw, my strategy is very similar to yours.
You could output a string array representing the board, but only for the test cases, not the validators.
The main idea is to postpone the STRIKE as much as possible while gathering the giants near you.
I suppose your algorithm STRIKEs a turn or two earlier or on the last STRIKE one or two giants are not hit.
Not really.
During the validation of some levels I still manage to escape for quite a long time but then fail to strike when there’s no more possibility to escape.
Still the very same code works fine for 100% of test cases and most of the validation cases.
So I just wonder why it doesn’t strike here too… 
Have a look at my replay with problem showed