Robot Programming
Le jeu Robozzle fait partie
d'une grande famille de jeux de programmation de robots1. Dans ce jeu,
des robots se déplacent dans un espace avec un ensemble
d'objectifs à réaliser. Le but du jeu consiste à produire un
programme (usuellement dans un langage
simplifié) permettant au robot d'accomplir l'ensemble de ces
objectifs. Dans Robozzle, l'objectif consiste à ramasser
l'ensemble des étoiles sur le plateau sans tomber hors des
limites. Ainsi, dans l'exemple suivant, le programme doit
conduire le robot tout droit, et le faire tourner sur les cases
vertes, à gauche au début, puis a droite à partir de la case
rouge, tout cela pour atteindre l'étoile :
Un petit langage de programmation comme celui utilisé dans ce jeu permet quand même de créer des dizaines de puzzles plus ou moins complexes. La page des techniques est accessible et permet d'aborder les puzzles à travers diverses techniques de programmation accessibles : le color turning, le stacking ou counting (techniques d'utilisation de la pile pour implémenter des compteurs), le wall hugging / crawling et le dizzying.
L'objectif de ce projet consiste à produire un ensemble d'outils permettant de construire des puzzles du style précédent, exécuter des programmes sur ces puzzles, vérifier s'ils sont capables d'atteindre correctement un ensemble d'objectifs, et enfin concevoir des algorithmes capables, étant donné un puzzle, de trouver un ou plusieurs programmes capables de le résoudre.
|
|
| Image tirée du site Robozzle pour le puzzle "Right on Red" | Code Javascript spécifiant ledit puzzle |
Un petit langage de programmation comme celui utilisé dans ce jeu permet quand même de créer des dizaines de puzzles plus ou moins complexes. La page des techniques est accessible et permet d'aborder les puzzles à travers diverses techniques de programmation accessibles : le color turning, le stacking ou counting (techniques d'utilisation de la pile pour implémenter des compteurs), le wall hugging / crawling et le dizzying.
L'objectif de ce projet consiste à produire un ensemble d'outils permettant de construire des puzzles du style précédent, exécuter des programmes sur ces puzzles, vérifier s'ils sont capables d'atteindre correctement un ensemble d'objectifs, et enfin concevoir des algorithmes capables, étant donné un puzzle, de trouver un ou plusieurs programmes capables de le résoudre.
Un fichier JSON contenant 5000 puzzles a été ajouté à votre
dépôt de code, et d'autres puzzles sont accessibles sur le
site. Il est par ailleurs possible de récupérer le code d'un
puzzle donné en fouillant dans le code de la page permettant
de jouer au puzzle (par
example celle-ci,
dans une balise
<script> de la
partie <head>).
Le sujet est dédié à l'utilisation et à la compréhension de
techniques de programmation fonctionnelle. Les programmeurs
sont invités à proposer des outils et des extensions du sujet
propres à mettre en valeur ces techniques. La partie
"interface graphique" du sujet est considérée
comme mineure, sauf si elle met en
pratique des techniques de programmation fonctionnelle.
Robots, programmes, et mondes
Les mondes sont des grilles 2D de taille
12x162. Chaque
case de la grille est colorée d'une couleur dans l'ensemble {
Les programmes sont en fait des tableaux de :
Une instruction définit soit une action de la part du robot, soit un appel à une fonction du programme (dans la liste des fonctions disponibles). Parmi les instructions du langage, il est demandé de pouvoir faire un
L'exécution d'un programme consiste à appeler la première fonction du programme. L'appel d'une fonction exécute chacune de ses instructions en séquence, s'arrêtant à la fin de cette liste. Si l'une de ses instructions consiste à appeler une fonction, alors celle-ci est exécutée récursivement, en utilisant la même méthode. En cela, l'exécution d'un programme va faire que des appels de fonctions s'empilent et se dépilent, amenant au choix soit à la terminaison de l'exécution, soit à des boucles infinies d'exécution, soit à une explosion de la pile d'appel. A titre d'information, le puzzle suivant permet de comprendre comment utiliser la pile d'appel dans un problème.
Un puzzle consiste en la donnée :
Pour simplifier le problème, le sujet fixe un certain nombre de limites à l'exécution des fonctions :
BLEU,
ROUGE, VERT, NOIR }. La
couleur NOIR est considérée comme inaccessible. Les
cases en dehors du monde sont aussi considérées comme
inaccessibles. Chaque case accessible peut comporter une étoile
ou un autre élément de décor3.
Les programmes sont en fait des tableaux de
N fonctions, chaque fonction représentée par un
indice de ce tableau (allant de 1
à N). Une fonction est une
suite finie d'instructions représentée par
les dessins suivants
Une instruction définit soit une action de la part du robot, soit un appel à une fonction du programme (dans la liste des fonctions disponibles). Parmi les instructions du langage, il est demandé de pouvoir faire un
MOVE (avancer le
robot d'une case dans la direction qu'il vise),
un LEFT et un RIGHT (tourner le robot
d'un quart de tour), et un CALL_I (appeler la
fonction d'indice I).
Chaque instruction peut être colorée en
{ BLEU, ROUGE, VERT },
auquel cas elle ne s'applique que si le robot est situé sur une
case de la même couleur, sinon elle n'a aucun effet. Les
instructions sont par défaut colorées en NOIR, ce
qui signifie qu'elles s'appliquent sur toutes les cases. Comme
le montre le dessin ci-dessus, les instructions n'ont pas de
raisons d'être limitées à celles présentes sur le site de
Robozzle.
L'exécution d'un programme consiste à appeler la première fonction du programme. L'appel d'une fonction exécute chacune de ses instructions en séquence, s'arrêtant à la fin de cette liste. Si l'une de ses instructions consiste à appeler une fonction, alors celle-ci est exécutée récursivement, en utilisant la même méthode. En cela, l'exécution d'un programme va faire que des appels de fonctions s'empilent et se dépilent, amenant au choix soit à la terminaison de l'exécution, soit à des boucles infinies d'exécution, soit à une explosion de la pile d'appel. A titre d'information, le puzzle suivant permet de comprendre comment utiliser la pile d'appel dans un problème.
Un puzzle consiste en la donnée
- d'un monde, contenant au minimum une case accessible et une position pour le robot sur une case accessible,
- d'une spécification des objectifs devant être réalisés sur ce monde (par exemple : ramasser toutes les étoiles, mais si vous avez d'autres éléments de décor, cela peut varier),
- et d'une spécification des programmes autorisés (à savoir la taille des programmes possibles et des fonctions à l'intérieur des programmes, et la liste des instructions autorisées pour résoudre le puzzle).
Pour simplifier le problème, le sujet fixe un certain nombre de limites à l'exécution des fonctions :
- Les programmes ne peuvent pas comporter plus de 5 fonctions en tout (sinon il s'agit d'une "Invalid program specification").
- L'exécution d'un programme ne peut demander d'appliquer plus de 1000 instructions (l'appel d'une fonction comptant comme une instruction), sous peine d'être déclarée comme "Infinite loop error".
- La même exécution ne peut pas dépasser plus de 50 appels de fonctions imbriqués sous peine d'être déclarée comme "Stack overflow error".
- Toute exécution amenant le robot à se retrouver dans une position inaccessible est déclarée comme "Out of ground error".
- Le chargement d'une carte incorrecte (par exemple comportant des lignes incomplètes) produit un "Incorrect world error", tandis que l'application d'une instruction inconnue ou incorrecte produit un "Unknown instruction error".
Description du projet
Le projet se propose de réaliser à la fois une bibliothèque
permettant de créer des mondes et des programmes, d'exécuter
lesdits programmes sur lesdits mondes, et de concevoir et
résoudre des puzzles bien pensés. Une décomposition des tâches
possibles est discutée ici.
-
Concevoir un langage de programmation
simplifié.
Proposer une manière de décrire des programmes et des instructions permettant de déplacer un robot dans un monde donné. Les instructions utilisées dans Robozzle doivent être présentes. D'autres instructions peuvent être ajoutées, à discuter avec vos encadrants. -
Écrire un évaluateur pour ce langage.
Programmer un ensemble de fonctions Ecmascript qui, étant donné un programme, et un monde, réalisent l'exécution de ce programme sur le monde, et produisent un compte-rendu de cette exécution, ainsi que son résultat (soit une terminaison normale, soit l'erreur d'exécution). -
Proposer un afficheur pour les
exécutions.
Écrire un code générant une page HTML permettant de visualiser les exécutions de vos programmes. L'afficheur devra permettre de visualiser la pile d'appel. Pour les besoins de ce projet, cette partie est considérée comme mineure. Un fichier d'exemple vous est fourni comme base de départ à modifier. -
Concevoir une manière de représenter les
objectifs pour une exécution.
Par exemple, dans le cas de Robozzle, un objectif consiste à vérifier qu'à la fin d'une exécution, le robot est passé par toutes les cases contenant une étoile au moins une fois. Selon le puzzle, on peut imaginer que l'objectif accepte qu'à la fin de l'exécution, le robot s'arrête de lui-même, ou bien termine sur une "Out of ground error" après avoir ramassé toutes les étoiles. -
Proposer des façons d'étendre le monde
pour en complexifier les mécanismes.
Simplement, il suffit, en plus des étoiles, d'ajouter des clés, des portes, des murs, des bombes, des canards tirant des lasers et des lapins sautillants … -
Proposer des méthodes pour engendrer des
problèmes.
Dans cet objectif, il est demandé d'engendrer des programmes simples non triviaux, dans l'idée de concevoir des puzzles à partir de ces programmes. L'exemple du puzzle "recursed" montre qu'il est possible de faire des puzzles complexes avec très peu d'instructions. Évidemment, il faut engendrer le monde en même temps que le programme. Pour cela, on peut envisager différentes tactiques raffinant la simple génération aléatoire. -
Proposer des méthodes pour trouver des
solutions auxdits problèmes.
Trouver un programme résolvant un puzzle se résume à explorer l'espace des programmes possibles. Dans certains cas, cet espace est d'une taille suffisamment restreinte pour explorer toutes les possibilités. D'un autre côté, les programmes ainsi construits sont généralement facilement encodables dans de simples chaînes de caractères. Des algorithmes génétiques peuvent être envisagés pour obtenir des solutions aux puzzles. Le sujet laisse la porte ouverte à d'autres types d'algorithmes. - Offrir la possibilité de pouvoir revenir en arrière dans les exécutions. . L'idée serait de pouvoir aider au débuggage des fonctions pour mieux comprendre comment l'évaluateur a pu prendre ses décisions au cours de l'exécution.
Détails techniques
Pour les besoins du projet, les fichiers devront être organisés de la
manière suivante dans le dépôt :
Le code du projet doit être écrit en Typescript, et compilé avec le compilateur
Le code du projet devra respecter les règles
Le
Le code doit contenir un exécutable qui peut être démarré (après compilation) en utilisant la commande suivante :
Les paramètres passés à cet exécutable sont laissés à la liberté
des programmeurs, néanmoins ils doivent être décrits précisément
dans la documentation. Il est demandé que l'exécutable réponde
au minimum aux options
/ -- Base directory
Makefile -- Global Makefile
/src -- Source files
/test -- Test files
/dist -- Compiled and Web files (should be empty in the repository)
Le code du projet doit être écrit en Typescript, et compilé avec le compilateur
tsc dans le
répertoire dist. Le sujet ne fait aucune obligation
sur l'utilisation qui est faite du langage (en particulier en ce
qui concerne les types), à part l'obligation d'avoir un code qui
compile sans erreurs selon la
configuration tsconfig.json fournie.
Le code du projet devra respecter les règles
ESLint
(cf. la section
dédiée) imposées dans le
fichier eslint.config.js. Il n'est évidemment pas
autorisé de modifier les fichiers de configuration fournis.
Le
Makefile doit contenir au minimum :
-
une règle
make buildqui compile l'ensemble des fichiers nécessaires au fonctionnement du code dans le répertoiredist. -
une règle
make testpermettant d'exécuter les tests propres au projet, ainsi que d'une règlegenpour générer un ensemble de fichiers dans le répertoirepublic. -
une règle
make eslintexécutant la commandeeslintsur les fichiers de code dans le dépôt (cf. la section dédiée) pour en vérifier la syntaxe; -
une règle
make servequi doit lancer, à traversParcel(cf. la section dédiée), un serveur HTTP tournant surlocalhost:1234et permettant d'afficher l'exécution d'une partie.
Le code doit contenir un exécutable qui peut être démarré (après compilation) en utilisant la commande suivante :
node dist/src/main.js-h et --help
pour décrire son fonctionnement.
node dist/src/main.js --help- un
fichier tsconfig.json
servant de configuration
pour
tsc; - un
fichier eslint.config.js
servant de configuration
pour
ESLint(cf. partie sur ESLint); - un fichier
jest.config.ts
servant de configuration pour
jest(cf. partie sur Jest).
Node.js nécessaires au
fonctionnement du code et pouvant apparaître au sein du
fichier package.json doivent se restreindre à la
liste suivante@types/jest, @types/node,
@types/underscore,
commander, eslint,
fp-ts, immutable,
jest, parcel,
pure-rand,ramda,
ts-jest, ts-node,
typescript, typescript-eslint
et underscore.
Le dépôt ne devra en aucun cas contenir
les modules
Le dépôt ne devra en aucun cas contenir de fichier de données gigantesques. Toute présence d'un fichier (ou d'un ensemble de fichiers) d'une taille déraisonnable dans le dépôt à un instant du développement verra attribuer un malus de
L'exécution de toutes les parties du code (page web comprise) ne devra en aucun cas faire appel à une quelconque ressource sur le réseau, et devra donc pouvoir s'exécuter sans accès à Internet.
Node.js utilisés dans le code. Toute
présence d'un quelconque répertoire node_modules
d'une taille strictement positive dans le dépôt à un instant
du développement verra attribuer un malus
de -2 à la note finale du projet, ce malus
étant cumulatif.
Le dépôt ne devra en aucun cas contenir de fichier de données gigantesques. Toute présence d'un fichier (ou d'un ensemble de fichiers) d'une taille déraisonnable dans le dépôt à un instant du développement verra attribuer un malus de
-2
à la note finale du projet, ce malus
étant cumulatif. Pour fixer les idées,
les tailles raisonnables sont de l'ordre de 100ko.
L'exécution de toutes les parties du code (page web comprise) ne devra en aucun cas faire appel à une quelconque ressource sur le réseau, et devra donc pouvoir s'exécuter sans accès à Internet.
Utilisation de ESLint
ESLint est un analyseur statique de code, qui
permet de vérifier un certain nombre de règles syntaxiques. Il
peut être configuré pour vérifier du code TypeScript.
- Page principale
d'
eslint; -
Tutoriel pour l'utilisation de
ESLint - Liste des
règles disponibles dans
ESLint.
ESLint est la suivante :
npx eslint src tst
Utilisation de Jest
Jest est un framework de test en Javascript qui
peut lui aussi être configuré pour être utilisé avec TypeScript.
- Page principale
de
Jest; - Tutoriel
pour l'utilisation de
Jest; - Documentation des matchers;
Principalement, la commande à retenir pour
utiliser Jest est la suivante :
|
L'exemple simple de test en Jest est le
suivant :
|
npx jest mytest.ts |
|
Utilisation de Parcel
Une partie du sujet propose de produire une page présentant les
capacités du projet. Cette page peut faire appel à un ensemble
d'autres fichiers présents dans le dépôt (styles CSS, fichiers
JS). La pratique courante consiste à utiliser un logiciel pour
préparer le code aussi appelé bundler. Le
bundler autorisé pour ce projet se
nomme :
Parcel-
Page principale
de
Parcel. - Tutoriel
pour l'utilisation de
Parcel(privilégiernpmàyarn). -
Options de
la CLI de
Parcel.
Parcel est la suivante :
npx parcel serve src/index.html
Recommandations
Pour l'ensemble du projet, il est recommandé de
systématiquement :
- Définir formellement les éléments nécessaires pour représenter le jeu, et les relier à leur implémentation.
- Définir formellement les algorithmes proposés, et étudier leur complexité (temps/mémoire).
- Caractériser dans les algorithmes et structures de données ce qui ressort de la programmation fonctionnelle et ce qui n'en est pas.
- Suivre les standards de codage développés dans le cours de programmation fonctionnelle et disponibles à l'adresse suivante.
Contact
Pour toute information complémentaire, contacter : David RENAULT.
| 1. | Qui existent en version numérique comme au format jeu de plateau, comme le fort connu RoboRally, mais ce n'est qu'un exemple parmi beaucoup. |
| 2. | Les tailles 12x16 sont
prescrites par le site du jeu, mais il peut être envisagé de
construire des puzzles de tailles différentes. |
| 3. | Des fruits, des instruments de musique, des animaux ... tout ce que l'Unicode vous permet de réaliser, tant que c'est de bon goût. |