Messages de PlateauDeSaclay

Le 08 décembre 2018 à 01:08:34 PinkHair-- a écrit :

Le 08 décembre 2018 à 01:03:41 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 01:02:41 PinkHair-- a écrit :

Le 08 décembre 2018 à 01:01:56 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 01:00:58 PinkHair-- a écrit :

Le 08 décembre 2018 à 00:59:29 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
retirer S[i] et S[i+1]
si i>0 alors i--
}
}

Propre.https://image.noelshack.com/fichiers/2017/02/1484388157-obama.png

Cest marrant j'ai retrouvé exactement le même code C sur gfg, avec la même boucle while et les mêmes noms de variableshttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png

gfg = ?

Geeksforgeeks, je pioche les exos que je donne aux licences là bashttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png

Ils sont bons les licences en algo ?https://image.noelshack.com/fichiers/2016/47/1480064732-1467335935-jesus4.png

Aussi médiocres que les centraliens, si je devais les situerhttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png

Plus sérieusement, ils sont bons pour programmer et pour faire du visuel. Dès lors qu'il s'agit de se creuser les méninges, les étudiants qui s'en sortent se comptent sur les doigts d'une mainhttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png

Si je suis ce type d'étudiant tu me conseille quoi pour pousser loin l'algo ? Irl ces mecs la tu les laisse tranquille ou tu les pousses un peu ?https://image.noelshack.com/fichiers/2016/47/1480064732-1467335935-jesus4.png

Le 08 décembre 2018 à 01:06:22 Mecadam a écrit :
i=0
while(i != len(txt)):
j = i+1
while(j < len(txt) and (txt[i] == txt[j].lower() or txt[i] == txt[j].upper() or txt[i] == txt[j])):
if (j < len(txt)):
txt = txt[:i]+txt[j:]
taille = len(txt)
j+=1
i+=1

Voilà en O(n) en 10 lignes en python khey :)

Pas du O(n) je crois à cause de txt = ...

Le 08 décembre 2018 à 01:02:41 PinkHair-- a écrit :

Le 08 décembre 2018 à 01:01:56 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 01:00:58 PinkHair-- a écrit :

Le 08 décembre 2018 à 00:59:29 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
retirer S[i] et S[i+1]
si i>0 alors i--
}
}

Propre.https://image.noelshack.com/fichiers/2017/02/1484388157-obama.png

Cest marrant j'ai retrouvé exactement le même code C sur gfg, avec la même boucle while et les mêmes noms de variableshttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png

gfg = ?

Geeksforgeeks, je pioche les exos que je donne aux licences là bashttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png

Ils sont bons les licences en algo ?https://image.noelshack.com/fichiers/2016/47/1480064732-1467335935-jesus4.png

Le 08 décembre 2018 à 00:59:06 EnBaDuBlok a écrit :
Le pire c'est que vous continuez avec vos O(n) pour le palindrome alors qu'après 6 pages de topic aucun de vous a été foutu de trouver la solution du premier problème avec tous vos trucs théoriques :rire:

Allez le singe on retourne pisser du python en faisant autant d'erreurs que l'auteur :hap:

Le 08 décembre 2018 à 00:56:31 PinkHair-- a écrit :
Sinon j'attends le pseudo-code pour le plus long palindrome d'une chaîne de caractèreshttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png

Je veux une complexité en o(n), je vous ai laissé des indices sur les structures de données à utiliser. Les L1 de Jussieu, vous avez le droit à un tiers-temps parce que vous puez la défaite eh ehhttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png

C'est impossible en o(n)
Ayez un peu de rigueur quand vous donnez un énoncé, c'est O(n)

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

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

https://image.noelshack.com/fichiers/2017/31/5/1501863678-risitas596bestreup.png

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 mutablehttps://image.noelshack.com/fichiers/2018/47/1/1542653887-95803-full.jpg
à 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. :(

Mais si. Tu peux pas juste ignorer comment on implémente les trucs sinon (par exemple) avoir la taille d'une liste ça va du O(1) au O(n) (différentes structures de données tout ça)
La on s'en branle oui mais faut faire gaffe

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

https://image.noelshack.com/fichiers/2017/31/5/1501863678-risitas596bestreup.png

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 mutablehttps://image.noelshack.com/fichiers/2018/47/1/1542653887-95803-full.jpg
à 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 bordelhttps://image.noelshack.com/fichiers/2017/16/1492891722-jesustas.pnghttps://image.noelshack.com/fichiers/2017/16/1492891722-jesustas.png

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à. :pf:

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)

Et le lru_cache sur des grosses valeurs te donne pas du n2

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.https://image.noelshack.com/fichiers/2017/14/1491667530-risitas-salut.jpg

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

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

https://image.noelshack.com/fichiers/2017/31/5/1501863678-risitas596bestreup.png

C'est pas O(n) je pense

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

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 :rire:
20 euros paypal je te fais ton devoir :rire:
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 :rire:

Mais qu'est-ce tu dis toi ? :rire:

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 ?... :pf:

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.https://image.noelshack.com/fichiers/2016/41/1476132386-1.png

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

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.https://image.noelshack.com/fichiers/2016/41/1476132386-1.png

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

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

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

C'est possible ça ?

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

[00:07:26] <PlateauDeSACLAY>

Le 08 décembre 2018 à 00:05:27 [Ban2]PTSI-PT a écrit :
Pour le O(n) il suffit de parcourir la liste une fois pour repérer les paires déjà présentes au début
Puis à chaque fois qu'on supprime une paire, on vérifie si on en créé pas une nouvelle à supprimer en regardant les caractères immédiatement à droite et à gauche

Au pire on fait 2n opérations

Hmm ça a l'air flou. Ca sert à quoi de garder la liste de toutes les paires ?
(C'était inutile pour ce que j'ai proposé)

Chaque paire à supprimer dans la liste de départ est le début d'une récursion

Mouais admettons

Le 08 décembre 2018 à 00:05:27 [Ban2]PTSI-PT a écrit :
Pour le O(n) il suffit de parcourir la liste une fois pour repérer les paires déjà présentes au début
Puis à chaque fois qu'on supprime une paire, on vérifie si on en créé pas une nouvelle à supprimer en regardant les caractères immédiatement à droite et à gauche

Au pire on fait 2n opérations

Hmm ça a l'air flou. Ca sert à quoi de garder la liste de toutes les paires ?
(C'était inutile pour ce que j'ai proposé)

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

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 :rire:
20 euros paypal je te fais ton devoir :rire:
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 :rire:

Mais qu'est-ce tu dis toi ? :rire:

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 ?... :pf:

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.https://image.noelshack.com/fichiers/2016/41/1476132386-1.png

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

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.https://image.noelshack.com/fichiers/2016/41/1476132386-1.png

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

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

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 :rire:
20 euros paypal je te fais ton devoir :rire:
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 :rire:

Mais qu'est-ce tu dis toi ? :rire:

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 ?... :pf:

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.https://image.noelshack.com/fichiers/2016/41/1476132386-1.png

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

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.https://image.noelshack.com/fichiers/2016/41/1476132386-1.png

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

Le 07 décembre 2018 à 23:52:42 Celestin_27cm a écrit :
ca allait bien jusqu'à ce que tu dises "Faites-le en 10 lignes ou moins"https://image.noelshack.com/fichiers/2018/29/6/1532128784-risitas33.png

je galere à initialiser une matrice 4x4 avec appendhttps://image.noelshack.com/fichiers/2018/13/4/1522325846-jesusopti.png

Ca prends une ligne une matrice

Exo d'algo
Ca parle pas de complexité
Même pas je regarde