Épreuve de qualification de la DCI pour les CS Games 2016
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
_runner
LICENSE
README.md
run.bat
run.sh
runner
solution.java
solution.py
tests.json

README.md

Qualification CS Games 2016

DCIETS

L’objectif de l’épreuve de qualification de la DCI pour les CS Games 2016 sera de concevoir et développer un programme communiquant avec un gestionnaire de mission et remplir les missions assignées par celui-ci. Ainsi, votre logiciel devra pouvoir résoudre une série de missions différente afin de maximiser votre score et faire partie de la prochaine délégation de l’ÉTS!

Communication

Afin de recevoir et répondre aux missions, votre logiciel devra être en mesure d’implémenter un protocole très simple. La communication de votre programme avec le gestionnaire de mission se fera via les entrées et sorties standard (stdin et stdout).

Ainsi, les requêtes de mission sont reçues en lisant une ligne de l’entrée standard de votre programme (par exemple, en Java vous pourriez utiliser BufferedReader.readLine). Chaque requête est composée d’un identifiant représentant le type de mission et les paramètres de ladite mission. Les types de missions possibles sont présentés plus loin. Les paramètres de mission seront toujours encodés en ASCII et leur format est spécifique à chaque type de mission. Le type de mission et ses paramètres sont séparés par deux points (:).

Ainsi, une requête de mission de type Ping avec le paramètre Pong serait reçue sous la forme:

1:Pong

La réponse est simplement envoyée en écrivant une ligne dans la sortie standard de votre programme. Ainsi, la réponse à la requête précédente serait:

Pong

Outil de test

Un logiciel est fourni afin d’exécuter votre application et d’évaluer ses performances en la testant à un petit ensemble de données. Pour tester votre application, éditer run.sh en ajoutant les lignes de commande nécessaires pour exécuter votre application. Par la suite, exécutez les tests avec ./runner ./run.sh. Vous pouvez aussi utiliser le paramètre -i 3 pour exécuter seulement la suite de tests de la mission 3.

Dans le cas où votre soumission ne supporte pas une mission, veuillez répondre à la mission avec une ligne vide.

Trois fichiers d’exemples sont fournis (run.sh, solution.py et solution.java). Ceux-ci offrent un exemple très simple pour répondre à une requête de type Ping en Python et Java. Libre à vous de vous en inspirer pour développer votre solution dans un autre langage!

Note

  • Les données textes sont encodées en ASCII.

  • Vous pouvez écrire des messages dans stderr afin de les voir affichés dans la sortie de l’outil de test.

  • Il est possible que les sorties de votre programme soient mises en tampon. Assurez-vous d’appeler "flush" sur la sortie standard après l'envoi de chaque message. Vous pouvez aussi désactiver la mise en tampons de stdout (setbuf(stdout, NULL); en C/C++).

Missions

Mission 1 - Ping (2 Pts)

La mission est simplement de renvoyer une réponse avec la chaîne de caractère donnée en paramètre.

Exemple

# Paramètre de Requête Réponse
1 ping ping
2 foobar foobar

Mission 2 - Palindrome (3 Pts)

La mission est d’envoyer true si la chaîne donnée en paramètre est un palindrome ou false dans le cas contraire.

Exemple

# Paramètre de Requête Réponse
1 foobar false
2 barrab true
3 xyzazyx true

Mission 3 - Trie (3 Pts)

La mission est de trier en ordre croissant la liste de nombres séparés par des virgules.

Exemple

# Paramètre de Requête Réponse
1 6,5,4,3,2,1 1,2,3,4,5,6
2 6345, 234, 945 234,945,6345

Mission 4 - Compter (3 Pts)

La mission est de compter le nombre d’éléments distincts passés en paramètre séparé par des espaces. La réponse doit être sous la forme <Élément>;<Nombre> avec chaque élément séparé par des espaces, en ordre alphabétique.

Exemple

# Paramètre de Requête Réponse
1 c b a a;1 b;1 c;1
2 aa a aa aa bb a;1 aa;3 bb;1

Mission 5 - Recherche de texte (4 Pts)

La mission est d’envoyer le nombre d’instances d’une chaîne de caractères X dans le texte Y. Les deux paramètres sont séparés par un point virgule (;): <X>;<Y>

Exemple

# Paramètre de Requête Réponse
1 a;aabbccdda 3
2 aba;foobababa 2
3 foo;aabbcc 0

Mission 6 - Mathématique (4 Pts)

La mission contient une expression mathématique et vous devez renvoyer la réponse sous forme d’un nombre décimal avec une précision arrondie de deux chiffres après la virgule.

Opérations supportées: (),-,+,*,/,^,sin,cos,tan et e.

Exemple

# Paramètre de Requête Réponse
1 1+4*(3-5)/7 -0.14
2 2^4 16
3 cos(1)+e 3.26

Mission 7 - Mathématique II (10 Pts)

Tout comme la mission 6, cette mission consiste à résoudre une expression mathématique. Par contre, cette mission inverse l’ordre de priorité des opérations. Ainsi, les additions et soustractions doivent être effectuées avant les multiplications et divisions.

Opérations supportées: -,+,* et /.

Exemple

# Paramètre de Requête Réponse
1 3+4*2 14
2 12/4-2 6

Mission 8 - Parsing (8 Pts)

La mission est de retrouver une valeur précise dans un arbre de propriété N-aire sous un format maison. Le premier paramètre est le chemin à parcourir de la feuille à trouver. Le chemin est représenté sous forme de clés séparé par des points (.). Un point virgule (;) sépare le chemin des données de l’arbre. Les données de l’arbre sont représentées sous forme de liste de valeurs entre parenthèses séparées par des virgules. Le premier élément de la liste est la clé du noeud et le reste est ses enfants. Si un noeud a un seul enfant, celui-ci est considéré comme une feuille de l’arbre. Par exemple, l’élément (a, 1) représente le noeud a avec la valeur 1. Dans le cas où le chemin ne se rend pas à une feuille de l’arbre, la réponse doit être -1.

Le format de l’arbre est défini par la grammaire suivante:

Arbre := ( Noeud )
Noeud := ( Elements )
Elements: Clé, Liste | Clé, Feuille
Liste := Noeud | Noeud, Liste
Clé := [a-zA-Z0-9]
Feuille := [a-zA-Z0-9]

Exemple

# Paramètre de Requête Réponse
1
a.b;(a, (a, 1), (b, 42), (c, 13))
Représente l’arbre:
   |
   a
  /|\
 a b c
 | |  \
 1 42 13
42
2 a.b.c;(a, (b,1), (c,2)) -1
2 a.b;(a, (b, (c,2))) -1
3
foo.bar;(foo, (bar, 7),(biz, (a, 1), (b, 2)))
Représente l’arbre:
    / \
 foo   biz
  |     | \
 bar    a b
  |     | |
  7     1 2
7

Mission 9 - ASCII Art (10 Pts)

Cette mission consiste à traduire sous forme texte un nombre représenté sous forme de dessin ASCII. Les glyphes utilisés sont prédéfinis et alignés verticalement. Par contre, il est possible que des espaces soient insérés entre les lettres. Les sauts de ligne du dessin ASCII sont remplacés par des points-virgules (;). Les glyphes utilisés sont les suivants:

1 2 3 4 5
##
 #
 #
###
 ##
#  #
  #
####
###
  ##
####
###
# #
# #
###
  #
###
##
  #
###
6 7 8 9 0
 ##
#
###
###
###
 #
#
#
###
# #
###
###
###
###
  #
##
###
# #
# #
###

Exemple

# Paramètre de Requête Réponse
1
##   ##  ### ;
 #  #  #   ##;
 #    #  ####;
### #### ### ;
(Les sauts de ligne sont ajoutés pour la présentation seulement)
123
2
# #     ###;
# #      # ;
###     #  ;
  #     #  ;
(Les sauts de ligne sont ajoutés pour la présentation seulement)
47

Mission 10 - Mathematique III (10 Pts)

Cette mission est similaire à Mathematique I, par contre cette fois il vous est demandé de trouver la valeur de x dans une expression d’égalité algébrique. La réponse doit être sous forme d’un nombre décimal avec une précision arrondie de deux chiffres après la virgule.

Opérations supportées: -,+,*,/ et ^.

Exemple

# Paramètre de Requête Réponse
1 x=10+1 11
2 1 + x * 1000 = 126 - 2 0.12
3 2 ^ x = 8 3

Mission 11 - Labyrinthe (10 Pts)

La mission est de trouver un chemin pour compléter le labyrinthe reçu en paramètre. Des points additionnels sont donnés si la solution donnée est le chemin le plus rapide. Le labyrinthe est représenté sous la forme:

###e#;
#...#;
#s###

e est le départ, s la sortie, # un mur, un passage libre et ; le délimiteur de ligne. Les sauts de ligne sont ajoutés pour la présentation seulement.

La réponse est envoyée sous le format de caractère séparé par des espaces indiquant les directions à prendre à partir du début avec U, pour haut, R pour droite, D pour bas et L pour gauche.

Exemple

# Paramètre de Requête Réponse
1
###e#;
# # #;
#   #;
#s###
(Les sauts de ligne sont ajoutés pour la présentation seulement)
D D L L D

Mission 12 - Labyrinthe II (13 Pts)

Cette mission est similaire à la mission 11 - Labyrinthe. Par contre, le format du labyrinthe envoyé en paramètre est isométrique. Les directions possibles sont UR pour la diagonale haut-droite, DR pour la diagonale bas-droite, DL pour la diagonale bas-gauche et UL pour la diagonale haut-droite.

Exemple

# Paramètre de Requête Réponse
1
/\           ;
\e\  /\      ;
 \ \ \s\     ;
  \ \ \ \/\  ;
  / / / /\ \ ;
  \ \/  \/ / ;
   \  /\  /  ;
    \/  \/   ;
(Les sauts de ligne sont ajoutés pour la présentation seulement) Ce labyrinthe peut être visualisé de la façon suivante:
 ###
 #e#
 # #
## ###
#  #s#
# ## #
#    ##
### # #
  #   #
  #####
DR DR DR DL DR DR UR UR UR UL UL

Remise

Votre soumission doit être envoyée via une archive compressée avec votre nom comme nom de fichier à dci+qualif16@aeets.com.

L’archive doit contenir:

  • Les sources de votre programme.

  • Votre programme compilé s’il y a lieu.

  • Le fichier run.sh qui exécute votre programme.

La correction sera effectuée en exécutant la commande ./runner ./run.sh -t correction.json.

Pointage

Tâche Critère Point
Mission 1 - Ping Exactitude des réponses 2
Mission 2 - Palindrôme Exactitude des réponses 3
Mission 3 - Trie Exactitude des réponses 3
Mission 4 - Compter Exactitude des réponses 3
Mission 5 - Recherche de texte Exactitude des réponses 4
Mission 6 - Mathématique Exactitude des réponses 4
Mission 7 - Mathématique II Exactitude des réponses 10
Mission 8 - Parsing Exactitude des réponses 8
Mission 9 - ASCII Art Exactitude des réponses 10
Mission 10 - Mathématique III Exactitude des réponses 10
Mission 11 - Labyrinthe Exactitude des réponses 6
Chemins optimaux 4
Mission 12 - Labyrinthe II Exactitude des réponses 10
Chemins optimaux 3
Total 80