Discussion :

[xtebeun]

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

[bistouille]

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

[wiztricks]

Salut,

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

[xtebeun]

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

[wiztricks]

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

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

[BufferBob]

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'

[xtebeun]

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

[Sve@r]

Bonjour

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

[BufferBob]

sensé !!!

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

[Sve@r]

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

Oups... exact.

Désolé pour cette erreur honteuse

[wiztricks]

Salut,

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

[xtebeun]

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

[BufferBob]

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.

[xtebeun]

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

[Sve@r]

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