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

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

[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

[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'