Geipi Polytech — NSI 2025

Présentation de l'épreuve

Cette épreuve de Numérique et Sciences Informatiques fait partie du concours Geipi Polytech, édition 2025. Elle est constituée d'un seul grand exercice, portant sur la modélisation d'un plateau de jeu (carré ou hexagonal), le calcul de distances sur une grille, et le partage d'informations entre joueurs via une base de données relationnelle.

Exercice unique — Exploration d'un plateau à la recherche d'un objectif

Un club de robotique lycéen organise un défi entre robots programmés par ses membres. Le plateau de jeu peut être soit un grand carré composé de cases carrées, soit un grand hexagone composé de cases hexagonales régulières. Certaines cases contiennent un mur, une case contient l'objectif à atteindre, les autres cases sont vides ; la case centrale du plateau est toujours vide. Le robot part du centre, et son objectif est d'atteindre la case-objectif en minimisant son nombre de déplacements. Deux cases sont dites adjacentes si elles ont un côté en commun ; à chaque coup, le robot se déplace sur une case adjacente à sa position (jamais plus loin), et ne connaît le contenu d'une case que s'il est déjà passé sur l'une de ses cases adjacentes.

La forme du plateau est représentée par un dictionnaire à une seule clé, 'carre' ou 'hexagone', dont la valeur est la longueur d'un côté du plateau.

Remarque 1. La distance entre les centres de deux cases adjacentes vaut toujours 1, et la longueur d'un côté du plateau est la distance entre les centres des cases situées à ses deux extrémités ; un côté de longueur $\ell$ comporte donc $\ell + 1$ cases.

Remarque 2. La longueur d'un côté d'un plateau carré doit être paire ; si elle est impaire, les fonctions se comportent comme si on lui retirait une unité.

Les coordonnées d'une case sont un couple d'entiers (colonne, ligne), repérant le centre de la case.

Remarque 3. Sur un plateau hexagonal, les coordonnées d'une case sont soit deux entiers pairs, soit deux entiers impairs ; un couple formé d'un entier pair et d'un entier impair ne correspond à aucune case.

Remarque 4. Sur un plateau hexagonal, les six cases adjacentes à la case (colonne, ligne) sont celles de coordonnées (colonne, ligne+2), (colonne, ligne-2), (colonne+1, ligne+1), (colonne+1, ligne-1), (colonne-1, ligne+1) et (colonne-1, ligne-1). Sur un plateau carré, les quatre cases adjacentes à (colonne, ligne) sont celles de coordonnées (colonne±1, ligne) et (colonne, ligne±1).

Un plateau est représenté par un dictionnaire dont les clés sont les coordonnées des cases, et les valeurs 'mur', 'objectif' ou 'vide'. La case (0, 0) est toujours 'vide', et la valeur 'objectif' n'est associée qu'à une seule clé.

1. La fonction dmin(forme, col, ligne) renvoie le nombre minimal de déplacements nécessaires pour atteindre la case (col, ligne) depuis le centre (0, 0), en l'absence de tout mur ; elle renvoie inf si la forme est inconnue ou si les coordonnées ne correspondent à aucune case du plateau. Donner la valeur renvoyée par chacun des appels suivants :

(a) dmin({'carre': 6}, 3, 2) (b) dmin({'carre': 6}, -1, 3) (c) dmin({'carre': 4}, 3, 2) (d) dmin({'hexagone': 3}, -3, 3) (e) dmin({'hexagone': 2}, 1, 3) (f) dmin({'hexagone': 4}, 2, 7)

2. Compléter la définition de dmin. Il est interdit d'utiliser math.sqrt ou d'ajouter une structure de contrôle supplémentaire (if/while) ; les fonctions abs, max et min sont autorisées.

from math import inf
 
def dmin(forme, col, ligne):
    if ① in forme.keys():
        n = forme[①] // 2
        if max(abs(col), abs(ligne)) <= n:
            return abs(col) + abs(ligne)
    if ② in forme.keys():
        n = forme[②]
        if (③ <= n) and (④ <= 2 * n) and (col % 2 == ⑤):
            return abs(col) + max(0, (⑥) // 2)
    return ⑦

3. Les fonctions num_colonne(forme) et num_ligne(forme) renvoient chacune un couple d'entiers donnant les bornes (min, max) des numéros de colonne, respectivement de ligne, valables sur le plateau ; elles renvoient (0, 0) si la forme est inconnue. Compléter leur définition (voir remarque 2).

def num_colonne(forme):
    n = 0
    if 'carre' in forme.keys():
        n = ①
    if 'hexagone' in forme.keys():
        n = ②
    return (-n, n)
 
def num_ligne(forme):
    n = 0
    if 'carre' in forme.keys():
        n = ③
    if 'hexagone' in forme.keys():
        n = ④
    return (-n, n)

4. La fonction creer_plateau(forme) renvoie un plateau dont toutes les cases valides sont 'vide' (un dictionnaire vide si la forme est inconnue). Compléter sa définition, en utilisant num_colonne, num_ligne et dmin.

def creer_plateau(forme):
    (cmin, cmax) = num_colonne(forme)
    (rmin, rmax) = num_ligne(forme)
    plateau = {}
    for c in range(cmin, cmax + 1):
        for r in range(rmin, rmax + 1):
            if ① in forme.keys():
                plateau[c, r] = 'vide'
            if ② in forme.keys():
                if dmin(forme, c, r) ③ forme[②]:
                    plateau[c, r] = 'vide'
    return plateau

5. La fonction deplacements(forme, plateau, col, ligne) renvoie la liste des coordonnées des cases adjacentes à (col, ligne) sur lesquelles le robot peut se déplacer (celles qui existent sur le plateau et ne contiennent pas de mur) ; elle renvoie une liste vide si (col, ligne) n'est pas une case valide. Compléter sa définition (voir remarque 4).

def deplacements(forme, plateau, col, ligne):
    if (col, ligne) not in plateau.keys():
        return []
    if plateau[col, ligne] == 'mur':
        return []
    if 'carre' in forme.keys():
        mvt = ①
    if 'hexagone' in forme.keys():
        mvt = ②
    adj = []
    for (x, y) in mvt:
        if (col + x, ligne + y) in plateau.keys():
            if plateau[col + x, ligne + y] != 'mur':
                adj.append((③, ④))
    return adj

6. Un robot programmé pour toujours se diriger vers la case adjacente la plus proche de l'objectif (au sens de dmin) peut, dans certaines configurations de murs, perdre beaucoup de temps par rapport à une stratégie plus prudente. Expliquer, en une ou deux phrases, pourquoi une telle stratégie purement gloutonne peut être sous-optimale, et donner un exemple de situation où c'est le cas.

Pour rendre le défi plus intéressant, les robots d'une même équipe ne communiquent pas directement entre eux, mais mettent en commun, via une base de données relationnelle partagée, les informations découvertes au fil de l'exploration. Seules les cases dont le contenu est connu (donc différent de 'inconnu') sont stockées. Le schéma relationnel comporte deux relations :

• cases(id_case, colonne, ligne, contenu)
• adjacence(#id_case_1, #id_case_2)

Les attributs colonne, ligne, id_case, id_case_1 et id_case_2 sont des entiers, contenu est une chaîne de caractères ; les clés primaires sont soulignées, et adjacence.id_case_1 comme adjacence.id_case_2 référencent cases.id_case.

7. (a) Le tuple (4, 9) apparaît dans la relation adjacence. Peut-on affirmer qu'il existe forcément un tuple où id_case vaut 4 dans la relation cases ?

(b) Le tuple (15, 2, 2, 'vide') apparaît dans la relation cases. Peut-on affirmer qu'il existe forcément un tuple où id_case_1 vaut 15 dans la relation adjacence ?

8. Compléter la requête SQL ci-dessous, dont le résultat donne les coordonnées (colonne, ligne) de toutes les cases connues qui sont adjacentes à un mur (une case ne doit apparaître qu'une seule fois dans le résultat, même si elle est adjacente à plusieurs murs).

SELECT ① x.colonne, x.ligne
FROM cases x, cases y, adjacence
WHERE y.contenu = 'mur'
  AND ( (adjacence.id_case_1 = x.id_case ② adjacence.id_case_2 = y.id_case)
        ③ (adjacence.id_case_1 = y.id_case ② adjacence.id_case_2 = x.id_case) );