Wednesday, January 29, 2014

Top 5 des erreurs stupides

Dans les problèmes de programmation du type CodinGame, ACM, Google Code Jam, etc., certaines erreurs reviennent fréquemment. C’est d’autant plus rageant qu’elles sont difficiles déboguer (sur les exemples ça marche) et qu’une fois trouvées, on se rend compte que ce sont des erreurs triviales déjà faites plusieurs fois.
Voyons donc ce que je considère comme mon top 5 d’erreurs stupides.

Les int overflow


En C++ la norme demande qu’un int soit codé sur au moins 16 bits, il peut donc contenir au moins des entiers de -32767 à 32767. En pratique je n’ai jamais vu (en 2014) de système où un int n’est pas codé sur au moins 32 bits, il peut alors contenir des entiers de -2147483647 à 2147483647. Il est donc raisonnable d’utiliser des int lorsque les nombres considérés sont inférieurs à 10^9.
Le problème étant que de nombreux problèmes demandent le résultat modulo un grand nombre. Et là même si le modulo est inférieur à 10^9 et donc que le résultat final tient bien dans un int, ce n’est pas le cas des résultats intermédiaires.
Dans ce code récursif (pour info la version itérative est sensiblement plus rapide) de l’exponentiation rapide modulaire:
int expMod(int a, int b, int MOD){
    if(b==0) return 1;
    long long tmp = expMod(a, b/2, MOD);
    tmp = (tmp*tmp)%MOD;
    if(b%2==0)
        return tmp;
    return (a*tmp)%MOD;
}
Si on défini tmp comme un int et non comme un long long le code devient complètement faux. Attention également à bien prendre le modulo à chaque multiplication est à ne pas faire plusieurs multiplications en une seule étape. Typiquement faire (tmp*tmp*a)%MOD produit également un code faux même avec des long long.
La meilleure manière d’éviter ces problèmes d’int overflow est bien sûr d’y penser avant de coder. Voici cependant plusieurs indicateurs:
  • Vous utilisez des int, le résultat devrait être positif et il est négatif
  • En remplaçant brutalement tous les int par des long long le résultat change
C’est que vraisemblablement vous avez un problème d’int overflow. Si la solution de tous les remplacer par des long long ne suffit pas. Il est aussi très simple d’utiliser gmp (les bindings c++ font que les grands entiers se comportent comme des types de base, vous pouvez alors simplement faire un typedef mpz_class bigInt et utiliser les bigInt comme des int). Le problème de GMP est qu’il est difficile de l’inclure dans votre fichier afin de respecter les contraintes imposées par les sites de programmation. Dans ce cas j’ai récemment trouvé cette librairie qui fourni des infInt avec les bons binding et qui est suffisamment petite pour être inclue dans votre code source.

Les modulo négatifs


Pas grand chose à dire, sur ce problème, mais lorsqu’on ne le sait pas il peut être difficile à trouver. L’opérateur modulo % renvoie un nombre entre -MOD et MOD suivant le signe de votre nombre de départ. Par exemple -5%2==-1, ce qui est plutôt perturbant. Si vous voulez un modulo plus classique, c’est à dire avec un résultat entre 0 est MOD-1, il faut faire ((n%MOD)+MOD)%MOD.

Ne pas réinitialiser ses données


Probablement la pire des erreurs, mais elle n’apparait que lorsqu’il y a plusieurs testcases dans le même fichier. Typiquement lors du second testcase, votre code utilise encore des données liées au premier testcase. C’est souvent compliqué à déboguer, car sur un unique testcase tout semble correct. De plus, si les testcases sont donné par taille croissante il est possible qu’ils se réécrivent dessus, il qu’il n’y ait donc aucun problème.
Je vous conseille donc d’une part de toujours tester votre code sur un fichier de plusieurs testcases, et de rajouter le premier testcase à la fin (dans le but de casser ce problème de testcase de taille croissante).
Une autre solution est de n’avoir aucune structure globale et de définir vos structures de données exactement là où elles sont initialisées. De cette manière les données du testcase précédent n’existent plus lors du testcase suivant. Cela implique souvent de devoir passer en paramètre toutes les données à vos fonctions annexes. Vu qu’il est possible (et souhaitable) de les passer par référence le surcout est négligeable mais c’est vrai que parfois (dans le cas de code très simple) c’est pénible à faire. L’avantage étant qu’il est plus facile de modifier significativement de larges portions de votre algorithme sans casser tout le reste. Par défaut je trouve que c’est la meilleure solution.

Laisser le code de débogue


La vérification étant généralement basée sur un simple diff, laisser un cout de débogue est la meilleure manière d’obtenir un WRONG ANSWER. Dans certains cas, il n’est pas évident de voir le problème, par exemple si l’affichage n’a lieu que dans un cas très précis qui n’a pas lieu sur vos exemples. Ou plus bêtement, si après avoir passé beaucoup de temps à déboguer, vous ne faite plus attention aux messages de débogue corrects.
Le plus simple pour éviter ce problème est de ne pas utiliser la sortie standard pour afficher vos messages de débogue mais plutôt le canal d’erreur par exemple (cerr). Pour éviter le TIME LIMIT si vous avez beaucoup de messages de débogue (il est donc possible que votre programme passe un temps non négligeable à les afficher), vous pouvez les afficher uniquement en mode débogue en utilisant la directive de préprocesseur #ifdef et en compilant en local avec l’option -DDEBUG.
    #ifdef DEBUG
    cerr << "à la ligne 17 t contient:" << endl;
    for(int x:t)
        cerr << x << ' ';
    cerr << endl;
    #endif

Lire les cartes en sautant les espaces

Cette erreur n’est pas si courante, mais vu qu’elle m’a déjà pas mal pénalisé je la mets ici.
Par défaut cin saute les caractères blancs (espace, tabulation, retour de ligne). Si vous devez lire un plan en ASCII et que les cases vides sont représentées par des espaces vous allez donc lire n’importe quoi. De même si vous devez lire une phrase. Vous pouvez alors soit passer noskipws à cin afin qu’il ne saute plus les caractères blancs (attention il faut alors lui passer skipws pour qu’il retrouve son comportement usuel), ou bien simplement utiliser getline.

No comments:

Post a Comment