TD J3 : numpy / listes et jeu de labyrinthe (correction)

Dans cet exercice on considère un jeu de labyrinthe, dont le plateau sera modélisé par un tableau à deux dimensions avec 10 colonnes et 6 lignes. Les cases du labyrinthe peuvent être de trois types~:

• les cases vides, notées V ;
• les murs, notés M ;
• les cases spéciales, notées D pour la case de départ et A pour la case d'arrivée.

Partie 1 : initialisation du plateau

L'objectif de cette partie est d'initialiser le plateau de jeu avec une configuration simple. On va procéder étape par étape pour obtenir le plateau représenté en étape 4:

Q1. Dans la cellule ci-dessous on a placé une commande qui crée un tableau numpy nommé plateau. Celui-ci est vide, de la taille demandée (10x6) et dont toutes les cases seront des chaînes de caractères. Compléter progressivement cette cellule par les commandes (à base de slices) qui permettent d'obtenir la plateau de la configuration de l'étape 4.

import numpy as np

plateau = np.empty((6,10), dtype=str) # tableau 6x10 de type str

# Étape 1
plateau[:] = 'M'

# Étape 2
plateau[1,0]='D'
plateau[-2,-1]='A'

# Étape 3
plateau[1:-1,1:-1]='V'

# Étape 4
plateau[2,1:6]='M'
plateau[1:4,7]='M'

print(plateau)

[['M' 'M' 'M' 'M' 'M' 'M' 'M' 'M' 'M' 'M']
 ['D' 'V' 'V' 'V' 'V' 'V' 'V' 'M' 'V' 'M']
 ['M' 'M' 'M' 'M' 'M' 'M' 'V' 'M' 'V' 'M']
 ['M' 'V' 'V' 'V' 'V' 'V' 'V' 'M' 'V' 'M']
 ['M' 'V' 'V' 'V' 'V' 'V' 'V' 'V' 'V' 'A']
 ['M' 'M' 'M' 'M' 'M' 'M' 'M' 'M' 'M' 'M']]

Partie 2 : compression

Dans cette partie on souhaite maintenant compresser le stockage de notre plateau. Dans l'état actuel, si chaque case est représentée par un octet (8 bits) il nécessite $10*6=60$ octets.

Afin de diminuer cette taille, on souhaite stocker tout le tableau dans une liste python construite de la façon suivante:

• Les deux premiers éléments sont le nombre de lignes, et de colonne du tableau (cette information est nécessaire pour reconstituer le tableau à partir de la liste),
• ensuite, les données se lisent par deux. La première est la valeur de la case (ici M, V, A ou D), et la deuxième le nombre de cases consécutives contenant cette valeur. Avec l'exemple précédent cela donnerait un liste qui commence ainsi:

lst_finale = [5,10,'M',10,'D',1,'V',8,'M',2,...]

On transforme le tableau 2D en liste 1D

Q2. Compléter la fonction D2toD1(tab) -> list qui reçoit un tableau numpy qui représente le plateau de jeu et qui renvoie une liste python obtenue en concaténant toutes les lignes du tableau. Par exemple, avec le plateau de cet exercice le début de la liste obtenue doit être :

$$ \big[\underbrace{'M','M',...,'M'}_{10\,M},\ 'D',\underbrace{'V','V',...,'V'}_{6\,V},'M',...\big] $$

def D2toD1(tab : np.array)-> list:
    n_lig, n_col = np.shape(tab)
    lst = []
    
    for l in range(n_lig):
        for c in range(n_col):
            lst.append(tab[l,c])
            
    # ou bien directement : lst = list(np.reashpe(tab,n_lig*n_col))

    return lst

print(D2toD1(plateau))

['M', 'M', 'M', 'M', 'M', 'M', 'M', 'M', 'M', 'M', 'D', 'V', 'V', 'V', 'V', 'V', 'V', 'M', 'V', 'M', 'M', 'M', 'M', 'M', 'M', 'M', 'V', 'M', 'V', 'M', 'M', 'V', 'V', 'V', 'V', 'V', 'V', 'M', 'V', 'M', 'M', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'V', 'A', 'M', 'M', 'M', 'M', 'M', 'M', 'M', 'M', 'M', 'M']

On comprime la liste 1D en deux listes 1D

Q3. La fonction compress(lst : list) -> (list,list) reçoit une liste telle que celle obtenu en question précédente, et renvoie deux listes. La première contient les valeurs et l'autre les effectifs correspondants. Par exemple avec la liste précédente on devrait obtenir deux listes qui commencent par:

values = ['M','D','V',...] et counts = [10,1,8,...]

On donne ci-dessous le code partiel de cette fonction. À vous de compléter les zones 1 à 4 manquantes:

def compress(lst : list) -> (list,list):
    car = lst.pop(0)
    values = [car]
    counts = [1]
    while len(lst)>0 :
        car = lst.pop(0)
        if car == values[-1]:
            counts[-1] += 1
        else:
            values.append(car)
            counts.append(1)
    return values, counts

V,C = compress(D2toD1(plateau))
print(V)
print(C)

['M', 'D', 'V', 'M', 'V', 'M', 'V', 'M', 'V', 'M', 'V', 'M', 'V', 'M', 'V', 'A', 'M']
[10, 1, 6, 1, 1, 7, 1, 1, 1, 2, 6, 1, 1, 2, 8, 1, 10]

On assemble les deux listes pour finaliser

Q4. Écrire alors une fonction comp_final(tableau : np.array) -> list qui reçoit un tableau numpy représentant un plateau de jeu et qui renvoie une liste telle que demandée dans l'énoncé.

def comp_final(tableau : np.array)->list :
    l,c = np.shape(tableau)
    final = [l,c]
    val, count = compress(D2toD1(tableau))
    for i in range(len(val)):
        final.append(val[i])
        final.append(count[i])
    return final

print(comp_final(plateau))

[6, 10, 'M', 10, 'D', 1, 'V', 6, 'M', 1, 'V', 1, 'M', 7, 'V', 1, 'M', 1, 'V', 1, 'M', 2, 'V', 6, 'M', 1, 'V', 1, 'M', 2, 'V', 8, 'A', 1, 'M', 10]

Q5. Déterminer la liste finale obtenue dans l'exemple de l'exercice, donner son nombre d'éléments et voir si on a bien diminué la taille...

print(f"Il faut {len(comp_final(plateau))} octets pour stocker notre plateau")

Il faut 36 octets pour stocker notre plateau

Remarque : on n'a pas gagné beaucoup, mais selon les configurations le gain pourrait être bien meilleur...

Partie 3 : décompression

Q6. Écrire pour finir une fonction  decompression(lst : list)-> np.array qui reçoit une liste issue de la compression d'un tableau telle celle obtenue à la questyion précédente, et qui renvoie le tableau numpy initial associé.

def decompress(lst : list) -> np.array :
    n_lig = lst[0]
    n_col = lst[1]
    tab = np.empty((n_lig,n_col), dtype=str)
    l, c = 0,0
    for i in range(2,len(lst),2):
        val = lst[i]
        count = lst[i+1]
        for j in range(count):
            tab[l,c]=val
            c += 1
            if c==n_col :
                c = 0
                l += 1
    return tab

print(decompress(comp_final(plateau)))

[['M' 'M' 'M' 'M' 'M' 'M' 'M' 'M' 'M' 'M']
 ['D' 'V' 'V' 'V' 'V' 'V' 'V' 'M' 'V' 'M']
 ['M' 'M' 'M' 'M' 'M' 'M' 'V' 'M' 'V' 'M']
 ['M' 'V' 'V' 'V' 'V' 'V' 'V' 'M' 'V' 'M']
 ['M' 'V' 'V' 'V' 'V' 'V' 'V' 'V' 'V' 'A']
 ['M' 'M' 'M' 'M' 'M' 'M' 'M' 'M' 'M' 'M']]

On a bien retrouvé le plateau inital...