The Viking mythology predicted that Saturday, February 22, 2014, would be the day of Ragnarok, an apocalyptic end of the world where Men, Gods and Giants would fight in an ultimate battle from which no-one would come back alive.
The courageous programmer who joined the battle could incarnate a young Thor, struggling against a horde of furious Fire Giants on the Vigrid plains.
“That challenge was just…AWESOME!”
skypers_
“Won’t get a reward this time 😛 Anyway, the concept was excellent! I really
liked mission to Mars, but I loved this one”
I208iN
“It’s a good thing there’s a challenge every month: if it was every week, I
guess I wouldn’t have any Saturday evening free anymore ^^”
pulse_
Two Coding Puzzles for a 4-Hour Coding Challenge
Power of Thor
The challenge started with this simple puzzle. You had to go from point A to point B on the map in order to reach the power of lightning and restore Thor’s hammer’s precious strength. To succeed, you just had to take the shortest path to the power of lightning.
Thor Versus Giants
The second puzzle revealed to be more tricky. The goal was to annihilate all the Giants with the lightning power, knowing that you had a limited number of lightning bolts to use. The Giants relentlessly moved towards Thor.
A fleeing strategy consisted in moving towards the Giants to attract them and then turn away to move towardsthe Giants’ barycenter.
A difficulty was to choose the most appropriate moment to strike: not too far from the Giants, and not too late.
The Strategy of the Top Players
“The first problem was a rather classical problem dealing with paths on a chessboard (with moves in 8 directions).
For the second puzzle, after a few trivial attempts that consisted in waiting for the Giants to come nearby, I adopted a more aggressive strategy by asking Thor to quickly move towards the Giants.
Basically, I wanted to calculate the minimal number of Giants that had to be beaten at each attack. So I wouldn’t strike a lightning bolt if the number of Giants within reach didn’t exceed this minimum number (except of course if Thor gets cornered).
Then I defined a “level of risk” for each square: a square is considered “dangerous” if it contains a Giant, or if it is within a distance of 1 case from a Giant (meaning that it will be reached by a Giant on the next turn).
That being said, the movement strategy consisted in moving towards the “safest dangerous square”, that is, the safest square next to a Giant. In case of a tie, I chose to move towards the center of the game.
I first decided to move towards the barycenter of Giants rather than the center of the game, but tests proved that this tended to lead Thor to the corners of the map if the Giants were not initially centered, which led test 10 to fail. You can still see quite a lot of this barycenter strategy in the remaining code.
Short story: I had not read the statement properly at first, and thought the lightning could touch 9 squares centered on Thor (a 3*3 square). This is when I got to the last set of tests that I realized I had been mistaken because, with my hypothesis, it was impossible to eliminate 15 Giants in only one strike. So for most of the time, I coded taking a harder constraint into consideration. In the end, it was positive and rather stimulating.
Another story: I based my calculations of distances on the infinity norm / 2-norm (which is the most common norm for movements in 8 directions on a chessboard), which I renamed “norm 1″ by mistake in the code…”
Gawen
“A simple greedy algorithm works surprisingly well. You just had to be as greedy as you can. I’ve checked some other people’s code and apparently, not everyone is greedy enough. Being greedy in this case means that Thor should try to get as close as he can to the center of the Giants’ bounding rectangle while trying to use the hammer as late as possible.
More formally:
- Determine giants’ bounding rectangle and its center.
- Determine a grid cell next to Thor that’s closest to the center but not in near any of the giants.
If such cell is found – move there
If there’s no such cell, check if waiting without a hammer strike will get Thor killed. If it will get Thor killed – STRIKE, if not – WAIT- If you are feeling fancy, you can also check if you could kill all giants if you did a strike right now – to finish a game earlier.
And that’s it. Waiting as long as possible while trying to get to the center of the horde ensures that Thor kills as many giants as he can with every strike.
I ordered the giants by their distance to Thor and printed their coordinates relative to Thor, so it’s easier to see what’s going on from Thor’s point of view.
I thought that the giants moved at the same time as Thor which led to some problems and caused me to lose some time. I should have read the problem statement more carefully!
Pretty simple. Hope it explains :)”
Redvasily
“For the first puzzle, there are 8 possible directions. I just take the one that minimizes the Manhattan distance between Thor’s location and the Light’s location.
The main logic for the second puzzle goes as follow: each turn, Thor can move to 8 possible locations or stay where he is. After moving, each of the giants will move towards Thor. For each of the 9 locations, I calculated the sum of the square distances between Thor and the giants after the move and pick the location which minimized this sum.
The reason for doing this is simple: the giants will form a simple polygon on the (x,y) plane and we would like to keep Thor at the center of this polygon. The center of a polygon is a location which minimizes the square of distances to the vertices of the polygon.
Now, after picking the above location, if a giant would be able to move on top of Thor, then Thor must strike before making that move.”
Gaurav
The Coding Competition Results
Even if this contest was finally shorter than previous ones, it took the first contestants quite a while to reach 100%.
Gawen finished first in 01:35:51 in Java, followed by redvasily (01:49:16 in Python) and by Zoyd (02:04:08 in Java too). Two Java advocates on the podium, that’s a first for CodinGame… Check out the full leaderboard.
