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

Le 08 décembre 2018 à 00:43:16 CryTime1v9 a écrit :
<code>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()</code>

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

yes

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

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.

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:50:33 KheyAuxPommes a écrit :

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

La première L forme des elites on dirait

Le 08 décembre 2018 à 00:50:02 KheyAuxPommes a écrit :

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/

Merci. Et du coup vos trucs là, c'est niveau L3, prépa?

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

AYAAAAAAAAAAAAAAAAAAAAA

Depuis le début vous faites les mecs à parler de trucs auxquels que je comprends rien genre O(n), O(n²), matrices et tout je sais pas quoi, et au final je vous ai juste mis en PLS en codant ça en 5 min sans me poser de questions

Le 08 décembre 2018 à 00:51:03 PuceauTimide a écrit :

Le 08 décembre 2018 à 00:43:16 CryTime1v9 a écrit :
<code>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()</code>

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

yes

yes quoi ?

Le 08 décembre 2018 à 00:51:05 PlateauDeSACLAY a écrit :

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

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.

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

Je fais gaffe quand il le faut, là on s'en branle, c'est pas le coeur de l'algo.

Le 08 décembre 2018 à 00:51:18 EnBaDuBlok 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é.

AYAAAAAAAAAAAAAAAAAAAAA

Depuis le début vous faites les mecs à parler de trucs auxquels que je comprends rien genre O(n), O(n²), matrices et tout je sais pas quoi, et au final je vous ai juste mis en PLS en codant ça en 5 min sans me poser de questions

Ta quel niveau d'études

Le 08 décembre 2018 à 00:50:33 KheyAuxPommes a écrit :

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

Pourquoi t'es allé en L si t'aimes faire des exos de programmation ou d'algo par exemples ?

Le 08 décembre 2018 à 00:53:15 europol2 a écrit :

Le 08 décembre 2018 à 00:51:18 EnBaDuBlok 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é.

AYAAAAAAAAAAAAAAAAAAAAA

Depuis le début vous faites les mecs à parler de trucs auxquels que je comprends rien genre O(n), O(n²), matrices et tout je sais pas quoi, et au final je vous ai juste mis en PLS en codant ça en 5 min sans me poser de questions

Ta quel niveau d'études

Je suis en L3

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

Le 08 décembre 2018 à 00:50:33 KheyAuxPommes a écrit :

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

Pourquoi t'es allé en L si t'aimes faire des exos de programmation ou d'algo par exemples ?

Pour pouvoir raconter de belles histoires...

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

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

Le 08 décembre 2018 à 00:50:33 KheyAuxPommes a écrit :

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

Pourquoi t'es allé en L si t'aimes faire des exos de programmation ou d'algo par exemples ?

Pour pouvoir raconter de belles histoires...

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

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

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.

mais si putain, à chaque fois que tu fais reduction+=ctu reparcours reductionpour refaire une chaine. Rien que ca ca te fait passer de O(n) à O(n²).
C'est juste la faute de python par contre pour le coup

Sinon j'attends le pseudo-code pour le plus long palindrome d'une chaîne de caractères

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 eh

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ères

Je veux une complexité en o(n), je vous ai laissé des indices les L1 de Jussieu, vous avez le droit à un tiers-temps

https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm

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ères

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

C'est moi qui attend ton pseudo code depuis tout a l'heure quai

Le 08 décembre 2018 à 00:57:32 KheyAuxPommes a écrit :

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ères

Je veux une complexité en o(n), je vous ai laissé des indices les L1 de Jussieu, vous avez le droit à un tiers-temps

https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm

Pas toi imbécile, je sais bien que tu connais

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

Voilà

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ères

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 eh

Mais mon code c'était pas du Python c'était du pseudo-code, désolé si tu t'es fourvoyé, c'est vrai que les deux ont une syntaxe similaire.