L'exercice vient de Prologin demi-finale 2011, exercice nommé Épiphanie. Il s'agit de coder un exo d'algorithmique en Python et de soumettre son code sur le serveur de Prologin en essayant de réussir le maximum de tests (dans le cas de l'exercice ci-dessus, c'est 7 tests). Pour soumettre un code, il faut juste s'être inscrit sur le site de Prologin.
Je vous résume : vous avez un gâteau circulaire constitué de n secteurs égaux. Chaque secteur porte un motif. Au total, il y a p motifs distincts. On vous demande de déterminer une part du gâteau contenant un minimum de secteurs mais ayant les p motifs. Ce qu'on appelle part, c'est une succession de secteurs consécutifs du gâteau. Dans le cas du dessin ci-dessous, la réponse demandée est 4.
Les détails, les contraintes temps et mémoire sur le site de Prologin. Attention, ils travaillent avec la version 2.5 de Python.
Je trouve dommage que tu ne l'ai pas proposé sur le forum "Autres Langages" mais bon, je respecte ton choix.
En attendant, voici une solution naïve qui semble répondre correctement au problème.
## Renvoie le nombre de fruits distincts
nb_distinct_elems = lambda liste : len(list(set(liste)))
## Permet de faire comme si on travaillait sur une liste cyclique.
def cycle (liste, size, deb, fin):
if fin < size:
return liste[deb:fin]
else:
return liste[deb:size] + liste[0:fin%size]
## Renvoie la taille de la plus petite part avec tous les "fruits".
def smallest_slice (item_list):
nb_elem = nb_distinct_elems(item_list)
min_len = nb_elem
size = len(item_list)
while min_len < size:
for i in range(size):
if nb_elem == nb_distinct_elems(cycle(item_list, size, i, i+min_len)):
return min_len
min_len += 1
return size
## test
l = "aaababbbcc" #4
l1 = "abcdaaaaaabbbbbbbcdb" #4
l2 = "abbdceabcddddddddddde" #5
smallest_slice(l)
smallest_slice(l1)
smallest_slice(l2)
Voilà le mien, n'étant pas une bête de l'algorithmique, je suppose que mon algo doit être très naïf
J'ai hâte de voir d'autres algorithme.
def parcours(n, motifs):
liste = []
for i in xrange(n, len(motifs)):
liste.append(motifs[i])
return liste
def result(motifs):
L = []; N = []
NB_MOTIFS = len(set(motifs))
for k in xrange(len(motifs)):
ma_liste = parcours(k, motifs)
for j in ma_liste:
L.append(j)
if NB_MOTIFS == len(set(L)):
N.append(len(L))
L = []
L = []
return "%d pour le motif %s" %(min(N), motifs)
print result("aaababbbcc")
print result("abcdaaaaaabbbbbbbcdb")
print result("abbdceabcddddddddddde")
Résultat
5 pour le motif aaababbbcc
4 pour le motif abcdaaaaaabbbbbbbcdb
5 pour le motif abbdceabcddddddddddde
à mon avis ce genre d'algo doit avoir ses limites, mais je suis déjà content d'avoir réussi à pondre un code
Je trouve dommage que tu ne l'ai pas proposé sur le forum "Autres Langages" mais bon, je respecte ton choix.
Le problème est suffisamment intéressant pour que je te passe le relais afin de le faire partager à d'autres.
Citation : Lithrein
En attendant, voici une solution naïve qui semble répondre correctement au problème.
Ta solution semble correcte et elle passe les tests de Prologin. À mon avis, ta fonction cycle te fait perdre du temps. Tu as une solution en <math>\(n^2\)</math>, les perf sont correspondantes. Ci-dessous mon code, pareil c'est du <math>\(n^2\)</math> mais apparemment un peu plus rapide (30% ou 40%) mais lent quand même. Je suis convaincu qu'il doit y a voir une solution rapide à base de programmation dynamique mais j'ai pas le temps d'approfondir.
# -*- coding: utf-8 -*-
from random import shuffle
from string import printable
def candide(n, p, z):
for taille in range(p,n+1):
for debut in range(n):
v=len(set(z[debut:debut+taille]))
if v==p:
print taille
return
N=100
z=list(printable*N) # taille 100*N
shuffle(z)
zz=''.join(z)
candide(len(zz), len(set(zz)), zz*2)
$ time python candide_test.py
285
real 0m18.990s
user 0m18.901s
sys 0m0.004s
Je suis convaincu qu'il doit y a voir une solution rapide à base de programmation dynamique mais j'ai pas le temps d'approfondir.
En effet, il me semble que ma (seconde) solution est en O(N).
J'ai un peu de mal à expliquer l'algo clairement, alors voici mon code (C/C++) :
#include <iostream>
#include <string>
using namespace std;
unsigned distance (unsigned start, unsigned stop, unsigned sz)
{
if (stop >= start)
return stop - start;
else
return sz - start + stop;
}
unsigned partMin (string& str)
{
const unsigned sz = str.size();
unsigned piles[26] = {0};
// enregistre la qantite de chaque motif
for (unsigned i=0; i < sz; i++)
piles[str[i]-'a']++;
// détermine la part minimum pour start = 0
// (positionne stop)
unsigned start, stop;
for ( stop=sz-1; ; stop--)
if ( piles[str[stop]-'a'] > 1 )
piles[str[stop]-'a']--;
else
break;
// applique l'algorithme sur toutes les positions de départ
unsigned min = sz;
for ( start=0; start < sz; start++)
{
unsigned d = distance(start, stop, sz) + 1;
if ( d < min )
min = d;
unsigned char c = str[start];
piles[c-'a']--;
while ( piles[c-'a'] == 0 )
{
stop = (stop+1)%sz;
piles[str[stop]-'a']++;
}
}
return min;
}
int main()
{
int n;
string fruits;
cin >> n;
cin.ignore();
getline(cin, fruits);
cout << partMin(fruits) << endl;
return 0;
}
Merci à candide pour avoir proposé cet exo !
EDIT :
Code en python :
oui, je suis un noob en python...
import sys
def distance(start,stop,sz):
if stop >= start:
return stop - start
else:
return sz - start + stop
def longueurPart(n, fruits):
# étape 1 : on enregistre le nombre de chaque motif
piles = dict()
for c in fruits:
if c not in piles:
piles[c] = 1
else:
piles[c] += 1
# étape 2 : on trouve le point de coupe stop pour start == 0
stop = n-1
while piles[fruits[stop]] > 1:
piles[fruits[stop]] -= 1
stop -= 1
# étape 3 : on applique l'algo pour toutes les positions start
min = n
for start in range(0,n):
d = distance(start,stop,n)+1
if (d < min):
min = d
c = fruits[start]
piles[c] -= 1
while piles[c] == 0:
stop = (stop+1)%n
piles[fruits[stop]] += 1
# on retourne min
return min
if __name__ == '__main__':
n = int(raw_input())
fruits = raw_input()
print longueurPart(n, fruits)
Tu es sûr que c'est du O(N) ? Je suis certain pour le O(N²) (vu qu'en fait, ton algorithme est, je crois, équivalent à celui que j'avais proposé dans "Autres langages" :
from random import shuffle
from string import printable
def cyprien(n, p, z):
nb_occ = [0 for i in range(p)]
nb_mot = 0
debut = 0
debut_min = 0
fin_min = n
for courant in range(2*n):
if nb_occ[z[courant]] == 0 :
nb_mot += 1
nb_occ[z[courant]] += 1
while nb_occ[z[debut]] > 1:
nb_occ[z[debut]] -= 1
debut += 1
if nb_mot == p and courant - debut < fin_min - debut_min:
debut_min = debut
fin_min = courant
print(fin_min - debut_min + 1)
N=20
M=100
z=list([i for i in range(M)]*N)
shuffle(z)
cyprien(len(z), len(set(z)), z*2)
et même si je suis persuadé que c'est moins que du O(N²), c'est sûrement plus que du O(N) .
J'aimerais bien en avoir une preuve quoi (à défaut d'en trouver une moi-même pour le moment ).
Tu es sûr que c'est du O(N) ?
...
et même si je suis persuadé que c'est moins que du O(N²), c'est sûrement plus que du O(N) .
Attention, lorsque je dis O(N), ça veut simplement dire linéaire, même si cela peut très bien être du O(3N) par exemple...
Sinon, je ne vois pas ce qui te fais dire que c'est du O(N2). Il faudrait que tu argumentes...
EDIT :
Ah, ben j'avais pas vu ce topic, j'aurais posté mon code C++ là bas.
Je ne vois pas pourquoi tu doutes encore, après ce que tu écris :
Citation : Cyprien_
Je n'ai pas d'outils simple pour effectuer des benchs, mais sur le code suivant :
[...]
La différence est déjà flagrante : la fonction de candide met plusieurs secondes à s'exécuter, tandis que la mienne est presque instantanée.
EDIT2: je confirme, j'ai poussé un peu plus loin avec 2000 motifs différents et une chaîne de 5000*2000 caractères : le script de candide met plusieurs minutes contre 2-3 secondes pour le mien .
Je comprends ce que veut dire O(N) . C'est juste que non seulement tu parcours l'ensemble des points de départ, mais en plus, pour chaque point de départ, il y a cette boucle :
Après, je me trompe peut-être (sans doute même), je n'ai juste pas beaucoup cherché plus loin pour le moment.
(et pour moi, l'algo naïf proposé par candide est en O(n^3), à cause du v=len(set(z[debut:debut+taille])) qui ne s'effectue sûrement pas en temps constant !)
Je comprends ce que veut dire O(N) . C'est juste que non seulement tu parcours l'ensemble des points de départ, mais en plus, pour chaque point de départ, il y a cette boucle :
La différence entre l'algo naïf et le mien (le tien quoi), c'est ce que l'on fait sur chaque position de départ:
* Pour l'algo naïf, on doit vérifier à chaque fois si on a bien toutes les valeurs, donc à chaque fois (au pire) n opérations.
* Pour l'algo "intelligent", on se contente uniquement de chercher la valeur perdue par l'incrémentation de pos_start. On parcourra donc la chaine uniquement 2 fois au maximum : une avec pos_start (de pos_0 à pos_n), et une avec pos_end (de pos_end_initial à pos_n-1 en passant par pos_0).
Pour l'algo de candide, je ne sais pas, je n'ai pas compris son code...
Bon, je crois que j'ai une solution qui déboîte, les tests que j'ai fait sur le même bench que plus haut donnent 10ms contre 17s. Donc ×1700 sur un exemple.
les codes de yoch et la Hache me retourne 4 pour cette chaîne 'acccccdbbbbabcdcdaaaaaabbbbbbbcdb' alors que le réponse est 11 ...
le mien:
def foo(a):
l = len(set(a))
a *= 2
z = [(i,e-1)for e,i in enumerate(a[:-1],1)if i!=a[e]]
e = zip(*z)[0]
return min([(z[i+2][1]-z[i][1],z[i][1]) for i in range(len(e)-l)if len(set(e[i:i+l]))==l])[1]
foo('acccccdbbbbabcdcdaaaaaabbbbbbbcdb')
11
Woo, je suis super à la bourre . Je poste quand même mon algo puisque aucun d'entre vous n'a pensé à faire une classe pour l'occasion:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
class Cycle(list):
"""
Classe Cycle recréant le comportement d'un groupe
cyclique via un héritage de la classe list
"""
def __getitem__(self, x):
"""
Surcharge du slice et modification du comportement
initial du slice de la classe mère
"""
cycle = []
while len(cycle) < x.stop:
cycle.extend(self)
return cycle[x]
def solve(cycle):
"""
Retourne diverses information à propos de la plus petite
part d'un cycle contenant toutes les sortes d'éléments
"""
epiphany = set(cycle)
for length in range(len(epiphany), len(cycle)+1):
for part in range(len(cycle)+1):
if set(cycle[part:part+length]) == epiphany:
return """Slice: [{0}:{2}]
Length: {1}
Result: {3}""".format(part, length, part+length, cycle[part:part+length])
import sys
def longueurPart(n, fruits):
n = len(set(fruits))
l = len(fruits)
fruits += fruits
for y in range(n,l):
for i in range(0,l):
if len(set(fruits[i:i+y])) == n:
return y
if __name__ == '__main__':
n = int(raw_input())
fruits = raw_input()
print longueurPart(n, fruits)
J'ai pondu (sans copier !) un algo proche de celui de josmiley en moins élégant !
Je le donne quand même pour montrer les différences :
class Ring(str):
"""gère une string en anneau : successeur(dernier) = premier """
def rg_slice(self, start, length):
"""retourne la sous-liste des 'length' éléments
depuis la position start"""
# l'attribut N est créée par le main (N = len(ring))
stop = start + length
if stop > N :
stop -= N
ssch = self[start:] + self[:stop]
else:
ssch = self[start:stop]
return ssch
class GetOutOfLoop(Exception):
"""exception levée pour sortir des deux boucles imbriquées"""
pass
# __main__
test0 = 'badaac' # min = 4
test1 = 'badeaac' # min = 5
test2 = 'bbaaaebebccdebbaaccddae' # min = 6
test3 = 'b' + 1000*'a' + 'c' # min = 3
test4 = 'b' + 500*'a' + 'c' + 500*'a' # min = 502
gateau = test2
gateau = Ring(gateau)
N = len(gateau) # N = nbre total de parts
gateau.N = N
p = len(set(gateau)) # p = nbre de fruits différents
print("Ensemble de départ :\n", " ".join(gateau))
try :
for taille in range(p, N+1):
for start in range(N):
if len(set(gateau.rg_slice(start, taille))) == p :
taille_min = taille
raise GetOutOfLoop
except GetOutOfLoop: pass
print("taille mini :", taille_min)
josmiley résoud de façon différente deux pbs :
- la gestion de l'anneau (le 'gateau' est rond) : en doublant la chaîne 'fruits' , josmiley double en gros la complexité mémoire mais c'est une grande simplification de l'algorithme puisqu'on n'a plus à se préoccuper de la fin du 'gateau' pour boucler vers le début et le temps de calcul est meilleur. Chez moi, j'ai introduit une class pour traiter ça ...
- la sortie en une fois de deux boucles for imbriquées : pb classique en Python apparement. Trois solutions :
- une variable booléenne supplémentaire positionnée dans la boucle la plus interne et testée dans la(es) boucle(s) externe(s)
- lever une exception (ma solution)
- mettre les boucles dans une fonction : le return sort de toutes les boucles à la fois (solution josmiley) ... plus simple effectivement Au global, la solution josmiley est plus compacte pour une performance égale (avec un peu plus de mémoire consommée). Une petite remarque accessoire : la variable 'n' dans le main est inutile - elle est recalculée très logiquement en début de la fonction.
if __name__ == '__main__':
fruits = input()
print (longueurPart(fruits))
"bon on a tous fait le même ..." :
il y a au moins un autre type d'algorithme, qui m'est venu en premier d'ailleurs : prendre une tranche de la taille p (nb de fruits) et la faire croître à droite jusqu'à avoir les p fruits (ou jusqu'à la plus petite taille trouvée avant) et déplacer la tranche de la position 0 à N-1 en mémorisant la plus petite taille trouvée.
Dans le pire des cas, c'est apparemment meilleur que l'algo précédant, sur mon PC au moins. (Pire des cas = test4 de mon code pour le premier algo, test3 pour le 2eme algo.)
Pour info, ma version du dernier algo (c'est lourd mais ça marche !) :
class Ring(str):
"""gère une chaîne en anneau : successeur(dernier)= premier """
def rg_slice(self, start, length):
"""retourne une sous-chaîne des 'length' éléments
depuis la position start"""
# la var N est créée par le main (= len(ring))
stop = start + length
if stop > N :
stop -= N
ssch = self[start:] + self[:stop]
else:
ssch = self[start:stop]
return ssch
# __main__
test0 = 'badaac' # min = 4
test1 = 'badeaac' # min = 5
test2 = 'bbaaaebebccdebbaaccddae' # min = 6
test3 = 'b' + 1000*'a' + 'c' # min = 3
test4 = 'b' + 500*'a' + 'c' + 500*'a' # min = 502
gateau = test3
gateau = Ring(gateau)
N = len(gateau)
gateau.N = N
p = len(set(gateau))
print("Ensemble de départ :\n", " ".join(gateau))
nb_max = N # nb max d'éléments à tester suivants la slice en cours
# (rapidement proche de taille_min - p )
taille_min = N # valeur min cherchée
for start in range(N):
s_part = set(gateau.rg_slice(start, p)) # nouvelle slice de p éléments
suiv = start + p
delta = 0
while delta <= nb_max :
if len(s_part) == p :
taille_min = min(taille_min, p + delta)
nb_max = delta
if suiv >= N : suiv -= N
s_part.add(gateau[suiv])
suiv += 1
delta += 1
print("taille mini :", taille_min)
J'y avais pensé mais il m'a semblé que faire tourner toute la liste risquait d'être assez lourd en temps d'exécution, plus que le test de fin de liste et les manips d'index (je n'ai pas à vérifié ...)
@AlphaZeta : c'est fort possible ! excuse moi, je ne suis pas très costaud en Python et je n'ai pas tout compris dans ton code
@josmiley: Ben en gros dans mon code je fais exactement la même chose que toi en passant aussi par une classe (que j'ai nommée Cycle) qui fait exactement la même chose et pour trouver la plus petite part je fais exactement comme toi . Je ferais mieux de commenter mon code !
[Algo] Plus petite part contenant tous les fruits
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.