E06 - Décryptage II⚓︎
Le problème
Solution⚓︎
🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2011/semifinal/decryptage2
"""
# 0. Cœur du problème
def est_inclus(extrait: str, texte: str) -> bool:
"""Renvoie True si tous les caractères de 'extrait' sont inclus
dans 'texte', avec multiplicité, mais sans compter l'ordre.
>>> est_inclus("ABAC", "BRAVO, CHARLIE.")
1
>>> est_inclus("ABBAC", "BRAVO, CHARLIE.")
0
"""
CONST_ASCII = 128
def compte(morceau: str) -> list[int]:
"""Renvoie la liste du compte des caractères.
>>> compte("ABAC")[ord('A')]
2
>>> compte("ABAC")[ord('D')]
0
"""
compte_morceau = [0 for _ in range(CONST_ASCII)]
for caractere in morceau:
i = ord(caractere)
compte_morceau[i] += 1
return compte_morceau
# version fonctionnelle
return all(cpt_extrait <= cpt_texte
for cpt_extrait, cpt_texte in
zip(compte(extrait), compte(texte)))
# version itérative
compte_extrait = compte(extrait)
compte_texte = compte(texte)
for i in range(CONST_ASCII):
if compte_extrait[i] > compte_texte[i]:
return False
return True
# 1. Lecture
taille_message_scooby_naire = int(input())
message_scooby_naire = input()
taille_message_test = int(input())
message_test = input()
# 2. Écriture
print('1' if est_inclus(message_test, message_scooby_naire) else '0')
Commentaires⚓︎
Il n'était pas précisé dans l'énoncé que les caractères étaient tous en ASCII, donc avec un code (que l'on obtient avec ord) compris entre \(0\) et \(127\) inclus.
Proposons une version avec un dictionnaire, qui est capable de fonctionner avec tous jeux de caractères.
Nous proposerons ensuite une version avec un type nouveau Counter qui a été pensé justement pour les dictionnaires qui servent à compter des éléments d'un ensemble.
Version itérative avec dict⚓︎
🐍 Script Python
# 0. Cœur du problème
def est_inclus(extrait: str, texte: str) -> bool:
"""Renvoie True si tous les caractères de 'extrait' sont inclus
dans 'texte', avec multiplicité, mais sans compter l'ordre.
>>> est_inclus("ABAC", "BRAVO, CHARLIE.")
1
>>> est_inclus("ABBAC", "BRAVO, CHARLIE.")
0
"""
def compte(morceau: str) -> dict:
"""Renvoie un `Counter` des caractères.
>>> compte("ABAC") == {'A': 2, 'B': 1, 'C': 1}
True
>>> compte("ABBAC") == {'A': 2, 'B': 2, 'C': 1}
True
"""
compte_morceau = dict()
for caractere in morceau:
if caractere not in compte_morceau:
compte_morceau[caractere] = 1
else:
compte_morceau[caractere] += 1
return compte_morceau
# version itérative
compte_extrait = compte(extrait)
compte_texte = compte(texte)
for caractere in compte_extrait:
if caractere not in compte_texte:
return False
else:
if compte_extrait[caractere] > compte_texte[caractere]:
return False
return True
On constate qu'il faut tester l'appartenance d'une clé au dictionnaire...
Version itérative avec Counter⚓︎
🐍 Script Python
from collections import Counter
# 0. Cœur du problème
def est_inclus(extrait: str, texte: str) -> bool:
"""Renvoie True si tous les caractères de 'extrait' sont inclus
dans 'texte', avec multiplicité, mais sans compter l'ordre.
>>> est_inclus("ABAC", "BRAVO, CHARLIE.")
1
>>> est_inclus("ABBAC", "BRAVO, CHARLIE.")
0
"""
def compte(morceau: str) -> Counter:
"""Renvoie un `Counter` des caractères.
>>> compte("ABAC") == {'A': 2, 'B': 1, 'C': 1}
True
>>> compte("ABBAC") == {'A': 2, 'B': 2, 'C': 1}
True
"""
compte_morceau = Counter()
for caractere in morceau:
compte_morceau[caractere] += 1
return compte_morceau
# version itérative
compte_extrait = compte(extrait)
compte_texte = compte(texte)
for caractere in compte_extrait:
if compte_extrait[caractere] > compte_texte[caractere]:
return False
return True
Ici inutile de tester l'appartenance ; la valeur \(0\) est renvoyée par défaut.
Version fonctionnelle avec Counter⚓︎
🐍 Script Python
#...
# version fonctionnelle
compte_extrait = compte(extrait)
compte_texte = compte(texte)
return all(compte_extrait[caractère] <= compte_texte[caractere]
for caractere in compte_extrait)
On constate qu'on peut facilement utiliser compte_texte[caractere] qui est par défaut à \(0\) si caractere n'est pas une clé de compte_texte. Chose que nous n'aurions pas pu faire avec un dictionnaire conventionnel.