[Prog] Cet exo d'algo basique DETROUSSE le 18-25

Salut.

Je vous donne une chaîne de caractères S composée exclusivement des lettres de A à Z, majuscules comme minuscules.

Retirez tous les caractères adjacents qui représentent la même lettre mais dans une casse différente (l'un en majuscule, l'autre en minuscule). Répétez l'opération jusqu'à ce qu'aucun caractère ne puisse être retiré (il peut y avoir des réactions en chaînes).

• 'aA' ' ' (tout est retiré)
• 'AbBa' 'Aa' ' '
• 'abAB' 'abAB' (aucune réduction possible)
• 'aabAAB' 'aabAAB'
• 'dabAcCaCBAcCcaDA' 'dabAaCBAcCcaDA' 'dabCBAcCcaDA' 'dabCBAcaDA'

Êtes-vous capable de résoudre ce petit problème niveau L1 ?

Étant donnée cette chaîne de caractères : https://pastebin.com/raw/5QtbiaCd
Quelle est la taille de la chaîne de caractères après avoir appliqué la réduction ?

P.S. : Je suis pas un puceau de l'algorithmie, hein, j'ai déjà résolu ce problème tout à l'heure.
La solution est 9348, à vous de me montrer comment vous la trouveriez.

Bonus : Faites-le en 10 lignes ou moins.

Le 07 décembre 2018 à 23:27:39 PoubzDep13 a écrit :
c'est trivial.

Bah fais-le alors. Tu as 10 min.

Ayaaa mais ça se fait en 3 lignes

On fera pas tes devoirs Célestin

Le 07 décembre 2018 à 23:29:07 stuckRANG3 a écrit :
Ayaaa mais ça se fait en 3 lignes

On fera pas tes devoirs Célestin

3 lignes ? J'attends de voir.

Et comme je te l'ai dit, c'est pas mon devoir, je t'ai même donné la bonne réponse.

J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :

- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle

Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :

- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle

Quand est-ce que tu incrémentes X ?

Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :

- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle

Quand est-ce que tu incrémentes X ?

A chaque fois que la lettre actuelle est la même que la precedente

Le 07 décembre 2018 à 23:34:46 JaiLuLesCGU a écrit :
Tu parcours ta liste en comparant deux à deux les indices adjacents
Tu vérifies l'état de ta variable flag qui prend la valeur True si une réduction a été effectuée
Tu boucles avec flag comme condition

Fais-le en pseudo code, ça manque de précision là.

Le 07 décembre 2018 à 23:34:46 JaiLuLesCGU a écrit :
Tu parcours ta liste en comparant deux à deux les indices adjacents
Tu vérifies l'état de ta variable flag qui prend la valeur True si une réduction a été effectuée
Tu boucles avec flag comme condition

Avec cet algo la chaîne "abbba" sera réduite en "aba" je pense

Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :

- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle

Quand est-ce que tu incrémentes X ?

A chaque fois que la lettre actuelle est la même que la precedente

Comment ton algo procède sur AbBa ?

Le 07 décembre 2018 à 23:38:13 SorrowHill a écrit :
J'avais oublié à quel point les algos du début sont nuls...

Fais le, 5 min chrono en main alors pour le challenge.

Le 07 décembre 2018 à 23:40:46 [Ban2]PTSI-PT a écrit :
Trop simple d'un point de vue algorithmique c'est juste de l'implémentation de brute, non merci

Preuve ?

[23:39:31] <KheyAuxPommes>

Le 07 décembre 2018 à 23:38:13 SorrowHill a écrit :
J'avais oublié à quel point les algos du début sont nuls...

Fais le, 5 min chrono en main alors pour le challenge.

Khey il a raison c'est à chier hein

Ça c'est un problème à la fois abordable et intéressant : https://projecteuler.net/problem=82