Correction de Comparer des chaînes

Quelques propositions d'élèves, et à la fin un corrigé du professeur.

Propositions d'élèves
Corrigé du professeur

Propositions d'élèves

À la suite de chaque proposition de code, un commentaire de correction du professeur. Le cartouche demandé en introduction a été supprimé ici.

Proposition 1

def comparaison_alphabétique(nb_caractère1: int, chaîne1: str, nb_caractère2: int, chaîne2: str) -> str:
    """Cette fonction prend en paramètre deux chaînes 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 chaîne1[x] < chaîne2[x]:
                return chaîne1 
            else:
                return chaîne2
        if chaîne1[x] == chaîne2[x]:
            pass
        else:
            if chaîne1[x] < chaîne2[x]:
                return chaîne1 
            else:
                return chaîne2
   
# tests 
import doctest
doctest.testmod()

# Entrée
nb_caractère1 = int(input())
chaîne1 = input()
nb_caractère2 = int(input())
chaîne2 = input()
# Sortie
print(comparaison_alphabétique(nb_caractère1, chaîne1, nb_caractère2, chaîne2))

Ceci ne peut pas se produire !!!

   for x in range(nb_caractère_min):
        if x + 1 == nb_caractère_min:

Proposition 2

import itertools 
def comparaison_lexicographique(chaîne1:str,chaîne2:str) -> str:
    """ Prend 2 chaînes 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_chaîne1 = list(chaîne1)
    liste_chaîne2 = list(chaîne2)

    # On fait un tupple de chaque lettre de même rang dans chaque chaîne et puis on l'insère dans une liste,ça permet d'éviter les problèmes de taille
    liste_comparaison = list(zip(liste_chaîne1,liste_chaîne2))

    # On compare chaque lettre en regardant leurs positionnement dans la liste alphabet et renvoie la chaîne la plus petite
    for lettre_chaîne1,lettre_chaîne2 in liste_comparaison:
        # On prend le positionnement dans l'alphabet de chaque lettre à la même position dans les 2 chaînes de caractères
        positionnement_lettre_chaîne1 = alphabet.index(lettre_chaîne1)
        positionnement_lettre_chaîne2 = alphabet.index(lettre_chaîne2)

        # On cherche le plus petit selon l'odre léxicographique
        if positionnement_lettre_chaîne1 > positionnement_lettre_chaîne2:
            return chaîne2
        if positionnement_lettre_chaîne1 < positionnement_lettre_chaîne2:
            return chaîne1
    # Si il y a les mêmes lettres sur le même intervalle on renvoie la chaîne de caractère la plus courte
    if len(liste_chaîne1) > len(liste_chaîne2):
        return chaîne2
    else:
        return chaîne1


# tests
import doctest
doctest.testmod()

# Entrée
nb_caractères_chaîne1 = int(input())
chaîne1 = input()
nb_caractères_chaîne2 = int(input())
chaîne2 = input()

# Sortie
print(comparaison_lexicographique(chaîne1,chaîne2))

C'est bien, il n'y a pas de triche.
On peut faire bien plus simple. Voir corrigé.

Proposition 3

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 chaînes) ou .sort()...
On attend une fonction avec doctest.
mot_1 est plus clair que mot1.

Proposition 4

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

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 chaînes était interdite ici... C'est tricher !

Proposition 6

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

"""
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

# 0- Coeur du programme

def comparaison(longueur_1: int, chaîne_1: str, longueur_2: int, chaîne_2:str) -> str:
    """ Renvoie le premier mot entre chaîne_1 et chaîne_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 chaînes ont encore des lettres .
        if chaîne_1[id_lettre] != chaîne_2[id_lettre]:          # Si, les 2 lettres des 2 chaînes sont différentes alors, 
            for lettre in alphabet:                             # On peut déterminer le premier avec l'ordre de l'alphabet.
                if chaîne_1[id_lettre] == lettre:              
                    return chaîne_1
                if chaîne_2[id_lettre] == lettre:
                    return chaîne_2
        id_lettre += 1
    if longueur_1 == id_lettre:                                 # Les 2 chaînes n'ont pas la même longueur
        return chaîne_1                                         # Donc,celui qui a arrêté la boucle est le premier et a une longueur égale à id_lettre
    else:
        return chaîne_2

# 1- Tests

import doctest
doctest.testmod()

# 2- Lecture des entrées

longueur_1 = int(input())
chaîne_1 = input()
longueur_2 = int(input())
chaîne_2 = input()

# 3- Appel de la fonction / Sortie

print(comparaison(longueur_1, chaîne_1, longueur_2, chaîne_2))

Pas de triche ici, c'est bien.
On pouvait faire plus simple.

Proposition 9

def première_chaîne(nb_caracteres_1 : int, chaîne_1 : str, nb_caracteres_2 : int, chaîne_2 : str,) -> str :
    """ Renvoie la première chaîne de caractère selon l'ordre lexicographique
    entre 'chaîne_1' et 'chaîne_2'.
    >>> nb_caracteres_1 = 8
    >>> chaîne_1 = prologin
    >>> nb_caracteres_2 = 5
    >>> chaîne_2 = prolo
    prolo
    """
    longueur_max = max(len(chaîne_1), len(chaîne_2))
    mot1, mot2 = list(chaîne_1), list(chaîne_2)
    sortie = ''
    for lettre in range (longueur_max) :
        if mot1[lettre] > mot2[lettre] :
            sortie.append(chaîne_2) 
            break
        if mot1[lettre] < mot2[lettre] :
            sortie.append(chaîne_1) 
            break
        if mot1[lettre] == ' ' :
            sortie.append(chaîne_1) 
            break
        if mot2[lettre] == ' ' :
            sortie.append(chaîne_2) 
            break
        return sortie

# tests
import doctest
doctest.testmod()

# Entrée
nb_caracteres_1 = int(input())
chaîne_1 = input()
nb_caracteres_2 = int(input())
chaîne_2 = input()

# Sortie
print(première_chaîne(nb_caracteres_1, chaîne_2, nb_caracteres_2, chaîne_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

"""
auteur : Franck CHAMBON
https://prologin.org/train/2003/qualification/cases_inaccessibles
"""

def plus_petite(chaîne_1: str, chaîne_2: str) -> str:
    """Renvoie la plus petite des deux chaînes.
    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(chaîne_1)
    taille_2 = len(chaîne_2)
    taille_commune = min(taille_1, taille_2)
    for i in range(taille_commune):
        c_1 = chaîne_1[i]
        c_2 = chaîne_2[i]
        if c_1 < c_2:
            return chaîne_1
        if c_2 < c_1:
            return chaîne_2
    if taille_1 < taille_2:
        return chaîne_1
    if taille_2 < taille_1:
        return chaîne_2
    # ici on a 
    assert chaîne_1 == chaîne_2, f"Erreur curieuse"
    return chaîne_1

import doctest
doctest.testmod()

taille_1 = int(input())
chaîne_1 = input()
taille_2 = int(input())
chaîne_2 = input()

print(plus_petite(chaîne_1, chaîne_2))

Traditionnellement c est souvent un identifiant pour un caractère d'une chaîne.
Utiliser sort, sorted ou < sur les chaînes é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...