URL: https://linuxfr.org/users/bluebird/journaux/topcoder Title: Topcoder Authors: Philippe F Date: 2006年03月09日T22:26:25+01:00 Tags: Score: 0 Bonjour cher journal, Depuis un peu plus d'un mois, à la suite de la lecture d'un article sur kuroshin ( [http://www.kuro5hin.org/story/2005/12/10/155850/89](http://www.kuro5hin.org/story/2005/12/10/155850/89) ) je me suis inscrit sur topcoder : [http://www.topcoder.com/tc](http://www.topcoder.com/tc) Le principe est simple : une à deux fois par semaine, des épreuves sont proposées. Chaque épreuve est composée de 3 exercices, un facile, un moyen et un difficile, que l'on doit résoudre en moins d'une heure. Apres on dispose d'un quart d'heure pour observer le code de ses camarades et essayer de trouver un exemple pour planter leur code. Il y a un classement global qui évolue au gré des épreuves. J'étais plutôt attiré par l'aspect compétition et par l'idée de programmer un peu, puisque mon boulot n'implique plus de développement, juste de la gestion de projet. Le dev est en C++, C# ou java. Pas trop de place pour le logiciel libre . Au bout d'un mois, ce que j'en retire : Une heure, c'est super court. Ca veut dire qu'il faut apprendre à coder vite et juste. Pour l'instant, je n'ai pas réussi à terminer plus de deux programmes et systématiquement, l'un de ces deux programmes s'est fait allumé sur un test. Ca peut aller d'un test à la con à une vraie erreur de programmation. Ou bien à une sous-estimation de la complexité de mon implémentation : chaque programme doit résoudre le problème posé en moins de deux secondes. Je note un énorme progrès dans ma capacité à écrire du code concis et juste. Sur la dernière compétition, sur les trois programmes que j'ai écrit, les trois ont compilé du premier coup et ont résolu le problème du premier coup. Je n'en revenais pas ! Seuls deux étaient corrects cependant, j'avais une variable globale contenant une liste qui grossissait systématiquement et qui a épuisé toute la mémoire sur le plus gros test. En terme de langage, le C++ semble être assez populaire. J'aurai bien aimé participer en python mais python ne pourrait jamais à mon avis faire tourner les problèmes en moins de deux secondes. Cette compétition est vraiment impitoyable. Dans un programme concret, on est finalement rarement exposé directement à tous les bugs qu'on laisse passer. Beaucoup ne sont jamais activés. La, rien ne passe. Entre tes concurrents qui cherchent la petite bête pour gagner des points, les concepteurs de problèmes qui pensent à tous les cas tordus, je me suis vraiment pris une grosse claque. Je savais que je n'étais pas un cador, mais se ramasser sur des problèmes plutôt facile, ca fait mal. Sur mon premier programme, il fallait compter le nombre d'éléments vérifiant un pourcentage et j'ai eu le malheur de faire une division avec des floats : blam, le problème était conçu pour que les imprécisions sur les floats soient mis à jour. Il fallait en fait faire une multiplication et rester dans l'espace entier (je m'en doutais de toute façon). Ou bien j'avais fait un petit programme où le calcul de complexité me paraissait bon, sauf que j'avais une initialisation qui rajoutait une boucle for non prévue dans mon calcul initial : je me suis fait dégager. Donc là, je suis vraiment content parce que je pense que j'ai franchi une étape. Mes programmes semblent être corrects et conformes à ce que je veux en faire. Côté connaissance, j'ai appris à utiliser la STL et j'ai découvert quelques algos ou quelques concepts comme la programmation dynamique. Beaucoup de problèmes se résolvent par récursion vu que les récursions font des programmes concis et efficaces. J'ai appris à bien lire les problèmes et à faire au plus simple et plus direct. Beaucoup de problèmes demandent de retourner le nombre d'éléments vérifiant une certaine propriété. La tentation initiale est de trouver tous les éléments et d'en retourner le nombre, mais c'est souvent infaisable. On découvre que juste compter le nombre d'éléments sans les calculer est en revanche faisable dans les temps et de façon concise. Quand le temps est compté, on réfléchit à tous les racourcis. Tout le monde a une macro FOR(i,0,n) qui génère for(i=0; i<=n; i++) et toutes les variables utilisées sont sur un ou deux caractères. On découvre des nouveaux trucs au fur à mesure : le problème balance une suite de chaines de caractère contenant des chiffres. Au début, je convertissais naivement en double tableau d'entier. Maintenant, je travaille directement dans la chaîne avec str_lst[i][j] - '0' pour accéder aux différents éléments. S'il y avait une structure avec trois entiers, j'etais tenté de créer une structure pour les contenir. Maintenant, soit je fais des pair< int, pair< int, int > >, soit je les mets tous les trois dans un tableau simple en indexant par multiple de trois. Bref, tous les trucs sont bons pour que le code à ecrire soit plus concis et plus simple. On hésite pas non plus à dimensionner des tableaux aux tailles max supportées par le problème, genre int tab[20000][50][50] parce que c'est plus rapide à écrire qu'une allocation dynamique. Sur les aspects programmation, dans la division 2 (la division des newbie comme moi), je pense avoir fait le tour des problèmes. C'est toujours soit de la récursion, soit des graphes, soit de la programmation dynamique, soit un chouia de math. La difficulté est de reconnaitre un algorithme connu derrière le problème et de l'implémenter dans les temps. Côté division 1, il y a vraiment des killers. Le problème difficile demande souvent une véritable analyse mathématique, plus des astuces subtiles de programmation et d'algorithmie. En général, je ne trouve pas la solution. Et je suis épaté par des mecs qui trouvent et codent une solution en moins de 10 minutes. Voila, si vous voulez vous amuser un peu dans l'arène des programmeurs, je vous invite à faire un tour. Ah, j'oubliais. Il va surement y avoir un troll pour savoir si topcoder aide à mieux programmer. Il est clair qu'un certain nombre de trucs du codeurs sont des mauvais trucs à utiliser dans la programmation courante (nommage succints des variables, variables globales à tout va, ...) mais dans l'ensemble, je pense que ca aide à devenir un meilleur programmeur. Et en tout cas, c'est super fun !

AltStyle によって変換されたページ (->オリジナル) /