TD2-Structures

L'objectif principal du TD est l'utilisation des structures de données pour résoudre certains problèmes intéressants.

Vous êtes invités à travailler en groupe ou individuellement. N'oubliez pas de vous amuser !

Enquêter sur les structures de données

Listes

Tapez les lignes suivantes sur votre interpréteur interactif Python et voyez si elles correspondent à ce que vous attendez :

s = [0] * 3
print(s)
s[0] += 1
print(s)

s = [''] * 3
print(s)
s[0] += 'a'
print(s)

s = [[]] * 3
print(s)
s[0] += [1]
print(s)

Pourquoi cela se produit-il ? Envisagez d'utiliser la fonction "id" pour approfondir l'enquête. Que se passe-t-il lorsque nous remplaçons l'avant-dernière ligne par s[0] = s[0] + [1]? Et si nous remplaçons la ligne par s[0].append(1)?

Tuples

Écrivez une fonction pour calculer le plus grand commun diviseur PGCD de deux entiers positifs. Vous pouvez librement utiliser le fait que gcd(a, b) est mathématiquement égal à gcd(b, a % b), et que gcd(a, 0) == a.

def pgcd(a, b) :
    pass # Votre mise en œuvre ici
    
pgcd(10, 25) # => 5
pgcd(14, 15) # => 1
pgcd(3, 9) # => 3
pgcd(1, 1) # => 1

Il est possible d'accomplir cela en trois lignes de code Python (moins si vous êtes vraiment intelligent). Pensez à exploiter l'emballage et le déballage des tuples (tuple-packing, unpacking)!

Dictionnaires

En classe, nous avons vu une mise en œuvre (naïve) d'une compréhension de dictionnaire qui échange les clés et les valeurs dans un dictionnaire :

{value: key for key, value in dictionary.items()}

Cependant, cette approche échouera lorsqu'il y aura deux clés dans le dictionnaire ayant la même valeur.

Rédigez une fonction qui inverse correctement les clés et les valeurs d'un dictionnaire - chaque clé (à l'origine une valeur) doit correspondre à un ensemble de valeurs (à l'origine des clés) qui lui correspondent. Par exemple,

flip_dict({"CA": "US", "NY": "US", "ON": "CA"})
# => {"US": ["CA", "NY"], "CA": ["ON"]}

Note : il existe une structure de données dans le module collections de la bibliothèque standard appelée defaultdict qui fournit exactement ce type de fonctionnalité. Vous lui fournissez une méthode pour créer des valeurs par défaut dans le dictionnaire (dans ce cas, une liste.) Vous pouvez en savoir plus sur defaultdict et d'autres structures de données collections ici.

Compréhensions

Prévoyez le résultat de chacune des compréhensions de la liste suivante. Après avoir écrit votre hypothèse, lancez le code dans un interpréteur interactif pour voir si vous avez été correct. Si vous étiez incorrect, discutez avec des camarades des raisons pour lesquelles Python renvoie ce qu'il fait.

[x for x in [1, 2, 3, 4]]
[n - 2 for n in range(10)]
[k % 10 for k in range(41) if k % 3 == 0]
[s.lower() for s in ['PythOn', 'iS', 'cOoL'] if s[0] < s[-1]]

# Quelques choses bizarre ici. Pouvez vous trouver? 
arr = [[3,2,1], ['a','b','c'], [('do',), ['re'], 'mi']]
print([el.append(el[0] * 4) for el in arr])  # Que affiche t-il?
print(arr)  # Quel est le contenu de `arr`?

[letter for letter in "pYthON" if letter.isupper()]
{len(w) for w in ["its", "the", "remix", "to", "ignition"]}

Rédiger une compréhension pour transformer la structure de données d'entrée en structure de données de sortie

[0, 1, 2, 3] -> [1, 3, 5, 7]  # 2n + 1
['apple', 'orange', 'pear'] -> ['A', 'O', 'P']  # Mettre en majuscule la première lettre
['apple', 'orange', 'pear'] -> ['apple', 'pear']  # Mots contiennent 'p'

["TA_sam", "student_poohbear", "TA_guido", "student_htiek"] -> ["sam", "guido"]
['apple', 'orange', 'pear'] -> [('apple', 5), ('orange', 6), ('pear', 4)]

['apple', 'orange', 'pear'] -> {'apple': 5, 'orange': 6, 'pear': 4}

Le triangle de Pascal

Écrivez une fonction qui génère le niveau suivant du triangle de Pascal à partir d'une liste qui représente une ligne valide du triangle de Pascal.

generate_pascal_row([1, 2, 1]) -> [1, 3, 3, 1]
generate_pascal_row([1, 4, 6, 4, 1]) -> [1, 5, 10, 10, 5, 1]
generate_pascal_row([]) -> [1]

Pour rappel, chaque élément d'une rangée du triangle de Pascal est formé en additionnant les deux éléments de la rangée précédente directement au-dessus (à gauche et à droite) de ces éléments. S'il n'y a qu'un seul élément directement au-dessus, nous n'ajoutons que celui-ci. Par exemple, les 5 premières rangées du triangle de Pascal ressemblent à

Vous trouverez peut-être utile la fonction zip brièvement abordée en cours, ainsi qu'un peu d'intelligence. Vous pouvez également résoudre ce problème en utilisant la fonction enumerate. Evitez d'utiliser une boucle de la forme for i in len(range(row)):.

*Indice : Regardez le diagramme ci-dessous. Comment pourriez-vous utiliser cette idée pour aider à résoudre ce problème ?

  0 1 3 3 1
+ 1 3 3 1 0
-----------
  1 4 6 4 1

Mots triades

Les mots triades sont des mots anglais pour lesquels les deux plus petites chaînes de caractères que vous obtenez en extrayant des lettres alternées forment toutes deux des mots valables.

Écrivez une fonction pour déterminer si une phrase entière passée dans une fonction est composée de mots triades. Vous pouvez supposer que tous les mots sont constitués uniquement de caractères alphabétiques et sont séparés par des espaces. Nous considérerons que la chaîne vide est un mot anglais non valide.

is_triad_phrase("learned theorem") # => True
is_triad_phrase("studied theories") # => False
is_triad_phrase("wooded agrarians") # => True
is_triad_phrase("forrested farmers") # => False
is_triad_phrase("schooled oriole") # => True
is_triad_phrase("educated small bird") # => False
is_triad_phrase("a") # => False
is_triad_phrase("") # => False

Quelle serait une structure de données appropriée pour stocker les mots anglais ?

Trouver les mots triades dans le fichier /usr/share/dict/words (un fichier texte de 2,5M contenant plus de 200 mille mots anglais). Voous pouvez également télécharger le fichier ici. En guise de vérification, nous avons trouvé 2770 mots triades distincts (insensibles à la casse).

Mots surpassés (défi)

Les mots surpassés sont des mots anglais pour lesquels l'écart entre chaque paire de lettres adjacentes augmente strictement. Ces écarts sont calculés sans "enroulement" de Z à A.

Écrivez une fonction pour déterminer si une phrase entière passée dans une fonction est faite de mots surpassés. Vous pouvez supposer que tous les mots sont constitués uniquement de caractères alphabétiques et sont séparés par des espaces. Nous considérerons que la chaîne vide et une chaîne de 1 caractère sont des phrases de dépassement valables.

is_surpassing_phrase("superb subway") # => True
is_surpassing_phrase("excellent train") # => False
is_surpassing_phrase("porky hogs") # => True
is_surpassing_phrase("plump pigs") # => False
is_surpassing_phrase("turnip fields") # => True
is_surpassing_phrase("root vegetable lands") # => False
is_surpassing_phrase("a") # => True
is_surpassing_phrase("") # => True

Vous pouvez trouver les fonctions Python ord (chaîne d'un caractère à l'entier correspondant) et chr (un entier à la chaîne d'un caractère correspondante) utiles pour résoudre ce puzzle.

ord('a') # => 97
chr(97) # => 'a'

Trouver les mots surpassés dans le fichier /usr/share/dict/words. Nous avons trouvé 1931 mots surpassés distincts.

Mots cyclones (défi)

Les mots cyclones sont des mots anglais qui ont une séquence de caractères dans l'ordre alphabétique lorsqu'ils suivent un schéma cyclique.

Écrivez une fonction qui, pour déterminer si une phrase entière est faite de mots cyclones. Vous pouvez supposer que tous les mots sont constitués uniquement de caractères alphabétiques et sont séparés par des espaces.

is_cyclone_phrase("adjourned") # => True
is_cyclone_phrase("settled") # => False
is_cyclone_phrase("all alone at noon") # => True
is_cyclone_phrase("by myself at twelve pm") # => False
is_cyclone_phrase("acb") # => True
is_cyclone_phrase("") # => True

Trouver les mots cyclones dans le fichier /usr/share/dict/words. Nous avons trouvé 769 mots cyclones distincts.

Numéros de triangles

Le n-ième terme de la séquence des nombres du triangle est donné par 1 + 2 + ... + n = n(n+1)/2. Par exemple, les dix premiers nombres du triangle sont : 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

En convertissant chaque lettre d'un mot en un nombre correspondant à sa position alphabétique (A=1, B=2, etc) et en ajoutant ces valeurs, nous formons une valeur de mot. Par exemple, la valeur du mot SKY est "19 + 11 + 25 = 55" et 55 est un nombre triangulaire. Si la valeur du mot est un nombre triangulaire, alors nous appellerons le mot triangulaire.

Trouver les mots triangulaires dans le fichier /usr/share/dict/words. Nous avons trouvé 16303 mots triangulaires distincts.

Indice : vous pouvez utiliser ord(ch) pour obtenir la valeur ASCII entière d'un caractère

Autres puzzles (défi)

Déjà terminé ?

Lire Python's Style Guide, en gardant le Zen de Python à l'esprit. N'hésitez pas à sauter les parties du guide de style qui couvrent des sujets que nous n'avons pas encore abordés dans ce cours, mais il est toujours bien de commencer par un aperçu du bon style.

TD 2 : Structures de données