Wednesday, August 7, 2013

Codingame DevKings 2013

Sixième post de la série, comme toujours mes algos et codes en C++ pour les CodinGames. La page d’entrainement est toujours ici.

Contest sur le thème de l’open data. Ce qui veut malheureusement dire que les entrées ne sont pas formatées au plus simple. Je trouve le parsing plus commode en python qu’en C++. Mais j’ai tout de même codé en C++.

Le premier exercice demande étant donné un point x et un ensemble de points P, le point de P le plus proche de x. Il n’y a pas plusieurs requêtes, ce qui pourrait demander un prétraitement pour répondre vite à chaque requête donc l’algo est vraiment simple. On parcourt notre ensemble de points et on retourne le plus proche. La fonction de distance est un peu tordue, les points étant donné par leur latitude et longitude, mais heureusement la formule est fournie. Attention, même si bizarrement vous aurez tous les points sans le faire, la formule marche avec des angles en radian et les coordonnées sont en degrés.

Il y a tout de même deux difficultés (du moins en C++), le séparateur décimal est une virgule et non un point. D’où ma fonction conv qui convertit une chaine de caractère en double en commençant par transformer la virgule en point pour en utilisant des streams pour avoir gratuitement la conversion. Autre problème la lecture de l’entrée qui demande de lire ligne par ligne et pour chaque ligne d’utiliser le séparateur point-virgule. J’ai donc utilisé getline pour lire ligne par ligne. Je transforme ensuite ma ligne en un flux que je parse avec getline (en effet cette fonction accepte de prendre un délimiteur).

#include<iostream>
#include<string>
#include<sstream>
#include<cmath>
#include<limits>

using namespace std;

const double PI = atan(1)*4;

double conv(string & s){
  for(int i=0;i<int(s.size());++i)
    if(s[i]==',')
      s[i]='.';
  double res;
  stringstream(s) >> res;
  return res;
}

double dist(double lon1, double lat1, double lon2, double lat2){
  lon1*=PI/180, lat1*=PI/180;
  lon2*=PI/180, lat2*=PI/180;
  double x=(lon2-lon1)*cos((lat1+lat2)/2);
  double y=lat2-lat1;
  return sqrt(x*x+y*y)*6371;
}

int main(){
  string xx, yy;
  getline(cin, xx);
  getline(cin, yy);
  double x=conv(xx),y=conv(yy);
  int N;
  cin >> N;
  cin.ignore();
  double distmin=numeric_limits<double>::max();
  string name_res;
  for(int i=0;i<N;++i){
    string s;
    getline(cin, s);
    stringstream ss(s);
    string tmp, name, slon, slat;
    getline(ss, tmp, ';');
    getline(ss, name, ';');
    getline(ss, tmp, ';');
    getline(ss, tmp, ';');
    getline(ss, slon, ';');
    getline(ss, slat, ';');
    double lon=conv(slon), lat=conv(slat);
    double tmp1=dist(x,y,lon,lat);
    if(tmp1<distmin){
      distmin=tmp1;
      name_res=name;
    }
  }
  cout << name_res << endl;
}

Le deuxième exercice est plus intéressant algorithmiquement. Il faut trouver le plus court chemin dans un réseau de tram. Le plus court chemin étant défini comme celui dont la somme des distances « en ligne droite » entre les stations est minimale. On peut donc réutiliser le code de notre fonction de distance (cette fois, oublier la conversion degré vers radian validera les tests proposés, mais vous coutera 8% sur le score final).

Le parsing est là aussi pas complètement immédiat, mais on peut utiliser les mêmes techniques que précédemment. Attention, cette fois le délimiteur décimal est bien un point et le séparateur dans les lignes est une virgule. On peut donc facilement construire des tables de conversion des noms vers des entiers uniques et inversement, et modéliser notre réseau de tram par un vector<vector<pair<int,double graph ou graph[i] contient la liste des arrêts voisins de l’arrêt i ainsi que leur distance. Attention il faut aussi pouvoir faire la conversion entre le code de la station et son nom en Français. On peut se passer faire ces conversions en utilisant un map<vector<pair<string,double, mais je trouve plus simple de travailler sur des entiers.

Les distances étant positives (c’est idiot de le dire, mais c’est essentiel pour l’algo que nous allons utiliser) on peut utiliser l’algorithme de Dijkstra. S’il pouvait y avoir des distances négatives, on aurait dû utiliser l’algorithme de Bellman-Ford qui est plus lent.

L’algorithme de Dijkstra calcule la distance minimale d’un point à tous les autres. Il fonctionne ainsi, chaque sommet a trois états possible: « complètement traité » (on connait alors la distance finale d’où venir pour atteindre cette distance), « en cours de traitement » (on sait alors qu’on peut atteindre ce sommet en passant par tel point pour une distance totale) ou « jamais vu » (pour le moment ce sommet n’est pas accessible). Au début, tous les sommets sont « jamais vus » sauf notre point de départ qui est « en cours de traitement à distance 0, en venant de lui même ». Ensuite, tant qu’il y a des sommets « en cours de traitement », on prend celui ayant la plus petite distance, il devient « complètement traité » et l’on met à jour tous ses voisins qui ne sont pas « complètement traité ». Le point clé est qu’avec seulement des distances positives, le sommet « en cours de traitement » avec la plus petite distance a sa distance finale. En C++ pour trouver ce sommet rapidement on peut utiliser une priority_queue.

#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
#include<limits>
#include<algorithm>
#include<queue>
#include<map>

using namespace std;

const double PI = atan(1)*4;
const double INF = numeric_limits<double>::max();

typedef pair<int, double> vertex;
typedef pair<double, double> pf;

double conv(string & s){
  double res;
  stringstream(s) >> res;
  return res;
}

double dist(pf &p1, pf& p2){
  double lon1=p1.first*PI/180, lat1=p1.second*PI/180;
  double lon2=p2.first*PI/180, lat2=p2.second*PI/180;
  double x=(lon2-lon1)*cos((lat1+lat2)/2);
  double y=lat2-lat1;
  return sqrt(x*x+y*y)*6371;
}

struct edge {
  int x, y;
  double w;
  edge(int a=0, int b=0, double c=0): x(a), y(b), w(c) {}
  bool operator< (const edge &e) const {
    return w > e.w;
  }
};

void dijkstra(int s, vector<vector<vertex> > &g, vector<int> &pred, vector<double> &dist){
  priority_queue<edge> q;
  q.push(edge(s,s,0));
  while(!q.empty()){
    edge e = q.top();
    q.pop();
    if (pred[e.y]!=-1) continue;
    pred[e.y] = e.x;
    dist[e.y] = e.w;
    for(vertex v:g[e.y]){
      edge f(e.y, v.first, e.w + v.second);
      if (f.w < dist[f.y]) q.push(f);
    }
  }
}

int main(){
  string start, stop;
  getline(cin, start);
  getline(cin, stop);
  int N;
  cin >> N;
  cin.ignore();
  map<string, int> id_to_n;
  vector<string> n_to_id;
  map<string, string> id_to_name;
  vector<pf> pos;

  for(int i=0;i<N;++i){
    string s;
    getline(cin, s);
    stringstream ss(s);
    string id, name, tmp, slon, slat;
    getline(ss, id, ',');
    getline(ss, name, ',');
    getline(ss, tmp, ',');
    getline(ss, slat, ',');
    getline(ss, slon, ',');

    id_to_n[id]=i;
    n_to_id.push_back(id);
    id_to_name[id]=name.substr(1, name.size()-2);
    pos.push_back(pf(conv(slon), conv(slat)));
  }

  vector<vector<vertex> > graph(N);
  int M;
  cin >> M;
  for(int i=0;i<M;++i){
    string id1, id2;
    cin >> id1 >> id2;
    int n1=id_to_n[id1];
    int n2=id_to_n[id2];
    graph[n1].push_back(vertex(n2, dist(pos[n1], pos[n2])));
  }

  vector<int> pred(graph.size(),-1);
  vector<double> dist_vec(graph.size(), INF);

  dijkstra(id_to_n[start], graph, pred, dist_vec);

  if(pred[id_to_n[stop]]==-1)
    cout << "IMPOSSIBLE\n";
  else{
  vector<int> res;
  int curr=id_to_n[stop];
  while(curr!=id_to_n[start]){
    res.push_back(curr);
    curr=pred[curr];
  }
  res.push_back(curr);
  reverse(begin(res), end(res));

  for(int i:res)
    cout << id_to_name[n_to_id[i]] << '\n';
  }
}

No comments:

Post a Comment