Tuesday, October 15, 2013

Codingame septembre 2013

Huitième post de la série cette fois avec pas mal de retard, comme toujours mes algos et codes en C++ pour les CodinGames. La page d’entrainement est toujours ici.

Le premier exo demande de simuler les déplacements d’un robot. Algorithmiquement rien de très compliqué pour cet exo, en revanche il faut être organisé pour produire rapidement un code sans bug.

J’ai choisi de coder le robot par un objet contenant les variables pour décrire son état (sa position, vers où regarde-t-il, a-t-il été “inversé”, est-il en mode casseur, est-il vivant). Je stocke également tous ses déplacements précédents, vu que si le robot boucle, il faut simplement afficher “LOOP”. Cet objet contient également une méthode avance qui simule un déplacement.

Pour détecter si le robot boucle, on peut soit utiliser l’algorithme du lièvre et de la tortue où vu qu’ici la mémoire n’est pas critique simplement marqué chaque case vue avec l’état du robot. S’il repasse par la même case avec le même état, c’est qu’il boucle. Attention dans ce cas il ne faut pas seulement avoir l’état du robot, mais également celui du plateau. Vu que la seule modification du plateau possible est les obstacles destructibles, et que cette modification est irréversible, on peut simplement se souvenir du nombre de murs détruits.

Enfin une bonne factorisation, consiste à utiliser un vecteur contenant les déplacements possibles (ici mon vector<pi> D) plutôt que de copier coller le code correspondant à un déplacement dans chaque direction possible. Ceci est encore plus pratique lorsque les déplacements sont plus compliqués (par exemple un cavalier aux échecs).

Attention également à la lecture caractère par caractère avec des espaces, il faut penser à utiliser cin << noskipws.

Pour le reste des détails d’implémentation, voici mon code:

#include<iostream>
#include<vector>
#include<string>

using namespace std;

typedef pair<int, int> pi;

vector<string> carte;
vector<pi> teleport;
int l,c;

struct etat{
  int dir=0;
  bool prio=false;
  bool casseur=false;
  int destroy=0;
  etat(int a=-1, bool b=true, bool c=true, int d=0):
    dir(a), prio(b), casseur(c), destroy(d){};

  bool operator==(const etat& e) const{
    return dir==e.dir &&
        prio==e.prio &&
        casseur==e.casseur &&
        destroy==e.destroy;
  }
};

vector<vector<etat> > state;

struct Bender{
  int x,y;
  int dir=0;
  bool prio=false;
  bool casseur=false;
  int destroy=0;
  bool alive=true;

  vector<pi> D{pi(1,0), pi(0,1), pi(-1,0), pi(0,-1)};

  vector<string> past_dir;

  bool avance(){
    etat et(dir,prio,casseur,destroy);
    if(state[x][y]==et)
      return false;
    state[x][y]=et;

   int nx=x+D[dir].first, ny=y+D[dir].second;
   if(nx<0 || nx>=l || ny<0 || ny>=c || carte[nx][ny]=='#' ||
       (carte[nx][ny]=='X' && !casseur)){
     for(int i=0;i<4;++i){
       int ndir=prio?3-i:i;
       int nx=x+D[ndir].first, ny=y+D[ndir].second;
       if(nx<0 || nx>l || ny<0 || ny>c || carte[nx][ny]=='#')
     continue;
       if(carte[nx][ny]=='X' && !casseur)
     continue;
       
       dir=ndir;
       x=nx;
       y=ny;
      break;
     }
   }
   else{
     x=nx;
     y=ny;
   }

   if(dir==0)
     past_dir.push_back("SOUTH");
   else if(dir==1)
     past_dir.push_back("EAST");
   else if(dir==2)
     past_dir.push_back("NORTH");
   else
     past_dir.push_back("WEST");

    if(carte[x][y]=='X'){
      carte[x][y]=' ';
      destroy++;
    }
    else if(carte[x][y]=='$'){
      alive=false;
      return false;
    }
    else if(carte[x][y]=='S')
      dir=0;
    else if(carte[x][y]=='E')
      dir=1;
    else if(carte[x][y]=='N')
      dir=2;
    else if(carte[x][y]=='W')
      dir=3;
    else if(carte[x][y]=='B')
      casseur=!casseur;
    else if(carte[x][y]=='I')
      prio=!prio;
    else if(carte[x][y]=='T'){
      if(x==teleport[0].first && y==teleport[0].second){
    x=teleport[1].first;
    y=teleport[1].second;
      }
      else{
    x=teleport[0].first;
    y=teleport[0].second;
      }
    }
    
    return true;
  }
};


int main(){
  cin >> l >> c;
  cin.ignore();
  
  Bender b;
  state.assign(l,vector<etat>(c));

  for(int i=0;i<l;++i){
    string tmp;
    getline(cin, tmp);
    carte.push_back(tmp);
  }
  
  for(int i=0;i<l;++i)
    for(int j=0;j<c;++j){
      char tmp=carte[i][j];
      if(tmp=='@'){
    b.x=i;
    b.y=j;
    tmp=' ';
      }
      else if(tmp=='T')
    teleport.push_back(pi(i,j));
    }

   while(b.avance());

  if(!b.alive)
    for(auto s:b.past_dir)
      cout << s << '\n';
  else{
    cout << "LOOP\n";
  }

}

Le deuxième exo est assez classique et ressemble à “Dwarfs standing on the shoulders of giants”. Étant donné un graphe orienté sans cycle (un DAG) il faut trouver le plus long chemin. Cette fois les arêtes ont des poids, mais cela ne change pas vraiment le problème. Pour résoudre efficacement ce problème, il faut utiliser la programmation dynamique. Comme souvent je préfère écrire simplement ma fonction récursive et utiliser la mémoïzation afin de ne pas refaire des calculs. L’idée est simple, dès qu’un sous problème est résolu je stocke la solution dans une table. Si ce sous-problème apparait de nouveau il suffit de vérifier s’il n’est pas déjà dans la table, et dans ce cas renvoyer directement le résultat, sinon il faut faire le calcul.

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<limits>

using namespace std;

const int NEG_INF=numeric_limits<int>::min();

int aux(const string& start, map<string, vector<string> >& from,
    map<string, int >& money, map<string, int>& mem){
  if(mem[start]!=0) return mem[start];
  
  int res=(start=="0")?0:NEG_INF;
  for(auto pred:from[start])
    res=max(res, aux(pred, from, money, mem)+money[pred]);

  return mem[start]=res;
}

int main(){
  int n;
  cin >> n;
  map<string, int> mem;
  map<string, vector<string> > from;
  map<string, int > money;
  for(int i=0;i<n;++i){
    string in, out1, out2;
    int found;
    cin >> in >> found >> out1 >> out2;
    from[out1].push_back(in);
    from[out2].push_back(in);
    money[in]=found;
  }
  cout << aux("E", from, money, mem) << '\n';
}

Le dernier problème est plutôt original, étant donné des mesures de performance d’un algorithme, i.e. son temps d’exécution sur une entrée de taille donnée il faut prédire sa complexité.

Ma première idée était d’appliquer une transformation “inverse”, calculer le coefficient de corrélation linéaire, et prendre la transformation donnant le plus grand coefficient. Cela avait deux problèmes, calculer l’inverse de (n log(n)) n’est pas évident même si on peut toujours le faire numériquement. D’autre part, je ne sais pas comment distinguer une complexité constante d’une complexité linéaire.

La solution que j’ai retenue, est la suivante: je calcule les valeurs de référence xi pour chaque fonction possible, je prends ensuite un coefficient multiplicateur comme étant la moyenne des rapports xi/ti où ti est la valeur fournie par l’entré et xi la valeur théorique pour la taille de l’entrée. Je calculer ensuite la somme des carrés des écarts et je prends la fonction minimisant cette valeur. Du point de vue pratique, utiliser des valarray rend le code vraiment simple et concis.

Maintenant ma solution n’est pas vraiment bonne puisque pour valider ce problème j’ai du éliminer les données avec un temps d’exécution trop faible. Dans la vraie vie, ce serait justifié. En efet timer un programme s’exécutant instantanément n’a pas de sens dans la mesure où la moindre perturbation de la machine (un accès disque…) provoque des écarts de mesure significatifs.

#include<iostream>
#include<valarray>
#include<vector>

using namespace std;

double comp_diff(valarray<double>& x, const valarray<double>& t){
  x*=(t/x).sum()/t.size();
  valarray<double> tmp = (t-x)*(t-x);
  return abs(((t-x)*(t-x)).sum());
}

int main(){
  int N;
  cin >> N;

  vector<double> nn, tt;
  for(int i=0;i<N;++i){
    double n1, t1;
    cin >> n1 >> t1;
    if(t1>100){
      nn.push_back(n1);
      tt.push_back(t1);
    }
  }

  valarray<double> n(nn.data(), nn.size()), t(tt.data(), tt.size());

  valarray<double> x(1,t.size());

  double mini = comp_diff(x,t);
  string res = "O(1)";
  double tmp;

  //log
  x = log(n);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(log n)";
  }

  //n
  x = n;
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n)";
  }

  //nlog
  x = n*log(n);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n log n)";
  }

  //n2
  x = pow(n,2.);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n^2)";
  }

  //n2 log
  x = pow(n,2.)*log(n);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n^2 log n)";
  }

  //n3
  x = pow(n,3.);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n^3)";
  }

  //2^n
  x = pow(2.,n);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(2^n)";
  }

  cout << res << endl;
}

Et vous, comment avez-vous résolu ce dernier problème ?

No comments:

Post a Comment