Power Of Thor - Episode 2 - Puzzle discussion


#22

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.


#23

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é?


#24

That one had me sweat a little :slightly_smiling:
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.


#25

Man, you saved my life! :smiley:
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".


#26

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)... :astonished:


#27

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.


#28

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?


#29

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


#30

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


#31

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.


#32

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.


#33

To anyone who's having trouble, Here's what I did:
1. Go to the centroid, if possible
2. Strike if I can't move anywhere, or all giants are in range
3. If I can't move towards centroid, try all other directions and choose the one which puts maximum giants in range (basically greedy)
These 3 simple rules helped me pass all the tests. Hope it helps :slight_smile:


#35

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.


#36

Thank's CyberLemonade, i did this:
1. Go to the centroid (keep one cell between Thor and giants) with a little trick :sunglasses:,
2. Strike if I can't move, or all giants are in range

It was enough to validate all tests