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

Le 08 décembre 2018 à 00:19:16 [Ban2]PTSI-PT a écrit :

[00:15:14] <[Ban2]PTSI-PT>

[00:11:43] <stuckRANG3>

Le 08 décembre 2018 à 00:09:58 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:09:27 [Ban2]PTSI-PT a écrit :

[00:04:22] <PlateauDeSACLAY>

Le 08 décembre 2018 à 00:02:49 [Ban2]PTSI-PT a écrit :

[23:59:19] <PlateauDeSACLAY>

Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :

Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :

Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.

Toujours aucune implémentation 20 min plus tard.

Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?

Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.

Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos

Mais qu'est-ce tu dis toi ?

Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :

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 ?

Il faut réitérer l'algo tant que y'a eu des modifications

Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...

Donne nous donc ta solution efficace

A quoi servirait le topic ?...

En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas

Donne au moins ta complexité

Bah non.

L'op qui a pas mieux que O(n^2)

Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.

Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.

O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche

ababababBABABABA
Tu ne peux pas isoler le début car il peut y avoir des grosses réactions en chaîne

Quand on est à bB on le vire et on place le curseur à gauche au cas où justement sur le a
Donc je pense pas, mais ptet qu'il peut y avoir de telles réactions oui

Je suis d'accord ça marche et c'est plus simple que ce que j'ai proposé

Oui et c'est O(n).

Tu forces franchement khey c'est ce que j'avais fait a une ligne près

Maintenant donne moi un algo qui trouve le plus grand palindrome dans une chaîne de caractères en temps linéaire

On doit pouvoir adapter mon idée de récursion nan? En partant des sous listes de la forme [x,y,x] et [x,x] et en testant les extrémités de la liste à chaque profondeur de récursion

En testant les listes adjacentes ça marche en fait, sinon on peut passer plusieurs fois sur la même lettre et c'est en O(n^2)

Je suis pas sûr de capter mais ce que tu dit ça sera pas en O(n^2) ?

Le 08 décembre 2018 à 00:21:03 Chien-deter-10 a écrit :
Quelqu'un pour coder mon algo eco+ ?
J'ai rien pour faire du logiciel sur mon pc portable là...

Ton algo est O(n²), pas intéressant à implémenter.

Bon j'allais ouvrir une IDE jusqu'a ce que je me souvienne que j'avais Visual studio cet outil de Satan qui rame du cul

à l'arrache àlors, je vous préviens ca compile pas.

#include <iostream>
#include <string>
#include <cmath> #pour abs


int RemoveKebab (std::string StIn)
{
    int Kebab = 0, Index = 0 ;
    while( Index != StIn.length() || StIn.empty() == false )
    {
        if (abs(StIn[Index]-StIn[Index+1]) == 32 ) #si oui différence de casse selon table ASCII
        {
            StIn.remove(Index,2);
            --Index; 
            ++Kebab;
        }
        Index++;
    }
    return Kebab;
}

int main(int argc, char* argv[])
{
    std::string Srebrenica= "La chaine de merde de l'auteur"; #en vrai faudrait une fonc de lecture de .txt mais la flemme
    while(RemoveKebab(Srebrenica) != 0 ) {} 
    std::cout << "y reste "<<Srebrenica.length() << "caractères" <<std::endl;
    return 0;
}

niveau complexité ca pue la merde à mon avis, je sais pas si la méthode d'appels successifs sur une chaine de plus en plus petite permet pas de gratter un O(n ln(n)) mais j'ai pas confiance dans string.length() et je sais que string.remove() c'est pourri . on va dire polynomial

Le 08 décembre 2018 à 00:19:52 PinkHair-- a écrit :

Le 08 décembre 2018 à 00:11:43 stuckRANG3 a écrit :

Le 08 décembre 2018 à 00:09:58 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:09:27 [Ban2]PTSI-PT a écrit :

[00:04:22] <PlateauDeSACLAY>

Le 08 décembre 2018 à 00:02:49 [Ban2]PTSI-PT a écrit :

[23:59:19] <PlateauDeSACLAY>

Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :

Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :

Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.

Toujours aucune implémentation 20 min plus tard.

Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?

Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.

Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos

Mais qu'est-ce tu dis toi ?

Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :

Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :

Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :

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 ?

Il faut réitérer l'algo tant que y'a eu des modifications

Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...

Donne nous donc ta solution efficace

A quoi servirait le topic ?...

En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas

Donne au moins ta complexité

Bah non.

L'op qui a pas mieux que O(n^2)

Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.

Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.

O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche

ababababBABABABA
Tu ne peux pas isoler le début car il peut y avoir des grosses réactions en chaîne

Quand on est à bB on le vire et on place le curseur à gauche au cas où justement sur le a
Donc je pense pas, mais ptet qu'il peut y avoir de telles réactions oui

Je suis d'accord ça marche et c'est plus simple que ce que j'ai proposé

Oui et c'est O(n).

Tu forces franchement khey c'est ce que j'avais fait a une ligne près

Maintenant donne moi un algo qui trouve le plus grand palindrome dans une chaîne de caractères en temps linéaire

Flemme de détailler, suffit d'utiliser un arbre des suffixes légèrement modifié et le tour est joué

Explique ?

Le 08 décembre 2018 à 00:23:25 BeurFMTV a écrit :

Le 08 décembre 2018 à 00:14:55 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:13:14 BeurFMTV a écrit :
J'ai pas envie de le faire mais c'est simple:
tu répètes l'opération jusqu'à ce que tu ne puisses rien supprimer, donc tu mets par exemple un "while i~=0" avec i une variable à laquelle tu ajouteras "1" a chaque fois que tu supprimes un truc. Ensuite concernant la suppression des lettres tu convertis en ASCII la lettre sur laquelle t'es, celle d'avant et celle d'après et si y en a une des deux dont le code ASCII est le code ASCII de la lettre + 32 ou -32 (selon si elle est en majuscule ou en minuscule) tu la supprimes.
Franchement si c'est ça vos exos d'algo vous avez de la chance, je suis au Canada et ici ils te mettent des trucs en info... quand t'as un DM tu sais que ton w-e est mort

Bah oui mais ton algo est pas optimal donc faux.

Non, c'est juste ou c'est faux. Si c'est "pas optimal" c'est que c'est quand même juste

Je sais, c'était juste pour dire que 'j'attendais la solution optimale, sinon ça n'a que très peu d'intérêt.

Pour le truc des palindromes:

On parcours la chaîne de caractères dans l'ordre, on découpe la chaîne en morceaux de la forme 'xyx', 'xx' et 'x' en veillant à avoir le plus de sous chaîne de taille 2 et 3 possible.

Ensuite pour chaque sous-chaîne, on regarde si les sous-chaînes adjacentes sont symétriques (merde, il faut les parcourir pour ça en fait)
Si oui on concatène les 3 sous-chaines
Sinon on sort de la récursion et on retourne la taille de la sous-chaine

Ça a l'air d'être n^2, j'avais oublié de compter la comparaison des sous-chaines

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

Le 08 décembre 2018 à 00:29:39 [Ban2]PTSI-PT a écrit :
Pour le truc des palindromes:

On parcours la chaîne de caractères dans l'ordre, on découpe la chaîne en morceaux de la forme 'xyx', 'xx' et 'x' en veillant à avoir le plus de sous chaîne de taille 2 et 3 possible.

Ensuite pour chaque sous-chaîne, on regarde si les sous-chaînes adjacentes sont symétriques (merde, il faut les parcourir pour ça en fait)
Si oui on concatène les 3 sous-chaines
Sinon on sort de la récursion et on retourne la taille de la sous-chaine

Ça a l'air d'être n^2, j'avais oublié de compter la comparaison des sous-chaines

En vrai ça reviens a la solution naïve où tu part de chaque élément et tu regarde les éléments adjacents (en prenant aussi en compte les palindromes pairs)

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

Voilà mon implémentation en C++ :

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;
}

Je trouve 9359 de taille, donc je vois pas pourquoi j'ai un résultat différent du tiens l'auteur

[00:32:14] <stuckRANG3>

Le 08 décembre 2018 à 00:29:39 [Ban2]PTSI-PT a écrit :
Pour le truc des palindromes:

On parcours la chaîne de caractères dans l'ordre, on découpe la chaîne en morceaux de la forme 'xyx', 'xx' et 'x' en veillant à avoir le plus de sous chaîne de taille 2 et 3 possible.

Ensuite pour chaque sous-chaîne, on regarde si les sous-chaînes adjacentes sont symétriques (merde, il faut les parcourir pour ça en fait)
Si oui on concatène les 3 sous-chaines
Sinon on sort de la récursion et on retourne la taille de la sous-chaine

Ça a l'air d'être n^2, j'avais oublié de compter la comparaison des sous-chaines

En vrai ça reviens a la solution naïve où tu part de chaque élément et tu regarde les éléments adjacents (en prenant aussi en compte les palindromes pairs)

Nan parce que n^2 c'est dans le pire des cas mais wallah en moyenne c'est largement mieux

Edit: en vrai c'est pas sur du tout que c'est en O(n^2) et pas mieux, j'arrive pas à trouver d'exemple tel que ça se passe mal

Le 08 décembre 2018 à 00:36:02 EnBaDuBlok a écrit :
Voilà mon implémentation en C++ :

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;
}

Je trouve 9359 de taille, donc je vois pas pourquoi j'ai un résultat différent du tiens l'auteur

Après le erase il faut revenir en arrière de un

sinon un truc qui serait probablement pas mal pour gratter c'est de faire une première passe pour détecter tous les caractères isolés.

Genre quand tu vois un motif de type "aba" au milieu tu coupes au niveau du 'b' et t'appliques ton algo eco+ sur les 2 sous-chaines avant des les recoller et de repasser dessus. si t'es en O(n²) ou plus ca doit permettre un gain correct si tu coupes en 3 ou 4 à chaque fois.

enfin bon si tu proposes ca en solution c'est le double dropkick dans les couilles : "alors l'auteur, quelle est la taille optimale de sous-chaine qui maximise le gain en perf sachant que mon algo est en O(n^2 ln(n))"

Le 08 décembre 2018 à 00:37:22 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:36:02 EnBaDuBlok a écrit :
Voilà mon implémentation en C++ :

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;
}

Je trouve 9359 de taille, donc je vois pas pourquoi j'ai un résultat différent du tiens l'auteur

Après le erase il faut revenir en arrière de un

Pourquoi ?

Et revenir en arrière de 1 où ?
tu parles de décrémenter i ?

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.