Nerdle
1.1. Objectif
Le jeu Nerdle consiste à résoudre un casse-tête basé sur des nombres.
On désire offrir au joueur, un assistant, qui va lui donner, en fonction :
- d'une formule de calcul dont les opérateurs sont connus et bien placés
- ainsi que d'un ensemble possibles de chiffres
l'ensemble des formules valides.
Pour gagner en jouant à Nerdle il suffit de commencer par saisir les formules suivantes :
- 3*9+0=27
- 54/6-8=1
En effet, ces deux formules permettent de déterminer :
- quels chiffres sont utilisés, puisqu'on passe en revue 0, 1, ..., 9
- quels opérateurs sont utilisés puisqu'on a utilisé +, -, *, /
- où se trouve l'opérateur d'égalité : en position 6 ou 7, voire en position 5 si les positions 6 et 7 ne sont pas validées
1.2. Exemple
Dans le formulaire qui suit, la formule de calcul est donnée et commence par le chiffre 3. Les opérateurs doivent être spécifiés et la formule contient un signe '='.
Les points '.' représentent des chiffres qu'il faudra remplacer par les chiffres autorisés.
Attention avec les formules contenant des divisions car Javascript utilise la division réelle, donc $9/2 =4,5$ et non pas $4$. Il est donc nécessaire de tronquer le résultat (Math.trunc) si on veut une division qui s'apparente à une division entière.
1.3. Technique
Le but du projet consiste à écrire un programme C/C++ qui lit une expression comme présenté ci-dessus et la représente sous forme d'arbre afin de pouvoir l'interpréter par la suite.
On pourrait utiliser une structure d'arbre afin de représenter l'expression ainsi qu'un analyseur lexical et un analyseur syntaxique afin de l'analyser. Cependant, ce sont des techniques qui ne sont pas d'un niveau L1.
On propose donc afin d'évaluer l'expression une fois instanciée, de faire un appel système à la commande bc (An arbitrary precision calculator language, voir man bc) que l'on peut utiliser de deux manières différentes :
richer@zentopia\$ echo "1+2==3" | bc
1
richer@zentopia\$ bc <<< "1+2==4"
0
Pour ce faire on utilisera une la fonction de la librairie C appelée popen afin d'exécuter la commande mais également de récupérer sa sortie.
1.4. Le Programme
Le programme devra donc prendre en paramètres deux chaînes de caractères :
- la première est la formule qui contiendra les opérateurs et des '.' pour les chiffres qu'il faudra trouver
- la seconde représente l'ensemble des chiffres possibles, ceux-ci pouvant apparaître éventuellement plusieurs fois dans la formule
1.5. Méthode de résolution
Concevoir une méthode de résolution en se basant sur un traitement récursif qui consistera à instancier tous les '.' de la formule par un chiffre, puis à évaluer l'expression. Si celle-ci est vraie alors on l'affichera.
1.6. Travail
Pour la période de 17 au 21 avril 2023 :
- se familiariser avec les règles de Nerdle
- créer un programme C/C++ qui permet de lancer une commande, comme ls -l, puis de récupérer et afficher sa sortie dans le terminal. La commande doit être passée en argument du programme et récupérée en utilisant la variable argv
- élaborer l'algorithme de résolution du problème : définir les données en entrée ainsi que le déroulé de l'algorithme