Tuesday, June 25, 2013

Codingame mars 2013

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

Le but du premier exercice est de calculer la suite de Conway. Le terme initial est fixé et chaque terme suivant s’obtient en lisant le terme précédent. Par exemple le terme 1 2 1 1 sera lu “un 1, un 2, deux 1” le terme suivant sera alors 1 1 1 2 2 1.

Pour résoudre cet exo le plus simple est d’avoir une fonction qui pour un terme donné, calcule le terme suivant. Le principe de cette fonction pourrait être le suivant: On lit les entiers de notre terme de la suite de conway et on a deux variables, une indiquant l’entier dont on compte les occurrences et l’autre comptant son nombre d’occurrences. Si l’entier lu est le même que l’entier courant, on incrémente son nombre de vue. Sinon on met à jour le nouveau terme de la suite et on utilise le terme courant pour mettre à jour nos variables. Voici mon code:

#include<iostream>
#include<vector>

using namespace std;

void next(vector<int> & t){
  vector<int> tmp;
  int val=t[0];
  int nb=1;
  for(int i=1;i<int(t.size());++i){
    if(t[i]==val)
      nb++;
    else{
      tmp.push_back(nb);
      tmp.push_back(val);
      val=t[i];
      nb=1;
    }
  }
  tmp.push_back(nb);
  tmp.push_back(val);
  t=tmp;
}

int main(){
  int n, l;
  cin >> n >> l;
  vector<int> t{n};
  for(int i=1;i<l;++i)
    next(t);
 
  cout << t[0];
  for(int i=1;i<int(t.size());++i)
    cout << ' ' << t[i];
}

Le deuxième exo, demande de formater correctement un XML-like. Typiquement le genre d’exo où il vaut mieux commencer par bien réfléchir avant de commencer à coder. On peut lire caractère par caractère et formater l’entrée en direct. Mais attention par défaut cin saute les espaces. Vous pouvez utilisez cin >> noskipws pour être sûr de tout lire. J’ai eu besoin de trois variables: nline indique si je suis au début d’une nouvelle ligne (dans ce cas je vais sans doute devoir faire de l’indentation), indent compte le niveau d’indentation du bloc courant, enfin quote m’indique si je suis en train de lire une chaine de caractère (dans ce cas je dois garder les espaces). Si on regarde bien les règles (et pour ce problème c’est presque plus utile de regarder les exemples), on peut voir qu’il y a peu de caractères importants:

  • “’” : passe en mode chaine de caractère

  • “;” : fait un retour à la ligne.

  • “(” : affiche ( sur une nouvelle ligne, incrémente indent et va à la ligne

  • “)” : décrémente indent, affiche ) sur une nouvelle ligne. Attention à l’ordre par rapport à (, notez également qu’on ne va pas à la ligne ensuite (cas de (();()))

  • espace, tab, retour de ligne : ne pas les prendre en compte sauf si mode quote activé.

J’ai une fonction pour gérer l’affichage de l’indentation qui gère si je suis ou pas en début de ligne. J’indente donc toujours et la fonction n’a d’effet que si ne suis en début de ligne. Voici mon code.

#include<iostream>

using namespace std;

int indent=0;
bool nline=true;

void print_indent(){
  if(nline)
    for(int i=0;i<indent;++i)
      cout << "    ";
  nline=false;
}

int main(){
    int n;
    cin >> n; 
    bool quote=false;
    char c;
    cin >> noskipws;
    while(cin >> c){
        if(quote){
            quote=(c!='\'');
            cout << c;
        }
        else switch(c){
        case ' ':
        case '\t':
        case '\n':
            break;
        case ';':
            cout << ";\n";
            nline=true;
            break;
        case '(':
            if(!nline){
            cout << '\n';
            nline=true;
            }
            print_indent();
            ++indent;
            cout << "(\n";
            nline=true;
            break;
        case ')':
            if(!nline){
            cout << '\n';
            nline=true;
            }
            --indent;
            print_indent();
            cout << c;
            break;
        case '\'':
            quote=true;
            print_indent();
            cout << c;
            break;
        default:
            print_indent();
            cout << c;
        }
    }
}

No comments:

Post a Comment