Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Candidat au Club
    Suppression des doublons sur chaîne de caractère
    Bonjour à tous,

    Je viens vous faire part d'un sujet France IOI sur lequel je me casse les dents depuis un petit bout de temps.

    L'idée est de supprimer les doublons tant qu'il y en a d'une chaîne de caractères. Ex:

    baaabbacddc

    baaabbacc

    babbacc

    babba

    baa

    b

    Voici mon code avec lequel je ne réussit que 2 tests sur 14.

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
     
    morceau = input()
    newMorceau = ""
    while len(morceau) != len(newMorceau):
     
       iNote = 0
       while iNote < len(morceau):
          if len(morceau) == 1:
             newMorceau = morceau[iNote]
             iNote+=1
          elif len(morceau) == 2 and morceau[iNote] == morceau[iNote+1]:
             newMorceau = ""
             iNote+=2
          elif len(morceau) == 2 and morceau[iNote] != morceau[iNote+1]:
             newMorceau = morceau
             iNote+=2
          elif morceau[iNote] == morceau[iNote+1]:
             newMorceau += morceau[iNote+2]
             iNote+=3
          else:
             newMorceau += morceau[iNote]
             iNote+=1
          morceau = newMorceau 
    print(morceau)


    J'ai essayé plein de version avec des boucles en for et while mais rien n'y fait, je sèche complètement.

    J'espère que quelqu'un pourra me mettre sur la voie.

    Merci d'avance !!

  2. #2
    Membre habitué
    Plus de précisions, car c'est pas clair
    Salut.

    Quelle logique devrait faire qu'on supprime d'abord le 'dd' de fin de chaîne, puis après 'aaa' devienne 'a' en début de chaîne ?

    Qu'entends-tu par doublon ? Doublon pour moi signifie caractère présent plus d'une fois dans la chaîne.

    Est-ce que par doublon tu entends deux mêmes caractères consécutif dans la chaîne ?

    Puis quels sont les exemples de tests avec lesquels ton code se plante ?

    Edit :

    Si c'est bien une transformation en supprimant chaque double consécutif dans la chaîne, alors on pourrait faire ça en utilisant une liste pour stocker le résultat final, et de parcourir la chaîne de la fin vers le début. Ce qui pourrait donner.

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    chaines = (
        'baaabbacddc',
        'oonnoliilkbnnbbh',
        'obbaaaaabbbaccicdcdd',
    )
     
    def unifier(chaine) :
        # Liste où seront stockés les caractères non consécutifs
        list_cars = []
        # Parcours des caractères de la chaîne de la fin vers le début
        for car in chaine[::-1] :
            try :
                # On tente de récupérer le dernier caractère 
                dernier_car = list_cars[-1]
            except IndexError :
                # Il n'y pas encore de caratères dans la liste
                # On ajoute celui en cours
                list_cars.append(car)
                # On saute au tour suivant de la boucle
                continue
            # Si le caractère courant est identique au dernier caractère de list_cars
            if car == dernier_car :
                # On le supprime de la liste
                list_cars.pop()
            else :
                # On l'ajoute en fin de liste
                list_cars.append(car)
        # Retour de la liste convertie en str en inversant la liste
        return ''.join(list_cars[::-1])
     
     
    for chaine in chaines :
        print(chaine, '=>', unifier(chaine))
    Le temps ronge l'amour comme l'acide.

  3. #3
    Expert éminent sénior
    Salut,

    Citation Envoyé par xtebeun Voir le message
    J'espère que quelqu'un pourra me mettre sur la voie.
    Il faut prendre un papier et un crayon et visualiser ce qu'on fait pour supprimer les 2 caractères qui se répètent dans baaabbacddc puis dans baacc pour obtenir au final "b"

    Difficile de ne pas comparer successivement 2 caractères consécutifs... donc on pourrait commencer par écrire:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    s = "baaabbacddc"
    ns = ''
    i = 0
    while i < len(s) - 1:
          if s[i] == s[i+1]:
               i += 1
          else:
               ns += s[i]
          i += 1

    Par construction, on a un soucis avec le dernier caractère: si les deux derniers caractères ne sont pas égaux, on le saute à tous les coups. Il n'est jamais recopié dans la chaine de sortie (ns) puisque i < len(s) - 1.

    L'astuce est d'ajouter un caractère différent du dernier (exemple '*'). Les deux derniers caractères étant différents, on supprime les différents cas de figures à tester...

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  4. #4
    Candidat au Club
    Salut,

    Tout d'abord merci beaucoup pour vos retours !!!

    Merci Bistouille pour ta solution mais elle est plus avancée que mon niveau python actuel. Il y a plusieurs éléments que tu utilises et que je n'ai pas encore vus (j'espère rattrapper tout cela très prochainement.

    Est-ce que par doublon tu entends deux mêmes caractères consécutif dans la chaîne ?

    Puis quels sont les exemples de tests avec lesquels ton code se plante ?
    Effectivement, je n'ai donné que partiellement le sujet, j'aurais du être plus précis. Il s'agit de supprimer les doublons consécutifs.
    Pour ce qui est des tests sur lequel le code se plante, je ne les ai pas. France IOI ne les donne, j'imagine que c'est pour que le codeur n'ai pas trop d'indice pour l'aider.

    wiztricks, ton code correspond parfaitement à ce que je voulais faire et ton petit tricks d'ajouter un caractère est parfait. Je penserai à cette astuce la prochaine fois.

    Du coup j'ai réécris mon code comme ceci :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
     
     
    s = input() + '*'
    ns = ''
    fs = ''
     
    while len(s)>len(ns):
       i = 0
       while i < len(s) - 1:
          if s[i] == s[i+1]:
               i += 1
          else:
               ns += s[i]
          i += 1
       s = ns
     
    for i in range (len(ns)-1):
       fs += ns[i]
    print(fs)


    Je bloque encore car la chaîne de caractères doit repasser dans la même boucle jusqu'à ce qu'il n'y ait plus de doublons.
    Cependant, en remaniant mon code, j'arrive soit sur des boucles infinies, soit sur une chaîne où il reste encore un doublon.

    Je pense que ma condition sur le while n'est pas celle qu'il faut...

  5. #5
    Expert éminent sénior
    Citation Envoyé par xtebeun Voir le message
    Je bloque encore car la chaîne de caractères doit repasser dans la même boucle jusqu'à ce qu'il n'y ait plus de doublons.
    Tout à fait...

    Citation Envoyé par xtebeun Voir le message
    Je pense que ma condition sur le while n'est pas celle qu'il faut...
    Entre autres...

    Mais la solution, c'est papier crayon et faire un peu turbiner ses méninges...

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  6. ###raw>post.musername###
    Expert éminent
    salut,

    l'énoncé d'origine dit précisément :
    "dès qu'il voit deux notes identiques côte à côte, il les efface toutes les deux ! Il continue ainsi d'effacer tant qu'il existe deux notes égales consécutives."
    donc dans l'exemple "aaa" ne disparait pas d'un coup, il ne reste qu'un seul 'a' (lequel disparait ensuite avec un autre 'a' plus loin)

    une solution via les regex :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    import re
    def bla(s):
       z = ''
       while s != z:
          z = s
          s = re.sub('(.)\\1', '', s)
       return s


    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    >>> bla('baaabbacddc')
    'b'
      0  0

  7. #7
    Candidat au Club
    Citation Envoyé par wiztricks Voir le message
    Mais la solution, c'est papier crayon et faire un peu turbiner ses méninges...
    Je sais bien, ça fait un moment que je suis sur celui là. Mais j'ai jamais bloqué autant sur les exos précédents... Pourtant cela ne me parait pas si sorcier. Allez on y croit

    Merci BufferBob pour ta soluce mais à l'entrée du niveau 3 sur IOI, on n'a pas encore vu les regex. Du coup je vais essayer avec les outils que je suis censé avoir !!

  8. #8
    Expert éminent sénior
    Bonjour
    Citation Envoyé par xtebeun Voir le message
    baaabbacddc

    baaabbacc

    babbacc

    babba

    baa

    b

    Je sais bien, ça fait un moment que je suis sur celui là.
    Moi il y a un truc qui me gêne dans la logique. Première ligne, on a baaabbacddc. Le "dd" disparait. Pourquoi lui et pas le "aa" du début ?
    Ok, on va dire que le truc part de la fin de la chaine et remonte vers le début.
    Mais dans la second ligne, il y a "baaabbacc" et c'est le "aa" qui disparait. Pourquoi lui ? Si on garde la même logique (logique qui sous-tend toute base d'un algorithme), ce devrait être soit le "cc" situé à la fin ou bien, en admettant que le truc continue à partir de la dernière position traitée et en remontant vers le début, alors ce devrait être le "bb".
    Donc tant que tu ne nous expliqueras pas le principe indiquant comment effacer, tu ne pourras pas l'expliquer à un programme...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  9. #9
    Expert éminent
    Citation Envoyé par Sve@r Voir le message
    sensé !!!
    raté c'est "censé" ici (on peut remplacer par "supposé")

  10. #10
    Expert éminent sénior
    Citation Envoyé par BufferBob Voir le message
    raté c'est "censé" ici (on peut remplacer par "supposé")
    Oups... exact.

    Désolé pour cette erreur honteuse
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  11. #11
    Expert éminent sénior
    Salut,

    Citation Envoyé par xtebeun Voir le message
    Je sais bien, ça fait un moment que je suis sur celui là. Mais j'ai jamais bloqué autant sur les exos précédents... Pourtant cela ne me parait pas si sorcier. Allez on y croit
    Compliquons les choses en espérant les simplifier...
    Vous avez cela:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    s = "baaabbacddc" + '*'
    ns = ''
    i = 0
    while i < len(s) - 1:
          if s[i] == s[i+1]:
               i += 1
          else:
               ns += s[i]
          i += 1

    qui effectue une itération. Et le soucis et d'en faire plusieurs pour arriver au résultat final. Vous pourriez l'encapsuler dans une fonction:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def f(s):
        s = s + '*'  
        ns = ''
        i = 0
        while i < len(s) - 1:
              if s[i] == s[i+1]:
                  i += 1
              else:
                  ns += s[i]
              i += 1
        return ns

    Et vous concentrer sur quoi remplacer les '...' dans une boucle qui englobe les appels à cette fonction:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    s = input()
    ....
    while ...:
        ...
        ns = f(s)
        ...
    print(ns)

    Puis éventuellement remplacer l'appel à la fonction par son contenu.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  12. #12
    Candidat au Club
    Citation Envoyé par Sve@r Voir le message
    Bonjour

    Moi il y a un truc qui me gêne dans la logique. Première ligne, on a baaabbacddc. Le "dd" disparait. Pourquoi lui et pas le "aa" du début ?
    Ok, on va dire que le truc part de la fin de la chaine et remonte vers le début.
    Mais dans la second ligne, il y a "baaabbacc" et c'est le "aa" qui disparait. Pourquoi lui ? Si on garde la même logique (logique qui sous-tend toute base d'un algorithme), ce devrait être soit le "cc" situé à la fin ou bien, en admettant que le truc continue à partir de la dernière position traitée et en remontant vers le début, alors ce devrait être le "bb".
    Donc tant que tu ne nous expliqueras pas le principe indiquant comment effacer, tu ne pourras pas l'expliquer à un programme...
    Salut Sve@r, effectivement cela n'est pas très logique, mais il s'agit bien de l'exemple donné pour l'exercice.

    Merci wiztricks, je vais plancher là dessus.

    J'avais effectué mes premiers essais sur cet exercice avec avec des fonctions. N'y arrivant pas, petit à petit j'ai changé trop d'éléments dans mon code jusqu'à m'y perdre complètement...

  13. #13
    Expert éminent
    la tournure de l'énoncé est exactement :
    "(...) une suite possible d'élimination des doublons est la suivante : (...)"
    ce qui laisse entendre qu'il y a d'autres façons de faire, et donc que le but n'est pas forcément de reproduire la logique de l'exemple à l'identique.

    si on tente de dégager les doublons de gauche à droite, un seul à la fois :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
                      baaabbacddc
    b[aa]abbacddc --> babbacddc
      ba[bb]acddc --> baacddc
        b[aa]cddc --> bcddc
          bc[dd]c --> bcc
            b[cc] --> b

    on obtient bien la même chose.

  14. #14
    Candidat au Club
    Alléluia !!!!!!!!!

    J'ai enfin pu résoudre l'exercice après que cette boucle m'ait rendu fou.

    Alors qu'en réalité, mon code était bon depuis un petit moment... Je m'explique, voici mon code gagnant (merci wiztricks pour la mise sur la voie) :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def f(s):
        s = s + '*'  
        ns = ''
        i = 0
        while i < len(s) - 1:
              if s[i] == s[i+1]:
                  i += 1
              else:
                  ns += s[i]
              i += 1
        return ns
     
    s = input()
    cond = True
     
    while cond:
     
        ns = f(s)
        cond = (len(ns) != len(s))
        s=ns
     
    print(ns)


    Or j'avais ajouté une section afin de supprimer le caractère '*' lors de la sortie de la nouvelle chaîne de caractère. Du coup j'étais focalisé sur la boucle qui finalement était correcte à partir d'un certain moment.

    Ci après je vous mets les corrections proposées par France IOI pour ceux que cela intéresse.

    Correction n°1 :

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    entree = list(input())
    nbNotes = len(entree)
    nbDoublons = -1
    while nbDoublons != 0:
       nbDoublons = 0
       iIn = 0
       iOut = 0
       while iIn < nbNotes :
          if (iIn < nbNotes - 1) and (entree[iIn] == entree[iIn+1]):
             iIn = iIn + 2
             nbDoublons = nbDoublons + 1
          else:
             entree[iOut] = entree[iIn]
             iIn = iIn + 1
             iOut = iOut + 1
       nbNotes = nbNotes - 2 * nbDoublons
    pos = 0
    for loop in range(nbNotes):
       print(entree[pos], end = '')
       pos = pos + 1


    Correction n°2:

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    entree = input()
    nbNotes = len(entree)
    sortie = [' '] * nbNotes
    lastPos = -1;
    pos = 0
    for loop in range(nbNotes):
       if lastPos >= 0 and sortie[lastPos] == entree[pos]:
          lastPos = lastPos - 1
       else:
          lastPos = lastPos + 1
          sortie[lastPos] = entree[pos]
       pos = pos + 1
    pos = 0
    for loop in range(lastPos + 1):
       print(sortie[pos], end = '')
       pos = pos + 1

  15. #15
    Expert éminent sénior
    Citation Envoyé par xtebeun Voir le message
    Ci après je vous mets les corrections proposées par France IOI pour ceux que cela intéresse.
    Intéressant de voir comment on peut réfléchir différemment à un problème. On s'est à peu près tous focalisés sur "créer une nouvelle liste contenant la liste d'origine évidée" alors que les corrections se contentent de réécrire dans la même liste les notes qui conviennent et de compter combien il y a de note réécrite. Ensuite, elles affichent juste les notes "utiles" de la liste en n'affichant pas ce qui dépasse (et qui n'a pas disparu)...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

###raw>template_hook.ano_emploi###