Philippe F a écrit 2225 commentaires

<< Sinon, ces optimisations post-génération de code exécutables sont quand même applicables aux machines physiques ? >>

C'est plus ou moins ce qu'a fait transmeta avec son code morphing. Au final, c'etait beaucoup plus lent qu'un processeur pur.

<<
- Un compilateur utilisant massivement une analyse de flot
- Un compilateur qui dispose de bonnes informations, à priori sur les statistiques d'utilisation du code (ie. distribution des valeurs les plus courantes en entrée des fonctions).
>>

Et on en revient a la necessite d'avoir une grammaire du langage de programmation qui soit suffisamment expressive. Sinon, ces optimisations sont tres difficiles a mettre en oeuvre.

C'est bien pour cela que le JIT a attendu des langages comme Java ou C# pour devenir populaire.

<<
Dans le compilateur, il faudrait que l'analyse de flot analyse les sous graphes potentiellement très consommateurs en calculant leur complexité ainsi que les possibilités de "distributions" des paramètres dans l'intervalle possible (typiquement , on peut déduire, dans certains cas, par un moteur logique, que le param appliqué à la fonction f, dans le contexte se trouvera dans l'interval [20;100]).
>>

C'est tres proche de ce que fait le compilateur OCaml. C'est d'ailleurs ce qui explique malgre un langage "loin de la machine", il arrive a de tres bonne perfs : il y a une analyse de code tres poussee derriere qui va bien chercher les optimisations.

Cependant, l'analyse statique restera toujours limitee. Le comportement d'un programme depend de son code et de ses parametres en entree. Une optimisation statique a la compilation ne peut optimiser que le code d'un point de vue general. Elle ne peut pas connaitre quelle fonction est appelee plus souvent dans la pratique. C'est la que les optimisations JIT interviennent. Elles regardent le code s'executer et peuvent trouver les fonctions qui sont reellement utilisees en permanence.

Le C etant compile en assembleur avant d'etre execute, toute l'information sur la notion de fonction et de variable est perdue. Meme si cette information perdurait, a terme, la grammaire du C est trop peu expressive a mon sens pour permettre des optimisations de longue haleine (pas de notion d'interface, pas de notion de dictionnaire, utilisation de pointeurs pour gerer des tableaux, utilisation de pointeurs sans types, etc).

Donc plus ca va, plus le C va etre a la rue parce qu'il ne peut guere evoluer. D'un autre cote, cette stabilite est aussi ce qui a fait son succes.

> Vitesse : C gagne car proche du langage machine.

Mouai. Faudrait commencer a evoluer.

Par exemple, sur le "language shootout", OCaml est extremement proche du C pur en terme de vitesse:
http://shootout.alioth.debian.org/old/benchmark.php?test=all(...)

Et pourtant, je ne crois pas que OCaml soit "proche de la machine".

De meme, IronPython, une version de python ecrite pour le CLR de C# est plus rapide que la version de python en C.

Le C se prete bien a certaine manipulations mais pour des gros programme, je suis persuade qu'un langage qui expose correctement les intentions du programmeur dans sa grammaire pourra a terme etre mieux optimise par un bon compilateur. Le C et le C++ ont ce probleme que leur grammaire est complexe, avec des manipulations qui cachent ce que veut faire le developpeur. Au final, une information est perdue, celle de l'intention du programmeur et les optimisations sont donc limitees dans la mesure de l'expressivite du langage.

Si on regarde Java ou C#, on trouve plein d'outils de refactoring, d'analyseurs de code, de programmation oriente aspect, etc etc. La richesse de ces outils vient du fait que ces langages exposent une grammaire plus facile et que les outils annexes peuvent mieux comprendre et aider le programmeur.

Un tel systeme demandera a priori une gestion relativement specifique au moins pour dire qu'on ouvre les fichiers en mode asynchrone et non synchrone.

Donc au final, c'est l'application qui doit s'adapter et tu perds l'avantage de la transparence du systeme. Sous KDE, toutes les applications sont deja adaptees a ces problemes. Et KDE n'a eu besoin de demander l'autorisation de personne (Linus, ...) pour le mettre en place et le tester.

Un autre probleme de monter des repertoires distants via le kernel, c'est que l'api pour travailler sur les fichiers (open,read,write,close) suppose en permanence que la lecture d'un fichier est tres rapide, qu'en cas de probleme, tu as une erreur immediatement et que tous les appels sont synchrones (je bloque tant que je n'ai pas de reponse).

Utilise une telle API pour des lecteurs qui peuvent etre tres lent, ou la connection peut carrement etre perdue a tout moment donne un tres mauvais resultat. Des que tu as une operation lente, il veut mieux la faire de facon asynchrone et garder la main sur la partie visuelle de l'application, en proposant un dialogue permettant d'arreter immediatement l'operation en cours.

Si tu as deja utilise un disque dur foireux ou tu fais un ls et tu attends deux minutes sans rien pouvoir faire, tu as une idee de ce que peut etre la latence sur un systeme de fichier monte a distance : super penible.

En fait, tu ne peux pas concevoir une application qui travaille sur un systeme de fichier ayant des caracteristiques reseau (latence, perte de connection) sans integrer ce parametre dans ton application.

Donc les fuse-ioslave, ca peut resoudre qqs problemes pratiques mais ce n'est pas la panacee.

Tu peux utiliser le VFS de KDE avec fuse depuis plus de deux ans :

http://kde.ground.cz/tiki-index.php?page=KIO+Fuse+Gateway

Et donc, tu peux utilsier tous les ioslave KDE sous bash.

Dans la pratique, ce n'est pas tres pratique donc pas tres utilise.

Il y a eu une enfilade de deux mois sur un VFS commun entre Gnome et KDE sur la liste freedesktop. Pour resumer, le VFS de Gnome est moins mature a l'heure actuelle que celui de KDE (bien qu'il semble y avoir des trucs plus interessants sous certains aspects) et il y a enormement de problemes techniques pour la realisation.

Ensuite viendrait la question de ce qui pourrait pousser une desktop comme KDE qui a une solution robuste et eprouvee depuis maintenant 5 ans pour passer a un truc inferieur (moins de ioslave que sous KDE) et mal teste. Ca arrivera surement mais ce ne se fera pas simplement.

Bref, je ne critique pas le fait d'unifié les systèmes, je critique le fait que gnome et kde ont par le passé unifié leur système respectif mais par la même un peu exclu le reste.

J'avais tendance a penser comme toi mais en fait, l'experience montre que c'est la voie naturelle. Tu ne peux pas commencer a prevoir l'integration dans un autre environnement que le tien tant que tu n'as pas essaye la solution d'abord chez toi.

Pour le coup des framework VFS, Gnome est arrive tres en retard sur KDE et a fait un truc different, avec des URLs incompatibles avec celle de KDE.

Si on prend l'exemple de DCOP et DBUS, la situation est relativemetn similaire. D'abord on valide une solution qui marche (DCOP) puis on derive qq chose qui va plus loin (DBUS). Si tu essayes de faire DBUS du premier coup, tu n'y arrveras jamais.

Il y a scite qui est assez connu et marche meme sous windows. Il y a plein de mecs dans ma boite qui l'utilisent pour editer et executer du python.

Je pense qu'en fait pour les gens qui editent vraiment _beaucoup_, un gain de productivite meme leger represente un confort important, et que c'est ce qui les conduits a des editeurs comme vim ou emacs, qu'ils defendent avec ardeur.

Tu as raison. Ce qui reste interessant tout de meme, c'est que comme tu le constates, je suis loin d'utiliser toute la puissance de vi. Et pourtant, c'est deja suffisant pour moi pour creer un gain de productivite significatif.

Pour mon cas particulier, aller cherche l'accolade, c'est un shift plus la touche a cote de (je suis en clavier americain), ce qui veut dire deux utilisations du petit doigt droit et gauche. C'est un mouvement plutot difficile et fatiguant, ce qui fait que je ne l'utilise pas souvent.

Pour les jjjjj, pour moi, c'est plus rapide de les taper que de compter le nombre de lignes a l'ecran, de taper le nombre puis de taper j.

Un des gros avantages de vim que j'apprecie personellement (et qui est au passage le truc le plus deroutant pour les debutants), c'est qu'il y a deux modes d'editions :

- un mode ou le texte que tu tapes est insere, comme sur Kate ou les autres editeurs classiques

- un mode ou chaque touche correspond en fait a une action, que tu lancerais sur les autres editeurs via des combinaisons de Control ou ALT.

Ce second mode permet d'effectuer des actions complexes en laissant tes doigts a des emplacements faciles a joindre sur le clavier. D'une part, c'est moins fatiguant pour les mains, d'autre part, c'est beaucoup plus rapide.

Exemple, tu veux faire un copier/ colle :
- Kate version souris : tu selectionne le texte, tu fais menu-droit copy, tu scroll ton texte avec la souris, tu positionnes le surceurs, tu fais menu-droit-paste

- Kate version clavier : tu selectionnes le texte, tu fais Control-C, tu scrolles ton texte avec Page-Down et Cursor-Down, tu fais Control-V

- Vi version souris : tu selectionne le texte, tu fais menu-droit copy, tu scroll ton texte avec la souris, tu positionnes le surceurs, tu fais menu-droit-paste (a noter que c'est la meme chose que Kate version souris)

- Vi version clavier : tu demarra ta selection de texte avec V. Tu deplace ton curseur avec la touche kjhl pour contenir toutes les lignes que tu veux selectionner. Tu tapes y pour faire la copie. Tu te deplace a coup de page-up ou page-down (j'ai jamais pu me rappeler le racourci pour les sauts de pages), tu positionnes ton curseur avec les touches khjl et tu tapes P.

Si on compare kate et vi au clavier, on pourrait imaginer la suite de touches suivantes :
[Down]
[Down]
Control-[Right]
Control-[Right]
[Shift appuye]
[Down]
[Down]
Control-C
[Page-Down]
[Page-Down]
[Down]
[Down]
Control-V

et
j
j
w
w
v
j
j
y
[Page-Down]
[Page-Down]
j
j
p

Tu notes que les touches vi sont plus faciles a taper. A noter aussi que vi est relativement compatible avec un mode d'edition a la kate, de sorte qu'on peut envisager un apprentissage plus lent des foncitonnliates specifiques vi (par exemple, se deplacer au curseur plutot qu'avec jkhl).

Ca demande a savoir bien coder en récursif, et savoir ce que c'est qu'une fonction au sens mathématiques du terme :p

Ce sont des concepts qu'on est ravi d'utiliser quand on veut juste changer une option de config a la con. :-)

On n'a pas la meme definition d'alourdir. Si je suis ton raisonnement, tout ce qui n'est pas ecrit en assembleur est lourd.

Je trouve que tu utilises un vocabulaire imprecis et une analyse hyper theorique eloignee des realites pratiques et des problematiques reelles, ce qui conduit a des conclusions qui sont a mon sens plutot denudees de justesse.

Derriere le vocable fourre-tout "ajouter une couche", il y a differentes operations possibles, l'une pouvant ralentir de facon signficatives les performances du programme et meme en affecter le fonctionnement (genre rajouter xine au dessus de alsa) et l'autre a un impact negligeable (ajouter un ou deux appels de fonctions pour acceder a le meme fonctionnalite).

Je ne sais pas ou tu as lu que KDE ne pretend pas a la legerete (peut-etre dans le marketing de Gnome ?) mais ce n'est pas du tout le cas. Toutes les versions de KDE depuis la 2.0 sont plus rapides les unes que les autres et consomment moins en memoire.

La convivialite est en revanche une preoccupation importante de KDE et si cela veut dire "alourdir" le protocole ssh en "rajoutant une couche" avec kio pour que ce soit plus convivial, ca me semble une bonne chose.

Juste pour rire, est-ce que qq'un a deja note que fish: etait plus lent que scp ? Est-ce que qq'un a deja eu un probleme de ce style au point de vouloir supprimer fish ?

Le communisme en Chine, c'est une grosse blague. J'ai jamais vu un pays aussi ultra-liberal.

Moui enfin les 2 logiciels libre multiplateformes les plus connus sont: OpenOffice et Mozilla.
Ils sont aussi célebre pour être des monstres gourmands, la question est donc: est-ce lié?
J'aurais tendance à penser que ce n'est pas obligatoire car Opéra bien que multi-plateforme est légé, mais le risque existe..

Et justement, opera utilise Qt, tout comme KDE.

Ce portage vers windows ne fait pas l'unanimité dans la communauté KDE. Mais bon, je vois mal les développeurs KDE interdire à qq'un de faire le portage. Pour un soft en LGPL/BSD, ce serait un comble.

Par contre; je ne sais pas où tu as rêvé que ce portage coûtait du temps ou de l'argent à Qt ou KDE. Qt tourne sous windows depuis la version 1.0 donc pas d'impact de ce côté-là. Concernant KDE, ce ne sont pas les gens qui dévelppaient auparavant sur KDE qui font le portage windows, ce sont des gens qui n'interviennent que sur cet aspect-là. Il n'y a donc pas de gachis ou de perte, simplement des contributeurs supplémentaires qui travaillent sur un aspect du projet qui n'avait pas encore été exploré.

En revanche, visiblement, David Faure a accès à un MacOs X et patch régulièrement pour cette plate-forme.

En tout cas, le projet KDE n'a pas dit "on va porter KDE sur windows parce que c'est une plateforme stratégique". C'est une bande de contributeurs indépendants qui font le travail, qui a d'ailleurs longtemp été héberge sur sourceforge, en tant que projet indépendant de KDE. Ils n'ont pas reçu d'interdiction de KDE de faire ce boulot.

Je ne suis pas d'accord avec toi. Unifier une API, ce n'est pas nécéssairement l'alourdir. Cf mon message plus bas avec kio comme exemple. Kio n'alourdit pas le protocole html ou le protocole ssh, il se contente de l'utiliser en fournissant une interface uniforme pour les applications KDE.

D'un point de vue programmation, phonon rajoute une couche, mais d'un point de vue fonctionnel, phonon est complètement transparent.

Finalement, la plus grosse nouveaute dans ce projet, c'est le nom : Phonon. C'est quand meme plus joli que kdemm .

Quelque part ça me semble évident. Si arTs propose les fonctionnalités A, B et C et que ESD propose B, C et D, pour être parfaitement interopérable, Phonon doit supporter B et C.

Ou bien phonon fournira une emulation de A. Ou bien les applications qui necessitent D auront la possibilite de demander si la fonctionnalite est disponible et si ce n'est pas le cas, de dire a l'utilisateur "Pour s'executer, ce programme necessite la fonctionnalite D dans le backend multimedia mais cette fonctionnalite n'est pas disponible sur votre backend".

A noter que ce type de comportement est deja utilise dans plein d'application ou de technologies. Par exemple, la surveillance de la mise a jour des repertoires (un nouveau fichier est-il arrive ?) se fait via une bibliotheque (dont j'ai oublie le nom) qui par defaut va faire du polling sur le repertoire, mais qui si l'option qu'il faut est dans le noyau et que le filesystem le supporte, va utiliser un mecanisme du file system pour etre informe des modifications du repertoire.

Prenons un autre exemple: kio. C'est la facon standard sous KDE d'acceder a un fichier. kio offre des backend pour:
- local filesystem
- http
- ftp
- ssh
- samba
- nfs
- pda

Tu peux dire que kio n'offre qu'un sous-ensemble de tous les protocoles cites et c'est vrai. Je doute que tu puisses executer une commande ssh avec redirection de port via kio. Mais est-ce un probleme ? kio repond a une problematique, acceder a ses fichiers a distance de facon transparente pour toutes les applications KDE. Si tu veux faire de la redirection de port ssh, il semble plus correct d'utiliser directement ssh. Mais dans ce cas, tu changes la problematique, tu n'es plus en train d'acceder a tes fichiers a distance, tu es en train de faire un truc specifique a ssh.

De meme, la problematique de phonon n'est pas de tierer partie du moteur xine ou gstreamer pour faire du mixage video ou que sais-je, mais de fournir des fonctionnalites de base a l'utilisateur (cf la page web):
- faire en sorte que toutes les applications KDE puissent "faire du bruit" de facon simple sans se soucier du backend
- faire en sorte que KDE n'impose pas un moteur multimedia a l'utilisateur vu qu'il y en a pour tous les gouts et les couleurs
- pouvoir regler le son de facon simple sous KDE sous toutes les applications
- faire facilement de la capture de son


Le probleme pendant longtemp sous Linux a ete l'absence de moteur multimedia. Les differentes solutions developpees pallient cette absence, mais ont globalement un jeu de fonctionnalite tres similaire. Donc cette unification est plutot la pour gerer la diversite des moteurs multimedia et pas pour faire un meta-moteur.

L'avantage de la structure actuelle, c'est qu'il y a tres peu de programmation en jeu. Notammnent, il n'y a aucune programmation graphique. Sur tu regardes les sources, tu verras des scripts bash et des .desktop, rien de plus.

On peut dire que Bram protege precieusement vim pour qu'il reste tres stable. C'est un peu ce qui nous a oblige a demarrer yzis. Un pour rajouter une configuration en ligne de commande qui n'etait pas utilisee par vim de toute facon (uniquement kvim), ca nous a calme.

En terme de sauvegarde, ESC : w est la suite de touche que je tape des que j'entre en mode "normal". C'est devenu un pur reflexe et je n'ai jamais besoin de compter sur vim pour me restaurer mes fichiers.

Pour faire court sur le choix lua vs python, disons que lua, en deux jours t'as un truc fonctionnel et utilisable.

En python, apres 2 semaines de bataille avec boost ou l'api C de python, t'as un truc qui marche a peu pres mais qui compile pas systematiquement sous toutes les plateformes (notamment sous windows, je m'arrache les cheveux).

En tant que fan de python, je suis pour python qui a plus de potentiel mais clairement, lua marche beaucoup mieux aujourd'hui et pour longtemp et remplit 95% du besoin.

J'ai un convertisseur vim -> lua qui marche pas mal sur des scripts pas trop complexes. Ca m'interesse d'avoir des scripts vim qui des gens utilisent pour pouvoir tester le convertisseur de facon un plus poussee et valider qu'on a bien toutes les interfaces qu'il faut dans yzis.

Interessant.

Pida marche parce que vim utilise une fenetre gtk par defaut et que pida est en gtk et gtk dispose d'un mecanisme pour incruster ses propres fenetres. Faire l'integration de vim gtk dans un widget Qt est beaucoup beaucoup plus complique puisqu'on dependait d'une fonctionnalite, XEmbed, qui avait ete incompletement implementee et peu testee par Trolltech et Gtk.

J'ai pas essaye, mais je pense qu'il reste des limitations. Le protocole de communication vim-server vim-client est plutot leger et ne permet par de faire un certain nombre de chose. Notamment, si on envoit une commande via ce canal, on ne peut pas savoir si la commande a reussi ou pas.

Bonjour,

Un point interessant a noter dans les fonctionnalites les plus demandees :
http://www.vim.org/sponsor/vote_results.php

L'integration dans un autre GUI. Nous, les auteurs de kvim avions fait ce travail et avons finalement renonce a cause de la trop grande difficulte de travailler sur la base de code de vim, et le manque de volonte de Bram de modifier Vim dans ce sens.

Donc la 3e fonctionnalite la plus demandee n'est pas prete d'arriver.

En revanche, nous avons demarre un autre projet, yzis, qui est un clone de vim sans les ``limitations'' imposees par l'architecture de vim. Quelques choix techniques :
- dev en C++
- scripting en lua
- moteur de syntaxe de kate
- gui en Qt, KDE et ncurses pour l'instant (sans limitations d'autres possibilites)
- utilisation de libyzis comme moteur vi independant (facon scintilla)
etc.

Plus de details sur :
http://linuxfr.org/2005/02/16/18311.html
http://www.yzis.org

Le developpement a un peu ralenti ces derniers mois mais repart, avec notamment le portage complet a Qt4 qui nous permettra d'avoir un yzis Windows, MacOs et Linux sous GPL tres facilement.

On est pas au niveau de vim question fonctionnalite et stabilite, mais on s'en approche a grand pas. Et c'est vraiment facile de participer grace a l'architecture propre en C++ (l'architecture de vim et a s'arracher les cheveux).

Un exemple de solution (pas de moi) :

#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;
}
};

Les programmes doivent etre rapides a ecrire et rapide a executer. Python et ruby sont bons au moins dans la premiere categorie.

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 :-)

J'ai essaye mais il ne semble pas possible de livrer les sujets sans s'inscrire. Et a la fin de chaque probleme, il y a un gros copyright.

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.

J'ai pas precise mais en fait, tu codes dans une application java qui compile et execute le code sur leur serveur. Au final, tu livres un bout de code source donc c'est vraiment topcoder qui impose le langage.

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).