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

Le 08 décembre 2018 à 00:34:30 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:29:41 KheyAuxPommes a écrit :
Ma solution en 12 lignes btw :

def reduce(string):
reduction = ""
for c in string:
if not reduction:
reduction += c
continue
prev = reduction[-1]
if prev.isupper() != c.isupper() and c.lower() == prev.lower():
reduction = reduction[:-1]
else:
reduction += c
return reduction

C'est pas O(n) je pense

Pourquoi ? Je ne parcours qu'une seule fois la chaîne de caractères d'entrée.

Le 08 décembre 2018 à 00:39:41 KheyAuxPommes a écrit :
Ma solution pour le palindrome :

@lru_cache(None)
def palin(string):
    if len(string) < 2:
        return string
    if string[0] == string[-1] and len(palin(string[1:-1])) == len(string) - 2:
        return string
    return max(palin(string[:-1]), palin(string[1:]), key=len)

7 lignes.

Pas aussi optimal que l'algorithme de Manacher bien sûr, mais petit O(n²) en programmation dynamique.

Pas du O(n2), le len(string[1:-1]) est couteux je crois

Le 08 décembre 2018 à 00:40:25 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:39:41 KheyAuxPommes a écrit :
Ma solution pour le palindrome :

@lru_cache(None)
def palin(string):
if len(string) < 2:
return string
if string[0] == string[-1] and len(palin(string[1:-1])) == len(string) - 2:
return string
return max(palin(string[:-1]), palin(string[1:]), key=len)

7 lignes.

Pas aussi optimal que l'algorithme de Manacher bien sûr, mais petit O(n²) en programmation dynamique.

Pas du O(n2), le len(string[1:-1]) est couteux je crois

C'est du O(n²) grâce au cache.
Si on évite la récursion, ça s'implémente avec un tableau 2D et on remarque plus distinctement le O(n²).

Le 08 décembre 2018 à 00:40:54 PlateauDeSACLAY a écrit :
Et le lru_cache sur des grosses valeurs te donne pas du n2

Tu parles de détail d'implémentations là.

Idem quand tu dis que "string[1:-1]" est coûteux.

def reduc(a, b):
    if a.upper() == b.upper():
        if a.isupper() and b.islower() or a.islower() and b.isupper():
            return True
        else:
            return False
    else:
        return False




def main():
    chaine = "AbBaa"
    indice = 0
    indiceAdj = 1

    liste = list(chaine)

    while indice + 1  != len(liste) :
        if len(liste) == 1:
            break

        if reduc(liste[indice],liste[indiceAdj]) == True :
            liste[indice] = '0'
            liste[indiceAdj] = '0'
            indice = 0
            indiceAdj = 1

            while liste.count('0') > 0:
                liste.remove('0')
        else :
            indice += 1 
            indiceAdj += 1


    print(liste)        



main()

J'ai fais ca en étant bourré dites moi si y'a des trucs qui vont pas

edit: je sais que cest pas opti du tout mais je suis défoncé donc pardonnez moi

Le 08 décembre 2018 à 00:41:39 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:40:54 PlateauDeSACLAY a écrit :
Et le lru_cache sur des grosses valeurs te donne pas du n2

Tu parles de détail d'implémentations là.

Idem quand tu dis que "string[1:-1]" est coûteux.

Tu donne du code donc on regarde ça oui
Et la mémoisation ça peut être très subtile, donc dire "ça marche" ça suffit pas toujours (la elle est triviale à implémenter bien oui)

Le 08 décembre 2018 à 00:43:58 EnBaDuBlok a écrit :
En tout cas l'auteur tu t'es trompé c'est 9359 et pas 9348

Non, j'ai raison (en fait l'exercice vient d'un site, la solution est bien 9348).

Le 08 décembre 2018 à 00:43:16 CryTime1v9 a écrit :

J'ai fais ca en étant bourré dites moi si y'a des trucs qui vont pas

edit: je sais que cest pas opti du tout mais je suis défoncé donc pardonnez moi

C'est beau ce dévouement

Le 08 décembre 2018 à 00:40:24 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:34:30 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:29:41 KheyAuxPommes a écrit :
Ma solution en 12 lignes btw :

def reduce(string):
reduction = ""
for c in string:
if not reduction:
reduction += c
continue
prev = reduction[-1]
if prev.isupper() != c.isupper() and c.lower() == prev.lower():
reduction = reduction[:-1]
else:
reduction += c
return reduction

C'est pas O(n) je pense

Pourquoi ? Je ne parcours qu'une seule fois la chaîne de caractères d'entrée.

T'es en python khey, srting est pas un type mutable
à chaque fois que tu fais reduction = reduction[:-1]ou reduction += cca te crée une nouvelle chaine et parcourt reductionpour la remplir avant d'affecter ca à la même adresse.

Le 08 décembre 2018 à 00:43:58 EnBaDuBlok a écrit :
En tout cas l'auteur tu t'es trompé c'est 9359 et pas 9348

Merde... En fait t'as raison, il manquait 2 caractères dans mon c/c ce qui fausse le résultat. Putain, désolé.

Le 08 décembre 2018 à 00:48:38 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:43:58 EnBaDuBlok a écrit :
En tout cas l'auteur tu t'es trompé c'est 9359 et pas 9348

Merde... En fait t'as raison, il manquait 2 caractères dans mon c/c ce qui fausse le résultat. Putain, désolé.

l'op tes en prépa ou fac ?

Le 08 décembre 2018 à 00:44:45 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:43:58 EnBaDuBlok a écrit :
En tout cas l'auteur tu t'es trompé c'est 9359 et pas 9348

Non, j'ai raison (en fait l'exercice vient d'un site, la solution est bien 9348).

Bah explique moi pourquoi je me suis trompé alors, si tu n'arrives pas à m'expliquer pourquoi c'est que c'est toi qui te trompes

int main()
{
    string cake;

    cake = "tonbordel"

    bool b = true;

    while (b)
    {
        b = false;

        for(int i = 0; i < cake.size(); i++)
        {


            if( (cake[i+1] == cake[i] -32 ) || (cake[i] == cake[i+1] - 32 ))
            {

                cake.erase(i,2);
                b = true;

            }
        }
    }

    cout << " Taille : " << cake.size();

    return 0;
}

Mon algo est très simple

Il parcourt toute la chaîne et supprime les caractère maj/min adjacents.
Il répète ensuite l'opération encore et encore, et si il parcourt une fois la chaîne sans rien supprimer, alors il affiche la taille.

Je vois pas où est la faille

Le 08 décembre 2018 à 00:44:45 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:43:58 EnBaDuBlok a écrit :
En tout cas l'auteur tu t'es trompé c'est 9359 et pas 9348

Non, j'ai raison (en fait l'exercice vient d'un site, la solution est bien 9348).

Tu peux donner le site stp? J'aimerai bien m’entraîner aussi
Au fait c'est de quel niveau vos exos? Je suis en L1 et j'ai jamais vu des trucs aussi dur

Le 08 décembre 2018 à 00:48:21 gay_pom_12 a écrit :

Le 08 décembre 2018 à 00:40:24 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:34:30 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:29:41 KheyAuxPommes a écrit :
Ma solution en 12 lignes btw :

def reduce(string):
reduction = ""
for c in string:
if not reduction:
reduction += c
continue
prev = reduction[-1]
if prev.isupper() != c.isupper() and c.lower() == prev.lower():
reduction = reduction[:-1]
else:
reduction += c
return reduction

C'est pas O(n) je pense

Pourquoi ? Je ne parcours qu'une seule fois la chaîne de caractères d'entrée.

T'es en python khey, srting est pas un type mutable
à chaque fois que tu fais reduction = reduction[:-1]ou reduction += cca te crée une nouvelle chaine et parcourt reductionpour la remplir avant d'affecter ca à la même adresse.

Le sticker bordel

Le 08 décembre 2018 à 00:48:21 gay_pom_12 a écrit :

Le 08 décembre 2018 à 00:40:24 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:34:30 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:29:41 KheyAuxPommes a écrit :
Ma solution en 12 lignes btw :

def reduce(string):
reduction = ""
for c in string:
if not reduction:
reduction += c
continue
prev = reduction[-1]
if prev.isupper() != c.isupper() and c.lower() == prev.lower():
reduction = reduction[:-1]
else:
reduction += c
return reduction

C'est pas O(n) je pense

Pourquoi ? Je ne parcours qu'une seule fois la chaîne de caractères d'entrée.

T'es en python khey, srting est pas un type mutable
à chaque fois que tu fais reduction = reduction[:-1]ou reduction += cca te crée une nouvelle chaine et parcourt reductionpour la remplir avant d'affecter ca à la même adresse.

Mais encore une fois, on s'en fout ça, c'est un détail, ça change rien à l'algo en lui-même.

Le 08 décembre 2018 à 00:49:12 europol2 a écrit :

Le 08 décembre 2018 à 00:44:45 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:43:58 EnBaDuBlok a écrit :
En tout cas l'auteur tu t'es trompé c'est 9359 et pas 9348

Non, j'ai raison (en fait l'exercice vient d'un site, la solution est bien 9348).

Tu peux donner le site stp? J'aimerai bien m’entraîner aussi
Au fait c'est de quel niveau vos exos? Je suis en L1 et j'ai jamais vu des trucs aussi dur

https://adventofcode.com/

Flemme de continuer, mais je confirme que ma méthode est en o(n):

Prenons une chaîne result et une chaîne s (celle de départ):

- Prendre le caractère le plus à gauche, tant que le premier caractère de la sous-chaine est égal au second ou qu'il est égal au dernier caractère de la chaîne result, reduire (result et s). Une fois le while terminé, ajouter à la fin de result le premier caractère de la chaîne s.
Relancer la fonction avec le s résultant de l'opération précédente

Retourner result à la fin de l'algo 🤔🤗

Le 08 décembre 2018 à 00:49:00 CryTime1v9 a écrit :

Le 08 décembre 2018 à 00:48:38 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:43:58 EnBaDuBlok a écrit :
En tout cas l'auteur tu t'es trompé c'est 9359 et pas 9348

Merde... En fait t'as raison, il manquait 2 caractères dans mon c/c ce qui fausse le résultat. Putain, désolé.

l'op tes en prépa ou fac ?

1ère L