Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Algo] Plus petite part contenant tous les fruits

Épiphanie (Prologin demi-finale 2011)

    30 mars 2011 à 2:46:33

    Bonjour,

    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.


    Image utilisateur


    Les détails, les contraintes temps et mémoire sur le site de Prologin. Attention, ils travaillent avec la version 2.5 de Python.




    • Partager sur Facebook
    • Partager sur Twitter
      30 mars 2011 à 3:27:35

      Moi je veux la part avec les 3 pokeballs.
      • Partager sur Facebook
      • Partager sur Twitter
        2 avril 2011 à 14:10:47

        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)
        

        • Partager sur Facebook
        • Partager sur Twitter
        Anonyme
          2 avril 2011 à 16:56:37

          Voilà le mien, n'étant pas une bête de l'algorithmique, je suppose que mon algo doit être très naïf :p

          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 :p
          • Partager sur Facebook
          • Partager sur Twitter
            2 avril 2011 à 17:37:01

            @fred1599: Soit j'ai mal compris l'énoncé, soit tu as oublié qu'on travaille sur un gâteau rond, non ?

            Tu devrais donc trouver pour ton premier test la valeur 4.
            5 pour le motif aaababbbcc
            • Partager sur Facebook
            • Partager sur Twitter
              2 avril 2011 à 23:23:06

              Citation : Lithrein

              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
              • Partager sur Facebook
              • Partager sur Twitter
                10 avril 2011 à 0:59:42

                Citation : candide

                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)
                
                • Partager sur Facebook
                • Partager sur Twitter
                Anonyme
                  10 avril 2011 à 12:02:39

                  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 :p ).
                  • Partager sur Facebook
                  • Partager sur Twitter
                    10 avril 2011 à 12:47:45

                    Citation : Cyprien_

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

                    • Partager sur Facebook
                    • Partager sur Twitter
                    Anonyme
                      10 avril 2011 à 13:52:40

                      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 :

                      while ( piles[c-'a'] == 0 )
                              {
                                  stop = (stop+1)%sz;
                                  piles[str[stop]-'a']++;
                              }
                      


                      C'est à cause d'elle que je doute ^^ .

                      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 !)

                      Mais bon, à nouveau, je peux me tromper.
                      • Partager sur Facebook
                      • Partager sur Twitter
                        10 avril 2011 à 14:43:47

                        Citation : Cyprien_

                        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 :

                        while ( piles[c-'a'] == 0 )
                                {
                                    stop = (stop+1)%sz;
                                    piles[str[stop]-'a']++;
                                }
                        



                        C'est à cause d'elle que je doute ^^ .


                        Cette boucle ne remet pas en cause la complexité.

                        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...
                        • Partager sur Facebook
                        • Partager sur Twitter
                        Anonyme
                          10 avril 2011 à 14:56:15

                          Ouaip, j'ai compris ça peu de temps après mon post en fait ^^ .

                          Pour l'algo de candide, bah en gros, il teste tous les ensembles d'au moins p éléments possibles grâce à :

                          for taille in range(p,n+1):
                                  for debut in range(n):
                          

                          et pour chaque ensemble, il teste s'il a bien p éléments distincts en utilisant v=len(set(z[debut:debut+taille])).

                          set(...) construit un ensemble (au sens mathématique du terme) et élimine donc les doublons, ce qui permet de compter les éléments distincts.
                          • Partager sur Facebook
                          • Partager sur Twitter
                            1 novembre 2011 à 1:14:08

                            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.

                            spoil
                            
                            • Partager sur Facebook
                            • Partager sur Twitter
                              1 novembre 2011 à 18:22:27

                              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
                              
                              • Partager sur Facebook
                              • Partager sur Twitter

                              "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                                1 novembre 2011 à 18:34:54

                                @josmiley:
                                tu as le droit de prendre le premier et les 3 derniers, donc ça fait bien 4.

                                Sur un gâteau en couronne, il n'y a pas de 'début'. C'est cyclique.
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  1 novembre 2011 à 18:44:43

                                  Citation : la Hache

                                  @josmiley:
                                  tu as le droit de prendre le premier et les 3 derniers, donc ça fait bien 4.

                                  Sur un gâteau en couronne, il n'y a pas de 'début'. C'est cyclique.



                                  non mais je ne sais pas lire .. j'ai cru qu'il fallait retourner la position de la plus petite part. désolé ...

                                  et d'façon mon algo est faux ^^
                                  • Partager sur Facebook
                                  • Partager sur Twitter

                                  "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                                  Anonyme
                                    11 septembre 2014 à 13:45:32

                                    Woo, je suis super à la bourre :p. 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])

                                    Et le résultat pour le "gâteau" 'acabcadehfacg':

                                    Slice: [3:13]
                                    Length: 10
                                    Result: ['b', 'c', 'a', 'd', 'e', 'h', 'f', 'a', 'c', 'g']

                                    -
                                    Edité par Anonyme 13 septembre 2014 à 18:25:30

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      12 septembre 2014 à 15:51:47

                                      ha tiens, je l'avais pas fini celui-là:

                                      bon on a tous fait le même ...

                                      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)

                                       

                                      -
                                      Edité par josmiley 12 septembre 2014 à 15:58:00

                                      • Partager sur Facebook
                                      • Partager sur Twitter

                                      "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                                        13 septembre 2014 à 14:41:54

                                        Salut,

                                        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)
                                        

                                        Voilà, j'arrête là !


                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                        Anonyme
                                          13 septembre 2014 à 15:32:34

                                          La classe Ring peut être remplacée avantageusement avec le module collections et sa classe deque

                                          from collections import deque
                                          
                                          class Ring(str):
                                              def rg_slice(self, n):
                                                  
                                                  d = deque(self)
                                                  d.rotate(n)
                                                  return ''.join(d)

                                          Enfin si j'ai bien compris ce que tu souhaites faire avec cette classe...

                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                          Anonyme
                                            13 septembre 2014 à 17:52:05

                                            @Rozo2: Je dirais que ton algo est plus proche du mien que de celui de josmiley, tu t'es trompé ou je me suis trompé ?
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              13 septembre 2014 à 17:58:13

                                              @oldprogrammer :

                                              Exact : rotate sur un deque est envisageable.

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

                                              -
                                              Edité par Rozo2 13 septembre 2014 à 18:04:38

                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                              Anonyme
                                                13 septembre 2014 à 18:17:02

                                                @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 :p. Je ferais mieux de commenter mon code !
                                                • Partager sur Facebook
                                                • Partager sur Twitter

                                                [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.
                                                • Editeur
                                                • Markdown