:: Enseignements :: ESIPE :: E3INFO :: 2011-2012 :: Programmation C ::

Challenger (IR1, IG1 et OC1)

But du projet

Avant de vous couvrir d'or, de vous offrir un bureau de PDG, des repas traiteurs à l'oeil tous les jours et des billets d'avion en première pour aller aux conférences de votre choix, les grandes compagnies de l'industrie du logiciel aiment bien taquiner ceux qui postulent pour venir chez elles en les soumettant à des tests de programmation. Voici l'un de ces tests (note: dans la vraie vie, vous auriez 4h pour le faire).

On souhaite disposer d'un programme permettant de manipuler des intervalles d'entiers positifs ou nul. En entrée, on fournit au programme deux listes d'intervalles notés X-Y représentant toutes les valeurs entre X et Y, bornes comprises, où X est supposé inférieur ou égal à Y. Un intervalle constitué d'une seule valeur est donc noté X-X. Les intervalles d'une liste sont fournis dans un ordre quelconque, et peuvent se chevaucher ou s'inclure les uns les autres. Le but du programme est de fournir en sortie la liste triée par ordre croissant des intervalles contenant toutes les valeurs de la première liste qui ne sont pas dans la seconde liste. Voici quelques exemples:

Exemple 1:

liste d'inclusion: 10-20 50-100
liste d'exclusion: 17-62
résultat: 10-16 63-100

Exemple 2:

liste d'inclusion: 30-40 10-35
liste d'exclusion:
résultat: 10-40

Exemple 3:

liste d'inclusion: 1-7 10-100
liste d'exclusion: 5-20 89-92 30-43
résultat: 1-4 21-29 44-88 93-100

Exemple 4:

liste d'inclusion: 10-100 101-200 50-300
liste d'exclusion: 50-100 40-90 80-110
résultat: 10-39 111-300

La mort subite

Tout programme incapable de fournir un résultat correct pour les 4 exemples précédents recevra zéro, sans espoir d'arracher la moindre larme de compassion à vos professeurs en leur expliquant que "c'est pas juste, j'y ai passé des heures". Dans la vraie vie, si un plombier vous dit qu'il a passé des heures pour essayer d'installer votre baignoire mais qu'il n'y arrive pas, vous ne payez pas le gaspillage de main d'oeuvre. Ici c'est pareil.

Dans le même ordre d'idées, nous vous précisons que les tests de vos projets se feront sur une configuration identique à celle déployée sur les machines étudiantes de l'université. Pensez donc bien à tester votre projet sur cet environnement pour éviter le syndrome du "pourtant je vous jure, ça marchait chez moi".

Piece of cake ?

IR1 et IG1, je vous ai compris. Je sens d'ici votre frustration à l'idée que le projet soit aussi simple et qu'il ne vous permette pas de donner la pleine mesure de votre créativité. C'est pourquoi, ne reculant devant aucun sacrifice, la maison vous impose la contrainte suivante (pour les les OC1, c'est un bonus facultatif). Un quart de la note du projet correspondra à votre capacité à gérer non pas des int, mais des entiers arbitrairement grands. Exemple:

liste d'inclusion: 1022333444555-20000000000001245654
liste d'exclusion: 5064578867568-7279550434433 303535656732123-40046346346366687
résultat: 1022333444555-5064578867567 7279550434434-303535656732122 40046346346366688-20000000000001245654

Vous serez jugé, entre autres, sur votre capacité à avoir écrit du code modulaire pour gérer ces entiers longs. Une bibliothèque fonctionnelle, séparée et facilement réutilisable ferait l'objet d'un bonus.

Tests

Comme on n'est jamais mieux servi que par soi-même, vous devrez réfléchir au moyen de prouver que votre programme fait ce qui est demandé. Cela pourra prendre la forme que vous voulez: une preuve mathématique formelle qui pique, des jeux de données de test très complets, du code supplémentaire pour faire des tests unitaires, etc. Vous devrez justifier au mieux vos choix dans votre rapport, en expliquant pourquoi vous pensez que vos tests sont convaincants.

Conditions de développement

Le but de ce projet est autant de pondre du code que de développer le plus proprement possible. C'est pourquoi, vous développerez ce projet sur le serveur CVS de l'université. Comme nous attendons de vous que vous le fassiez sérieusement, votre rendu devra contenir un dump du fichier de logs de votre projet CVS, afin que nous puissions nous assurer que vous avez bien développé par petites touches successives et propres (commits bien commentés), et non pas avec un seul commit du résultat la veille du rendu.

Conditions de rendu

Vous travaillerez en binômes, et vous lirez pour un profit maximum la charte des projets. Vous ne rendrez pas votre projet au moyen d'une archive, mais avec un package Debian. Le rendu consistera donc en un mail dans lequel vous donnerez l'URL de votre repository, qui devra se trouver sur votre compte web de l'université. Le test de votre projet se fera alors avec la commande:

sudo apt-get install challenger

La commande challenger doit alors être installée et doit pouvoir s'exécuter selon la syntaxe suivante:

challenger [OPTIONS]

Voici les options que vous devrez proposer:

-i/--inclusion F1: fichier contenant la première liste d'intervalles. Si cette option est omise, le résultat doit bien entendu être une liste vide.
-e/--exclusion F2: fichier contenant la seconde liste d'intervalles. Par défaut, toutes les valeurs de la liste d'entrées sont autorisées.
-o/--output F3: fichier de sortie. Par défaut, le résultat sera affiché sur la sortie standard du programme.

Vous ferez bien attention à pouvoir gérer sans erreur mémoire des listes d'intervalles arbitrairement grandes. La syntaxe des fichiers contenant des intervalles est la suivante: un fichier contient un nombre arbitraire de séquence X-Y, séparées entre elles par un nombre quelconque de séparateurs (espace, tabulation, \n). X et Y doivent être collés au tiret.

En cas de fichiers d'entrée mal formés, vous êtes libres de gérer les erreurs comme bon vous semble, l'essentiel étant que vos programmes ne crashent jamais sauvagement.

Naturellement, toutes les options devront être gérées avec getopt_long. Si vous avez géré les entiers longs sous la forme d'une bibliothèque séparée, votre package devra correctement gérer cette dépendance.

Afin de pouvoir accéder aux sources de votre travail, vous préparerez également un package source contenant les choses suivantes:

un répertoire src contenant les sources du projet ainsi qu'un Makefile. Lorsqu'on lance make, on doit obtenir un exécutable nommé challenger. La cible clean doit fonctionner correctement. Les sources doivent être propres, en anglais et commentées.
un fichier cvs_logs correspondant au dump des logs de votre projet CVS
un fichier doc.pdf contenant votre rapport qui devra décrire votre travail. En particulier, vous décrirez avec soin les algorithmes que vous avez utilisés, ainsi que votre méthodologie de test. Si votre projet ne fonctionne pas complètement, vous devrez en décrire les bugs.

Comme pour l'exécutable, l'accès à votre package source se fera au moyen de apt-get:

apt-get source challenger

Il est rigoureusement interdit d'utiliser du code externe: vous devrez tout coder vous-mêmes.
Tout code commun à plusieurs projets vaudra zéro pour tous les projets concernés.

Le projet est à rendre par mail à tous les enseignants (Boulanouar Ibtissem et Sébastien Paumier pour les IR1, Sylvain Cherrier et Sébastien Paumier pour les OC1), au plus tard le lundi 14 mai 2012 à 23h.