Suppression des doublons sur chaîne de caractère

Version imprimable

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:

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

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:

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

31/03/2019, 10h35
wiztricks
Salut,

Citation:

Envoyé par xtebeun

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 b~~aacc~~ pour obtenir au final "b"

Difficile de ne pas comparer successivement 2 caractères consécutifs... donc on pourrait commencer par écrire:
Code:

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

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.

Citation:

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:

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

31/03/2019, 21h01
wiztricks

Citation:

Envoyé par xtebeun

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

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
31/03/2019, 21h28
BufferBob
salut,

l'énoncé d'origine dit précisément :

Citation:

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

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:

1 2 >>> bla('baaabbacddc') 'b'
31/03/2019, 22h48
xtebeun

Citation:

Envoyé par wiztricks

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 !!
31/03/2019, 23h51
Sve@r

Bonjour

Citation:

Envoyé par xtebeun

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...
01/04/2019, 01h55
BufferBob

Citation:

Envoyé par Sve@r

sensé !!!

raté :aie: c'est "censé" ici (on peut remplacer par "supposé")
01/04/2019, 07h17
Sve@r

Citation:

Envoyé par BufferBob

raté :aie: c'est "censé" ici (on peut remplacer par "supposé")

Oups... exact.:oops:

Désolé pour cette erreur honteuse

Salut,

Citation:

Envoyé par xtebeun

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:

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:

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:

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

01/04/2019, 10h03
xtebeun

Citation:

Envoyé par Sve@r

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...
01/04/2019, 12h17
BufferBob
la tournure de l'énoncé est exactement :

Citation:

"(...) 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:

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.

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:

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:

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:

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

01/04/2019, 17h33
Sve@r

Citation:

Envoyé par xtebeun

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)...