class Array # # Dans les methodes qui suivent, pour simplifier les exercices, on # suppose que les elements d'un tableau sont toujours des nombres. # # ################################################################# # Utilisation comme array vs. comme objet avec each ################################################################# # Retourne le premier element du tableau s'il existe, sinon nil. # # Exemple: # [10, 23, 30].first_array == 10 # # Contrainte de mise en oeuvre: on suppose que l'objet est un Array. # def first_array return nil if self == [] self[0] # [0] ne fonctionne pas! end # Retourne le premier element du tableau s'il existe, sinon nil. # # Exemple: # [10, 23, 30].first_avec_each == 10 # # Contrainte de mise en oeuvre: on ne doit pas tenir compte que # l'objet est un Array, i.e., on suppose uniquement qu'il definit la # methode each. # def first_avec_each fail "*** Doit definir each" unless respond_to? :each each do |x| return x end nil end ################################################################# # select et reject ################################################################# # Retourne un tableau avec les elements pairs du tableau initial. # # Exemple: # [10, 23, 30].pairs == [10, 30] # def pairs select { |x| x.even? } end # # Retourne une partition des elements du tableau, en fonction d'un 'pivot'. # # Plus specifiquement, retourne trois sous-tableaux du tableau # initial: # - Les elements plus petits que le pivot # - Les elements egaux au pivot # - Les elements plus grands que le pivot # # L'ordre des elements du tableau initial est respecte. # # Exemple: # [32, 10, 30, 40].partitionner(11) == [[10], [], [32, 30, 40]] # def partitionner( pivot ) [ select { |x| x < pivot }, select { |x| x == pivot }, select { |x| x > pivot } ] end def _partitionner( pivot ) reduce([[], [], []]) do |partitions, x| partitions[ (x <=> pivot) + 1] << x partitions end end # # Retourne une version triee des elements du tableau, en ordre croissant. # # Exemple: # [32, 10, 30, 40].trier == [10, 30, 32, 40] # def trier # Note: Semblable a la methode sort... que vous ne pouvez # evidemment pas utiliser! Vous devez plutot utiliser # partitionner, et donc trier a l'aide d'une methode style # quicksort! # # Rappel: [10, 20] + [12, 13] == [10, 20, 12, 13] return [] if empty? petits, egaux, grands = partitionner( self[0] ) petits.trier + egaux + grands.trier end # # Retourne un tableau avec les memes elements que le tableau # initial, mais sans les nil. # # Exemple: # [10, 30, nil, false, nil].compacter == [10, 30, false] # def compacter reject { |x| x.nil? } end # ################################################################# # map ################################################################# # Retourne un tableau qui, pour chaque nombre du tableau initial, # contient un sous-tableau avec autant de fois le nombre 1 lorsque # le nombre est positif, sinon un sous-tableau vide lorsque le # nombre est nul ou negatif. # # Exemple: # [-1, 3, 0, 1].juste_des_1.must_equal [ [], [1,1,1], [], [1] ] # # Indices: # (1..0).map { K } == [] # (1..3).map { K } == [K, K, K] # def juste_des_1 map { |n| (1..n).map { 1 } } end # ################################################################# # reduce ################################################################# # Retourne l'element maximum du tableau, ou nil si le tableau est # vide. # # Exemples: # [10, 20, 30].le_max == 30 # [-10, -20, -30].le_max == -10 # def le_max # Note: Semblable a la methode max, que vous ne pouvez evidemment # pas utiliser. return nil if empty? reduce(self[0]) { |m, x| x > m ? x : m } end # # Retourne *l'index* de l'element maximum, nil si le tableau est vide. # # Exemple: # [10, 20, 30, 11].index_du_max == 2 # # Indice: # Il faut effectuer une reduction via les index, et non via les elements eux-memes. # def index_du_max return nil if empty? (0...size) .reduce(0) { |index_max, k| self[k] > self[index_max] ? k : index_max } end # # Retourne une version inversee du tableau, i.e., avec les meme # elements mais en ordre inverse (et le tableau initial n'est pas # modifie). # # Exemple: # [10, 20, 30].inverse == [30, 20, 10] # def inverse # Note: Semblable a la methode reverse, que vous ne pouvez # evidemment pas utiliser. # # Indices: # [10] + [] == [10] # [30] + [20, 10] == [30, 20, 10] # reduce([]) { |a, x| [x] + a } end # ################################################################# # map et reduce ################################################################# # Retourne le nombre d'inversions entre elements adjacents, i.e., le # nombre de paires d'elements adjacents qui ne sont pas dans le bon # ordre. # # Exemple: # [10, 9, 8, 10, 11, 8].nb_inversions == 3 # # Indices: # - A evaluer en deux passes: # 1. map # 2. reduce # - La aussi il faut travailler avec (mapper sur) les index # et non avec (sur) les elements eux-memes. # def nb_inversions (1...size) .map { |k| self[k-1] > self[k] ? 1 : 0 } .reduce(0, &:+) end # ################################################################# # group_by ################################################################# # Comme partitionner plus haut, mais cette fois en utilisant # group_by. # # Exemple: # [32, 10, 30, 40].partitionner_bis(11) == [[10], [], [32, 30, 40]] # # Indice: # x <=> y == -1 si x < y # 0 si x == y # 1 si x > y # # # [2, 4, 6].group_by { |x| x % 2 }[0] == [2, 4, 6] # [2, 4, 6].group_by { |x| x % 2 }[1] == nil # def partitionner_bis( pivot ) groupes = group_by { |x| x <=> pivot } [groupes[-1] || [], groupes[0] || [], groupes[1] || [] ] end # ################################################################# # Utilisation de yield ################################################################# # Itere sur les elements d'un tableau, mais a partir des elements a # la fin du tableau plutot qu'a partir du debut. # # Exemples: # [10, 20, 30].hcae { |x| puts x } # 30 # 20 # 10 # # res = [] # [10, 20, 30].hcae { |x| res << x; p res } # [30] # [30, 20] # [30, 20, 10] # # Indice: Utilisez la methode inverse introduite precedemment. # def hcae inverse.each do |x| yield x end end # Itere sur les elements d'un tableau mais dans un ordre complement # aleatoire. # # Exemples: # [10, 20, 30].each_random { |x| puts x } # 20 # 10 # 30 # # [10, 20, 30].each_random { |x| puts x } # 10 # 30 # 20 # # Indices: # - (i...j).to_a = [i, i+1, ..., j-1] # - rand n = nombre aleatoire compris entre 0 et n-1 # - Array#delete_at # >> a = [10, 20, 30]; a.delete_at(1); a # => [10, 30] # - Il ne faut pas modifier le tableau initial! # def each_random indices = (0...size).to_a until indices.empty? i = rand indices.size yield self[indices[i]] indices.delete_at(i) end end # Version avec un Hash def each_random indices = (0...size).map { |i| [i, true] }.to_h until indices.empty? i = rand size until indices.include?(i) # Peut boucler plusieurs fois :( yield self[i] indices.delete(i) end end # # Applique un bloc, qui doit avoir deux arguments, sur chaque # element du tableau et combine cet element a l'element # correspondant de l'autre tableau par l'intermediaire du bloc. # # Exemple: # [10, 20, 30].map2( [1, 2, 3] ) { |x, y| x + y } == [11, 22, 33] # [10, 20, 30].map2( [1, 2, 3] ) { |x, y| x * y } == [10, 40, 90] # def map2( autre ) fail "*** Tailles differentes: #{size} vs. #{autre.size}" unless size == autre.size (0...size).map do |k| yield( self[k], autre[k] ) end end # # Iterateur qui genere chacun des prefixes du tableau et applique le # bloc recu sur ces prefixes. # # Un prefixe d'un tableau est un sous-tableau qui part du debut de # ce tableau. # # Exemple: # res = [] # [10, 20, 30].each_prefixe { |pref| res << pref } # res == [[], [10], [10, 20], [10, 20, 30]] # # Indices: # [10, 20, 30][0...0] = [] # [10, 20, 30][0...1] = [10] # [10, 20, 30][0...2] = [10, 20] # etc. # def each_prefixe (0..size).each do |k| yield self[0...k] end end end