Available nodes

 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:

const puzzle = {
   id:644,
   title:"Right on red",
   about:"",
   robotCol:7,
   robotRow:6,
   robotDir:0,
   subs:[5,4,0,0,0],
   allowedCommands:0,
   board:[ '                ',
           '                ',
           '                ',
           '     gbbbbbbg   ',
           '     b      b   ',
           '     b      b   ',
           '     b bbbbbg   ',
           '     b          ',
           '   B grg        ',
           '   b  b         ',
           '   gbbg         ',
           '                ' ]
};
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 { 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).
Un programme est considéré résoudre un puzzle s'il suit ses spécifications et atteint ses objectifs. Un puzzle est considéré comme bien pensé si il existe au moins un programme le résolvant.
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 :
    /               -- 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 build qui compile l'ensemble des fichiers nécessaires au fonctionnement du code dans le répertoire dist.
  • une règle make test permettant d'exécuter les tests propres au projet, ainsi que d'une règle gen pour générer un ensemble de fichiers dans le répertoire public.
  • une règle make eslint exécutant la commande eslint sur 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 serve qui doit lancer, à travers Parcel (cf. la section dédiée), un serveur HTTP tournant sur localhost:1234 et 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
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 -h et --help pour décrire son fonctionnement.
node dist/src/main.js --help

Des fichiers de configuration sont fournis pour les différents outils, et ce sont ceux utilisés sur la forge pour les tests:

Ces fichiers sont utilisés en particulier sur la forge pour compiler, vérifier la syntaxe et tester le code.

Les paquetages 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 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. Principalement, la commande à retenir pour utiliser 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.
Principalement, la commande à retenir pour utiliser Jest est la suivante : L'exemple simple de test en Jest est le suivant :
npx jest mytest.ts
const sum = require('../src/sum');

test('adds 1 + 2 to equal 3', () => {
    expect(sum(1, 2)).toBe(3);
});

 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: Principalement, la commande à retenir pour utiliser 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.