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 ) je me suis inscrit sur topcoder :
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 !
Journal Topcoder
9
mar.
2006
# Python VS C#
Posté par Fabien Engels . Évalué à 2.
Le Python est si lent que ça par rapport au C# ?
[^] # Re: Python VS C#
Posté par TImaniac (site web personnel) . Évalué à 2.
http://shootout.alioth.debian.org/debian/benchmark.php?test=(...)
(Psycho compte pas, il apporte des avantages mais au prix de gros inconvénients évidents)
[^] # Re: Python VS C#
Posté par Fabien Engels . Évalué à 4.
[^] # Re: Python VS C#
Posté par TImaniac (site web personnel) . Évalué à 3.
[^] # Re: Python VS C#
Posté par Philippe F (site web personnel) . Évalué à 2.
Leur business model est d'aider des grosses boites a trouver des bons programmeurs. Ils prennent donc des langages populaires dans l'industrie, d'ou l'absence de langage un peu moins conventionnels, mais qui conviendraient tres bien aux types de problemes proposes (lisp, ocaml, haskell, scheme ou python, ruby).
[^] # Re: Python VS C#
Posté par TImaniac (site web personnel) . Évalué à -1.
Ben non puisqu'une partie du problème est de faire un programme rapide.
[^] # Re: Python VS C#
Posté par Philippe F (site web personnel) . Évalué à 1.
Le C++ est populaire a mon avis parce qu'il n'y a aucune penalite a l'exeuction. Sur un probleme, un type a fait un analyse et la verification des depassements de tableaux fait que le C# ou le java sont plutot lent sur un tableau a 3 index par exemple. En C++, tu es sur d'eviter ce genre de probleme.
Pour les macros, meme si tout le monde en utilises quelques unes, ca reste du "sucre syntaxique", c'est a dire que t'economises quelques caracteres mais ca ne va pas plus loin (genre #define ALL(v) (v).begin(), (v).end() ).
Ce qui fait la difference, c'est vraiment la capacite a comprendre rapidement l'algorithme a utiliser et a le coder rapidement. Sur les problemes faciles et moyens, si ton programme fait plus de 50 lignes, c'est que tu n'as pas su simplifier le probleme suffisamment. Sur le probleme dur, je dirai que les 2/3 des solutions font aussi moins de 50 lignes de toute facon. Par contre, il faut s'accrocher pour les comprendre :-)
[^] # Re: Python VS C#
Posté par Matthieu Moy (site web personnel) . Évalué à 2.
# Question bête
Posté par Florent Bayle (site web personnel) . Évalué à 8.
Ça m'intéresserait de voir des exemples de sujets demandés, et éventuellement d'essayer de les résoudre, mais j'ai l'impression qu'il absolument être inscrit.
Sinon, pourrais-tu donner quelques exemples un peu plus précis que ce que tu décris dans ton texte ?
[^] # Re: Question bête
Posté par Philippe F (site web personnel) . Évalué à 4.
Je peux quand meme parler des types de problemes. L'avant dernier jeu de problemes etait pas mal:
pb facile:
Soit:
- A tq 10 <= A <= 100000
- B tq A <= B <= 100000
- A-B <= 1000
- trouver le nombre d'entiers entre A et B tq si v est un nb qu'on cherche, il n'y a aucun nombre premier entre v-10 et v+10 inclus
Rappel: temps d'execution en moins de deux secondes.
Exemple :
97001
97691
Returns: 89
La bonne methode, c'est de faire un crible d'Eratosthene. Sinon, meme en y allant bourrin, ca marche. Genre tu iteres sur tous les nombres entre A et B, et pour chacun de ces nombres tu vas de nombre-10 a nombre+10 et pour chacun de ces sous-nombres, tu verifies s'il est premier. J"ai gagne des points en cassant une solution qui faisait (A-B)*20 verifications de nombre premier, sans optimiser ou cacher la recherche de nombre premier en java et qui au final prenait plus de 2 secondes. Des que tu optimises un minimum (cache facon Eratosthene) ou tentative de division par tous les nombre jusqu'a sqrt(n), ca passe en 2 secondes.
Ca parait choquant d'etre bourrin, mais le but, c'est de coder ca en moins de 10 minutes.
Probleme moyen:
Tu plies un carre en 2 jusqu'a obtenir un triangle faisant 1/8 de ton carre original (le dernier pli est en diagonal). Tu fais des trous sur ce triangle, et il faut generer le carre deplie avec les trous.
L'entree est un vector qui represente le triangle avec des * pour les trous et des . pour les non-trous.
Exemple :
{"*",
"..",
".*.",
".**.",
".*.**"}
Returns:
{"**.*..*.**",
"*.**..**.*",
".*.*..*.*.",
"***....***",
"....**....",
"....**....",
"***....***",
".*.*..*.*.",
"*.**..**.*",
"**.*..*.**" }
C'etait plutot facile, il suffit de faire des symetries dans tous les sens.
Probleme difficile:
Tu as une suite de chambres. Chaque piece contient un interrupteur qui controle la lumiere dans une autre piece. Tu commences avec la premiere piece allumee. Tu peux aller a tout moment dans n'importe quelle piece du moment que la lumiere est deja allumee et tu ne peux pas eteindre la lumiere dans ta propre piece. Tu veux fnir avec la lumiere allumee dans la derniere piece uniquement. Retourner le nombre minimal de deplacement necessaires, ou -1 si c'est pas possible.
Maximum 16 pieces.
Exemple:
{7, 11, 1, 12, 6, 3, 0, 2, 6, 0, 0, 5, 9}
Returns: 15
Celui-la etait coton. Mais j'avais deja vu un probleme dans le meme style. Chaque etat global de tes pieces peut etre represente sous forme d'un entier, avec un bit par piece + une valeur entre 0 et 15 pour ta position. Tu veux partir de l'etat 1e piece allumee, present dans la premiere piece, jusqu'a l'etat derniere piece allumee, present dans la derniere piece. C'est donc un graphe dans lequel tu cherches le chemin le plus court. Pour un etat donne, il est facile de trouver tous les etats que tu peux rejoindre : le meme etat avec l'interrupteur qui a bascule (cout 0) ou bien le meme etat mais present dans une autre piece allumee (cout 1). Un petit coup de djikstra et tu trouves le chemin le plus court.
A coder en une heure, je peux te dire que tu n'a pas le temps de respirer.
[^] # Re: Question bête
Posté par Philippe F (site web personnel) . Évalué à 2.
#define FOR(i,n) for(int i=0; i<(n); i++) typedef vector VI; struct CrazySwitches { int minimumActions(vector s) { int n = s.size(); int N = (1<<n); VI v(N * n, 999999); // idx = N * room + on bits v[1] = 0; queue q; q.push(1); while (!q.empty()) { int t = q.front(); q.pop(); int on = t % N, r = t / N; FOR(i, n) { if (s[i] == r && i != r) { // can switch int tt = t ^ (1<<i); if (v[tt] > v[t]) v[tt] = v[t], q.push(tt); } } FOR(i, n) if (i != r) { if ((on & (1<<i)) == 0) continue; // cannot move to this room int tt = on + i * N; if (v[tt] > v[t] + 1) v[tt] = v[t] + 1, q.push(tt); } } int ret = v[(n-1) * N + (1 << (n-1))]; return ret == 999999 ? -1 : ret; } };# not in real life
Posté par Jay . Évalué à 1.
Effectivement, sur un vrai gros projet au sein d'une équipe, c'est pas jouable de programmer avec des variables de 2 caractères ;-) mais je suppose que c'est en participant à des concours comme ca qu'on arrive à écrire le code DeCSS le plus court du monde ;-)
http://www.cs.cmu.edu/~dst/DeCSS/Gallery/hannum-efdtt-source(...)
J'vais aller tenter un ou deux challenges moi ... et peut-être qu'un jour on m'appelera « DVD Jay » ;-)
[^] # Re: not in real life
Posté par Johann Ollivier-Lapeyre (site web personnel) . Évalué à 3.
- HD-DVD
- Blue-ray
- messenger (audio) (audio de msn)
- DRM m$
...
[^] # Re: not in real life
Posté par jahrynx . Évalué à 3.
[^] # Re: not in real life
Posté par Jarod_Summers . Évalué à 7.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.