Aller au contenu

Q2 - Comparer des chaines⚓︎

Le problème

Comparer des chaines

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]
  1. L'auteur de ce code fait du Python2 à la fin, pas du Python3 ; ce n'est probablement pas un élève en NSI !!!
  2. L'esprit du problème est de ne pas utiliser les outils builtin comme < (sur les chaines) ou .sort()...
  3. On attend une fonction avec doctest.
  4. mot_1 est plus clair que mot1.

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 type str et ne possède pas de méthode .append.
  • Erreur si un mot est un préfixe de l'autre. pro et produit 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 de pro 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...