Ragnarok Top CodinGamers' code reviews

STAY CONNECTED, FOLLOW CODINGAME NOW


At a CodinGame challenge, no-one better explains a perfect code that the CodinGamer themselves. So we asked the best ranked Ragnarok players to comment their code, so that everybody could learn from their smart strategies. And they did, thanks a lot to them!



Gawen's (1st in rankings) solution in Java explained:



Exercise 1:

Nothing special to mention. It's a rather classical problem dealing with paths on a chessboard (with moves in 8 directions).

Exercise 2:

After a few trivial attempts that consisted in waiting that the Giants came nearby, I adopted a more aggressive strategy by asking Thor to quickly move towards the Giants.

Basically, the idea was to calculate the minimal number of Giants that had to be beaten for each attack, and most importantly, not to launch an attack as long as the number of Giants within reach did not 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).

This 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, we should choose to move towards the center of the game.

I first decided to go 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.

Little 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 most of the time, I coded taking a harder constraint into consideration, which, in the end, was positive and rather stimulating.

Other 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 as you can see.


Redvasily's (2nd place) solution in Python explained:


As for the code the, a simple greedy algorithm works surprisingly well, you just have 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 hammer as late as possible.

More formally:

1. Determine giants' bounding rectangle and its center
2. Determine a grid cell next to Thor that's closest to the center and it's not next to any of the giants.
2.1. If such cell is found - go there
2.2. 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

3. 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.

My code has some unused parts that could be optimized away, but that's the way it evolved.

At a line 103 I am done parsing input and outputting debugging information. The only interesting thing here is that I order giants by the distance from Thor, and print there coordinates relative to Thor, so it's easier to see what's going on from Thor's point of view.

Lines 103-114 - is a simple quickest route selection routine. Nothing fancy there.

At lines 121 - 124 are some residual code when I thought that giants move at the same time as Thor which lead to some problems later and caused me to lose some time. Read problem statement more carefully!

Code at lines 129 - 134 checks if Thor will end up close to a giant and should STRIKE instead.

Than the real magic happens at lines 136 - 158. If it was previously decided that we need to STRIKE, this part tries to delay STRIKE while getting to the center of the giants mob. Just loop through all possible direction, check if a cell Thor would go is valid (e.g. not an abyss), and measure distance to the target cell (mob center). If this location is found - go there.

Lines 159-161 do nothing. I thought I had some synchronization problems, e.g. my calculated Thor position didn't match actual Thor position.

Pretty simple. Hope it explains :)


Gaurav (4th place) solution in C++ explained:


Exercise 1:

#include <iostream>
#include <string>

using namespace std;

int main()
{
   // Read init information from standard input, if any   int lx,ly,tx,ty;
   cin>>lx>>ly>>tx>>ty;

   while (1) {
       // Read information from standard input       int n;
       cin >> n;
       // There are 8 possible directions, just take the one that minimizes
       // the Manhattan distance between Thor's location and Light's location

       if(tx<lx) {
           if(ty<ly) { cout<<"SE\n"; ty++; }
           else if(ty>ly) { cout<<"NE\n"; ty--; }
           else cout<<"E\n";
           tx++;
       }
       else if(tx>lx) {
           if(ty<ly) { cout<<"SW\n"; ty++; }
           else if(ty>ly) { cout<<"NW\n"; ty--; }
           else cout<<"W\n";
           tx--;
       }
       else {
           if(ty<ly) { cout<<"S\n"; ty++; }
           else { cout<<"N\n"; ty--; }
       }
   }

   return 0;
}

Exercise 2:

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

// Given 2 points (x1,y1) and (x2,y2), this method
// returns the square of distance between the points

int getdist(int x1,int y1,int x2,int y2) {
   return ((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

// This method does the same thing as in Question-1, i.e.,
// given initial position (tx,ty) and target position (lx,ly),
// it performs the best move available. This method will be
// used to determine the giants' moves towards Thor

void move(int &tx,int &ty,int lx,int ly) {
   if(tx<lx) {
       if(ty<ly) ty++;
       else if(ty>ly) ty--;
       tx++;
   }
   else if(tx>lx) {
       if(ty<ly) ty++;
       else if(ty>ly) ty--;
       tx--;
   }
   else {
       if(ty<ly) ty++;
       else if(ty>ly) ty--;
   }
}

// dn[i] is the ith direction in counter-clockwise order
// starting from East
// dx[i], dy[i] are the corresponding change in x and y coordinates

string dn[8]={"E","NE","N","NW","W","SW","S","SE"};
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,-1,-1,-1,0,1,1,1};

int main()
{
   // Read init information from standard input, if any   int tx,ty,h,n;
   cin>>tx>>ty;
   
   while (1) {
       // Read information from standard input
       cin >> h >> n;
       int gx[n],gy[n];
       bool f=true;
       for(int i=0;i<n;i++) {
           cin>>gx[i]>>gy[i];
           if(abs(gx[i]-tx)>4 or abs(gy[i]-ty)>4) f=false;
       }
       // If all remaining giants are within the strike-square
       // then strike to finish the game

       if(f) cout<<"STRIKE\n";   
       
       // Compute logic here
       // The main idea of this solution is as follows: In each time
       // unit we can move to any of the 8 adjacent locations or stay
       // in the same location, so there are 9 possible locations for Thor:
       // NW   N  NE
       // W  Stay  E
       // SW   S  SE
       // After making the move, each of the giants will move towards Thor.
       // For each of the 9 locations, we calculate the sum of square of
       // distances between Thor and the giants after the move and pick that
       // location which minimizes this sum. The reason for doing this is simple:
       // The locations of giants will form a simple polygon on XY plane and we
       // would like to keep Thor at the center of this polygon and 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, otherwise
       // he can simply move to that location. The following code implements
       // the above idea and gives 100% score.

       int mdist=1000000000,dir=-1;
       for(int i=0;i<8;i++) {
           int nx=tx+dx[i],ny=ty+dy[i];
           if(nx<0 or nx>=40 or ny<0 or ny>=18) continue;
           int d=0;
           for(int j=0;j<n;j++) {
               int tmpx=gx[j],tmpy=gy[j];
               move(tmpx,tmpy,nx,ny);
               int td=getdist(tmpx,tmpy,nx,ny);
               if(td==0) {
                   d=1000000000;
                   break;
               }
               else d+=td;
           }
           if(d<mdist) {
               mdist=d;
               dir=i;
           }
       }
       if(dir!=-1) {
           int nx=tx+dx[dir],ny=ty+dy[dir];
           bool done=false;
           for(int i=0;i<n;i++) {
               move(gx[i],gy[i],nx,ny);
               if(gx[i]==nx and gy[i]==ny) {
                   cout<<"STRIKE\n";
                   done=true;
                   break;
               }
           }
           if(not done) {
               tx=nx; ty=ny;
               cout<<dn[dir]<<"\n";
           }
       }
       else {
           bool done=false;
           for(int i=0;i<n;i++) {
               move(gx[i],gy[i],tx,ty);
               if(gx[i]==tx and gy[i]==ty) {
                   cout<<"STRIKE\n";
                   done=true;
                   break;
               }
           }
           if(not done)
               cout<<"WAIT\n";
       }
       
   }

   return 0;
}



No comments

Post a Comment