Q2 - Comparer des chaines⚓︎
Le problème
Proposition 1⚓︎
🐍 Script Python
def comparaison_alphabétique(nb_caractère1: int, chaine1: str, nb_caractère2: int, chaine2: str) -> str:
"""Cette fonction prend en paramètre deux chaines de caractères composées uniquement de lettre minuscules
et sans accents ainsi que le nombre de caractère, et renvoie la première selon l'odre lexicographique.
>>> 8
prologin
5
prolo
prolo
"""
nb_caractère_min = 0
if nb_caractère1 < nb_caractère2:
nb_caractère_min = nb_caractère1
else:
nb_caractère_min = nb_caractère2
for x in range(nb_caractère_min):
if x + 1 == nb_caractère_min:
if chaine1[x] < chaine2[x]:
return chaine1
else:
return chaine2
if chaine1[x] == chaine2[x]:
pass
else:
if chaine1[x] < chaine2[x]:
return chaine1
else:
return chaine2
# tests
import doctest
doctest.testmod()
# Entrée
nb_caractère1 = int(input())
chaine1 = input()
nb_caractère2 = int(input())
chaine2 = input()
# Sortie
print(comparaison_alphabétique(nb_caractère1, chaine1, nb_caractère2, chaine2))
- Ceci ne peut pas se produire !!!
🐍 Script Python
for x in range(nb_caractère_min):
if x + 1 == nb_caractère_min:
Proposition 2⚓︎
🐍 Script Python
import itertools
def comparaison_lexicographique(chaine1:str,chaine2:str) -> str:
""" Prend 2 chaines de caractères en minuscule et renvoie la plus petite selon l'ordre lexicographique
>>> comparaison_lexicographique('bonjour','hola')
'bonjour'
>>> comparaison_lexicographique('holaster','hola')
'hola'
"""
alphabet = ['a', 'b', 'c', 'd', 'e','f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o','p', 'q', 'r', 's', 't', 'u', 'v','w','x', 'y', 'z']
liste_chaine1 = list(chaine1)
liste_chaine2 = list(chaine2)
# On fait un tupple de chaque lettre de même rang dans chaque chaine et puis on l'insère dans une liste,ça permet d'éviter les problèmes de taille
liste_comparaison = list(zip(liste_chaine1,liste_chaine2))
# On compare chaque lettre en regardant leurs positionnement dans la liste alphabet et renvoie la chaine la plus petite
for lettre_chaine1,lettre_chaine2 in liste_comparaison:
# On prend le positionnement dans l'alphabet de chaque lettre à la même position dans les 2 chaines de caractères
positionnement_lettre_chaine1 = alphabet.index(lettre_chaine1)
positionnement_lettre_chaine2 = alphabet.index(lettre_chaine2)
# On cherche le plus petit selon l'odre léxicographique
if positionnement_lettre_chaine1 > positionnement_lettre_chaine2:
return chaine2
if positionnement_lettre_chaine1 < positionnement_lettre_chaine2:
return chaine1
# Si il y a les mêmes lettres sur le même intervalle on renvoie la chaine de caractère la plus courte
if len(liste_chaine1) > len(liste_chaine2):
return chaine2
else:
return chaine1
# tests
import doctest
doctest.testmod()
# Entrée
nb_caractères_chaine1 = int(input())
chaine1 = input()
nb_caractères_chaine2 = int(input())
chaine2 = input()
# Sortie
print(comparaison_lexicographique(chaine1,chaine2))
- C'est bien, il n'y a pas de triche.
- On peut faire bien plus simple. Voir corrigé.
Proposition 3⚓︎
🐍 Script Python
longueur_mot1 = int(input())
mot1 = input()
longueur_mot2 = int(input())
mot2 = input()
liste = [mot1, mot2]
liste.sort()
print liste[0]
- L'auteur de ce code fait du Python2 à la fin, pas du Python3 ; ce n'est probablement pas un élève en NSI !!!
- L'esprit du problème est de ne pas utiliser les outils builtin comme
<
(sur les chaines) ou.sort()
... - On attend une fonction avec doctest.
mot_1
est plus clair quemot1
.
Proposition 4⚓︎
🐍 Script Python
longueur_premier_mot = int(input())
premier_mot = input()
longueur_second_mot = int(input())
second_mot = input()
mot_final = None
for i in range(min(longueur_premier_mot, longueur_second_mot)):
lettre_1 = premier_mot[i]
lettre_2 = second_mot[i]
if ord(lettre_1) < ord(lettre_2):
mot_final = premier_mot
break
elif ord(lettre_2) < ord(lettre_1):
mot_final = second_mot
break
if mot_final is None:
mot_final = premier_mot if longueur_premier_mot < longueur_second_mot else second_mot
print(mot_final)
- Argh, un
break
; ce n'est pas interdit, mais on peut l'éviter avec une fonction, et obtenir un doctest au passage.
Proposition 5⚓︎
🐍 Script Python
def ordre(mot1, mot2):
""" Renvoie le premier mot selon l'ordre lexicographique.
>>> ordre('prologin', 'prolo')
'prolo'
"""
if mot1 < mot2:
return mot1
else:
return mot2
# Test
import doctest
doctest.testmod()
# Entrées
nb1 = int(input())
mot1 = input()
nb2 = int(input())
mot2= input()
if not (1< len(mot1) < 1000):
raise ValueError("Trop de lettres au premier mot")
if not (1< len(mot2) < 1000):
raise ValueError("Trop de lettres au deuxième mot")
# Sortie
print(ordre(mot1, mot2))
- L'utilisation de
<
directement sur les chaines était interdite ici... C'est tricher !
Proposition 6⚓︎
🐍 Script Python
liste_tryer = []
longueur_mots1 = int(input())
liste_tryer.append(input())
longueur_mots2 = int(input())
liste_tryer.append(input())
liste_tryer.sort()
print(liste_tryer[0])
"""
interdit
if premier_mots <= deuxieme_mots:
print(premier_mots)
else:
print(deuxieme_mots)
"""
- Utiliser
.sort()
c'est comme utiliser<=
; c'est interdit aussi ici 😉
Proposition 7⚓︎
🐍 Script Python
"""
Cette algorithme renvoie la première chaine de caractère selon l'ordre lexicographique (ordre du dictionnaire).
Exemple d'entrée: 8
prologin
5
prolo
Exemple de sortie: prolo
Exemple d'entrée: 4
toto
4
titi
Exemple de sortie: titi
"""
# tests
import doctest
doctest.testmod()
#Entrée
nb1_chaine_cara = int(input())
mot_1 = input()
nb2_chaine_cara = int(input())
mot_2 = input()
#Algorithme
Liste =[mot_1,mot_2]
Liste_triée = sorted(Liste)
#Sortie
print(Liste[0])
- L'utilisation de
sorted
était interdite.
Proposition 8⚓︎
🐍 Script Python
# 0- Coeur du programme
def comparaison(longueur_1: int, chaine_1: str, longueur_2: int, chaine_2:str) -> str:
""" Renvoie le premier mot entre chaine_1 et chaine_2 dans l'ordre lexicographique
>>> comparaison(8, "prologin", 5, "prolo")
'prolo'
>>> comparaison(4, "toto", 4, "titi")
'titi'
"""
alphabet = "abcdefghijklmnopqrstuvwxyz"
id_lettre = 0
while longueur_1 != id_lettre and longueur_2 != id_lettre: # On continue tant que les chaines ont encore des lettres .
if chaine_1[id_lettre] != chaine_2[id_lettre]: # Si, les 2 lettres des 2 chaines sont différentes alors,
for lettre in alphabet: # On peut déterminer le premier avec l'ordre de l'alphabet.
if chaine_1[id_lettre] == lettre:
return chaine_1
if chaine_2[id_lettre] == lettre:
return chaine_2
id_lettre += 1
if longueur_1 == id_lettre: # Les 2 chaines n'ont pas la même longueur
return chaine_1 # Donc,celui qui a arrêté la boucle est le premier et a une longueur égale à id_lettre
else:
return chaine_2
# 1- Tests
import doctest
doctest.testmod()
# 2- Lecture des entrées
longueur_1 = int(input())
chaine_1 = input()
longueur_2 = int(input())
chaine_2 = input()
# 3- Appel de la fonction / Sortie
print(comparaison(longueur_1, chaine_1, longueur_2, chaine_2))
- Pas de triche ici, c'est bien.
- On pouvait faire plus simple.
Proposition 9⚓︎
🐍 Script Python
def première_chaine(nb_caracteres_1 : int, chaine_1 : str, nb_caracteres_2 : int, chaine_2 : str,) -> str :
""" Renvoie la première chaine de caractère selon l'ordre lexicographique
entre 'chaine_1' et 'chaine_2'.
>>> nb_caracteres_1 = 8
>>> chaine_1 = prologin
>>> nb_caracteres_2 = 5
>>> chaine_2 = prolo
prolo
"""
longueur_max = max(len(chaine_1), len(chaine_2))
mot1, mot2 = list(chaine_1), list(chaine_2)
sortie = ''
for lettre in range (longueur_max) :
if mot1[lettre] > mot2[lettre] :
sortie.append(chaine_2)
break
if mot1[lettre] < mot2[lettre] :
sortie.append(chaine_1)
break
if mot1[lettre] == ' ' :
sortie.append(chaine_1)
break
if mot2[lettre] == ' ' :
sortie.append(chaine_2)
break
return sortie
# tests
import doctest
doctest.testmod()
# Entrée
nb_caracteres_1 = int(input())
chaine_1 = input()
nb_caracteres_2 = int(input())
chaine_2 = input()
# Sortie
print(première_chaine(nb_caracteres_1, chaine_2, nb_caracteres_2, chaine_2))
- Attention,
sortie
est de typestr
et ne possède pas de méthode.append
. - Erreur si un mot est un préfixe de l'autre.
pro
etproduit
donne 7 tours de boucle, qui ne sont pas arrêtés, au quatrième tour, une erreur se produit pour lire le quatrième caractère depro
qui n'existe pas.
Corrigé du professeur⚓︎
🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2003/qualification/cases_inaccessibles
"""
def plus_petite(chaine_1: str, chaine_2: str) -> str:
"""Renvoie la plus petite des deux chaines.
En suivant l'ordre lexicographique,
et sans utiliser la fonction de la bibliothèque interne.
>>> plus_petite("prologin", "prolo")
'prolo'
>>> plus_petite("toto", "titi")
'titi'
"""
taille_1 = len(chaine_1)
taille_2 = len(chaine_2)
taille_commune = min(taille_1, taille_2)
for i in range(taille_commune):
c_1 = chaine_1[i]
c_2 = chaine_2[i]
if c_1 < c_2:
return chaine_1
if c_2 < c_1:
return chaine_2
if taille_1 < taille_2:
return chaine_1
if taille_2 < taille_1:
return chaine_2
# ici on a
assert chaine_1 == chaine_2, f"Erreur curieuse"
return chaine_1
import doctest
doctest.testmod()
taille_1 = int(input())
chaine_1 = input()
taille_2 = int(input())
chaine_2 = input()
print(plus_petite(chaine_1, chaine_2))
- Traditionnellement
c
est souvent un identifiant pour un caractère d'une chaine. - Utiliser
sort
,sorted
ou<
sur les chaines était tricher, le sujet demandait de ne pas utiliser de fonction toute prête de la bibliothèque.
Il ne faut pas chercher à contourner un problème pour progresser, voire il faut savoir en imaginer...